十种经典排序算法（动图演示）

0、算法概述

0.1 算法分类

十种常见排序算法可以分为两大类：

• 比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破 O(nlogn)，因此也称为非线性时间比较类排序。
• 非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。

0.2 算法复杂度

0.3 相关概念

• 稳定：如果 a 原本在 b 前面，而 a=b，排序之后 a 仍然在 b 的前面。
• 不稳定：如果 a 原本在 b 的前面，而 a=b，排序之后 a 可能会出现在 b 的后面。
• 时间复杂度：对排序数据的总的操作次数。反映当 n 变化时，操作次数呈现什么规律。
• 空间复杂度：是指算法在计算机内执行时所需存储空间的度量，它也是数据规模 n 的函数。

1、冒泡排序（Bubble Sort）

冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢”浮”到数列的顶端。

1.1 算法描述

• 比较相邻的元素。如果第一个比第二个大，就交换它们两个；
• 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
• 针对所有的元素重复以上的步骤，除了最后一个；
• 重复步骤 1~3，直到排序完成。

1.2 动图演示

1.3 代码实现

void BubbleSort::sort(std::vector<int>& arr) {
    bool swapped;
    for (size_t i = 0; i < arr.size(); ++i) {
        swapped = false;
        for (size_t j = 0; j < arr.size() - 1 - i; ++j) {
            if (arr[j] > arr[j + 1]) {
                std::swap(arr[j], arr[j + 1]);
                swapped = true;
            }
        }
        // 如果没有交换发生，说明数组已经排序好，可以提前退出
        if (!swapped) break;
    }
}

1.4 算法分析

2、插入排序（Insertion Sort）

插入排序（Insertion-Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

2.1 算法描述

• 每次将一个待排序的记录按其关键字大小插入到前面已经排好序的子序列中，直到全部的记录插入完成。

2.2 动图演示

2.2 代码实现

// 1.直接插入排序
void InsertionSort::sort(std::vector<int>& arr) {
    int len = arr.size();
    // 1.外层遍历
    for(int i=1;i<len;i++){ //第0位默认有序
        int temp = arr[i]; // 将当前值暂存
        int j = 0; // 寻找应放在当前已排序的前半部分那个位置
        while(j<i && temp>=arr[j]) j++;//2.比较
        for(int l=i;l>j;l--) {arr[l] = arr[l-1];} // 3.将后面的元素全部往后移
        arr[j] = temp; //最后将当前元素放在j位置上
    }

}
// 2.折半插入排序
void InsertionSort::sort(std::vector<int> &arr)
{
    int len = arr.size();
    // 1.外层遍历
    for (int i = 1; i < len; i++)
    {                      // 第0位默认有序
        int temp = arr[i]; // 将当前值暂存

        // 2.折半查找
        /* 需要high=mid-1;low=mid+1;   否则，将会在最后仅剩两项的时候，一直保持low<=high，而进入死循环*/
        int high = i,low = 0;
        while(low<=high){
            int mid = (high + low)/2; 
            if(arr[mid]>temp) high = mid-1; 
            else if(arr[mid]==temp) {
                low = mid;
                break;
            }
            else low = mid+1;
        }
        // 3.将后面的元素全部往后移
        for (int l = i; l > low; l--)arr[l] = arr[l - 1];
        arr[low] = temp; // 最后将当前元素放在j位置上
    }
}

2.4 算法分析

插入排序在实现上，通常采用 in-place 排序（即只需用到 O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

3、选择排序（Selection Sort）

选择排序(Selection-sort)是一种简单直观的排序算法。

3.1 算法描述

它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

3.2 动图演示

3.3 代码实现

// 选择排序(升序)
void SelectionSort::sort(std::vector<int>& arr) {
    /* 每一趟遍历选择最小的元素放到最前面 */
    for(int i=0;i<arr.size();i++){ // 外层循环
        int min = i; // 开始找本次的最小值
        for(int j=i;j<arr.size();j++)
            if(arr[j]<arr[min]) min = j; // 找到本次的最小值
        if(min!=i) swap(arr[i],arr[min]);  // 如果i就是最小值，则不需要进行交换
    }
}

3.4 算法分析

适用性：顺序表 | 链表

4、希尔排序（Shell Sort）

