快速排序

快速排序

快速排序

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

其最优情况下时间复杂度为O(nlogn),最坏情况下时间复杂度O(n^2),平均时间复杂度O(nlogn)

首先，我们选择一个基准元素pivot,我们以pivot为基准点，将比pivot小的元素放到pivot左边，比pivot大的元素放到右边。通常我们选择第一个元素或最后一个元素作为pivot，这里我们选择第一个元素为pivot。

我们设立两个指针l,r。我们先来讨论区间为[1,n]的情况，然后递归求解每个子区间即可。
令l=1,r=n,因为我们整个过程需要始终保证l < r并且不断滚动l,r指针直到l和r重合,我们结束，找到了下一个pivot的位置。

因为我们选取第一个元素为pivot,所以我们需要先从r指针开始。当a[r]>=pivot,r--;直到找到一个小于pivot的元素，并将a[r]赋值给a[l]。同理，当a[l]<=pivot,l++；直到找到一个大于pivot的元素,并将a[l]赋值给a[r]。
重复整个过程,直到l=r时，我们再将pivot赋值给a[l]，并返回l作为当前的分界点。

然后我们只需要递归求解上述过程，分别递归求解左右两个子区间，也就是quickSort(l,pivot-1), quickSort(pivot+1,r);即可得到最终的排序结果。

附代码：

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
using namespace std;
int n;
int a[10005];
int partition(int l,int r) {
    int pivot=a[l];
    while(l<r) {
        while(l<r&&a[r]>=pivot) {
            r--;
        }
        a[l]=a[r];
        while(l<r&&a[l]<=pivot) {
            l++;
        }
        a[r]=a[l];
    }
    a[l]=pivot;
    return l;
}
void quickSort(int l,int r) {
    if(l<r) {
        int pivot=partition(l,r);
        quickSort(l,pivot-1);
        quickSort(pivot+1,r);
    }
}
int main() {
    scanf("%d",&n);
    for(int i=1; i<=n; i++) {
        scanf("%d",&a[i]);
    }
    quickSort(1,n);
    for(int i=1; i<=n; i++)
        printf("%d ",a[i]);
    printf("\n");
    return 0;
}