分治-快速排序

数组排序任务可以如下完成:
1)设k=a[0],将k挪到适当的位置,使得比k小的元素都在k左边,比k打的元素都在k右边,和k相等的,不关心在k左右出现均可(O(n)时间完成)
2)把k左边的部分快速排序
3)把k右边的部分快速排序

动画演示地址

https://visualgo.net/zh/sorting

时间复杂度

O(nlogn)
将枢纽k移动到中间后,怎么保证左边元素与右边元素差不多呢,这是不能保证的
我们一般来说快排的时间复杂度是nlogN,最坏情况是n2(n的平方)
最坏情况:前一半元素为0个,后一半是所有的元素
如果担心会出现最坏情况,可以先将数组顺序打乱

代码

#include <iostream>
using namespace std;

//采用引用方式,此时改变形参的值,实参也会变
void swap(int &a,int &b)
{
    int tmp = a;
    a = b;
    b = tmp;
}

void QuickSort(int a[],int s,int e)
{
    if(s>=e)
        return;
     int k=a[s];
     int i=s,j=e;
     while(i != j)
     {
         //奇数次排序后a[j]=k,也就是说换枢纽，目标是将k移动到中间位置
         while(j>i && a[j]>=k)
            --j;
         swap(a[i],a[j]);
         while(i<j && a[i]<=k)
            ++i;
         swap(a[i],a[j]);
     }
     //把左边一半排序
     QuickSort(a,s,i-1);
     //把右边一半排序
     QuickSort(a,i+1,e);
}
int a[] = {93,27,30,2,8,12,2,8,30,89};
int main()
{
    //计算数组元素的个数
    int size = sizeof(a)/sizeof(int);
    //元素个数减去1就是末尾元素下标
    QuickSort(a,0,size-1);
    for(int i=0;i<size;++i)
        cout<<a[i]<<",";
    cout<<endl;
}