1959 年 Shell 发明，第一个突破 O(n2)的排序算法，是简单插入排序的改进版。它与插入排序的不同之处在于，它会优先比较距离较远的元素。

希尔排序又叫 缩小增量排序，“先追求表中元素部分有序，再逐渐逼近全局有序”。

4.1 算法描述

先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：

• 选择一个增量序列 t1，t2，…，tk，其中 ti>tj，tk=1；
• 按增量序列个数 k，对序列进行 k 趟排序；
• 每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

4.2 动图演示

4.3 代码实现

// 希尔排序
void ShellSort::sort(std::vector<int>& arr) {
    int i=0,j=0,len = arr.size();
    int d = len/2; 
   	// 步长初始设置为数组的一半
    while (d>=1) {
      //插入排序
        for (i=1; i<len; i++) { 
        // 第0位是默认有序
          int temp = arr[i];
          for (j=i-1; j>=0; j--) { 
          // 寻找当前元素i需要插入到有序列中的什么位置
            if(temp<arr[j]){
              arr[j+1]=arr[j]; 
              // 未匹配的位置循环依次往后移动
            }else break; 
            // 匹配到插入位置:j+1
          }
          // 在插入位置，将temp赋值
          arr[j+1] = temp;
        }
        d/=2; // 步长进行减小一半；直到为1
    }

4.4 算法分析

5、快速排序（Quick Sort）

快速排序(Quick Sort)使用分治法策略。
它的基本思想是：选择一个基准数，通过一趟排序将要排序的数据分割成独立的两部分；其中一部分的所有数据都比另外一部分的所有数据都要小。然后，再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

5.1 算法描述

快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：

• (1) 从数列中挑出一个基准值。
• (2) 将所有比基准值小的摆放在基准前面，所有比基准值大的摆在基准的后面(相同的数可以到任一边)；在这个分区退出之后，该基准就处于数列的中间位置。
• (3) 递归地把”基准值前面的子数列”和”基准值后面的子数列”进行排序。

5.2 动图演示

5.3 代码实现

// QuickSort.cpp
#include "QuickSort.h"

// 快速排序主函数
void QuickSort::sort(std::vector<int> &arr)
{
    // 递归调用快速排序函数，对整个数组进行排序
    quickSort(arr, 0, arr.size() - 1);
}

// 返回排序器的名称
std::string QuickSort::name() const
{
    return "QuickSort"; // 该排序算法的名称是QuickSort
}

// 快速排序的递归实现
void QuickSort::quickSort(std::vector<int> &arr, int low, int high)
{
    if (low < high)
    { // 递归终止条件：如果low >= high，表示区间内的元素已经排好序
        // 执行分区操作，并返回当前分区的基准元素索引
        int pivot = partition(arr, low, high);
        // 递归排序基准元素左侧子数组
        quickSort(arr, low, pivot - 1);
       // 递归排序基准元素右侧子数组
        quickSort(arr, pivot + 1, high);
    }
    // 如果low >= high，递归停止，因为数组已经排好序
}

// 快速排序的分区操作
// 功能：将数组分成两部分，并确保左边的元素都小于等于pivot，右边的元素都大于等于pivot
int QuickSort::partition(std::vector<int> &arr, int low, int high)
{
    int pivot = arr[low]; // 选择当前区间的第一个元素作为基准元素（pivot）
    // 开始分区操作
    while (low < high)
    {
        // 从右侧开始，找到一个小于pivot的元素
        while (arr[high] >= pivot && low < high)
            high--; // 向左移动high指针，直到找到一个比pivot小的元素,并且要满足low < high
        // 将这个小于pivot的元素放到左侧
        arr[low] = arr[high];
        // 从左侧开始，找到一个大于pivot的元素
        while (arr[low] <= pivot && low < high)
            low++; // 向右移动low指针，直到找到一个比pivot大的元素,并且要满足low < high
        // 将这个大于pivot的元素放到右侧
        arr[high] = arr[low];
    }
    // 结束分区操作，将pivot元素放到最终的位置（low == high）
    arr[low] = pivot; // 将pivot元素放到正确的位置（此时pivot两边的元素都已经排序）
    // 返回当前基准元素的最终位置
    return low;
}

5.4 算法分析

每一层的QuickSort只需要处理剩余的待排序元素，时间复杂度不超过$O(n)$

• 稳定性：不稳定
  • 1 2 2 ==> 1 2 2
• 一次划分 ≠ 一趟排序

优化：尽可能取的pivot能够正好将数据中分

1. 在头、中、尾元素中，取中间值
2. 随机选择一个元素作为pivot

6、堆排序（Heap Sort）

什么是堆（heap)

