Java快速排序以及其优化（双路快排、三路快排）

1.快速排序思想快速排序是属于交换排序的基本思想。选择一个基准值val把比val小的放在前面比val大的放在后面最后把val放在两 1.快速排序

---

思想

快速排序是属于交换排序的基本思想。选择一个基准值val把比val小的放在前面比val大的放在后面最后把val放在两个区域中间val就到了最终的位置。

很明显快排是一个原地排序也是一个不稳定排序。

空间复杂度1.可以是为新数组开辟额外空间On 2.当然也可以在原数组内交换得来O1

时间复杂度Onlogn

代码实现

1.把数组第一个元素作为val先用变量val存下来设置两个指针i用来标记遍历的元素j-1用来标记

2.i start1j start遇到array[i]小于val的情况就把array[i]和array[j]交换小于区域扩张ji遇到大于val的情况就继续判断下一个ii直到i>j,把第一个元素和第j个元素交换返回j的下标为下一次递归边界做准备。

3.运用递归接着把[startkey-1]和[key1end]进行第2步操作。

4.重复2.3.步直到start>end退出递归。

startj--i----------------------end

start-----j---------i----------end

public static int[] qiuckSort(int[] array){if(array.length end) return;//选取key值int key selectionKey(array, start, end);//key左边快排qiuck(array,start,key-1);//key右边快排qiuck(array,key1,end);}//l……r//v……j……iprivate static int selectionKey(int[] array, int start, int end){//先设置为第一个元素int key array[start];//[start,j]是key的区域int i start1;while(i < end){//大于key不动 小于key跟array[j]交换if(array[i] 存在优化

1.当数组中元素基本上有序每次取得第一个元素都是最大或最小值会导致元素左右个数分布不不均匀当完全有序时近似于一个On^2的排序。

解决随机选取val值在与第一个元素交换让递归顺利进行。

2.当数组中存在大量重复元素无论是小于等于交换还是小于交换都会导致一边区域数据远大于另一半当重复量很大时近似于一个On^2的排序。

解决运用双路快排把等于val的大量元素均匀的分在两个区域里。

 

2.双路快排

---

思想

把等于val的元素均匀分布在小于、大于区域内。

代码实现

1.避免数组近乎有序先随机取出一个val和第一个元素交换。

2.定义两个指针i从头开始指向小于val的区域后一个元素j从尾开始指向大于val的第一个元素。

3.当i所指向的值小于等于vali否则暂停。当j所指向的值大于等于valj--否则暂停。当i和j都暂停时交换i和j所指位置的元素。直到i>j结束让start赋给j所指向的位置返回j。

4.重复2.3直到start>end排序完成。

 

public static int[] qiuckSort2(int[] array){if (array.length end) return;int key selectionKey2(array,start,end);qiuck2(array,start,key-1);qiuck2(array,key1,end);}private static int selectionKey2(int[] array, int start, int end){int random (int)(Math.random()*(end-start1)start);swap(array,random,start);//找到一个随机keyint value array[start];//从头开始往后[start1,i-1]int i start1;//从尾开始往前[j1,end]int j end;while (true){//相当于把等于key的值均分到两边while (ij) break;swap(array,i,j);i;j--;}swap(array,start,j);return j;}

存在优化

1.当数组重复元素过多时每次比较val的元素会浪费时间虽浪费的时间不足一提但是还是可以优化的。

解决三路快排把等于value的元素放在另一个区间内不参与下次的排序。

 

3.三路快排

---

思想

在二路排序的基础上把等于value的元素放在另一个区间内不参与下次的排序。

代码实现

1.避免数组近乎有序先随机取出一个val和第一个元素交换。

2.定义三个指针lt从头开始指向小于val的区域后一个元素lt start-1i指向目前比较的元素i startgt从尾开始指向大于val的第一个元素gt end1。保证一开始都是空集合。

3.当i所指向的值小于等于valswapilt1lt。当i所指向的值大于等于valswapigt-1gt--否则i。直到i>gt排序完成。将start和lt交换。

4.[start,lt-1]和[gt,end]重复2.3直到start>end排序完成。

 

start----lt----i----gt-----end

小于 [startlt-1]

等于[ltgt-1]

大于[gtend]

public static void qiuckSort3(int[] array){if(array.length end) return;if(end - start <15){//如果数据量少就使用直接插入insert(array,start,end);return;}int random (int)(Math.random()*(end-start1)start);swap(array,random,start);//找到一个随机keyint value array[start];int lt start; int gt end1; int i start1;for(;i注在此省略了直接插入和swap交换函数。

---

这样一步一步优化下来快排适用了任何数据模式具有了稳定的时间复杂度。

【文章原创作者：阿里云代理 http://www.558idc.com/aliyun.html 复制请保留原URL】