图解算法-快速排序
1. 关于快速排序
快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要 Ο(nlogn) 次比较。在最坏状况下则需要 Ο(n2) 次比较,但这种状况并不常见。事实上,快速排序通常明显比其他 Ο(nlogn) 算法更快,因为它的内部循环(inner loop)可以在大部分的架构上很有效率地被实现出来。
2. 快速排序步骤
- 从数组中挑出一个元素,作为 "基准"(pivot)元素,可以任意选,可以第一个,也可以是最后一个,也可以中间的任意一个;
- 遍历数组元素,比基准值小的放在在基准左边,比基准值大的放在基准的右边(相同的数可以到任一边)。循环完之后得到两个新的数组,基准左边的和基准右边的。当然左边或者右边数组有可能为空.
- 将左边和右边数组重复的执行步骤1和2(递归)
特殊情况说明:
当数组元素个数小于2时,无须比较,直接返回即可
3. 图解
1. 假如有一个数组为:12,3,28,32,18,22,9,82,34,53
2. 选定基准值(第一个数):12
3. 循环数组,将比12小的数字放在左边,比12大的放在右边
如图:
4. 将左边的数组3,9和右边的数组28,32,18,22,82,34,53 按照步骤1,2,3执行
5. 以此类推,递归循环,得出结果,如下图
最终得出排序结果:left + pivot + left1 + pivot1 + pivot2 + left3 + pivot3
4. 示例代码:
public static int[] qsort(int arr[],int start,int end) { int pivot = arr[start]; int i = start; int j = end; while (i<j) { while ((ipivot)) {j--; } while ((i<j)&&(arr[i]<pivot)) {i++; } if ((arr[i]==arr[j])&&(istart) arr=qsort(arr,start,i-1); if (j+1<end) arr=qsort(arr,j+1,end); return (arr); } public static void main(String[] args) { int arr[] = new int[]{12,3,28,32,18,22,9,82,34,53}; int len = arr.length-1; arr=qsort(arr,0,len); for (int i:arr) { System.out.print(i+"\t"); } }