堆（heap)是一种满足特定条件的完全二叉树，主要分为两类：

• 小顶堆(min heap) 任意节点的值 ≤ 其子节点的值；
• 大顶堆(max heap) 任意节点的值 ≥ 其子节点的值；

堆作为完全二叉树的一个特列，有以下特性：

• 最底层的节点靠左填充，其他层的节点都被填满；
• 二叉树的根节点被称为堆顶，最底层靠右的节点称为堆底；
• 对于大顶堆（小顶堆），堆顶元素（根节点）的值是最大（最小）的；

【补充】完全二叉树的性质

1. 假设完全二叉树中有n个节点

   1. 最后一个非叶子节点 —— $ \lfloor n/2 \rfloor$
   2. 第一个叶子节点 ——$ \lfloor n/2 \rfloor+1 $

2. 假设 i 为其中的某一个非叶子节点：

   1. i的左孩子 —— $2i$
   2. i的右孩子 —— $2i+1$
   3. i的父节点 —— $\lfloor i/2 \rfloor$
   4. i所在的层数 —— $ \lfloor log_2(i) \rfloor +1$ 或 $\lceil log_2(i+1) \rceil$

3. 假设完全二叉树中有n个节点，i 为其中的某一个非叶子节点：

   1. 判断i是否有左孩子 —— $2i ≤n$?
   2. 判断i是否有左孩子 —— $2i+1≤n$?
   3. 判断i是否有分支节点 —— $i>\lfloor n/2 \rfloor$?

6.1 算法描述

6.2 动图演示

6.3 代码实现

// HeapSort.cpp
#include "HeapSort.h"

void HeapSort::sort(std::vector<int> &arr)
{
    int n = arr.size();

    // 构建初始的大顶堆
    buildMaxHeap(arr, n);

    // 取出堆顶元素，交换到最后一个位置，再调整堆
    for (int i = n - 1; i > 0; --i)
    {
        // 将堆顶元素和堆底元素进行交换
        swap(arr[0], arr[i]);
        // 因为只交换了堆顶和堆底元素，堆的大体结构没有被破坏
        // 只需要从交换上来的堆底元素开始，进行heapify操作
        heapify(arr, i, 0); 
    }
}

// 构建最大堆
void HeapSort::buildMaxHeap(std::vector<int> &arr, int n)
{	// 从最后一个非叶子节点开始，向前进行“下坠操作”
    for (int i = n / 2 - 1; i >= 0; --i)
        heapify(arr, n, i);
}

// 调整堆，使其符合堆性质
void HeapSort::heapify(std::vector<int> &arr, int n, int i)
{
    int max = i;               // 假设当前值为最大值
    int left_son = 2 * i + 1;  // 当前节点的左孩子
    int right_son = 2 * i + 2; // 当前节点的右孩子

    // 检查是否有左孩子,且左孩子是否大于当前节点
    if (left_son < n && arr[left_son] > arr[max])
        max = left_son;

    // 检查是否有右孩子,且右孩子是否大于当前节点
    if (right_son < n && arr[right_son] > arr[max])
        max = right_son;
    
    // 如果最大值不是当前节点，交换并且继续调整堆
    if (max != i)
    {
        // 交换较大的子节点
        swap(arr[i], arr[max]);
        // 继续从调整的子节点开始，检查并调整剩下的节点
        heapify(arr, n, max);
    }
}

// 返回排序器的名称
std::string HeapSort::name() const
{
    return "HeapSort";
}

6.4 算法分析（以大顶堆为例）

时间复杂度

buildMaxHeap(int &arr, int n)函数分析:

• 一个节点，每下坠一层，最多需要比较2次关键字；

• 若堆高为h，某个节点在i层，这个节点最多向下调整h-i层，对比关键词次数 ≤ 2(h-i)；

• 第i层最多有$2^{i-1}$个节点，第i层的节点总共需要对比关键词:
  $
  <= 2^{i-1}*2(h-i) = 2^{i}(h-i) 次
  $

