排序算法——快速排序

2023-12-13 11:32:34

快速排序是计算机科学中最著名和广泛使用的排序算法之一。自1960年由英国计算机科学家托尼·霍尔(Tony Hoare)发明以来,它以其高效率和简洁的实现而闻名。在本文中,我们将深入探讨快速排序的工作原理、其优缺点,并提供一个用C++编写的实现示例。

工作原理

快速排序是一种“分而治之”的算法。它的核心思想是选取一个元素作为“基准”(pivot),然后将数组分为两部分,使得左边的元素都比基准小,右边的元素都比基准大。这个过程称为“分区”(partitioning)。之后,算法递归地在左右两个子数组上重复这个过程,直到整个数组排序完成。

分区操作

分区是快速排序中最关键的步骤。选择一个元素作为基准值,然后对数组进行重排,使得所有小于基准值的元素都在其左侧,所有大于基准值的元素都在其右侧。基准值在这个过程中会被放置在其最终位置上。

递归排序

一旦完成分区操作,基准值就位于其最终位置。这时,可以递归地对基准值左侧和右侧的子数组执行相同的操作,直到子数组的大小缩减到1或0,这时数组就被认为是排序完成的。

实现示例(C++)

下面是一个用C++编写的快速排序的简单实现。这个实现使用了“Lomuto分区方案”,其中基准值选为子数组的最后一个元素。

#include <iostream>
#include <vector>

using namespace std;

void quickSort(vector<int>& arr, int low, int high) {
    if (low < high) {
        int pivot = arr[high];
        int i = low;

        for (int j = low; j < high; j++) {
            if (arr[j] < pivot) {
                swap(arr[i], arr[j]);
                i++;
            }
        }
        swap(arr[i], arr[high]);

        quickSort(arr, low, i - 1);
        quickSort(arr, i + 1, high);
    }
}

int main() {
    vector<int> arr = {10, 7, 8, 9, 1, 5};
    quickSort(arr, 0, arr.size() - 1);

    for (int num : arr) {
        cout << num << " ";
    }
    return 0;
}

优缺点

优点

  1. 效率:在平均情况下,快速排序的时间复杂度为O(n log n),这使得它在多数情况下非常高效。
  2. 就地排序:快速排序不需要额外的存储空间,它是一种就地排序算法。
  3. 适应性:对于大型数据集,快速排序通常比其他O(n log n)复杂度的排序算法表现得更好。

缺点

  1. 最坏情况性能:在最坏情况下(如输入数组已排序或反向排序),快速排序的时间复杂度降至O(n^2)。
  2. 不稳定:快速排序不是一个稳定的排序算法,这意味着相等元素的初始顺序可能在排序后被改变。

文章来源:https://blog.csdn.net/bairui6666/article/details/134893975
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。