快速排序

目录(?)[-]

啥叫快速排序排序原理和思想代码实现如有错误欢迎留言指正

重点内容#快速排序  闲来无事，研究了一下快速排序，相比以前使用的冒泡效率高出很多，特写博客和大家分享；

啥叫快速排序

---

快速排序由 C. A. R. Hoare（东尼霍尔，Charles Antony Richard Hoare）在1960年提出，之后又有许多人做了进一步的优化。 快速排序算法仅仅是东尼霍尔在计算机领域才能的第一次显露，后来他受到了老板的赏识和重用，公司希望他为新机器设计一个新的高级语言。你要知道当时还没有PASCAL或者C语言这些高级的东东。于是他便设计了“ALGOL 60”的一个子集版本。 这个版本在执行效率和可靠性上都在当时“ALGOL 60”的各种版本中首屈一指，因此东尼霍尔受到了国际学术界的重视。比如PASCAL、C、Java语言等等。当然，东尼霍尔在计算机领域的贡献还有很多很多，他在1980年获得了图灵奖。

---

排序原理和思想

首先在数组中选择一个基数，也就是参照数，然后基于这个参照数， 将小于这个数的数字放到它的左边，大于它的数字放到右边比如数组 int[] a=new int[]{6,1,2,7,9,3,4,5,10,8}即 1.从最右边开始往前找，找到一个小于基准数的数a[j] j--; 2.再从左边开始找一个数a[i]大于基准数 i++; 3.将两个数调换位置 以此类推，将小于这个数的数字放到它的左边，大于它的数字放到右边。

---

代码实现

private static void quicksort(int left,int right) { int i,j,t,temp; if(left>right){ return; } temp=a[left]; //temp中存的就是基准数 i=left; j=right; while(i!=j) { //顺序很重要，要先从右边开始找 while(a[j]>=temp && i<j){ j--; } //再找右边的 while(a[i]<=temp && i<j){ i++; } //交换两个数在数组中的位置 if(i<j) { t=a[i]; a[i]=a[j]; a[j]=t; } } //最终将基准数归位,当i=j时跳出当前循环，并且将基准数与当前a[i]调换位置，保证了基准左边的数都小于基准右边的数 a[left]=a[i]; a[i]=temp; quicksort(left,i-1);//继续处理左边的，这里是一个递归的过程 quicksort(i+1,right);//继续处理右边的 ，这里是一个递归的过程 }

---

如有错误欢迎留言指正

如果还有不理解可以参考此文便于理解