【算法系列 | 5】深入解析排序算法之——快速排序

浅浅的花香味﹌ 2023-10-12 13:41 39阅读 0赞

#  #

![ed32705022624cba8751a8424bb8272b.png][]

# 序言 #

> 你只管努力，其他交给时间，时间会证明一切。

> 文章标记颜色说明：
> 
>  *  黄色：重要标题
>  *  红色：用来标记结论
>  *  绿色：用来标记一级论点
>  *  蓝色：用来标记二级论点

> 决定开一个算法专栏，希望能帮助大家很好的了解算法。主要深入解析每个算法，从概念到示例。
> 
> 我们一起努力，成为更好的自己！
> 
> 今天第5讲，讲一下排序算法的快速排序（Quick Sort）

# 1 基础介绍 #

> 排序算法是很常见的一类问题，主要是将一组数据按照某种规则进行排序。
> 
> 以下是一些常见的排序算法：
> 
> 1.  冒泡排序（Bubble Sort）
> 2.  插入排序（Insertion Sort）
> 3.  选择排序（Selection Sort）
> 4.  归并排序（Merge Sort）
> 5.  快速排序（Quick Sort）
> 6.  堆排序（Heap Sort）

# 一、快速排序介绍 #

## 1.1 原理介绍 ##

![e8bbe6fc1cf44c74942d8441944eef9f.png][]

> 快速排序（Quick Sort）是一种常用的排序算法，也是一种基于分治思想的排序算法。
> 
> 快速排序的基本思想是选取一个基准元素，将数组分成两部分，使得左边部分的元素都小于等于基准元素，右边部分的元素都大于等于基准元素，然后对左右两部分分别递归进行排序，最终得到一个有序数组。

> 下面来详细介绍一下快速排序的原理和实现过程：
> 
> 1.  选择基准元素
>     
>     快速排序的第一步是选择一个基准元素，一般情况下是选择数组的第一个元素或最后一个元素作为基准元素。选择基准元素的目的是将数组划分成两个部分，使得左边部分的元素都小于等于基准元素，右边部分的元素都大于等于基准元素。
> 2.  划分数组
>     
>     在选择了基准元素之后，需要将数组划分成两部分。具体方法是使用两个指针 i 和 j 分别从数组的左右两端开始扫描，当 i 指向的元素大于等于基准元素时，停止移动，当 j 指向的元素小于等于基准元素时，停止移动，然后交换 i 和 j 指向的元素，继续移动指针。当 i 和 j 相遇时，将基准元素与 i 指向的元素交换位置，这样就完成了一次划分。
> 3.  递归排序
>     
>     划分数组之后，将左右两部分分别递归进行排序，直到每个部分只剩下一个元素或空数组为止。递归排序的过程中，需要重复执行以上两个步骤，即选择基准元素和划分数组。
> 4.  合并数组
>     
>     在递归排序完成之后，需要将左右两部分合并成一个有序数组。由于左右两部分都已经有序，可以使用归并排序的思想来合并数组。

### 示例讲解 ###

> 下面举一个例子来说明快速排序的过程：
> 
> 1.  原数组：`[3, 5, 1, 9, 7, 2, 8, 4, 6]`
> 2.  选择基准元素 3，分成左半部分 `[1, 2]` 和右半部分 `[5, 9, 7, 8, 4, 6]`
> 3.  对左半部分 `[1, 2]` 递归调用快速排序算法，得到有序数组 `[1, 2]`
> 4.  对右半部分 `[5, 9, 7, 8, 4, 6]` 选择基准元素 5，分成左半部分 `[4]` 和右半部分 `[9, 7, 8, 6]`
> 5.  对左半部分 `[4]` 递归调用快速排序算法，得到有序数组 `[4]`
> 6.  对右半部分 `[9, 7, 8, 6]` 选择基准元素 9，分成左半部分 `[7, 8, 6]` 和右半部分 `[]`
> 7.  对左半部分 `[7, 8, 6]` 选择基准元素 7，分成左半部分 `[6]` 和右半部分 `[8]`
> 8.  对左半部分 `[6]` 递归调用快速排序算法，得到有序数组 `[6]`
> 9.  对右半部分 `[8]` 递归调用快速排序算法，得到有序数组 `[8]`
> 10. 将左半部分 `[6]`、基准元素 7 和右半部分 `[8]` 拼接起来，得到有序数组 `[6, 7, 8]`
> 11. 将左半部分 `[4]`、基准元素 5 和右半部分 `[6, 7, 8, 9]` 拼接起来，得到有序数组 `[4, 5, 6, 7, 8, 9]`
> 12. 将左半部分 `[1, 2]`、基准元素 3 和右半部分 `[4, 5, 6, 7, 8, 9]` 拼接起来，得到有序数组 `[1, 2, 3, 4, 5, 6, 7, 8, 9]`

## 1.2 复杂度 ##