• 只有1~(h-1)层的节点才有可能需要进行下坠

• 所以，将整棵树调整为大顶堆，关键字对比次数：
  $
  <= \sum_{i=h-1}^{1}2^{i}(h-i)次
  $

• n个节点的完全二叉树树高 h = $\lceil log_2n \rceil +1$

• 所以带入上式，令j=h-i，关键字对比次数：

$
<= \sum_{j=1}^{h-1}2^{h-j}j <=2n\sum_{j=1}^{h-1}j/2^j (等比求和) <= 4n 次
$

heapify(int &arr, int n, int i)函数分析:

• 任意i∈[1,h-1]节点最多需要下坠h-i层，下坠一层最多对比2次

• 因此每次heapify(i)排序复杂度 :
  $
  <=2(h-i)<=2(h-1)<=O(h)=O(log_2n)
  $

稳定性：

7、归并排序（Merge Sort）

归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而**治(conquer)**的阶段则将分的阶段得到的各答案”修补”在一起，即分而治之)。

7.1 算法描述

• 把长度为 n 的输入序列分成两个长度为 n/2 的子序列；
• 对这两个子序列分别采用归并排序；
• 将两个排序好的子序列合并成一个最终的排序序列

7.2 动图演示

7.3 代码实现

// MergeSort.cpp
#include "MergeSort.h"

void MergeSort::sort(std::vector<int>& arr) {
    if(arr.size()<=1) return;
    std::vector<int> temp(arr.size());
    // 栈分配   适用于小规模数据，内存管理简单，适合大多数场景
    //std::vector<int> *temp = new std::vector<int>(arr.size()); 
    //堆分配    适用于数据量较大或者需要跨多个函数共享内存的场景，但需要手动管理内存
    mergeSort(arr,temp,0,arr.size()-1);
}

void MergeSort::mergeSort(std::vector<int>& arr, std::vector<int>& temp, int left, int right) {
    if(left<right){ //等于即只有一个元素，停止递归
        int mid = left + (right-left)/2;
        mergeSort(arr,temp,left,mid);
        mergeSort(arr,temp,mid+1,right);
        merge(arr,temp,left,mid,right);
    }
}

void MergeSort::merge(std::vector<int>& arr, std::vector<int>& temp, int left, int mid, int right) {
    int k=left,i=left,j=mid+1;
    //比较i和j所指向的数的大小，依次放入暂存数组中
    while(i<=mid&&j<=right){
        if(arr[i]<=arr[j]) temp[k++]=arr[i++];
        else temp[k++]=arr[j++];
    }

    //将剩余的元素依次放入暂存数组中
    while(i<=mid) temp[k++]=arr[i++];
    while(j<=right)  temp[k++]=arr[j++];

    //将暂存数组中的值重新给到原数组
    for(int f=left;f<=right;f++) arr[f] = temp[f];
}

std::string MergeSort::name() const {
    return "MergeSort";
}

7.4 算法分析

二路归并排序

从形态上来看就是一颗倒立的二叉树

• 满足 $ 归并趟数(除开初始序列) = h-1 = \lceil log_2n \rceil $
• 每趟归并时间复杂度为$O(n)$，算法时间复杂度为$O(nlog_2n)$
• 空间复杂度为$O(n)$,来自辅助数组B
• 算法是稳定的，你可以决定在merge()的时候，相同的数那个应该在前

8、计数排序（Counting Sort）

计数排序不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

8.1 算法描述

• 找出待排序的数组中最大和最小的元素；
• 统计数组中每个值为 i 的元素出现的次数，存入数组 C 的第 i 项；
• 对所有的计数累加（从 C 中的第一个元素开始，每一项和前一项相加）；
• 反向填充目标数组：将每个元素 i 放在新数组的第 C(i)项，每放一个元素就将 C(i)减去 1。

8.2 动图演示

8.3 代码实现

// CountingSort.cpp
#include "CountingSort.h"
#include <vector>
#include <algorithm>

