算法(第四版)之快速排序

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了算法(第四版)之快速排序，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2012字，纯文字阅读大概需要3分钟。

内容图文

快速排序是目前使用最广泛的排序, 同时也是目前最快的排序,它也体现了分治的思想:将数组分成两部分, 并分别独立地进行排序. 和归并排序不同的是, 归并排序是将两个有序的数组合并为一个有序的大数组, 而快排则是当小数组有序时, 大数组就自然有序了

快速排序是用一个数v将数组切分, v左边的数全都小于v, v右边的数全都大于v, 在将小数组继续切分, 直到不能再分为止, 这样数组就有序了:

我们先写排序主体:

1     public static void sort(int[] a, int lo, int hi) {
2         if(hi <= lo) return;
3         int j =  partition(a, lo, hi);
4         sort(a, lo, j-1);
5         sort(a, j+1, hi);
6     }    

 

然后写切分函数partition():

 1     private static int partition(int[] a, int lo, int hi) { //普通的快排
 2         int i = lo, j = hi + 1;
 3         int v = a[lo];
 4         while(true) {
 5             while(a[++i] < v) 
 6                 if(i == hi) break;
 7             while(a[--j] > v) 
 8                 if(j == lo) break;
 9             if(i >= j) break;
10             int tmp = a[i];
11             a[i] = a[j];
12             a[j] = tmp;
13         }
14         int tmp = a[lo];
15         a[lo] = a[j];
16         a[j] = tmp;
17         return j;
18     }

当然, 这不是最优的代码, 还有更优的解决方案, 那就是将数组切分为三部分, 大于v, 等于v和小于v的三部分:

 1 　　private static void quick3way(int[] a, int lo, int hi) { //三项切分的快速排序
 2         if(hi <= lo)
 3             return;
 4         int lt = lo, i = lo+1, gt = hi;
 5         int v = a[lo];
 6         while(i <= gt) {
 7             if(a[i] < v) {
 8                 int tmp = a[i];
 9                 a[i++] = a[lt];
10                 a[lt++] = tmp;
11             } else if(a[i] > v) {
12                 int tmp = a[i]; 
13                 a[i] = a[gt];
14                 a[gt--] = tmp;
15             } else i++;
16         }
17         quick3way(a, lo, lt-1);
18         quick3way(a, gt+1, hi);
19     }

可以预见, 在含有大量相同元素的情况下, 三项切分对快排的性能会有很大提升

普通的快速排序时间复杂度为O(nlogn), 三项快排的时间复杂度在O(n)和O(nlogn)之间, 但他们的空间复杂度都为O(lgn), 他们都频繁的使用了递归调用

 

内容总结

以上是互联网集市为您收集整理的算法(第四版)之快速排序全部内容，希望文章能够帮你解决算法(第四版)之快速排序所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---