排序算法——快速排序

快速排序是计算机科学中最著名和广泛使用的排序算法之一。自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. 不稳定:快速排序不是一个稳定的排序算法,这意味着相等元素的初始顺序可能在排序后被改变。

相关推荐

  1. 排序算法——快速排序

    2023-12-10 10:32:02       40 阅读
  2. 排序算法——快速排序

    2023-12-10 10:32:02       39 阅读
  3. 排序算法-快速排序

    2023-12-10 10:32:02       43 阅读
  4. 排序算法——快速排序

    2023-12-10 10:32:02       14 阅读

最近更新

  1. TCP协议是安全的吗?

    2023-12-10 10:32:02       16 阅读
  2. 阿里云服务器执行yum,一直下载docker-ce-stable失败

    2023-12-10 10:32:02       16 阅读
  3. 【Python教程】压缩PDF文件大小

    2023-12-10 10:32:02       15 阅读
  4. 通过文章id递归查询所有评论(xml)

    2023-12-10 10:32:02       18 阅读

热门阅读

  1. 在uniapp中,可以使用那些预定义的样式类

    2023-12-10 10:32:02       28 阅读
  2. 1-5、JDK API文档

    2023-12-10 10:32:02       38 阅读
  3. 从零开始搭建链上dex自动化价差套利程序(11)

    2023-12-10 10:32:02       35 阅读
  4. 【力扣100】最大子数组和

    2023-12-10 10:32:02       38 阅读
  5. 数据结构之散列查找

    2023-12-10 10:32:02       29 阅读
  6. 5G常用简称

    2023-12-10 10:32:02       31 阅读
  7. 中国移动频段划分

    2023-12-10 10:32:02       72 阅读
  8. SpringMVC-注解版本

    2023-12-10 10:32:02       36 阅读
  9. tensorflow中张量tensor

    2023-12-10 10:32:02       44 阅读
  10. PHP基础 - 数据类型

    2023-12-10 10:32:02       46 阅读