快速排序
快速排序法事应用最广泛的排序算法之一，最佳情况下时间复杂度是 O(nlogn)。但是最坏情况下可能达到O(n^2)。说明快速排序达到最坏情况的原因。并提出改善方案并实现之。
答：
最坏情况就是，每次分都分出有一部分只有一个元素的。这样T(n) = n + T(n-1) = O(n*n);
最好的情况下，就是每次都各分一半。这样T(n) = 2*T(n/2)+n = 2*log2(n) + n*log2(n) = O(nlog2(n))
改进方案：改进选取枢轴的方法
1.随机选。2.选端值或者中心值。3.选取到中位数（不过觉得选到来。。。还不如排序了吧）
最终，选择用第一种，拼人品。
排序思想：分而治之，选取到一个值，以他为准，分两半，对这两半递归再分，直至只有一个元素。
#include <iostream>
#include <stdio.h>
#include <time.h>
using namespace std;
int myrand(int low , int high){
return (rand()%(high - low))+low;
}
template<typename T>
void quicksort(T * array,int low,int high){
if( low < high){
int x = array[myrand(low,high)];
int i = low,j = high;
while( i < j){
// 从左往右找到大于x的数
while(i < j && array[i] < x)
i++;
// 从右往左找到小于x的数
while(i < j && array[j] > x)
j--;
//如果i<j就交换值
if(i < j)
swap(array[i],array[j]);
}
quicksort(array,low,i - 1);
quicksort(array,i+1,high);
}
}
int main(){
srand(unsigned int(time(NULL)));
int array[10];
for(int i = 0;i<10;i++)
array[i] = myrand(0,100);
for(auto& elem : array)
cout << elem << " ";
cout << endl;
quicksort(array,0,9);
for(auto& elem : array)
cout << elem << " ";
cout << endl;
system("pause");
return 0;
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2015-08-22，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读