> **时间复杂度：**
> 
> 快速排序的平均时间复杂度为 O(nlogn)，其中 n 表示要排序的数组的长度。
> 
> 在最坏情况下，即每次选择的基准元素都是当前数组中最小或最大的元素，递归树的深度将达到 n，此时的时间复杂度为 O(n^2)。
> 
> 但是，快速排序的平均时间复杂度远远优于最坏情况下的时间复杂度。
> 
> 快速排序的优势在于它是一种原地排序算法，即不需要额外的存储空间，只需要通过交换数组中的元素来实现排序。这使得快速排序在实际应用中表现出色，被广泛使用。

> **空间复杂度：**
> 
> 快速排序的空间复杂度为 O(logn) 至 O(n)，其中 n 表示要排序的数组的长度。
> 
> 在递归调用快速排序算法时，需要使用递归栈来保存每一层递归的状态。
> 
> 在最坏情况下，即每次选择的基准元素都是当前数组中最小或最大的元素，递归树的深度将达到 n，此时的空间复杂度为 O(n)。
> 
> 但是，在平均情况下，递归树的深度通常为 O(logn)，因此空间复杂度为 O(logn)。
> 
> 另外，快速排序是一种原地排序算法，即不需要额外的存储空间，只需要通过交换数组中的元素来实现排序。因此，快速排序的空间复杂度在最优情况下为 O(1)。

## 1.3使用场景 ##

> 快速排序是一种高效的排序算法，在实际应用中被广泛使用。以下是一些快速排序的应用场景：
> 
> 1.  排序大规模数据：快速排序的时间复杂度为 O(nlogn)，比其他常见的排序算法如冒泡排序、选择排序和插入排序等更快，因此适用于需要处理大规模数据的场景。
> 2.  搜索数据：快速排序可以对数据进行排序，使得搜索数据时可以更快速地定位到目标数据，因此适用于需要频繁搜索数据的场景。
> 3.  数据压缩：快速排序可以将相似的数据放在一起，从而提高数据的压缩率，因此适用于需要进行数据压缩的场景。
> 4.  数据库查询：快速排序可以对数据库中的数据进行排序，从而提高查询效率，适用于需要频繁查询数据库的场景。
> 5.  数组去重：快速排序可以将数组中相同的元素放在一起，从而方便去重操作，适用于需要进行数组去重的场景。

> 需要注意的是，在实际应用中，需要根据具体情况来选择合适的排序算法。
> 
> 虽然快速排序的时间复杂度较低，但是在最坏情况下会出现时间复杂度为 O(n^2) 的情况，因此需要采用一些优化措施来避免最坏情况的出现。

## 1.4 优缺点 ##

### 优点： ###

> 快速排序是一种高效的排序算法，具有以下优点：
> 
> 1.  时间复杂度低：快速排序的平均时间复杂度为 O(nlogn)，比其他常见的排序算法如冒泡排序、选择排序和插入排序等更快。
> 2.  原地排序：快速排序是一种原地排序算法，即不需要额外的存储空间，只需要通过交换数组中的元素来实现排序。
> 3.  分治思想：快速排序采用分治思想，将问题分解为若干个子问题进行求解，从而简化了问题的复杂度。
> 4.  可以进行原地去重操作：快速排序可以将数组中相同的元素放在一起，从而方便去重操作。

### 缺点： ###

> 但是，快速排序也存在一些缺点：
> 
> 1.  最坏情况下的时间复杂度较高：在最坏情况下，即每次选择的基准元素都是当前数组中最小或最大的元素，递归树的深度将达到 n，此时的时间复杂度为 O(n^2)。
> 2.  对于小规模数据排序效率低：当要排序的数据规模较小的时候，快速排序的效率不如其他简单的排序算法，如插入排序和冒泡排序等。
> 3.  选择基准元素的难度：选择基准元素的方式会影响快速排序的性能，如果每次选择的基准元素都是当前数组中的最小或最大元素，将会导致快速排序的性能退化。
> 4.  不稳定性：快速排序是一种不稳定的排序算法，即在排序过程中相同的元素可能会被交换位置，从而导致相同元素的相对位置发生变化。

> 需要根据具体情况来选择合适的排序算法，对于快速排序的缺点，可以通过一些优化措施来避免或缓解。

# 二、代码实现 #

![3d6c55354279433e8f25719418312a48.png][]

## 2.1 Python 实现 ##

> 下面是 Python 代码实现快速排序算法，并提供测试代码，对代码进行详细讲解：

def quick_sort(arr):
        """
        快速排序算法的实现函数
    
        Parameters:
            arr (list): 要排序的数组
    
        Returns:
            list: 排序后的数组
        """
        # 如果数组长度小于等于1，则直接返回
        if len(arr) <= 1:
            return arr
    
        # 选择基准元素
        pivot = arr[0]
    
        # 分割数组
        left = [x for x in arr[1:] if x <= pivot]
        right = [x for x in arr[1:] if x > pivot]
    
        # 递归调用快速排序算法，并将分割后的数组合并起来
        return quick_sort(left) + [pivot] + quick_sort(right)

