快速排序算法总结

一、思想
举例说明:对数组[2,4,9,3,6,7,1,5]进行快速排序

步骤1: 首先用2当作基准，使用i j两个指针分别从两边进行扫描，把比2小的元素和比2大的元素分开

2 2 4 9 3 6 7 1 5 首先比较2和5，5比2大，j左移

2 2 4 9 3 6 7 1 5 比较2和1，1小于2，所以把1放在2的位置

2 1 4 9 3 6 7 1 5 比较2和4，4大于2，因此将4移动到后面

2 1 4 9 3 6 7 4 5 比较2和7，2和6，2和3，2和9，全部大于2，满足条件，因此不变

经过第一轮的快速排序，元素变为下面的样子

[1] 2 [4 9 3 6 7 5]

步骤2：分别递归排序2左边和右边的序列

思想提炼：

1.将数组a第一个元素设为key,i指向数组第一个元素，j指向数组最后一个元素
2.从右向左直到找到比key小的元素j，将j的数组值赋给i的数组值：a[i] = a[j]
3.从做向右直到找到比key大的元素i,将i的数组值赋给j的数组值：a[j] = a[i]
4.a[i] = key，此时数组a被划分为3块：比a[i]小的字数组，a[i]，比a[i]大的字数组
5.分别递归i左边和右边的字数组

二、代码

 1 public  void sort(int[] a,int left,int right){
 2     if（left >= right)
 3         return;
 4     int key = a[left], i = left, j = right;
 5        while (i < j){
 6            while (i < j && a[j] >= key)
 7                   j--;
 8            a[i] = a[j];
 9            while (i < j && a[i] <= key)
10             i++;
11            a[j] = a[i];
12        }
13        a[i] = key;
14        sort(a, left, i - 1);
15        sort(a, i + 1, right);
16 }

三、性能
1.快速排序是不稳定的算法
2.快速排序交换次数较多
3.快速排序的最坏时间为O(n2)，但就平均性能而言，它是基于关键字比较的内部排序算法中速度最快者，它的平均时间复杂度为O(nlgn)。

快速排序算法总结

相关推荐