题外话:
一般情况下,快速排序被认为是最快的排序算法(人如其名啊),因此可以说是最常用的排序算法,并受大多数公司的青睐,是一定要熟练掌握的。
简介:
快速排序是不稳定的,而且是中比较个性的排序
算法——初始顺序越乱,排序效果越好,一般情况下,我们认为其时间复杂度为O(NlogN),当排序队列已经是顺序队列,时间复杂度达到最差O(n*n),具体是实现是用分治算法,因此涉及到栈,再因此,其空间复杂度略大,达到同样的O(NlogN),在这个效率为先的环境下,以牺牲些许空间换取更短的时间还是非常值得的。
算法思想:
快排采取了分治策略,也是分治算法的一个经典习题,因此其算法思想也符合分治算法,具体的思想是:
1.从数列中找到一个数
2.确定该数在队列中的位置,比它小的都放在左边,大的都在右边
3.将左右两部分分而治之。
伪代码如下:
void quickSort(int[] a, int begin, int end) { /* * 找到所选数字的位置,并记录下来该位置index */ quickSort(a, begin, i - 1);//对左边子问题进行排序 quickSort(a, i + 1, end);//对右边子问题进行排序 }
下一步,好了,算法框架已经搭好,剩下的问题就是,怎么找到所选数字的位置。
结合实例来详细介绍一下:
↓(i) ↓(j)
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
5 | 7 | 8 | 2 | 6 | 125 | 41 | 341 | 34 | 63 | 28 | 97 |
首先我们需要找到97在数列中的位置:
首先设左右两个指针,i 向左走,j 向右走,a[ i ] 遇到比97大的,就换到a[ j ]的位置,j-- (换 j 向左走)
↓i(换到 j 处) ↓ j ← ↓ j
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
5 | 7 | 8 | 2 | 6 | 125 | 41 | 341 | 34 | 63 | 28 | 97 |
得: ↓ i ↓ j
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
5 | 7 | 8 | 2 | 6 | 41 | 341 | 34 | 63 | 28 | 125 |
同理,a[j] 遇到比97小的,就换到a[ i ]的位置,i++
↓ i → ↓ i ↓ j
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
5 | 7 | 8 | 2 | 6 | 28 | 41 | 341 | 34 | 63 | 125 |
i、j分别向左走向右走,迟早会遇到。
当两个指针相遇,即i == j时,这样就能完成了比97小的,都被换到了左边,大的都被换到了右边。想不通的面壁去。因此 相遇的位置即97的位置。
PS:我们看到每当做一次交换,则换另一个指针走。
这样每趟只需要做n次对比、操作,分治之后的树的高度是logN,因此时间复杂度为O(NlogN)
好了,下面用代码实现:
int i = begin;//记录两个指针的初始位置 int j = end; int tem = a[end];//选择基数,可以随便选,一般选择端点,简单,安全 boolean tag = true;//标记该哪个指针走,true表示 i 指针走 while (i != j) {//如果两个指针没相遇,则一直循环下去 if (tag) {//左边指针走 if (a[i] < tem) {//如果不满足交换条件,就继续走 i++; continue; } else {//满足交换条件,将大数换到右边 a[j] = a[i]; j--;//该句可以略去,若略去,a[j]要多对比一次 tag = !tag;//换右指针向左走 } } else { if (a[j] > tem) {//同上 j--; continue; } else { a[i] = a[j]; i++;//可略去 tag = !tag; } } } a[i] = tem;//最右当i 、j相遇时,把当时所选的数放进去即可
上述代码相对比较傻瓜,是完全按照上面一步一步来的,代码可以进一步压缩:
while(i < j){ while(i < j && a[j] > tem){ j--;} swap(a[i],a[j]);//交换两个数 while(i < j && a[j] < tem){i++;} swap(a[i],a[j]); } a[i] = tem;
当然,分治法用到了递归,是肯定要设置一个出口的,
if(end <= begin){ return; }
以上即可。
附录:
下面把完整外码贴出来
public class QuickSort { static void quickSort(int[] a, int begin, int end) { /* * 找到某个数字的制定位置,并记录下来 */ if(end <= begin){ return; } int i = begin; int j = end; int tem = a[end]; boolean tag = true; while (i != j) { if (tag) { if (a[i] < tem) { i++; continue; } else { a[j] = a[i]; tag = !tag; } } else { if (a[j] > tem) { j--; continue; } else { a[i] = a[j]; tag = !tag; } } } a[i] = tem; quickSort(a, begin, i - 1); quickSort(a, i + 1, end); } public static void main(String[] args) { int[] a = { 5, 7, 8, 2, 6, 125, 41, 341, 34, 63, 28, 97 }; quickSort(a, 0, a.length - 1); } }
相关推荐
快速排序 * 1.i=left,j=right,将基准数挖出形成第一个坑a[i]; * 2.j--由后向前找比它小的数,找到后挖出此数填前一个坑a[i]; * 3.i++由前向后找比它大的数,找到后挖出此数填到前一个坑a[j]中 * 4.以i为中线,...
与本人博文《算法专项(1)——快速排序》相配套的工程源码,用JAVA实现
(1)数据结构与算法概念...(15)排序算法(五)——快速排序 (16)排序算法(六)——希尔排序 (17)排序算法(七)——堆排序 (18)排序算法(八)——基数排序 (19)排序算法(九)——八大排序算法总结
算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...
冒泡排序实际上是将数据从右至左排序完成(从右至左、从大到小进行交换排序),而快速排序是将数据从左到右排序完成(从左至右、从小到大进行交换排序),虽然选择排序相对于冒泡排序将交换次数从O(n2)O(n^2)O(n2)...
java代码-使用java解决java排序之-快速排序的问题的源代码 ——学习参考资料:仅用于个人学习使用!
分享一套算法与数据结构的视频课程——《算法与数据结构体系课》,课程一共16周内容,提供配套的源码和图文资料...【阶段3:算法与数据结构进阶】第10周、冒泡排序,希尔排序和排序算法大总结 【阶段3:算法与数据结
堆6.6 左式堆6.6.1 左式堆性质6.6.2 左式堆操作6.7 斜堆6.8 二项队列6.8.1 二项队列结构6.8.2 二项队列操作6.8.3 二项队列的实现6.9 标准库中的优先队列小结练习参考文献第7章 排序7.1 预备知识7.2 插入排序7.2.1...
堆6.6 左式堆6.6.1 左式堆性质6.6.2 左式堆操作6.7 斜堆6.8 二项队列6.8.1 二项队列结构6.8.2 二项队列操作6.8.3 二项队列的实现6.9 标准库中的优先队列小结练习参考文献第7章 排序7.1 预备知识7.2 插入排序7.2.1 ...
算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...
7.3 一些简单排序算法的下界 7.4 希尔排序 7.5 堆排序 7.6 归并排序 7.7 快速排序 7.7.1 选取枢纽元 7.7.2 分割策略 7.7.3 小数组 7.7.4 实际的快速排序例程 7.7.5 快速排序的分析 7.7.6 选择问题的线性期望时间算法...
java代码-使用java解决快速排序的源代码 ——学习参考资料:仅用于个人学习使用!
本文件讲了十种JAVA排序方法(冒泡(Bubble)排序——相邻交换 、选择排序——每次最小/大排在相应的位置 、插入排序——将下一个插入已排好的序列中 、壳(Shell)排序——缩小增量 、归并排序 、快速排序 、堆排序 ...
堆6.6 左式堆6.6.1 左式堆性质6.6.2 左式堆操作6.7 斜堆6.8 二项队列6.8.1 二项队列结构6.8.2 二项队列操作6.8.3 二项队列的实现6.9 标准库中的优先队列小结练习参考文献第7章 排序7.1 预备知识7.2 插入排序7.2.1 ...
7.7.3 小数组 7.7.4 实际的快速排序例程 7.7.5 快速排序的分析 7.7.6 选择问题的线性期望时间算法 7.8 排序算法的一般下界 7.9 桶式排序 7.10 外部排序 7.10.1 为什么需要一些新的算法 7.10.2 外部...
4.6 快速排序法 113 4.6.1 快速排序算法 113 4.6.2 快速排序算法示例 114 4.7 堆排序法 116 4.7.1 堆排序算法 116 4.7.2 堆排序算法示例 121 4.8 合并排序法 123 4.8.1 合并排序算法 123 4.8.2 合并排序...
- 快速排序 ###第八章 -不相交集 ###第九章 -邻接表(Versioni 1,2) -拓扑排序(Versioni 1,2) -单源最短路径算法 -最大网络流 -最小生成树 -深度优先搜索 -双连通性 -欧拉回路 ###第十章 -分治算法:最近点问题 -动态...
7.7.3 小数组 7.7.4 实际的快速排序例程 7.7.5 快速排序的分析 7.7.6 选择问题的线性期望时间算法 7.8 排序算法的一般下界 7.9 桶式排序 7.10 外部排序 7.10.1 为什么需要一些新的算法 7.10.2 外部...