Skip to content

Latest commit

 

History

History
143 lines (114 loc) · 6.01 KB

28 快速排序.md

File metadata and controls

143 lines (114 loc) · 6.01 KB

#数据结构 #算法 #C

[86] 快速排序

快速排序（英语：Quicksort），又称分区交换排序（partition-exchange sort），交换排序的另一种。是一种排序算法，最早由东尼·霍尔提出。

1. 算法思想

快速排序使用分治法（Divide and conquer）策略来把一个序列（list）分为较小和较大的2个子序列，然后递归地排序两个子序列。 步骤为：

  • 挑选基准值：从数列中挑出一个元素，称为“基准”（pivot），
  • 分割：重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（与基准值相等的数可以到任何一边）。在这个分割结束之后，对基准值的排序就已经完成，
  • 递归排序子序列：递归地将小于基准值元素的子序列和大于基准值元素的子序列排序。
  • 递归到最底部的判断条件是数列的大小是零或一，此时该数列显然已经有序。

换种数学公式表达： 在待排序表 $L[1, … n]$ 中任取⼀个元素pivot作为枢轴（或基准，通常取⾸元素），通过⼀趟排序将待排序表划分为独立的两部分: $$L[1, … k - 1]$$ 和 $$L[k + 1, … n]$$ 使得:

  • $L[1,…k-1]$ 中的所有元素小于pivot，
  • $L[k+1,…n]$中的所有元素大于等于pivot，
    则pivot放在了其最终位置 $L(k)$ 上，这个过程称为⼀次“划分”。 然后分别递归地对两个⼦表重复上述过程，直⾄每部分内只有⼀个元素或空为止，即所有元素放在了其最终位置上。

2. 算法过程

以数组A{49,38,65,97,76,13,27,49}为例，以递归工作栈的方式来实现快速排序。 把最起初的数字array[0]的值49作为中枢，即基准。小于pivot的放于左侧，大于pivot的放于右侧。

第一轮排序完成，继续以pivot为中枢，对其他元素按照大小值，小于pivot的放于左侧，大于pivot的放于右侧。然后将pivot填入其中。 进入下一层递归：

左子表排序完成，退出递归。对右子表执行排序。

排序完成。

3. 算法实现

// 用第一个元素将待排序序列划分分为左右两个部分
int Partition(int array[], int low, int high)
{
    // 把第一个元素当作枢轴
    int pivot = array[low];

    // 用low、high搜索枢轴的最终位置，
    // 当low 与 high 相碰的时候和或者 low 溢出 high 的时候结束
    while (low < high)
    {
        // 比枢轴小的元素移动到左端
        while (low < high && array[high] >= pivot)
        {
            high--;
        }
        array[low] = array[high];
        
        // 比枢轴大的元素移动到右端
        while (low < high && array[low] <= pivot)
        {
            low++;
        }
        array[high] = array[low];
    }
    array[low] = pivot;
    return low;
}

// 快速排序
void QuickSort(int array[], int low, int high)
{
    if (low < high)
    {
        int pivot = Partition(array, low, high);
        QuickSort(array, low, pivot - 1);
        QuickSort(array, pivot + 1, high);
    }
}

每⼀层的QuickSort只需要处理剩余的待排序元素，时间复杂度不超过 $O(N)$ 。 再次，以数组A{49,38,65,97,76,13,27,49}为例，以递归方式，从代码角度演示： 初始状态，进入第34行代码：int pivot = Partition(array, low, high);,调用Partition函数。

当顺次移动low、high指针所对应的值与pivot比较，如果较小，放到low处，较大放到high处,再顺次移动指针。 当low与high指针重合，本轮排序结束，跳出循环，找到pivot的位次，代码进入第35行，继续调用QuickSort。

第二层调用，指针重合调用结束，进入第三层调用。

第三层调用，结束，左子表轮次排列完整。右子表的排列和左子表类似，会直至调用第四层，第四层结束才会返回。

4. 算法性能

把n个元素组织成⼆叉树，⼆叉树的层数就是递归调⽤的层数:

  • n个结点的⼆叉树最⼩⾼度 = $⌊log_2{n}⌋ + 1$ 。
  • 最⼤⾼度 = $n$

特殊情形下的快速排序

若每⼀次选中的“枢轴”将待排序序列划分为很不均匀的两个部分，则会导致递归深度增加，算法效率变低。 比如，初始序列有序或逆序，则快速排序的性能最差（因为每次选择的都是最靠边的元素）。

快速排序的优化

尽量选择可以把数据中分的枢轴元素,而不是从头开始。 例如：

  1. 选头、中、尾三个位置的元素，取中间值作为枢轴元素；
  2. 随机选⼀个元素作为枢轴元素。

综合对比

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

时间复杂度 = $O(N * 递归层数)$， 最好时间复杂度= $O(N\log_{2}{N})$ = $O(N^2)$ ，平均时间复杂度 = $O(N\log_{2}{N})$ 空间复杂度 = $O(递归层数)$， 最好空间复杂度= $O(\log_{2}{N})$ ，最坏时间复杂度 = $O(N)$ 。

稳定性

快速排序是不稳定的排序。