void CountingSort::sort(std::vector<int>& arr) {
    // 找到数组中的最大值和最小值
    int maxElement = *std::max_element(arr.begin(), arr.end());
    int minElement = *std::min_element(arr.begin(), arr.end());
    
    //创建计数数组
    std::vector<int>count(maxElement-minElement+1,0);

    //统计每个元素出现的次数
    for(int num:arr){
        count[num-minElement]++;
    }

    //将元素放入原数组
    int index = 0;
    for(int i=0;i<count.size();i++){
        while(count[i]-- >0){ //count[i] 代表元素出现的次数
            arr[index++] = i+minElement; //i代表被排序的元素
        }
    }
}

std::string CountingSort::name() const {
    return "CountingSort";
}

8.4 算法分析

计数排序是一个稳定的排序算法。当输入的元素是 n 个 0 到 k 之间的整数时，时间复杂度是 O(n+k)，空间复杂度也是 O(n+k)，其排序速度快于任何比较排序算法。当 k 不是很大并且序列比较集中时，计数排序是一个很有效的排序算法。

9、桶排序（Bucket Sort）

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排）。

9.1 算法描述

• 设置一个定量的数组当作空桶；
• 遍历输入数据，并且把数据一个一个放到对应的桶里去；
• 对每个不是空的桶进行排序；
• 从不是空的桶里把排好序的数据拼接起来。

9.2 图片演示

9.3 代码实现

void BucketSort::sort(std::vector<int>& arr) {
    if (arr.empty()) return;

    // 找到数组中的最大值和最小值
    int minElement = *std::min_element(arr.begin(), arr.end());
    int maxElement = *std::max_element(arr.begin(), arr.end());

    // 根据最大值和最小值的差值计算桶的数量
    int bucketCount = (maxElement - minElement) / arr.size() + 1;

    // 创建桶
    std::vector<std::vector<int>> buckets(bucketCount);

    // 将元素分配到不同的桶中
    for (int num : arr) {
        int index = (num - minElement) * (bucketCount - 1) / (maxElement - minElement);
        buckets[index].push_back(num);
    }

    // 对每个桶进行排序（这里使用插入排序）
    for (auto& bucket : buckets) {
        std::sort(bucket.begin(), bucket.end());
    }

    // 将所有桶中的元素按顺序合并回原数组
    int index = 0;
    for (auto& bucket : buckets) {
        for (int num : bucket) {
            arr[index++] = num;
        }
    }
}

9.4 算法分析

桶排序最好情况下使用线性时间 O(n)，桶排序的时间复杂度，取决与对各个桶之间数据进行排序的时间复杂度，因为其它部分的时间复杂度都为 O(n)。很显然，桶划分的越小，各个桶之间的数据越少，排序所用的时间也会越少。但相应的空间消耗就会增大。

10、基数排序（Radix Sort）

基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。

10.1 算法描述

• 取得数组中的最大数，并取得位数；
• arr 为原始数组，从最低位开始取每个位组成 radix 数组；
• 对 radix 进行计数排序（利用计数排序适用于小范围数的特点）；

10.2 动图演示

10.3 代码实现

void RadixSort::sort(std::vector<int>& arr) {
    int max = getMax(arr);  // 找到数组中的最大值
    // 对每一位进行计数排序，从最低位到最高位
    for (int exp = 1; max / exp > 0; exp *= 10) {
        countingSort(arr, exp);
    }
}

std::string RadixSort::name() const {
    return "RadixSort";
}

void RadixSort::countingSort(std::vector<int>& arr, int exp) {
    int n = arr.size();
    std::vector<int> output(n);  // 输出数组
    std::vector<int> count(10, 0);  // 计数数组，存储每个数字的出现次数

    // 根据当前位数（exp）对每个元素进行计数
    for (int i = 0; i < n; i++) {
        count[(arr[i] / exp) % 10]++;
    }

    // 计算计数数组的累积值
    for (int i = 1; i < 10; i++) {
        count[i] += count[i - 1];
    }

    // 进行排序
    for (int i = n - 1; i >= 0; i--) {
        int digit = (arr[i] / exp) % 10;
        output[count[digit] - 1] = arr[i];
        count[digit]--;
    }

    // 将排序后的数组复制回原数组
    for (int i = 0; i < n; i++) {
        arr[i] = output[i];
    }
}

int RadixSort::getMax(const std::vector<int>& arr) {
    int max = arr[0];
    for (int num : arr) {
        if (num > max) {
            max = num;
        }
    }
    return max;
}

10.4 算法分析

---