快速排序

1.快速排序

注：经典快速排序总是指定数组的最后一个元素作为基准值，随机快速排序指定数组或者某一部分中的随机值作为基准值。

（1）主要思想

快速排序的主要思想是分治思想：

任取一个元素作为分界点pivot
对数组区间进行调整（调整方式有很多种），所有比pivot小的元素都放在前面，比pivot大的元素都放在后面，形成左右两个子表
递归处理左右两端区间

（2）局限性

快速排序局限性：

快速排序是所有内部排序方法中最好的一个
快速排序是一种不稳定的排序方法
快速排序不是原地排序（程序中使用了递归需要递归调用栈的支持，而栈的长度取决于递归调用的深度）
平均时间复杂度O(nlog₂n)：QSort—O(log₂n)、Partition—O(n)
平均情况下需要使用O(logn)的栈空间，最坏情况下栈空间可以达到O(n)
快速排序不适用与对原本有序或基本有序的记录序列进行排序（划分元素值的随机性越好，排序速度越快，即非自然排序）
改变划分元素的选取方法，最多只能改变算法平均时间性能，无法改变最坏情况下的时间性能O(n²)
由于每次枢轴pivot记录的关键字都是大于其他所有记录的关键字，致使一次划分之后得到的子序列（1）的长度为0，这时的快速排序就已经退化成为了没有改进措施的冒泡排序了。

2.快速排序模板

（1）思路1：

将low值取出单独存放在key中，
对数组进行排序，排序方式为：当右侧比key小时将high覆盖low处值、当左侧比key大时将low覆盖high处
直到low与high相遇时，将key放回low与high相遇的位置
一轮排序完毕（key所在位置为最终有序位置）
递归处理左右两边区间

//写法1:使用2个变量 low high
int partition(int arr[], int low, int high) {
    int key = arr[low];//取low处元素的值作为比较参考
    while(low < high) {\]
        while(low < high && arr[high] >= key) --high;//右侧比key元素大的元素结点不动
        arr[low] = arr[high];//将比key元素小的结点搬到low位置
        while(low < high && arr[low] <= key) ++low;//左侧比key元素小的元素结点不动
        arr[high] = arr[low];//将比key元素大的结点搬到high位置
    }
    arr[low] = key;//low = high = pivot
    return low;
}

void quick_sort(int arr[], int low, int high) {//快速排序调用并指明排序下标范围(low ~ high)
    if (low < high) {//排序区间长度大于1则继续递归,否则退出递归
        int pivot = partition(arr, low, high);
        quick_sort(arr, low, pivot - 1);
        quick_sort(arr, pivot + 1, high);
    }
}

（4）思路2：

在low与hight的基础上再定义两个指针i、j，两个指针分别向中间移动
当 i 指针指向的数字小于pivot时，i 指针继续向右移动，直到 i 大于等于pivot时停下
当 j 指针指向的数字大于pivot时，j 指针继续向左移动，直到 j 小于等于pivot时停下
当 i、 j指针都停下时，若 i、j处于正常位置则交换对应值
否则表示while循环结束
递归处理左右两边区间

//写法2:使用4个变量 low high i j
void quick_sort(int arr[], int low, int high) {
    if (low >= high) return;
    //1.确定分界点
    int key = arr[low];
    int j = high + 1, i = low - 1;
    //2.调整左右两边区间
    while (i < j) {
        do ++i; while(arr[i] < key);
        do --j; while(arr[j] > key);
        if (i < j) swap(arr[i], arr[j]);
    }
    //3.递归处理左右两边区间
    quick_sort(arr, low, j);
    quick_sort(arr, j + 1, high);
}