当前位置： 首页 > article >正文

【数据结构与算法】九大排序算法实现详解

article 2025/1/30 16:32:46

文章目录

  • Ⅰ. 排序的概念及其运用
    • 一、排序的概念
    • 二、常见的排序算法
    • 三、排序算法的接口
    • 四、测试算法接口
    • 附：Swap接口（使用异或的方法实现）
  • Ⅱ. 排序算法的实现
    • 一、插入排序
    • 二、希尔排序( 缩小增量排序 )
    • 三、选择排序
    • 四、堆排序
    • 五、冒泡排序
    • 六、快速排序（优选算法会更新更快版本的快速排序，才能过力扣样例）
      • 递归版本
      • 对于【三数取中】与【小区间优化】的方法
      • 1. hoare版快速排序
      • 2. 挖坑版快速排序
      • 3. 前后指针版快速排序
      • 非递归版本（栈实现）
    • 七、归并排序
      • 递归实现
      • 归并排序非递归实现
      • 拓展：海量处理排序可用归并排序
    • 八、非比较排序（计数排序）
    • 九、基数排序
  • Ⅲ. 排序算法复杂度以及稳定性的分析
  • Ⅳ. 选择题

在这里插入图片描述

Ⅰ. 排序的概念及其运用

一、排序的概念

  • 排序： 所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
  • 稳定性： 若经过排序，这些记录的序列的相对次序保持不变，即在原序列中，r[i] = r[j] ，且 r[i] 在 r[j] 之前，而在排序后的序列中，r[i] 仍在 r[j] 之前，则称这种排序算法是稳定的；否则称为不稳定的。
  • 内部排序： 数据元素全部放在内存中的排序。
  • 外部排序： 数据元素太多不能同时放在内存中，根据排序过程的要求在内存外面的排序。（例如归并排序）

二、常见的排序算法

  • 插入排序
  • 希尔排序
  • 选择排序
  • 堆排序
  • 冒泡排序
  • 快速排序
  • 归并排序
  • 计数排序（非比较排序）
  • 基数排序

三、排序算法的接口

​ 排序 OJ(可使用各种排序跑这个OJ) : 排序数组

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<string.h>

void print(int arr[], int n);

// 插入排序
void InsertSort(int arr[], int n);

// 希尔排序
void ShellSort(int arr[], int n);

// 选择排序
void SelectSort(int arr[], int n);

// 堆排序
void AdjustDown(int arr[], int n, int root);
void HeapSort(int arr[], int n);

// 冒泡排序
void BubbleSort(int* a, int n);

// 快速排序递归实现
//三数取中函数
int GetMidIndex(int* a, int left, int right);
void QuickSort(int* a, int left, int right);
// 快速排序hoare版本
int PartSort1(int* a, int left, int right);
// 快速排序挖坑法
int PartSort2(int* a, int left, int right);
// 快速排序前后指针法
int PartSort3(int* a, int left, int right);
// 快速排序 非递归实现
void QuickSortNonR(int* a, int left, int right);

// 归并排序递归实现
void MergeSort(int* a, int n);
// 归并排序非递归实现
void MergeSortNonR(int* a, int n);

// 计数排序
void CountSort(int* a, int n);

四、测试算法接口

#include "sort.h"

// 测试排序的性能对比
void TestOP()
{
	srand((unsigned int)time(0));
	const int N = 100000;
	int* a1 = (int*)malloc(sizeof(int) * N);
	int* a2 = (int*)malloc(sizeof(int) * N);
	int* a3 = (int*)malloc(sizeof(int) * N);
	int* a4 = (int*)malloc(sizeof(int) * N);
	int* a5 = (int*)malloc(sizeof(int) * N);
	int* a6 = (int*)malloc(sizeof(int) * N);
	for (int i = 0; i < N; ++i)
	{
		a1[i] = rand();
		a2[i] = a1[i];
		a3[i] = a1[i];
		a4[i] = a1[i];
		a5[i] = a1[i];
		a6[i] = a1[i];
	}
	int begin1 = clock();
	InsertSort(a1, N);
	int end1 = clock();

	int begin2 = clock();
	ShellSort(a2, N);
	int end2 = clock();

	int begin3 = clock();
	SelectSort(a3, N);
	int end3 = clock();

	int begin4 = clock();
	HeapSort(a4, N);
	int end4 = clock();

	int begin5 = clock();
	QuickSort(a5, 0, N - 1);
	int end5 = clock();

	int begin6 = clock();
	MergeSort(a6, N);
	int end6 = clock();

	printf("InsertSort:%d\n", end1 - begin1);
	printf("ShellSort:%d\n", end2 - begin2);
	printf("SelectSort:%d\n", end3 - begin3);
	printf("HeapSort:%d\n", end4 - begin4);
	printf("QuickSort:%d\n", end5 - begin5);
	printf("MergeSort:%d\n", end6 - begin6);
	free(a1);
	free(a2);
	free(a3);
	free(a4);
	free(a5);
	free(a6);
}

