20-考研-数据结构-快速排序

上一节我们写了关于冒泡排序的内容，但是在算法执行效率上却牺牲了太多，时间复杂度达到了N^2,相比较桶排序浪费空间相比，有没有一个既不浪费时间又不浪费空间的算法呢，那就是快排了。

算法思想：

从一个序列中找一个基准数，用来参照（一般选第一个数字），接下来需要将这个序列中所有比基准数大的数字放在基准的右侧，所有比基准小的数字放在基准的左侧。

分别从两端开始探测，先右后左，相遇说明此时探测结束

基本图示：

举个粒子：

初始序列：6 1 2 7 9 3 4 5 10 8

从两端探测，以第一个数字6位基准，先从右侧开始找到一个比6小的数字（哨兵j），再从左边往侧找到一个比6大的数字（哨兵i），并且交换他们，j一步一步往左挪动（j--），直到找到一个小于6的数字5停下来，接下来i从左往右挪动（i++），直到找到一个大于6的数字7停止，交换i和j两个哨兵所指向的元素，序列为 6 1 2 5 9 3 4 7 10 8  ，第一次交换结束，j继续向左边挪动（每次都必须是j先移动），走到了4的位置，i向右挪动走到了9的位置，交换两个数字，此时的序列为 6 1 2 5 4 3 9 7 10 8  ，第二次交换结束了。j继续向左移动，到了3的位置，停止移动，i继续向右侧移动，此时i和j相遇在3所在的位置，说明此时的探测结束了，我们最后需要将基准6和3进行交换，此时序列为

3 1 2 5 4 6 9 7 10 8 ，第一轮探测结束。  现在基准6已经归位了，6左侧的都比6小，右侧都比6大。

我们将原来的序列以6为分界，分成两个序列，左侧 3 1 2 5 4  右侧  9 7 10 8  接下来分别处理这连个序列，左侧以3为基准。。。。。。。。。。。。。。。。（人的本质是什么？当然是重复啊！）

分析时间复杂度：

快排之所以快，是因为相比冒泡，他的每次交换都是跳跃式的，总的比较和交换次数少了，速度自然就提高了。当然在最坏的情况下仍可能是相邻的两个数字进行比较和交换。因此快排的最差时间复杂度和冒泡是一样的O(N^2),平均复杂度为O(NlogN),其实是基于二分的思想。

时间复杂度数学证明：https://blog.****.net/huanting74/article/details/79794728

代码演示：

10

10 6 1 2 7 9 3 4 5 10 8

#include<stdio.h>
#include<iostream>
using namespace std;
#define maxSize 100
//定义全局变量数组，在子函数中会用到
int a[maxSize],n;

//快速排序函数
void quickSort(int left,int right){
    if(left>right){
        return;
    }
    int temp=a[left];
    int i=left;
    int j=right;
    while(i!=j){
        //顺序很重要，需要先从右边往左边找
        while(a[j]>=temp&&i<j){
            j--;
        }
        while(a[i]<=temp&&i<j){
            i++;
        }
        //交换两个数字的位置
        if(i<j){//当没有相遇时候
            int t=a[i];
            a[i]=a[j];
            a[j]=t;
        }
    }
    //最终将基准归位
    a[left]=a[i];
    a[i]=temp;
    quickSort(left,i-1);//继续处理左侧
    quickSort(i+1,right);//继续处理右侧
}

int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d",&a[i]);
    }
    quickSort(0,n-1);//调用快速排序函数

    //输出快排之后的结果
    for(int i=0;i<n;i++){
        printf("%d ",a[i]);
    }
    return 0;
}

代码结果展示；