快速排序的时间复杂度为:
递归版本快排
//快速排序(从小到大) void quickSort(int left, int right, vector<int>& arr) { if(left >= right) return; int i, j, base, temp; i = left, j = right; base = arr[left]; //取最左边的数为基准数 while (i < j) { while (arr[j] >= base && i < j) j--; while (arr[i] <= base && i < j) i++; if(i < j) { temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } //基准数归位 arr[left] = arr[i]; arr[i] = base; quickSort(left, i - 1, arr);//递归左边 quickSort(i + 1, right, arr);//递归右边 }
非递归版本快排:
1.用栈集合存放左右下标
2.用一个方法来得出中下标位置
3.判断中下标的左右区间
4.回到步骤1循环这几步操作,知道栈为空,则排序完成。
#include <iostream> #include <stack> using namespace std; //划分算法 int Partition( int a[], int low, int high ) { //假设每次都以第一个元素作为枢轴值,进行一趟划分: int pivot = a[low]; while( low<high ) { while( low<high && a[high]>=pivot ) --high; a[low] = a[high]; //停下来做交换 while( low<high && a[low]<=pivot ) ++low; a[high] = a[low]; //停下来做交换 } a[low] = pivot; //pivot的最终落点 return low; } //非递归快排 void QuickSort(int a[], int left, int right) { //手动利用栈来存储每次分块快排的起始点 //栈非空时循环获取中轴入栈 stack<int> s; if( left<right ) { int boundary = Partition(a,left,right); if( boundary-1>left ) //确保左分区存在 { //将左分区端点入栈 s.push(left); s.push(boundary-1); } if( boundary+1<right ) //确保右分区存在 { s.push(boundary+1); s.push(right); } while( !s.empty() ) { //得到某分区的左右边界 int r = s.top(); s.pop(); int l = s.top(); s.pop(); boundary = Partition(a,l,r); if( boundary-1>l ) //确保左分区存在 { //将左分区端点入栈 s.push(l); s.push(boundary-1); } if( boundary+1<r ) //确保右分区存在 { s.push(boundary+1); s.push(r); } } } } int main() { int a[5] = { 4, 1, 5, 3, 2 }; int left = 0, right = 4; QuickSort(a,left,right); //输出,检验结果 for( int i=0; i<5; ++i ) { cout << a[i] << " "; } cout << endl; }
当基准数选择最左边的数字时,那么就应该先从右边开始搜索;当基准数选择最右边的数字时,那么就应该先从左边开始搜索。不论是从小到大排序还是从大到小排序!