> 以上是基本的快速排序算法的实现。

### 测试 ###

> 接下来提供一个测试代码，测试快速排序算法的正确性：

import random
    
    # 生成随机数组
    arr = [random.randint(0, 100) for _ in range(10)]
    print("原始数组:", arr)
    
    # 对数组进行快速排序
    arr_sorted = quick_sort(arr)
    print("排序后数组:", arr_sorted)
    
    # 验证排序结果是否正确
    assert arr_sorted == sorted(arr), "排序结果不正确"
    print("排序结果正确")

> 测试代码中，首先生成一个包含 10 个随机整数的数组 `arr`，然后调用 `quick_sort` 函数对数组进行排序，并将排序后的数组存储在变量 `arr_sorted` 中。
> 
> 接着，使用 Python 内置的 `sorted` 函数对原数组进行排序，将排序后的结果存储在变量 `sorted_arr` 中，并使用断言来验证快速排序的结果是否正确。如果排序结果正确，则输出 "排序结果正确"，否则输出错误信息。

> 在测试代码中，我使用了 Python 内置的 `sorted` 函数来验证快速排序的结果是否正确，这是因为 `sorted` 函数是一种稳定且正确的排序算法，在验证结果时可以作为参照。

## 2.2Java实现 ##

> 下面是快速排序的 Java 代码实现：

public class QuickSort {
        public static void main(String[] args) {
            int[] arr = {3, 5, 1, 9, 7, 2, 8, 4, 6};
            quickSort(arr, 0, arr.length - 1);
            System.out.println(Arrays.toString(arr)); // 输出 [1, 2, 3, 4, 5, 6, 7, 8, 9]
        }
    
        public static void quickSort(int[] arr, int left, int right) {
            if (left >= right) {
                return;
            }
    
            int pivot = partition(arr, left, right);
            quickSort(arr, left, pivot - 1);
            quickSort(arr, pivot + 1, right);
        }
    
        public static int partition(int[] arr, int left, int right) {
            int pivot = arr[left];
            int i = left, j = right;
    
            while (i < j) {
                while (i < j && arr[j] >= pivot) {
                    j--;
                }
                if (i < j) {
                    arr[i++] = arr[j];
                }
    
                while (i < j && arr[i] <= pivot) {
                    i++;
                }
                if (i < j) {
                    arr[j--] = arr[i];
                }
            }
    
            arr[i] = pivot;
    
            return i;
        }
    }

> 这个实现使用了两个函数，一个是 `quickSort()` 函数，用于进行递归调用，另一个是 `partition()` 函数，用于划分数组。下面对这两个函数进行详细讲解：

### `quickSort()` 函数 ###

public static void quickSort(int[] arr, int left, int right) {
        if (left >= right) {
            return;
        }
    
        int pivot = partition(arr, left, right);
        quickSort(arr, left, pivot - 1);
        quickSort(arr, pivot + 1, right);
    }

> 这个函数使用递归的方式对数组进行排序。对于输入的数组和左右下标，首先判断左下标是否大于等于右下标，如果是，则直接返回。
> 
> 否则，使用 \`partition()\` 函数将数组划分成两个部分，分别对左半部分和右半部分递归调用 \`quickSort()\` 函数。

### `partition()` 函数 ###

public static int partition(int[] arr, int left, int right) {
        int pivot = arr[left];
        int i = left, j = right;
    
        while (i < j) {
            while (i < j && arr[j] >= pivot) {
                j--;
            }
            if (i < j) {
                arr[i++] = arr[j];
            }
    
            while (i < j && arr[i] <= pivot) {
                i++;
            }
            if (i < j) {
                arr[j--] = arr[i];
            }
        }
    
        arr[i] = pivot;
    
        return i;
    }

> 这个函数用于划分数组。在函数内部，使用两个指针 i 和 j 分别从数组的左右两端开始扫描，
> 
> 1.  当 i 指向的元素大于等于基准元素时，停止移动，
> 2.  当 j 指向的元素小于等于基准元素时，停止移动，然后交换 i 和 j 指向的元素，继续移动指针。
> 3.  当 i 和 j 相遇时，将基准元素与 i 指向的元素交换位置，这样就完成了一次划分。
> 4.  最后，将基准元素移动到正确的位置，并返回基准元素的下标。

> 需要注意的是，在划分数组时，要先从右边开始扫描，否则可能会导致数组越界的问题。
> 
> 此外，在移动指针时，需要判断 i 和 j 是否相遇，否则可能会导致死循环的问题。

> 今天就到这里了，下期见~

[ed32705022624cba8751a8424bb8272b.png]: https://img-blog.csdnimg.cn/ed32705022624cba8751a8424bb8272b.png
[e8bbe6fc1cf44c74942d8441944eef9f.png]: https://img-blog.csdnimg.cn/e8bbe6fc1cf44c74942d8441944eef9f.png
[3d6c55354279433e8f25719418312a48.png]: https://img-blog.csdnimg.cn/3d6c55354279433e8f25719418312a48.png