从排序开始(四)快速排序

发布于:2021-09-17 05:15:53

? ? ? 快速排序是由东尼?霍尔所发展的一种使用分治法(Divide and conquer)策略的排序算法。


? ? ? 它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。


? ? ? 基本步骤为:


? ? ? 1、从数列中挑出一个元素,称为 "基准"


? ? ? 2、重新排序数列,所有比基准值小的元素摆放在基准前面,所有比基准值大的元素摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作。


? ? ? 3、递归地把小于基准值元素的子数列和大于基准值元素的子数列排序。




下面的图解是基于交换值的实现方法,后面我们的实现是另一种方法:






最差时间复杂度: ?O(n^2)


最优时间复杂度: O(n logn)


*均时间复杂度: O(n logn)


最差空间复杂度: ?最好是O(log n)

稳定性:不稳定




快速排序的时间主要耗费在划分操作上,对长度为k的区间进行划分,共需k-1次关键字的比较。

最坏情况是每次划分选取的基准都是当前无序区中关键字最小(或最大)的记录,划分的结果是基准左边的子区间为空(或右边的子区间为空),而划分所得的另一个非空的子区间中记录数目,仅仅比划分前的无序区中记录个数减少一个。时间复杂度为O(n*n)

最好情况下,每次划分所取的基准都是当前无序区的"中值"记录,划分的结果是基准的左、右两个无序子区间的长度大致相等。总的关键字比较次数:O(nlgn)




优化:


一种比较常见的优化方法是随机化算法,即随机选取一个元素作为主元。这种情况下虽然最坏情况仍然是O(n^2),但最坏情况不再依赖于输入数据,而是由于随机函数取值不佳。实际上,随机化快速排序得到理论最坏情况的可能性仅为 1/(2^n)。所以随机化快速排序可以对于绝大多数输入数据达到O(n logn)的期望时间复杂度。




已优化实现:



#include

using namespace std;

void quickSort(int num[], int l, int r)
{
if (l >= r) return;

//实现随机选取基数,即随机选一个数并和最左端的数交换
int k = rand()%(r - l + 1) + l;
int t = num[k];
num[k] = num[l];
num[l] = t;

int i = l, j = r, key = num[l];
while (i < j)
{
//从右向左找第一个小于key的数
while(i < j && num[j] >= key)
j--;
if(i < j)
num[i++] = num[j];

// 从左向右找第一个大于等于key的数
while(i < j && num[i] < key)
i++;
if(i < j)
num[j--] = num[i];
}
num[i] = key;

//分治,递归
quickSort(num, l, i - 1);
quickSort(num, i + 1, r);
}

//简单测试
int main() {

int n;
while(cin>>n,n)
{
int *p = new int[n];
for( int i = 0;i p[i] = rand()%200;
quickSort(p,0,n-1);
for(int i=0;i cout< cout< delete []p;
}
return 0;
}



再优化:


? ? 其实上面的while循环里面“从右向左找第一个小于key的数”是不好的,想一想,如果输入数据都是 一样的,那么这个算法就会退化成 O(n^2),这是无法接受的!所以,我们要改为“从右向左找第一个小于等于key的数”,也就是判断条件从?while(i < j && num[j] >= key) 改为?while(i < j && num[j] > key) ,去掉等于号!


? ?另外,如果需要排序的数据量很小,那么插入排序是很快的,甚至于在 STL 的 sort 算法和 stdlib 的 qsort 算法中,都将插入排序作为快速排序的补充,用于少量元素的排序(通常为8个或以下)。我们加入一个 <8 的判断条件,如果小于8,那么采用插入排序。



void quickSort(int num[], int l, int r)
{
if(l >= r) return;

int k = l + rand()%(r-l+1);
int t = num[k];
num[k] = num[l];
num[l] = t;

if(r - l + 1 < 8){
for(int i = l+1;i <= r;++i)
if(num[i] < num[i-1])
{
int j,t = num[i];
for(j = i-1;j >= 0 && num[j] > t;j--)
num[j+1] = num[j];
num[j+1] = t;
}
return;
}

int i = l,j = r,key = num[l];
while(i < j)
{
while(i < j && num[j] > key)
j--;
if(i < j) num[i++] = num[j];

while(i < j && num[i] < key)
i++;
if(i < j) num[j--] = num[i];
}
num[i] = key;

quickSort(num,l,i-1);
quickSort(num,i+1,r);
}

相关推荐