1.说明
快速排序法(quicksort)是目前所公认最快的排序方法之一(视解题的对象而定),虽然快速排序法在最差状况下可以达O(n2),但是在多数的情况下,快速排序法的效率表现是相当不错的。快速排序法的基本精神是在数列中找出适当的轴心,然后将数列一分为二,分别对左边与右边数列进行排序,而影响快速排序法效率的正是轴心的选择。这边所介绍的第一个快速排序法版本,是在多数的教科书上所提及的版本,因为它最容易理解,也最符合轴心分割与左右进行排序的概念,适合对初学者进行讲解。
2.解法
这边所介绍的快速演算如下:
一趟快速排序的算法是:
- 设置两个变量start、end,排序开始的时候:start=1,end=N;
- 以第一个数组元素作为关键数据,赋值给pivot,即 pivot=arry[1];
- 从end开始向前搜索,即由后开始向前搜索(end--),找到第一个小于pivot的值arry[end],并与arry[start]交换,即swat(arry,start,end);
- 从start开始向后搜索,即由前开始向后搜索(start++),找到第一个大于pivot的arry[start],与arry[end]交换,即swat(arry,start,end);
- 重复第3、4步,直到 start==end,这个时候arry[start]=arry[end]=pivot,而pivot的位置就是其在整个数组中正确的位置;
- 通过递归,将问题规模不断分解。将pivot两边分成两个数组继续求新的pivot,最后解出问题。
3.代码实例
View Code
#include<iostream> #include<stdlib.h> #include<time.h> using namespace std; #define maxNum 10//需要排序的元素个数 void swap(int arry[],int a,int b) { int temp=arry[a]; arry[a]=arry[b]; arry[b]=temp; } int Partition(int arry[],int start,int end)//通过这一步保证了轴心位置被正确分配 { cout<<"轴心数组"<<endl; for(int i=start;i<=end;i++) cout<<arry[i]<<" "; cout<<endl; int pivot=arry[start];//轴心元素 while(start<end) { //当末尾的元素大于轴心元素值时,不做处理,让尾指针往前跳 while(start<end&&arry[end]>pivot) end--; //找到第一个不满足arry[end]>pivot的元素,让其arry[end]和arry[start]互换 swap(arry,start,end); //当前端的元素小于轴心元素时,不对元素做任何处理,让头指针往尾部跳 while(start<end&&arry[start]<pivot) start++; //找到第一个不满足arry[start]<pivot的元素,让其arry[end]和arry[start]互换 swap(arry,start,end); } //输出轴心位置 cout<<"输出轴心位置:"<<start<<endl; /*由于前面 while(start<end&&arry[end]>pivot)和while(start<end&&arry[start]<pivot)的限定, 保证了最后不会出现low>high的情况,因此最后low=high,该位置就是轴心元素在数组中的位置。 */ return start;//轴心位置 } void QSort(int arry[],int start,int end) { if(start<end) { //这一步保证了arry[pivot]大于左边的元素小于右边的元素,arry[pivot]被正确安排。 int pivot=Partition(arry,start,end); QSort(arry,start,pivot-1); QSort(arry,pivot+1,end); } } void QuickSort(int arry[],int len) { QSort(arry,1,len); } void main() { int arry[100]={0}; srand(time(NULL)); cout<<"排序前元素:"<<endl; for(int i=1;i<=maxNum;i++) { arry[i]=rand()%100; cout<<arry[i]<<" "; } cout<<endl; QuickSort(arry,maxNum);//快速排序 cout<<"排序后元素:"<<endl; for(int i=1;i<=maxNum;i++) { cout<<arry[i]<<" "; } cout<<endl; system("pause"); } /* 排序前数组: 42 52 61 32 94 86 38 34 18 59 初始化start和end的位置,用*标注 42* 52 61 32 94 86 38 34 18 59* pivot=42 <-end: 42* 52 61 32 94 86 38 34 18* 59 尾部遇到第一个小于pivot的数18*,则swap(arry,start,end); 18* 52 61 32 94 86 38 34 42* 59 start->: 18 52* 61 32 94 86 38 34 42* 59 头部遇到第一个大于povit的数52*,则swap(arry,start,end); 18 42* 61 32 94 86 38 34 52* 59 <-end: 18 42* 61 32 94 86 38 34* 52 59 swap 18 34* 61 32 94 86 38 42* 52 59 start->: 18 34 61* 32 94 86 38 42* 52 59 swap 18 34 42* 32 94 86 38 61* 52 59 <-end: 18 34 42* 32 94 86 38* 61 52 59 swap 18 34 38* 32 94 86 42* 61 52 59 start 18 34 38 32 94* 86 42* 61 52 59 swap 18 34 38 32 42* 86 94* 61 52 59 <-end: 18 34 38 32 42* 86* 94 61 52 59 18 34 38 32 42** 86 94 61 52 59 此时start==end,第一个轴心pivot找到,**就是轴心,位置为5 */
4.快速排序实例java版本(ps:2011-11-25)
思路和前面的一样,只是使用java来实现。
View Code
public class QuickSortTest1 { public static void main(String[] args) { // TODO Auto-generated method stub int arry[]={5,6,2,7,1}; int len=arry.length; System.out.println("数组长度:"+arry.length); System.out.print("快速排序前数组元素为:"); for(int i:arry) { System.out.print(i+" "); } System.out.println(); quickSort(arry,0,len-1); System.out.print("快速排序后数组元素为:"); for(int i:arry) { System.out.print(i+" "); } } //一次快速排序所执行的步骤 public static int quickSortOnce(int []arry,int start,int end) { int pivot=arry[start];//将首元素最为pivot while(start<end) { //找到第一个大于pivot的arry[end] while(pivot<arry[end]&&start<end) end--; arry[start]=arry[end]; //找到第一个小于pivot的arry[start] while(pivot>arry[start]&&start<end) start++; arry[end]=arry[start]; } //最后start==end以后的位置就是起始pivot存放的位置 arry[start]=pivot; //返回pivot的位置,后面按次位置分解 return start; } public static void quickSort(int []arry,int start,int end) { //判断start与end的位置 if(start>=end) return; int pivot=quickSortOnce(arry,start,end); quickSort(arry,start,pivot-1); quickSort(arry,pivot+1,end); } }
java版本快速排序的改进(ps:2012-5-23)
上面的java版本快速排序写的有点凌乱,下面给出改进版本,本文中的java版本快排并没有想前面c++版本那样使用swap方法。
View Code
public class QuickSort { //打印数组 public static void print(int arry[]) { for(int i:arry) { System.out.print(i+" "); } System.out.println(); } //partition返回某一个index,在index左边的元素都比index所在元素值小,右边的都比index所在元素值大 public static int partition(int []arry,int start,int end) { int pivot=arry[start];//将首元素最为pivot while(start<end) { //找到第一个大于pivot的arry[end] while(pivot<arry[end]&&start<end) end--; arry[start]=arry[end]; //找到第一个小于pivot的arry[start] while(pivot>arry[start]&&start<end) start++; arry[end]=arry[start]; } //最后start==end以后的位置就是起始pivot存放的位置 arry[start]=pivot; //返回pivot的位置,后面按次位置分解 return start; } public static void quickSort(int []arry,int start,int end) { //判断start与end的位置 if(start>=end) return; int pivot=partition(arry,start,end); quickSort(arry,start,pivot-1); quickSort(arry,pivot+1,end); } public static void main(String[] args) { // TODO Auto-generated method stub int arry[]={5,6,2,7,1}; int len=arry.length; System.out.print("快速排序前数组元素为:"); print(arry); quickSort(arry,0,len-1); System.out.print("快速排序后数组元素为:"); print(arry); } }
PS:2012-5-4对于数组中有相同数情况下的排序修改
如果使用上述方法进行快速排序,数组中有相同的数,那么排序过程中会出现死循环,这里需要修改Partition函数中的while循环的条件,将原来的arry[end]>pivot改为arry[end]>=pivot,arry[start]<pivot改为arry[start]<=pivot。
修改以后的Partition函数如下:
View Code
int Partition(int arry[],int start,int end)//通过这一步保证了轴心位置被正确分配 { cout<<"轴心数组"<<endl; for(int i=start;i<=end;i++) cout<<arry[i]<<" "; cout<<endl; int pivot=arry[start];//轴心元素 while(start<end) { //当末尾的元素大于轴心元素值时,不做处理,让尾指针往前跳 while(start<end&&arry[end]>=pivot) end--; //找到第一个不满足arry[end]>pivot的元素,让其arry[end]和arry[start]互换 swap(arry,start,end); //当前端的元素小于轴心元素时,不对元素做任何处理,让头指针往尾部跳 while(start<end&&arry[start]<=pivot) start++; //找到第一个不满足arry[start]<=pivot的元素,让其arry[end]和arry[start]互换 swap(arry,start,end); } //输出轴心位置 cout<<"输出轴心位置:"<<start<<endl; /*由于前面 while(start<end&&arry[end]>pivot)和while(start<end&&arry[start]<pivot)的限定, 保证了最后不会出现low>high的情况,因此最后low=high,该位置就是轴心元素在数组中的位置。 */ return start;//轴心位置 }
相关推荐
快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较,但这种状况并不常见。事实上,快速排序通常明显比其他Ο(n log n) 算法更快,因为...
分治法的另外一种排序算法,快速排序。有注释,便于阅读,因为交换时使用的引用,暂时归为C++,C语言版稍后奉上。
分治法的应用,快速排序是其中一种。注释便于读者明白。
快速排序算法C语言实现,快排序算法QuickSort.cpp
PHP_基于php实现的快速排序算法_QuickSort
快速排序算法,C语言 快速排序(Quicksort)是对冒泡排序的一种改进。由C. A. R. Hoare在1962年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有...
快速排序 快速排序(Quicksort)是一种常见的、高效的排序算法,它基于分治(Divide and Conquer)的思想
编写程序实现归并排序算法 MergeSortL 和快速排序算法 QuickSort;
快速排序算法快速排序算法快速排序算法快速排序算法快速排序算法
然后定义了quickSort函数来实现快速排序算法。在main函数中,我们定义了一个数组并对其进行快速排序,并打印排序后的结果。 快速排序是一种高效的排序算法,它的实现相对简单但性能优秀。希望这个示例能帮助你理解...
Hoare)在1962年发表的关于快速排序算法的原始论文,题为 "Quicksort",发表在《The Computer Journal》第5卷第1期上。这篇论文是计算机科学领域的经典文献之一,首次详细介绍了快速排序算法的原理和实现方法。 在...
用c语言实现的快排算法 附有简单的实例
1、 用快速排序算法QuickSort()先将数组排序; 2、 用数组b[]存储每个不同的数字出现的次数; 3、 求b[]数组中最大值,即为众数的重数; 4、 输出众数和重数;如果没有众数,则输出没有众数提示。
/********************快排算法************************/ void quicksort(int A[],int p,int r) { int q; if(p) { q=partition(A,p,r); quicksort(A,p,q-1); quicksort(A,q+1,r); } } /*****************...
日本程序员norahiko,写了一个排序算法的动画演示,非常有趣...目前,最常见的排序算法大概有七八种,其中"快速排序"(Quicksort)使用得最广泛,速度也较快。它是图灵奖得主C. A. R. Hoare(1934--)于1960时提出来的
JDK7的时候内置 的排序算法已经由经典快排变成了Dual-Pivot排序算法。那么Dual-Pivot到底是何方圣神,能 比我们学过的经典快排还要快呢?
CUDA-quicksort 是一种基于 GPU 的快速排序算法实现。 CUDA-quicksort 旨在利用现代 NVIDIA GPU 的计算能力。 “文献中介绍了两种基于 GPU 的快速排序实现:GPU 快速排序,一种计算统一设备架构 (CUDA) 迭代实现,...
一个非常简单的快速排序算法!!!站长你好,我现在大四,需要下载一个tsplib的数据来跑蚁群算法的实验,由与查重的原因暂时不能把程序上传上来,可以先给我过吗,等答辩完我再上传程序,谢谢~
在Java实现中,快速排序算法通过quickSort方法接收待排序数组和左右索引作为参数,递归地调用partition方法进行数据划分,并分别对划分后的子序列进行排序。partition方法选择数组中的一个元素作为基准,通过比较和...
本算法使用MapBasic编写而成,文件类型为".MB"。如果没有装相关软件,可以使用记事本打开。希望对大家有所帮助。