快速排序算法

快速排序算法是一种交换排序，基于冒泡排序的采用了二分思想的优化。
最坏情况将会退化为冒泡排序（这取决于基准字选取的方法）。

排序思想：

1. 将元素划分为以基准字为中心的两块，一块小于它一块大于它（每次划分结束，基准字都会放到最终位置上）
2. 继续对以基准字切分出来的两块进行划分-重复1（不包括基准值）
3. 当左右两块都只有一个或者0个元素时，退出。排序完成。

时间: O(nlog₂n), 最坏情况下O(n^2)
空间:递归栈的深度O(log₂n)。最坏情况深度为n，空间为O(n)
稳定性: 不稳定，排序后相同大小元素可能交换位置。

/*
快速排序
*/
#include<stdio.h>
#include<stdlib.h>
#define ElemType int
#define MAX_SIZE 1000
typedef struct List{
    ElemType data[MAX_SIZE];
    int length;
}ArrayList;

// 划分 - 将区间划分为左右两个部分，左边比右边 （大 or 小）
int _Sort(ArrayList& list, int low, int hight){
    ElemType k = list.data[low]; // 选定low的位置为基准字，也充当了哨兵保存了k的值，也就空出了一个位置用于交换
    while(low < hight){
        // 注意要判断 low < hight
        while(low < hight && list.data[hight] >= k) hight--;
        list.data[low] = list.data[hight];// 将找到小于k的元素放到low 那边
        // （不用担心会覆盖low上的值， 第一次覆盖k（但已经记录为基准字），且覆盖后，hight的位置相当于（空位 保证了low覆盖到hight的成立）
        while(low < hight && list.data[low] <= k) low++;
        list.data[hight] = list.data[low];// 将找到大于k的元素放到hight那边
        // 不用担心覆盖hight的值，hight已经复制到low上（low移动前）
    }
    list.data[low] = k; // 将基准元素放到最终位置上, 此时low == hight
    return low;// 返回基准元素位置，基准元素已经放到最终位置上（有序后的最终位置）
}
// 快速排序
void QuickSort(ArrayList& list, int low, int hight){
    if(low < hight){
        // 划分
        int pivotPos = _Sort(list, low, hight);
        // 对两边进行划分
        QuickSort(list, low, pivotPos - 1);
        QuickSort(list, pivotPos + 1, hight);
    }
}
// 插入到数组尾部
void InsertTail(ArrayList& list, ElemType data){
    if(list.length >= MAX_SIZE) return;
    list.data[++list.length] = data;
}
void Show(ArrayList list){
    for(int i = 1; i <= list.length; i++)
        printf("%d,", list.data[i]);
    printf("\n");
}


int main(){

    ArrayList list;
    list.length = 0;

    // 插入一组无序数列
    for(int i = 1; i <= 33; i++){
        InsertTail(list, i * 17 % 31);
    }
    Show(list);
    QuickSort(list, 1, list.length);
    Show(list);

    return 0;
}