> 文档中心 > 图解算法-快速排序

图解算法-快速排序


1. 关于快速排序

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要 Ο(nlogn) 次比较。在最坏状况下则需要 Ο(n2) 次比较,但这种状况并不常见。事实上,快速排序通常明显比其他 Ο(nlogn) 算法更快,因为它的内部循环(inner loop)可以在大部分的架构上很有效率地被实现出来。

2. 快速排序步骤

  1. ​​​数组中挑出一个元素,作为 "基准"(pivot)元素,可以任意选,可以第一个,也可以是最后一个,也可以中间的任意一个;
  2. 遍历数组元素,比基准值小的放在在基准左边,比基准值大的放在基准的右边(相同的数可以到任一边)。循环完之后得到两个新的数组,基准左边的和基准右边的。当然左边或者右边数组有可能为空.
  3. 将左边和右边数组重复的执行步骤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");     }    }