快速排序(Quicksort)是对冒泡排序的一种改进。由C. A. R. Hoare在1962年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
设要排序的数组是A[0]……A[N-1],首先任意选取一个数据(通常选用第一个数据)作为关键数据,然后将所有比它小的数都放到它前面,所有比它大的数都放到它后面,这个过程称为一趟快速排序。值得注意的是,快速排序不是一种稳定的排序算法,也就是说,多个相同的值的相对位置也许会在算法结束时产生变动。
一趟快速排序的算法是:
1)设置两个变量I、J,排序开始的时候:I=0,J=N-1;
2)以第一个数组元素作为关键数据,赋值给key,即 key=A[0];
3)从J开始向前搜索,即由后开始向前搜索(J=J-1即J--),找到第一个小于key的值A[j],A[j]与A[i]交换;
4)从I开始向后搜索,即由前开始向后搜索(I=I+1即I++),找到第一个大于key的A[i],A[i]与A[j]交换;
5)重复第3、4、5步,直到 I=J; (3,4步是在程序中没找到时候j=j-1,i=i+1,直至找到为止。找到并交换的时候i, j指针位置不变。另外当i=j这过程一定正好是i+或j-完成的最后令循环结束。)
以上文字摘自百度百科
private static void quickSort(int[] data) {
subSort(data, 0, data.length - 1);
}
// 对 data 数组中从 start ~ end 索引范围的子序列进行处理
// 使之满足所有小于分界值的放在左边,所有大于分界值的放在右边
private static void subSort(int[] data, int start, int end) {
// 需要排序
if (start < end) {
// 以第一个元素作为分界值
int base = data[start];
// i 从左边开始搜索,搜索大于分界值的元素的索引
int i = start;
// j 从右边开始搜索,搜索小于分界值的元素的索引
int j = end + 1;
while (true) {
// 找到大于分界值的元素的索引,或者 i 已经到了 end 处
while (i < end && data[++i] <= base);
// 找到小于分界值的元素的索引,或者 j 已经到了 start 处
while (j > start && data[--j] >= base);
if (i < j) {
swap(data, i, j);
} else {
break;
}
}
swap(data, start, j);
// 递归左边子序列
subSort(data, start, j - 1);
// 递归右边子序列
subSort(data, j + 1, end);
}
}
快速排序的时间效率很好,因为它每趟能确定的元素呈指数增长。
快速排序需要使用递归,而递归使用栈,因此它的空间效率为O(log2n)。
快速排序中包含跳跃式交换,因此是不稳定的排序算法。
以上代码文字摘自李刚的《疯狂java:突破程序员基本功的16课》
分享到:
相关推荐
快速排序 * 1.i=left,j=right,将基准数挖出形成第一个坑a[i]; * 2.j--由后向前找比它小的数,找到后挖出此数填前一个坑a[i]; * 3.i++由前向后找比它大的数,找到后挖出此数填到前一个坑a[j]中 * 4.以i为中线,...
NULL 博文链接:https://wojiaolongyinong.iteye.com/blog/1868188
舍伍德——快速排序源码报告和算法分析 有需要的朋友看下
算法与数据结构——快速排序
Python排序算法详解 Python排序算法——冒泡排序 Python排序算法——插入排序 Python排序算法——选择排序 Python排序算法——快速排序 Python排序算法——归并排序
以从小到大排序为例,选择排序是从某一列数字当中选出最小的数字与第一个位置交换,在从第二个数字开始寻找第二小的数字与第二个位置交换,以此类推,直至最后一个数字交换完毕,排序完成
#include #include class Array{ public: Array(int Size=150);//构造函数 ~Array() {delete[]T;}// 析构函数 //取数组长度 int qdivde(int low,int high); void print(); void exchange(int i,int j);...
快速排序有很多不同的算法来解决,在此我是用C++来编写这个程序的,根据快速排序的算法思想,很容易将此问题解决。还可以运用非递归的方法解决,但是我不熟练。
贪心算法中,背包问题的源代码。可以编译运行,用快速排序实现的。
基于mfc做的排序,包括快速排序,堆排序,希尔排序,插入排序,选择排序,冒泡排序等……
5.4 对链表进行快速排序 5.5 对多个键进行排序——不稳定排序的修正方法 5.6 网络排序 5.7 小结:选择一种排序算法 5.8 资源和参考资料 第6章 树 6.1 二叉树 6.1.1 树查找 6.1.2 节点插入 ...
利用python代码实现数据结构的经典算法——快速排序算法。
(1)数据结构与算法概念...(15)排序算法(五)——快速排序 (16)排序算法(六)——希尔排序 (17)排序算法(七)——堆排序 (18)排序算法(八)——基数排序 (19)排序算法(九)——八大排序算法总结
四种排序算法,插入排序 折半排序 快速排序 冒泡排序,c语言编写,可执行
利用随机函数产生N个随机整数(N = 500,1000,1500,2000,2500,…,30000),利用直接插入排序、折半插入排序,起泡排序、快速排序、选择排序、堆排序,基数排序七种排序方法(可添加其它排序方法)进行排序...
本文介绍了学习各种语言时,经典的几种算法的详细说明,对我们初学者应该有很大的帮助! 本资源为转载,版权属原作者!
算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...
文章目录快速排序思路注意!!!!!错误代码正确代码代码优化 快速排序 思路 如果列表为空或者只有一个元素则不用排序 选择首元素为基准值 创建两个列表:小于基准值的less=[ ]和大于基准值的high=[ ] 遍历整个列表...
与本人博文《算法专项(1)——快速排序》相配套的工程源码,用JAVA实现
快速排序 实验数据:input.txt(共100个数据) ——要求按从小到大进行排序 将排好序的数据输出到output.txt文件中