数据结构之浅析快速排序

àì夳堔傛蜴生んèń 2022-09-28 13:03 173阅读 0赞

# 快速排序 #

*  **定义**
 *  **实现**
 *  **复杂度分析**

## 1、定义 ##

> 快速排序主要是采用分而治之的思想，通过一趟排序将待排序列分割成独立的两大部分，其中一部分序列比另一部分序列都小，然后可以对这两部分序列继续进行分割排序，以达到最终的目的。

快速排序的大体过程：

1、对于输入序列\{ 50，10, 90, 30, 70, 40, 80, 60, 20\}，经过一轮的分割后

2、得到下面的序列\{ 20，10, 40, 30, 50, 70, 80, 60, 90\}，该序列以50为分割点，会得到两个子序列（左边子序列比右边小）

3、\{ 20，10, 40, 30\}、\{70, 80, 60, 90\}，然后再进行上述循环

4、最终得到有序的序列

## 2、实现 ##

void QSort(SqList *L, int low, int high)
    {
        int pivot;
        if (low < high)
        {
            //将原序列分割
            pivot = Partition(L, low, high);
    
            QSort(L, low, pivot - 1); //递归调用，实现左子序列有序
            QSort(L, pivot + 1, high); //递归调用，实现右子序列有序
        }
    
    }

上述程序中，Partition函数的作用主要是为了选取序列中的一个关键字，比如第一小节中的序列关键字为50，然后想办法将它左边序列的值都小于50，右边序列的值都大于50。

如下程序时Partition函数的实现过程：

int Partition(SqList *L, int low, int high)
    {
        int pivotkey;
        pivotkey = L->r[row];
        while (low < high)
        {
            //比关键字大时，标签向中间靠拢
            while (low < high && L->r[high] >= pivotkey)
                high--;
            swap(L, low, high); //交换的目的是，使右序列都大于等于关键字
    
            //比关键字小时，标签向中间靠拢
            while (low < high && L->r[row] <= pivotkey)
                low++;
            swap(L, low, high); //交换的目的是，使左序列都小于等于关键字
        }
        return row;
    }

1、如下图所示，这里的关键字是取得序列的第一个元素（没有经过优化，很大程度上会影响性能），然后定义左右两个标签。

![这里写图片描述][SouthEast]

3、对标签进行移动，若右标签上对应得值大于关键字，则不进行值交换，标签继续往中间靠拢，直到遇到比关键字小的值；若左标签上对应得值小于关键字，则不进行值交换，标签继续往中间靠拢，直到遇到比关键字大的值；

![这里写图片描述][SouthEast 1]

4、如此循环，就最终形成序列的左半部分小于关键字，右半部分大于关键字的序列。

![这里写图片描述][SouthEast 2]

> 主要：关键字的选择很重要，若恰好选取的是序列中的最小值或者最大值，对于本次循环没有任何效果。

## 3、复杂度分析 ##

1、时间复杂度：

> 在最优的情况下（即选取的关键字恰好是中间），快速排序的时间复杂度为O（nlogn）；在最坏的情况下（序列正序或逆序），需要执行n-1次递归调用，对于第i次划分都需要经过n-i次关键字的比较才能得到最终关键字的位置，因此复杂度为O（n\*n）。平均复杂度为O（nlogn）。

2、空间复杂度：

> 在最优的情况下（即选取的关键字恰好是中间），由于递归树的深度为logn，快速排序的空间复杂度为O（logn）；在最坏的情况下（序列正序或逆序），需要执行n-1次递归调用，复杂度为O（n）。平均复杂度为O（logn）。

[SouthEast]: /images/20220708/1dc7868bd0134690900d08e30ff21c07.png
[SouthEast 1]: /images/20220708/548a3b0774a9420a92e8f0306464fbe7.png
[SouthEast 2]: /images/20220708/7dd1128431e04d69826a53fb3a24dd42.png