附：Swap接口（使用异或的方法实现）

​ 使用异或方法的优点： 无需开辟临时变量，且不会发生溢出。

void Swap(int* a, int* b)
{
    if(*a == *b)//这个条件要加，因为如果两个数相等，会变成0
        return;
    
    *a ^= *b;
    *b ^= *a;
    *a ^= *b;
}

Ⅱ. 排序算法的实现

一、插入排序

​ 直接插入排序是一种简单的插入排序法，其基本思想是：把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列 。

​ 实际中我们玩扑克牌时，就用了插入排序的思想。

在这里插入图片描述

直接插入排序：

​ 当插入第 i (i >= 1)个元素时，前面的 array[0], array[1], …, array[i - 1] 已经排好序，此时用 array[i] 的排序码与 array[i - 1], array[i - 2], … 的排序码顺序进行比较，找到插入位置即将 array[i] 插入，原来位置上的元素顺序后移。

在这里插入图片描述

直接插入排序的特性总结：

  1. 元素集合越接近有序，直接插入排序算法的时间效率越高

  2. 时间复杂度：O(n^2)

  3. 空间复杂度：O(1)，它是一种稳定的排序算法

  4. 稳定性：稳定

代码实现：

void InsertSort(int* arr, int n)
{
    for(int i = 0; i < n - 1; ++i)
    {
        int end = i;
        int tmp = arr[end + 1];
        while(end >= 0)
        {
            if(arr[end] > tmp)
            {
                arr[end + 1] = arr[end];
                --end;
            }
            else
                break;
		}
        arr[end + 1] = tmp;
    }
}

二、希尔排序( 缩小增量排序 )

​ 希尔排序的由来：

​ 希尔排序是基于插入排序的以下两点性质而提出改进方法的：

  1. 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率。
  2. 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位。

​ 在以前排序算法不多的时候，科学家们想着如何优化时间复杂度…

​ 这时希尔想到，插入排序最坏的情况是 O(N^2)，是在序列逆序的情况下，以目标排升序为例，最大的数字在最前面，那么要是将插入进行分组会不会交换的更快？答案是确实是快了！

​ 因为将插入排序的思想进行分组插入后，如果分组越大，那么大的数字能更快的向后移动，而分组越小，大的数字就会越慢的向后移动。相反，分组越大，那么这个序列也越不接近有序，而分组越小，反而越接近有序。

​ 所以希尔就根据这种特点，创造了缩小增量排序的基本思想！

简单来说：

​ 希尔排序是按照不同步长对元素进行插入排序，==当刚开始元素很无序的时候，步长最大，所以插入排序的元素个数很少，速度很快；当元素基本有序了，步长很小，插入排序对于有序的序列效率很高。==所以，希尔排序的时间复杂度会比 O(n^2) 好一些。

​ 实质就是一种分组插入的思想！

在这里插入图片描述

