算法介绍:
快速排序(Quicksort)是对冒泡排序的一种改进。由C. A. R. Hoare在1962年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
设要排序的数组是A[0]……A[N-1],首先任意选取一个数据(通常选用数组的第一个数)作为关键数据,然后将所有比它小的数都放到它前面,所有比它大的数都放到它后面,这个过程称为一趟快速排序。值得注意的是,快速排序不是一种稳定的排序算法,也就是说,多个相同的值的相对位置也许会在算法结束时产生变动。
假设用户输入了如下数组:
下标
|
0
|
1
|
2
|
3
|
4
|
5
|
数据
|
6
|
2
|
7
|
3
|
8
|
9
|
创建变量i=0(指向第一个数据), j=5(指向最后一个数据), k=6(赋值为第一个数据的值)。
我们取走了下标0的数据,于是,我们需要找到一个数字来替换他。由于我们要把所有比6小的数移动到左面,所以我们可以开始寻找比6小的数并从右往左找。别急,我们要按顺序找哦。不断递减j的值,我们发现下标3的数据比6小,于是把3移到下标0(实际是i指向的位置。代码中要用i,因为后面还会循环这个步骤,不用i的话第二次循环:
下标
|
0
|
1
|
2
|
3 |
4
|
5
|
数据
|
3
|
2
|
7
|
6
|
8
|
9
|
i=0 j=3 k=6
由于变量k已经储存了下标0的数据,所以我们可以放心的把下标0覆盖了。如此一来,下标3虽然有数据,但是相当于没有了,因为数据已经复制到别的地方了。于是我们再找一个数据来替换他。这次要变成找比k大的了,而且要从前往后找了。递加变量i,发现下标2是第一个比k大的,于是用下标2的数据7替换j指向的下标3的数据,数据状态变成下表:
下标
|
0
|
1
|
2
|
3
|
4
|
5
|
数据
|
3
|
2
|
6
|
7
|
8
|
9
|
i=2 j=3 k=6
重复上面的步骤,递减变量j。这时,我们发现i和j“碰头”了:他们都指向了下标2。于是,循环结束,把k填回下标2里,即得到结果。
如果i和j没有碰头的话,就递加i找大的,还没有,就再递减j找小的,如此反复,不断循环。注意判断和寻找是同时进行的。
快速排序的示例:
(a)一趟排序的过程:
(b)排序的全过程
算法的实现:
public class QuickSort { public static void main(String[] agrs) { int a[] = new int[] {49, 38, 65, 97, 76, 13, 27, 36, 91}; System.out.println("排序之前:"); print(a); System.out.println("\n开始排序:"); sort(a, 0, a.length-1); System.out.println(); System.out.println("排序之后:"); print(a); } private static void sort(int[] a, int l, int r) { if (l < r) { int privotLoc = partition(a, l, r); //将表一分为二 sort(a, l, privotLoc - 1); //递归对左子表递归排序 sort(a, privotLoc + 1, r); //递归对右子表递归排序 } } // 注意: 如果把注释的代码打开,就可以去掉这行a[left] = k; private static int partition(int[] a, int left, int right) { int k = a[left]; //基准元素 System.out.println("left=" + left + ", right=" + right + ", k=" + k); while (left < right) { //从表的两端交替地向中间扫描 while (left < right && a[right] >= k) --right; //从right 所指位置向前搜索,至多到left+1 位置。将比基准元素小的交换到低端 if (left < right) { // int temp = a[left]; a[left] = a[right]; // a[right] = temp; } while (left < right && a[left] <= k) ++left; if (left < right) { // int temp = a[right]; a[right] = a[left]; // a[left] = temp; } } a[left] = k; //把k填回中间位置 print(a); return left; } private static void print(int[] a) { for (int i = 0; i < a.length; i++) { System.out.print(a[i] + " "); } System.out.println(); } }
结果输出:
排序之前: 49 38 65 97 76 13 27 36 91 开始排序: left=0, right=8, k=49 36 38 27 13 49 76 97 65 91 left=0, right=3, k=36 13 27 36 38 49 76 97 65 91 left=0, right=1, k=13 13 27 36 38 49 76 97 65 91 left=5, right=8, k=76 13 27 36 38 49 65 76 97 91 left=7, right=8, k=97 13 27 36 38 49 65 76 91 97 排序之后: 13 27 36 38 49 65 76 91 97
动画演示: http://www.tyut.edu.cn/kecheng1/site01/suanfayanshi/quick_sort.asp
分析:
快速排序是通常被认为在同数量级(O(nlog2n))的排序方法中平均性能最好的。但若初始序列按关键码有序或基本有序时,快排序反而蜕化为冒泡排序。为改进之,通常以“三者取中法”来选取基准记录,即将排序区间的两个端点与中点三个记录关键码居中的调整为支点记录。快速排序是一个不稳定的排序方法。
相关推荐
《数据结构与算法》-李春葆 实验报告-典型排序算法实践-快速排序
VC++多线程实现三种排序算法比较----冒泡排序、快速排序、归并排序,很有意思,可以下载看看!
算法设计与分析 一PRESETATION 仅做参考,请勿copy冲查重塔峰 排序算法性能分析 ...但注意理论上快速排序的空间复杂度较高为O(n),且最坏情况时时间复杂度也达到了O(n2)。所以快速算法也较为常用。
(matlab代码)带约束条件的非支配排序遗传算法NSGA-II,解决了一个多目标优化问题 (matlab代码)带约束条件的非支配排序遗传算法NSGA-II,解决了一个多目标优化问题 (matlab代码)带约束条件的非支配排序遗传算法...
各类排序算法整理--C语言描述--本人编写 排序算法种类有: 冒泡 快速排序 堆排序 希尔排序 插入排序 选择排序 二路归并排序
经典排序算法 - 快速排序Quick sort 经典排序算法 - 桶排序Bucket sort 经典排序算法 - 插入排序Insertion sort 经典排序算法 - 基数排序Radix sort 经典排序算法 - 鸽巢排序Pigeonhole sort 经典排序算法 - ...
详解Java常用排序算法-快速排序
最快的排序算法 谁才是最强的排序算法:快速排序-归并排序-堆排序,排序算法数据结构
最快的排序算法 计算机最快的算法-史上14个最快速算法:孩子的计算能力爆表!大脑堪比计算机!...,排序算法数据结构
算法设计,快速排序的C++实现代码,并测试运行时间
此文件为数据结构中的九种排序算法,包含一些排序方法的过程,其九种排序包括:直接插入排序,折半插入排序,希尔排序,冒泡排序,快速排序,选择排序,堆排序,归并排序,基数排序!
算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...
基于python的排序算法-快速排序Quick Sort
七大排序算法如下: 交换排序:快速排序quicksort,冒泡排序bubblesort 选择排序:直接选择排序selectionsort,堆排序maxheapsort 插入排序:直接插入排序insertsort,希尔排序shellsort 合并排序:归并排序...
4、快速排序算法并行化 5、描述了使用2m个处理器完成对n个输入数据排序的并行算法。 6、在最优的情况下并行算法形成一个高度为logn的排序树 7、完成快速排序的并行实现的流程图 8、完成快速排序的并行算法的实现
只需两个时钟即可输出12个数据的排序结果,内容简单易懂
算法-数据结构和算法-13-快速排序.rar
排序作为最基础的算法,有选择排序,冒泡排序,插入排序,希尔排序,堆排序,快速排序,归并排续等,我会用c++写一下,欢迎交流~
实现以下常用的内部排序算法并进行性能比较:"直接插入排序"," 折半插入排序"," 2—路插入排序"," 表插入排序"," 希尔排序"," 起泡排序"," 快速排序"," 简单选择排序"," 树形选择排序"," 堆排序"," 归并排序"," 链式...
Java代码-排序-直接插入排序、希尔排序、直接选择排序、冒泡排序、堆排序、快速排序、归并排序中部分排序以及算法-贪心法,大家可以将源码下载下来进行学习,附带着注释和解释,有不理解的可以找博主一起探讨,共同...