本文主要是介绍细说算法-------快速排序QuickSort，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
目录：
一、快速排序思想介绍
二、实现的三步骤（分解、子问题求解、合并）
三、C++代码实现
四、时间空间复杂度分析
------------------------------------------------------------------------分割线-----------------------------------------------------------------------------
一、快速排序思想介绍
快速排序（QuickSort）是对冒泡排序（BubbleSort）的一种改进。排序效率在同为O(N*logN)的几种排序方法中效率较高，再加上快速排序算法是 分治策略(Divide-and-ConquerMethod)的典型应用。因此很多软件公司的笔试面试，还有大大小的程序方面的考试中也常常出现快速排序的身影。博主就在蓝桥杯竞赛上遇到过。
快速排序由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的三个序列：第一个序列中所有的元素均不大于基准元素、第二个序列是基准元素、第三个序列中所有的元素均不小于基准元素。由于第二个序列已经处于正确位置，因此需要再按此方法对第一个和第三个序列分别进行排序，整个排序过程可以递归进行，最终可以使得整个序列变成有序序列。
二、实现的三步骤（分解、子问题求解、合并）
快速排序算法的基本思想是基于分治策略的，利用分治可将快速排序的基本思想描述如下：设当前待排序的序列为R[ low : high ] ，其中low <= high，如果序列的规模足够小则直接进行排序，否则分三步处理：
1、分解
在R[ low :high ]中选定一个元素作为基准元素（pivot），该基准元素的最终的位置（pivotpos）在划分的过程中确定。将比R[ pivotpos]大的数全放到它的右边R[pivotpos+1 : high]，小于或等于它的数全放到它的左边R[low : pivotpos-1 ]。
注意：基准元素如何选定，选哪个元素？基准元素最终的排序位置，在划分的过程中确定，如何确定？不要着急，下面讲解。
2、求解子问题
对两个子序列R[low :pivotpos-1 ]和R[pivotpos+1 : high]分别通过递归调用快速排序。
3、合并
由于对子序列R[low :pivotpos-1 ]和R[pivotpos+1 : high]的排序是就地进行的，所以在子序列R[low : pivotpos-1 ]和R[pivotpos+1 : high]都排序结束后，合并步骤无须做什么，整个序列R[ low : high ]就排好序了。
基准元素（pivot）的选取。最终位置（pivotpos）的确定。
快速排序要选定基准元素，选取基准元素应该遵循平衡子问题的原则：即使得划分后的两个子序列的长度尽量相同。基准元素的选择方法有很多种，常见的方式是把待排序列的首元素作为基准元素。
基准元素最终位置（pivotpos）的确定
快速排序中基准元素对序列进行划分，从而实现分治。假定待排序列为R[ low : high ]，该划分过程以第一个元素为基准元素。
1、设定两个参数i和j，他们的初值分别为待排序列的下界和上界，即i=low，j=high。
2、选取待排序列的第一个元素R[low]为基准元素，并将该值赋值给变量pivot。
3、令j自j位置开始向左扫面，如果j位置所对应的元素的值大于等于pivot，则j前移一个位置（即j--）。重复该过程，直到找到第一个小于pivot的元素R[j]，将R[j]和R[i]进行交换，i++。其实交换后R[j]所对应的元素就是pivot。
4、令i自i位置开始向右扫描，如果i位置所对应的元素的值小于等于pivot，则i后移（即i++）。重复该过程，直至找到第一个大于pivot的元素R[i]，将R[i]与R[j]进行交换，j--。其实，交换后R[i]所对应的元素就是pivot。
5、重复步骤3、4，交替改变扫描方向，从两端各自往中间靠拢直至i==j。此时i和j指向同一个位置，即基准元素pivot的最终位置。
三、C++代码实现如下：
#include <iostream>
#include <string>
using namespace std; //交换数组中两个元素位置
void swap(int &a,int & b) {int tmp;tmp=a;a=b;b=tmp;} int Partition(int * Arr,int low,int high) //划分方法
{ //i和j分别指向数组下界和上界，pivot是待排的第一个元素 int i=low,j=high,pivot=Arr[low]; while (i<j) { /* j自j位置开始向左扫面，如果j位置所对应的元素的值大于等于pivot，则j前移一个位置（即j--）。 重复该过程，直到找到第一个小于pivot的元素R[j]，将R[j]和R[i]进行交换，i++。 其实交换后R[j]所对应的元素就是pivot。*/ while (i<j && Arr[j]>=pivot) { j--; } if (i<j) { swap(Arr[i++],Arr[j]);//注意这里是交换元素，另外还有挖坑法实现，是元素覆盖。 } /* 令i自i位置开始向右扫描，如果i位置所对应的元素的值小于等于pivot，则i后移（即i++）。 重复该过程，直至找到第一个大于pivot的元素R[i]，将R[i]与R[j]进行交换，j--。 其实，交换后R[i]所对应的元素就是pivot。*/ while (i<j && Arr[i]<=pivot){i++;} if (i<j) { swap(Arr[i],Arr[j--]); } } /*此时i和j指向同一个位置，即基准元素pivot的最终位置。返回i的值*/ return i;
}
void QuickSort(int * Arr,int low,int high) //对数组Arr[low high]进行快速排序
{ int pivotpos; //划分的基本元素所在的位置 if(low<high) //区间长度大于1时才排序 { pivotpos=Partition(Arr,low,high);//对Arr[low high]进行划分 QuickSort(Arr,low,pivotpos-1); QuickSort(Arr,pivotpos+1,high); }
} void main()
{ int num; cout<<"请输入要排序元素的个数num="<<endl; cin>>num; int *array=new int[num]; cout<<"请给每一个元素赋初值\n"; for (int i=0;i<num;i++) { cin>>array[i]; } QuickSort ( array, 0,num-1); cout<<"输出排序后的结果"<<endl; for (int i=0;i<num;i++) { cout<<array[i]<<" "; } cout<<endl; system("PAUSE");
} int Partition(int * Arr,int low,int high)
{ int i = low, j = high; int pivot = Arr[low]; //Arr[low]已经保存，可以被覆盖，即第一个坑 while (i < j) { // 从右向左找小于pivot的数来填Arr[low] while(i < j && Arr[j] >= pivot) j--; if(i < j) {//将Arr[j]填到Arr[i]中，Arr[j]就形成了一个新的坑. //这里不再是交换元素位置。 Arr[i] = Arr[j]; i++; } // 从左向右找大于或等于pivot的数来填Arr[j] while(i < j && Arr[i] < pivot) i++; if(i < j) { Arr[j] = Arr[i]; //将Arr[i]填到Arr[j]中，Arr[i]就形成了一个新的坑 j--; } } //退出时，i等于j。将pivot填到这个坑中 Arr[i] = pivot; //返回调整后基准数的位置 return i;
} 四、时间空间复杂度分析
快速排序算法是递归执行，需要一个栈来存放每一层递归调用的必要信息，其最大容量应与递归调用的深度一致。最好的情况下，每次划分较为均匀，递归树的深度为O（logN），故递归所需要的栈空间为O（logN）。最坏情况下，递归树的高度为O（N），所需的栈空间为O（N）。平均情况下，所需栈空间为O（logN）。
这篇关于细说算法-------快速排序QuickSort的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