希尔排序的特性总结：

  1. 希尔排序是对直接插入排序的优化。

  2. 当 gap > 1 时都是预排序，目的是让数组更接近于有序。当 gap == 1 时，数组已经接近有序的了，这样就会很快 ，可看作 O(n)。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。

  3. 希尔排序的时间复杂度不好计算，需要进行推导，推导出来 平均时间复杂度： O(n^1.3）

  4. 稳定性：不稳定

总结：

gap 越大，大的和小的数可以更快的挪到对应的方向去

gap 越大，越不接近有序

gap 越小，大的和小的数可以更慢的挪到对应的方向去

gap 越小，就越接近有序

代码：

void ShellSort(int* arr, int n)
{
    int gap = n;
    while(gap > 1)
    {
        gap = (gap / 3) + 1; // 加一防止gap最后为0
        for(int i = 0; i < n - gap; ++i)
        {
            // 剩下操作和直接插入基本一样，区别就是步数从1变成gap
            int end = i;
            int tmp = arr[end + gap];
            while(end >= 0)
            {
                if(arr[end] > tmp)
                {
                    arr[end + gap] = arr[end];
                    end -= gap;
                }
                else 
                    break;
            }
            arr[end + gap] = tmp;
        }
    }
}

三、选择排序

​ 基本思想：采用双向选择，同时找大找小，进行一定程度的优化

​ 每一次从待排序的数据元素中选出最小和最大的两个元素，存放在序列的起始位置以及末尾，直到全部待排序的数据元素排完 。

  • 在元素集合 array[i] ~ array[n-1] 中选择关键码最大与最小的数据元素
  • 若它不是这组元素中的最后一个或者第一个元素，则将它与这组元素中的最后一个或第一个元素交换
  • 在剩余的 array[i] -- array[n-2]（array[i+1] ~ array[n-1]）集合中，重复上述步骤，直到集合剩余一个元素

直接选择排序的特性总结：

  1. 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用

  2. 时间复杂度：O(n^2)

  3. 空间复杂度：O(1)

  4. 稳定性：不稳定

代码：

void SelectSort(int* arr, int n)
{
    int left = 0;
    int right = n - 1;
    
    // 同时找最大和最小，从两边开始互换位置
    while(left <= right)
    {
        int max = left;
        int min = right;
        for(int i = left; i < right + 1; ++i)
        {
            if(arr[i] < min)
                min = i
            if(arr[i] > max)
                max = i;
        }
        
        Swap(&arr[left], &arr[min]);
         // 如果max和left位置重叠，max被换走了，要修正一下max的位置
        if (left == max)
            max = min;
        Swap(&arr[right], &arr[max]);

        left++;
        right--;
    }
}

四、堆排序

​ 堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。

​ 需要注意的是排升序要建大堆，排降序建小堆。 （具体的细节可以参考之前二叉树中的堆的内容）

在这里插入图片描述

堆排序的特性总结：

  1. 堆排序使用堆来选数，效率就高了很多。

  2. 时间复杂度：O(N*logN) —> 向下调整的 logN 乘以 一共 N 个数

  3. 空间复杂度：O(1)

  4. 稳定性：不稳定

代码：

//向下调整算法（大堆）
void AdjustDown(int* arr, int n, int root)
{
    int parent = root;
    int child = parent * 2 + 1;
    while(child < n)
    {
        if (child + 1 < n && arr[child] < arr[child + 1])
        {
            child += 1;
        }
        if (arr[parent] < arr[child])
        { 
            Swap(&arr[parent], &arr[child]);
            parent = child;
            child = parent * 2 + 1;
        }
        else
            break;
    }
}

void HeapSort(int* arr, int n)
{
    //建大堆
    for(int i = (n-1-1) / 2; i >= 0; --i)
        AdjustDown(arr, n, i);
    
    int end = n - 1;
    while(end > 0)
    {
        Swap(&arr[0], &arr[end]);
        AdjustDown(arr, end, 0);
        --end;
    }
}

五、冒泡排序

在这里插入图片描述

冒泡排序的特性总结：

  1. 冒泡排序是一种非常容易理解的排序

  2. 时间复杂度：O(n^2)

  3. 空间复杂度：O(1)

  4. 稳定性：稳定

代码：

void BubbleSort(int* arr, int n)
{
    for(int i = 0; i < n - 1; ++i)
    {
        int flag = 1;
        for(int j = 0; j < n - 1 - i; ++j)
        {
            if(arr[j] > arr[j + 1])
            {
                Swap(&arr[j], &arr[j + 1]);
                flag = 0;
            }
        }
        if(flag == 1)
            break;
    }
}

六、快速排序（优选算法会更新更快版本的快速排序，才能过力扣样例）

递归版本

​ 快速排序是 Hoare 于 1962 年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

​ 将区间按照基准值划分为左右两半部分的常见方式有：（会一种即可）

  1. hoare版本

  2. 挖坑法（本人比较喜欢这种方法）

  3. 前后指针版本

在这里插入图片描述

快速排序的特性总结：

  1. 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序

  2. 时间复杂度：O(N*logN)

在这里插入图片描述

  1. 空间复杂度：O(logN) （递归树的深度）

  2. 稳定性：不稳定

在写出个版本之前，我们先写出快速排序的主函数，让各版本的快排作为子函数，减少耦合性。

void QuickSort(int* arr, int left, int right)
{
    if(left >= right)  //递归结束的条件
        return;
    
    int key = PartQuickSort(arr, left, right); // 将快排作为子函数排序
    
    // 继续递归调用左右子区间
    QuickSort(arr, left, key -1);    
    QuickSort(arr, key + 1, right);
}

​ 而在快排的主函数中，我们又可以有以下两种优化手段：

  1. 三数取中法
  2. 递归到小的子区间时，可以考虑使用插入排序

对于【三数取中】与【小区间优化】的方法

​ 优化的产生原因：在理想情况下，我们都希望每次更好都是二分，每行有 N 个数，共有 logN 行，所以时间复杂度为O(N*logN)

在这里插入图片描述

​ 但是对于最坏的情况，就是这个数据序列本来就有序，共有 N 行，每行分别为 N、N-1、N-2、......、2、1 个，共 N(N-1)/2 个。

​ 若进行快排，则会有时间复杂度O(N^2)，效率非常低，但是我们可以发现，其实本来就不需要排多少个，居然会花了这么久的时间，如下图所示！所以就有了 三数取中的方法，来避免这种最坏的情况。

在这里插入图片描述

三数取中：

​ 将每次所给的区间中的 最左边的值 、最右边的值、 最中间的值 ，挑大小为中间的那个，并将这个数与最左边的数交换位置。

​ 代码如下所示：

int GetMidIndex(int* a, int left, int right)
{
     int mid = left + ((right - left)>>1); //运用位运算符防止溢出

     if (a[left] < a[mid])
     {
         if (a[mid] < a[right])
             return mid;
         else if (a[right] < a[left])
             return left;
         else
             return right;
     }
     else  //a[left] >= a[mid]
     {
         if (a[right] < a[mid])
             return mid;
         else if (a[left] < a[right])
             return left;
         else
             return right;
}

小区间优化:

​ 当要排的数据序列较大的时候，递归的层数就越深，特别是最后那几层或者几十层。但是我们仔细一想，其实在快排的前面的递归中，大部分区间的数据已经是解决有序了，所以这个时候我们 可以考虑让剩下的几层或者几十层使用插入排序，进行优化，减少递归的深度，防止过多的开辟栈空间。（效率其实是相差不大的，如今编译器对递归的优化很大，不亚于迭代）

​ 所以将上述的两种优化放到快排的主函数中，代码如下：

void QuickSort(int* a, int left, int right)
{
    // 记得递归返回条件
    if (left >= right)
        return;

    // 分小区间，数据多的继续递归，少的就直接插入排序
    // 这里的小区间取不同的大小，效果不一样，得看要排的数据多大
    if (right - left > 20)
    {
        // 三数取中
        int mid = GetMidIndex(a, left, right);
        Swap(&a[mid], &a[left]);

        int key = PartSort1(a, left, right);
        QuickSort(a, left, key - 1);
        QuickSort(a, key + 1, right);
    }
    else
    {
        InsertSort(a + left, right - left + 1);
    }
}

1. hoare版快速排序

​ hoare 版本比较经典，就是 左右指针法 的思想。

​ 步骤如下所示：

  1. 选出一个 key， 一般选最左边的值为 key，因为我们通过了三数取中的优化，不怕出现最坏的情况。
  2. 然后先让 right 从右边开始向左走，直到找到**比 key 处的值要小的数** 或者 遇到了 left。
  3. 若 right 找到后，就让 left 向右走，直到找到**比 key 处的值要大的数** 或者 遇到了 right。
  4. 交换 left 与 right 的值，然后一直循环，直到两个指针相遇。
  5. 最后将 key 处的值 与 left 处的值交换，将 left 作为返回值返回。

​ 代码：

int hoareQuickSort(int* arr, int left, int right)
{
    int key = left;
    while(left < right)
    {
         // 记得判断left < right，以及要a[right]要>=a[key]，否则死循环
        while(left < right && arr[right] >= arr[key])
            right--;
        while(left < right && arr[left] <= arr[key])
            left++;
        
        Swap(&arr[left], &arr[right]);
    }
    // 因为是右边先动，所以相遇时候left一定小于key的值，所以无需判断
    Swap(&arr[key], &arr[left]);
    return left;
}

2. 挖坑版快速排序

​ 挖坑法顾名思义就是不断挖坑😄

在这里插入图片描述

步骤：

  1. 选取最左值为 hole 值，并将 最左侧的位置想象成一个坑（默认已经三数取中优化）
  2. right 从右边往左开始找 比 hole 小的值，若找到了，则将 right 处的值 赋给 left 处，然后把 right 处 想象成新坑！
  3. left 从左往右开始找 比 hoke 大的值，若找到了，则将 left 处的值 赋给 right 处，然后把 left 处 想象成新坑！
  4. 直到 left 与 right 相遇，然后将 hole 填到最后的 left 处，补上坑。
  5. 最后返回 left 即可。

代码：

int holeQuickSort(int* arr, int left, int right)
{
    int hole = arr[left];
    while(left < right)
    {
        // right找小的
        while (left < right && a[right] >= hole)
            right--;
        // 填左边的坑，右边形成了新坑
        if(left < right)
        	a[left++] = a[right];

        // left找大的
        while (left < right && a[left] <= hole)
            left++;
        // 填右边的坑，左边形成了新坑
        if(left < right)
        	a[right--] = a[left];
    }
    // 最后用hole把坑填住
    a[left] = hole;
    return left;
}

3. 前后指针版快速排序

在这里插入图片描述

步骤:

  1. 取最左边为 key，然后让 prev 与 cur 一前一后指向数据序列。（默认已经三数取中优化）
  2. 让 cur 先走，找比 key 处小的值，直到出界。
  3. 若 cur 找到了小的，则先让 prev++ ，然后 判断 cur 处是否与 prev 处是相同的，若相同则无需交换，若不同再交换 cur 与 prev 处的数据。
  4. 若 cur 走到出界了，则交换 prev 与 key 处的值。

代码：

int back-and-forthQuickSort(int* arr, int left, int right)
{
    int key = left;
    int prev = left;
    int cur = left + 1;
    while(cur <= right)
    {
        if(arr[cur] < a[key] && prev != cur)
        {
            prev++;
            Swap(&arr[prev], &arr[cur]);
        }
        cur++;
    }
    Swap(&arr[key], &arr[prev]);
    return prev;
}

非递归版本（栈实现）

​ 思路：用栈来存储每个子区间的下标。

​ 首先将 left 和 right 入栈，然后进入循环，用 begin 和 end 分别标记每次 出栈的左右区间。接着对该区间进行快速排序（可以用我们前面实现的三种方式的其中一种），并标注 key ，然后继续将新的 [ begin, key - 1 ] , [ key + 1, end ] 入栈。

​ 若区间只有一个元素了则不入栈。

在这里插入图片描述

​ 注：用迭代主要是为了解决 递归栈溢出 的问题，而不是速度问题，因为现在的编译器优化已经做的很好了。

​ 代码：

#include "stack.h"
void QuickNonSort(int* arr, int left, int right)
{
    // 三数取中
    int mid = GetMidIndex(a, left, right);
    Swap(&a[mid], &a[left]);
    
    Stack st; // 初始化队列，顺便将left和right放进去
    StackInit(&st);
    StackPush(&st, left);
    StackPush(&st, right);
    
    while(!StackEmpty(&st))
    {
        int end = StackTop(&st);
        StackPop(&st);
        
        int begin = StackTop(&st);
        StackPop(&st);
        
        int key = holeQuickSort(arr, begin, end);
        if(begin < key - 1)
        {
            StackPush(&st, begin);
            StackPush(&st, key - 1);
        }
        if(key + 1 < end)
        {
            StackPush(&st, key + 1);
            StackPush(&st, end);
        }
    }
    StackDestroy(&st);
}

在这里插入图片描述

七、归并排序

​ 基本思想：

​ 归并排序（MERGE-SORT） 是建立在归并操作上的一种有效的排序算法,该算法是采用 分治法 的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

​ 归并排序核心步骤：

在这里插入图片描述

归并排序的特性总结：

  1. 归并的缺点在于需要 O(N) 的空间复杂度，归并排序的思考更多的是 解决在磁盘中的外排序问题。

  2. 时间复杂度：O(N*logN) （类似于二叉树，分解时共有 logN 行，每行合并的有 N 个，所以为 N*logN）

  3. 空间复杂度：O(N) （要开辟临时数组）

  4. 稳定性：稳定

递归实现

​ 思路：分解与合并过程类似二叉树的后序遍历，假设左区间有序了，右区间也有序了，那么一归并，整个数组就有序了。

void Merge(int* a, int begin1, int end1, int begin2, int end2, int* tmp) 
{
    // 两端有序子区间归并tmp，并拷贝回去
    int j = begin1;
    int i = begin1;
    while ((begin1 <= end1) && (begin2 <= end2))
    {
        if (a[begin1] <= a[begin2])
            tmp[i++] = a[begin1++];
        else
            tmp[i++] = a[begin2++];
    }
    // 将有可能还没结束的数据放到tmp中去
    while (begin1 <= end1)
        tmp[i++] = a[begin1++];
    while (begin2 <= end2)
        tmp[i++] = a[begin2++];

    // 拷贝回去
    for (j; j <= end2; j++)
        a[j] = tmp[j];
}
void _MergeSort(int a[], int left, int right, int* tmp)
{
    // 递归结束条件
    if (left >= right)
        return;

    // 分治步骤:分为[left, mid]和[mid + 1, right] 
    int mid = (left + right) >> 1;
    _MergeSort(a, left, mid, tmp);
    _MergeSort(a, mid + 1, right, tmp);

    // 由于下面迭代（非递归）版本也要用到这部分，所以整合出来当作子函数
    Merge(a, left, mid, mid + 1, right, tmp);
}

void MergeSort(int* a, int n)  // 归并排序的主函数接口
{
    int* tmp = (int*)malloc(sizeof(int) * n);
    if (tmp == NULL)
    {
        printf("malloc fail\n");
        exit(-1);
    }

    _MergeSort(a, 0, n - 1, tmp);
    free(tmp);
}

归并排序非递归实现

​ 思路：与递归不同的是，迭代是不需要分解的。只需要控制好每次归并的区间，让它们从一一归并、二二归并、四四归并…，直到最后归并成一个完整的数组。

注意： 归并时候可能存在的三种情况：（1、2点可合成为一点处理）

  1. 最后一个小组归并时，第一个小区间不够 gap 个，那么就不需要归并
  2. 最后一个小组归并时，第二个小区间不存在， 那么就不需要归并
  3. 最后一个小组归并时，第二个小区间存在，第二个区间不够 gap 个，那么只需要归并到第二个小区间的末尾即可
void MergeSortNonR(int* a, int n)
{
    int* tmp = (int*)malloc(sizeof(int) * n);
    if (tmp == NULL)
    {
        printf("malloc fail\n");
        exit(-1);
    }

    int gap = 1;
    while (gap < n)
    {
        for (int i = 0; i < n; i += gap * 2)
        {
            // 对区间 [i, i+gap-1]，[i+gap, i+2*gap-1] 归并
            int begin1 = i, end1 = i + gap - 1;
            int begin2 = i + gap, end2 = i + 2 * gap - 1;

            // 归并最后一小组时，如果不存在第二个小区间，则无需归并
            if (begin2 >= n)
                break;

            // 归并最后一小组时，如果第二个小区间不够gap个，则要调整一下end2
            if (end2 >= n)
                end2 = n - 1;

            Merge(a, begin1, end1, begin2, end2, tmp); //这个子函数在递归版本中
        }
        gap *= 2;
    }

    free(tmp);
}

拓展：海量处理排序可用归并排序

在这里插入图片描述

八、非比较排序（计数排序）

思想：计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。 操作步骤：

  1. 统计相同元素出现次数

  2. 根据统计的结果将序列回收到原来的序列中

在这里插入图片描述

计数排序的特性总结：

  1. 计数排序在数据范围集中时，效率很高，但是适用范围及场景有限，并且只适合整数，如果是浮点数、字符串等等就不行了。

  2. 时间复杂度：O(MAX(N,范围))

  3. 空间复杂度：O(范围)

  4. 稳定性：稳定

​ 思考： 若最小的数是从一万开始的，那前面的空间都浪费了，咋办？

​ 方法： 先求出原数组的最大值和最小值 max 和 min ，然后 开辟的数组只需要开辟 max - min + 1 个空间，表示最大值和最小值内的元素范围。

​ 要注意在计数时候要记得 减去 min，在回收的时候记得 加上 min。

void CountSort(int* a, int n)
{
    //先找数组里面的最大值和最小值
    int max = a[0];
    int min = a[0];
    for (int i = 0; i < n; i++)
    {
        if (a[i] > max)
            max = a[i];
        if (a[i] < min)
            min = a[i];
    }

    // 算出开辟空间的范围和大小
    int range = max - min + 1;
    int* count = (int*)malloc(sizeof(int) * range);
    if (count == NULL)
    {
        printf("malloc fail\n");
        exit(-1);
    }
    memset(count, 0, sizeof(int) * range);// 记得初始化为0

    // 哈希映射，注意这里要减去范围的最小值
    for (int i = 0; i < n; i++)
    {
        count[a[i] - min] += 1;
    }

    // 回收排序好的数据，记得加上范围的最小值
    int j = 0;
    for (int i = 0; i < range; i++)
    {
        while (count[i]--)
        {
            a[j++] = i + min;
        }
    }

    free(count);
}

九、基数排序

在这里插入图片描述

​ 基数排序算法是一种非比较算法，其原理是将整数 按每个位数分别比较。它利用了桶的思想。

​ 代码：（这里实现借助的是队列queue，比较方便）

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

const int MAX_COUNT = 3;  // 最大的位数
const int MAX_RADIX = 10; // 最大的基数桶数
queue<int> q[MAX_RADIX];

int GetKey(int n, int k)
{
	int key = 0;
	while (k--)
	{
		key = n % 10;
		n /= 10;
	}
	return key;
}

void Distribute(vector<int>& v, int left, int right, int k)
{
	for (int i = left; i < right; ++i)
	{
		int key = GetKey(v[i], k);
		q[key].push(v[i]);
	}
}

void Collect(vector<int>& v)
{
	int i = 0;
	for (int k = 0; k < MAX_RADIX; ++k)
	{
		while (!q[k].empty())
		{
			v[i++] = q[k].front();
			q[k].pop();
		}
	}
}

// 基数排序
void radixsort(vector<int>& v, int left, int right)
{
	if (v.size() == 0)
		return;

	for (int k = 1; k <= MAX_COUNT; ++k)
	{
		// 分发数据
		Distribute(v, left, right, k);

		// 回收数据
		Collect(v);
	}
}

int main()
{
	int arr[] = { 278, 109, 63, 930, 589, 184, 505, 269, 8, 83 };
	vector<int> v(arr, arr + sizeof(arr) / sizeof(arr[0]));

	auto it = v.begin();
	while (it != v.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;

	radixsort(v, 0, v.size());

	it = v.begin();
	while (it != v.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;
	return 0;
}

Ⅲ. 排序算法复杂度以及稳定性的分析

在这里插入图片描述

在这里插入图片描述

​ 此外，基数排序也是稳定的！

​ 稳定性应用： 考试交卷之后，自动评卷拿到成绩，成绩按交卷顺序填到数组中，然后我们对数组进行排序，进行排名。要求：若分数相同，先交卷的排在前面。所以用了不稳定的排序， 可能会改变相对顺序。

Ⅳ. 选择题

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述


http://www.kler.cn/a/522921.html

相关文章：

  • 【Rust自学】15.7. 循环引用导致内存泄漏
  • CAPL编程常见问题与解决方案深度解析
  • 构建 QA 系统：基于文档和模型的问答
  • SOME/IP--协议英文原文讲解2
  • Myeclipse最新版本 C1 2019.4.0
  • MySQL--》深度解析InnoDB引擎的存储与事务机制
  • 中科大：LLM检索偏好优化应对RAG知识冲突
  • 面向对象设计原则 - SOLID原则 (基于C++)
  • [Dialog屏幕开发] 设置方式对话框
  • 使用eNSP配置GRE VPN实验
  • 基于51单片机和ESP8266(01S)、8X8点阵屏的二进制WiFi时钟
  • 什么是循环神经网络？
  • python.tkinter设计标记语言(渲染7-动态呈现标签) - 副本
  • 1.2第1章DC/DC变换器的动态建模-1.2Buck-Boost 变换器的交流模型--电力电子系统建模及控制 (徐德鸿)--读书笔记
  • game101 环节搭建 windows 平台 vs2022
  • doris：STRUCT
  • 【阅读笔记】New Edge Diected Interpolation，NEDI算法，待续
  • 跨域问题解释及前后端解决方案（SpringBoot）
  • 接口技术-第2次作业
  • Gradle配置指南：深入解析settings.gradle.kts（Kotlin DSL版）
  • AAAI2024论文合集解读|Multi-dimensional Fair Federated Learning-water-merged
  • IBMSamllPower服务器监控指标解读
  • 【数据库初阶】表的查询语句和聚合函数
  • leetcode 2920. 收集所有金币可获得的最大积分
  • 10 款《医学数据库和期刊》查阅网站
  • Lesson 119 A true story