lwz blog

# 快速排序

基于交换排序，根据序列中两个元素关键字的对比结果来对换这两个记录在序列中的位置，从而达到排序的目的。

快速排序是所有内部排序中平均性能最优的排序算法

# 基本思想

在待排序表中任取一个元素 pivot 作为枢轴(通常是取首元素)，通过一趟排序将待排序列表划分为两个部分，其中一部分的所有元素均比枢轴小，另一部分的所有元素均比枢轴大，此时枢轴在其排好序后的正确位置，然后再用同样的方法递归地排序划分出的两个部分。直至每部分内只有一个元素或空为止，即所有元素排好序。


int arr = {4,1,2,5,7,4,8,6,3,5};

//声明变量 low=4 high=5 pivot=9
//第一轮排序 比pivot小的放在左边 比pivot大的放在右边
//得到排序的结果 {4,1,2,5,4,3,5,6,7,8}
//此时pivot的位置为5

//递归的处理上述的逻辑分为 左边的序列和右边的序列，也就是下标为0到3的序列和下标为5到9的序列。分别走上述的逻辑，直到序列中只有一个元素或者没有元素为止。

//代码实现

int partition(int *arr, int low, int high) {
  //取第一个元素为枢轴
    int p = arr[low];
    //当low<high的时候 证明序列中还有元素
    while (high > low) {
      //子循环处理右边的序列都要比枢轴大，不断向左移动high
        while (arr[high] >= p && high > low)
            high--;
      //子循环处理完后，将比枢轴小的元素放到左边 也就是当前的low位置
        arr[low] = arr[high];
      //子循环处理左边的序列都要比枢轴小，不断向右移动low
        while (arr[low] <= p && high > low)
            low++;
      //子循环处理完后，将比枢轴大的元素放到右边 也就是当前的high位置
        arr[high] = arr[low];
    }
    //当low=high 或者 high<low的时候 证明序列中没有元素了，将枢轴放到当前的low位置
    arr[low] = p;
    //返回枢轴的位置 方便下次递归
    return low;

}

void quickSort(int *arr, int low, int high) {
  //递归结束的条件 high<=low的话 也就是 没有元素或者只有一个元素，证明已经排序完成。
    if (low < high) {
        //得到枢轴的位置
        int pivot = partition(arr, low, high);
        //处理左边的序列
        quickSort(arr, low, pivot - 1);
        //处理右边的序列
        quickSort(arr, pivot + 1, high);
    }
}

# 算法分析

# 空间复杂度

取决于递归的深度，最好情况下为 O(logn) ，最坏情况下为 O(n) 。个人认为：类似于二叉树的深度 (log2(n+1)) ，最好的情况为完全二叉树，最坏的情况为只有左子树或者只有右子树 O(n) 。

  • 最好的情况下，每次都能将序列均匀的分为两个部分。这样就是完整的二叉树，递归的深度为 log2(n+1) 。
  • 最坏的情况下，待排序的序列已经是有序的了，每次都只能将序列分为一个元素和剩下的元素。这样就是只有左子树或者只有右子树，递归的深度为 n 。

# 时间复杂度

O(n*递归的深度)

  • 最好的时间复杂度=O(nlogn)
  • 最坏的时间复杂度=O(n^2)

最好和最坏的时间复杂度和空间复杂度是相对应的。也就是越有序，时间复杂度和空间复杂度越高。

# 稳定性

不稳定


2(1)   2(2)      1
low           high
// 排序后
1      2(2)    2(1)

# 其他

快速排序是所有内部排序中平均性能最优的排序算法，但是在最坏的情况下，时间复杂度为 O(n^2) ，所以需要对其进行优化。

  • 选择头、中、尾三个元素的中位数作为枢轴，这样可以避免最坏情况的发生。
  • 随机选择一个元素作为枢轴，这样可以避免最坏情况的发生。

← 简单排序 →