数据结构排序算法

每日一言

Listen to yourself whining and complaining like some sorry little victim! You can whimper all day for all I care, you’re nothing but a coward! – Naruto Uzumaki
from Naruto

排序简介

排序的目的：将一组无序的记录序列调整为有序。

排序的分类

根据文件记录存放位置分：

  1. 内部排序：排序过程中将全部记录放在内存中处理。
  2. 外部排序：排序过程中需在内外存之间交换信息。

根据相同关键字排序前后顺序分：

  1. 稳定排序：假设两个记录关键字相等 $K_i$ == $K_j$ ($ i \neq j$),若排序前记录$R_i$ 领先于 $R_j$ ，则排序后这种关系不变。
  2. 不稳定排序：不满足稳定排序的称为不稳定排序。

根据存储结构划分排序的种类：

  1. 顺序存储
  2. 链式存储
  3. 地址存储

根据内部排序的方法：

插入排序、交换排序、选择排序、归并排序、基数排序。

插入排序

假设我们已经排序i个数，则1~(i-1) 为有序区，i ~ n 为无序区

插入排序基本步骤：

  1. 在有序序列 $R_{1} \cdots R_{i-1}$中查找R[i]插入的位置 j，满足
    $$
    R_j \leq R_i \leq R_{j+1}
    $$
  2. 将 $R_{j+1} \cdots R_{i-1}$ 中的所有记录均向后移一个位置
  3. 将$R_i$ 插入到$R_{j+1}$的位置上

算法实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
void InsertSort(SqList& L)
{
    for (int i = 2; i <= L.length; i++)
    {
        //使用哨兵的顺序查找
        L.r[0] = L.r[i];
        int j;
        for (j = i - 1; L.r[0].key < L.r[j].key; j--)
            L.r[j + 1] = L.r[j];   //对哨兵查找增加的一边查找一边移动
        L.r[j + 1] = L.r[0];
    }//InsertSort
}

改进措施：

  1. 在1 到 i-1内查找时，通过折半查找法，减少比较次数。
  2. 2-路插入排序
    设置与R同样大小的辅助空间d，将$R_1$ 赋给d[1] , 并将d视为循环向量
    对于$R_i$ ，若R[i] >= d[1]，则插入d[1]之后的有序序列，反之插入d[1]之前的有序序列中。
    效果：减少记录的移动次数

表插入排序

在链表中采取插入排序的策略：选取未排序序列的第一个key，在已经排序序列里面找插入位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void InsertSortPoint(SqList& L)
{
    PNode p = Head->next;
    Head->next = NULL;
    while(p)
    {
        pTemp = Head->next;
        pPre = Head;
        //从链表头向后找
        //不能采用顺序存储的从后向前找的哨兵方法
        while (pTemp && (p->data.key >= pTemp->data.key))
        {   
            pPre = pTemp;
            pTemp = L.p[pTemp];
        }
        q=p->next;  //保存下一个结点的指针
        p->next = pPre->next;   //插入结点
        pPre->next=p;
        p=q;    //处理下一个结点

    }
}

希尔排序

算法思想

希尔排序（Shell Sort）是一种基于插入排序的高级排序算法，通过分组和逐步优化的策略显著提升了排序性能。它的核心思想是将序列按一定增量（d）划分为若干子序列，分别进行排序，再逐步减小增量，直至整个序列整体有序。通过对远距离元素的调整，希尔排序有效减少了插入排序中大量的移动操作，极大地提高了排序效率。

算法流程

  1. 选择增量序列：
    设定一个初始增量 d，将序列按间隔 d 分组。例如：

    • 第一组：索引为 (1, 1+d, 1+2\*d, ...)
    • 第二组：索引为 (2, 2+d, 2+2\*d, ...)
    • 第 d 组：索引为 (d, 2d, 3d, ...)

  2. 分组插入排序：
    对每一组数据进行直接插入排序。通过对每组的调整，使得间隔为 d 的元素局部有序。

  3. 缩小增量：
    按照某种规则减小增量 d（如 d = d/2 或更优化的增量序列）。重复分组与排序过程。

  4. 终止条件：
    当增量 d 缩小至 1 时，对整个序列再进行一次插入排序，此时序列整体有序。

希尔排序的效率依赖于增量序列的选择，经典的 d = n/2 序列尽管易于实现，但并非最优。近年来，研究者提出了多种优化的增量序列（如 Hibbard 增量、Sedgewick 增量等），使算法在理论和实践中表现更优。

算法实现

以下是希尔排序的典型实现，采用了动态增量序列的思想。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void ShellSortN(SqList &L, int dlta[], int t) {
    // 按增量序列 dlta[0..t-1] 对顺序表 L 作希尔排序
    for (int k = 0; k < t; k++) {
        int dk = dlta[k];   // 当前增量值，例如：15, 7, 3, 1
        for (int s = 1; s <= dk; s++) {  // 针对每组进行插入排序
            for (int i = s + dk; i <= L.length; i += dk) {
                if (L.r[i].key < L.r[i - dk].key) {
                    L.r[0].key = L.r[i].key; // 暂存待插入元素
                    int j;
                    for (j = i - dk; j > 0 && L.r[0].key < L.r[j].key; j -= dk) {
                        L.r[j + dk].key = L.r[j].key; // 元素后移
                    }
                    L.r[j + dk].key = L.r[0].key; // 插入元素
                }
            }
        }
    }
}

代码注释优化

  1. 增量选择：dlta 是传入的增量序列，可以依据需求设定为多种优化序列。
  2. 分组遍历：外层循环 for (s = 1; s <= dk; s++) 用于遍历每一组。
  3. 插入排序：每组内使用经典的插入排序，但以 dk 为间隔。
  4. 元素后移：通过内层 for 循环实现元素比较与后移，最终完成插入操作。

算法效率

希尔排序的时间复杂度与增量序列密切相关：

  • 最坏情况：根据不同增量序列，复杂度范围在 O(n^2) 到 O(n\*log^2(n)) 之间。
  • 平均情况：常见增量序列下，希尔排序的性能通常优于 O(n\*log(n))，接近快速排序。
  • 空间复杂度：O(1)，属于原地排序算法。

稳定性

希尔排序不是稳定排序算法，相同元素的相对顺序可能会改变。

交换排序

基本思想：两两比较，如果发生逆序则交换，直到所有记录都排好序为止。

冒泡排序

将两个相邻记录的关键字进行比较，若为逆序则交换两者位置，小者往上浮，大者往下沉。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void bubble_sort(int arr[], int n) {
    for (int i = 0; i < n-1; i++) 
    {
        int swapped = 0;  // 用来判断是否有元素交换
        for (int j = 0; j < n-i-1; j++) 
	{
            if (arr[j] > arr[j+1]) 
	    {
                // 交换 arr[j] 和 arr[j+1]
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
                swapped = 1;
            }
        }
        // 如果没有交换发生，说明数组已经是有序的，提前退出
        if (swapped == 0) {
            break;
        }
    }
}

时间复杂度分析

  1. 最佳情况（Best Case） ：
  • 如果待排序的序列已经是有序的（或者已经排列在正确的顺序中），冒泡排序只需要遍历一次，且不需要进行任何交换操作。
  • 时间复杂度： O(n) ，其中n是序列的长度。
  1. 最坏情况（Worst Case） ：
  • 如果待排序的序列是逆序的（即从大到小排列），每一轮遍历都需要进行交换。此时冒泡排序会进行n-1轮，每轮会进行n-i次比较，其中i是当前轮的索引。
  • 时间复杂度： O(n²) 。
  1. 平均情况（Average Case） ：
  • 在平均情况下，冒泡排序仍然需要n-1轮，每轮进行n-i次比较。因此，平均时间复杂度为： O(n²) 。

空间复杂度

  • 冒泡排序是一种原地排序算法，它只需要常数级别的额外空间来存储临时变量，因此空间复杂度为： O(1) 。

稳定性

  • 冒泡排序是稳定的排序算法。也就是说，如果两个元素相等，它们的相对顺序在排序后不会改变。

改进措施

  1. 每趟排序中，记录最后一次发生交换的位置，下次直接从该位置开始。
  2. 双向交替扫描

快速排序

快速排序（QuickSort）是一种高效的排序算法，其基本思想是通过分治法将一个数组分成较小的子数组，然后递归地排序这些子数组。以下是快速排序的基本步骤：

  1. 选择基准（Pivot） ：从数组中选择一个元素$R_p$作为基准。基准的选择可以是第一个元素、最后一个元素、中间元素或随机选择。
  2. 分区（Partition） ：通过一趟排序将基准元素$R_p$放在正确的位置上,使得整个序列满足：
    $$
    左边记录的关键字 \leq R_p \leq 右边记录的关键字
    $$
  3. 递归排序 ：对基准左边的子数组和右边的子数组分别递归地进行快速排序，直到每个子表的元素只剩一个
  4. 合并 ：由于每次分区后基准元素的位置已经确定，最终整个数组将被排序。

代码实现

快速排序的代码如下：

1
2
3
4
5
6
7
8
9
10
11
// 快速排序函数
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        // pi 是分区索引，arr[pi] 已经排好序
        int pi = partition(arr, low, high);

        // 分别对分区的两部分进行快速排序
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

其中的 partition()函数的作用是将基准元素放到合适的位置并返回排序后基准元素的下标，表示从以该下标将整个序列分为两半。它的具体实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int partition(int arr[], int low, int high) {
    arr[0] = arr[low]; // 暂存基准元素到0位置，同时将low位置空出待填
    int pivot = arr[low]; // 选择第一个元素作为基准
    while (low < high) {
        while (low < high && arr[high] >= pivot) // 从右向左找小于基准的元素
            high--;
        arr[low] = arr[high]; // 将小于基准的元素移到左边
        while (low < high && arr[low] <= pivot) // 从左向右找大于基准的元素
            low++;
        arr[high] = arr[low]; // 将大于基准的元素移到右边
    }
    arr[low] = arr[0]; // 将基准元素放到正确位置
    return low; // 返回基准元素的位置
}

时间复杂度

  1. 平均时间复杂度 ：O(n log n)
  • 在大多数情况下，快速排序的时间复杂度为O(n log n)。这是因为每次分区操作将数组分成大致相等的两部分，并且需要进行log n次递归调用，每次递归调用需要O(n)的时间来进行分区操作。
  1. 最坏时间复杂度 ：O(n^2)
  • 在最坏情况下（例如，每次选择的基准都是数组的最大或最小值），快速排序的时间复杂度为O(n^2)。这种情况会导致每次分区操作只减少一个元素，从而需要进行n次递归调用，每次递归调用需要O(n)的时间来进行分区操作。
  1. 最好时间复杂度 ：O(n log n)
  • 在最好情况下（例如，每次选择的基准将数组完美地分成两半），快速排序的时间复杂度为O(n log n)。

空间复杂度

  1. 平均空间复杂度 ：O(log n)
  • 快速排序的空间复杂度主要由递归调用栈的深度决定。在平均情况下，递归调用栈的深度为O(log n)。
  1. 最坏空间复杂度 ：O(n)
  • 在最坏情况下（例如，每次选择的基准都是数组的最大或最小值），递归调用栈的深度为O(n)。

稳定性

快速排序不是稳定排序算法，即相同元素的相对顺序可能会改变。

选择排序

简单选择排序

算法思想：每次从待排序列中选出关键字最小记录作为有序序列中最后一个记录，直至最后一个记录为止。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 交换两个元素的值
void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// 简单选择排序函数
void selectionSort(int arr[], int n) {
    for (int i = 0; i < n-1; i++) {
        // 找到未排序部分的最小元素
        int min_idx = i;
        for (int j = i+1; j < n; j++) {
            if (arr[j] < arr[min_idx]) {
                min_idx = j;
            }
        }
        // 交换找到的最小元素和当前元素
        swap(&arr[min_idx], &arr[i]);
    }
}

时间复杂度

  • 最坏情况时间复杂度 ：O($n^2$)
  • 平均情况时间复杂度 ：O($n^2$)
  • 最好情况时间复杂度 ：O($n^2$)

空间复杂度

  • 空间复杂度 ：O(1)

稳定性

  • 稳定性 ：不稳定

树形选择排序

只有这一页ppt….盲猜不靠

1733983455162

堆排序

堆排序用数的结构特征来描述数组中的元素，通过给线性空间中的元素赋予树的逻辑结构来进行排序。

大根堆和小根堆

大根堆和小根堆是堆数据结构的两种类型，分别用于不同的排序和优先级队列操作。

大根堆（Max Heap）

大根堆是一种完全二叉树，其中每个节点的值都大于或等于其子节点的值。换句话说，大根堆的根节点是整个堆中的最大值。但是大根堆通常用于构建升序排列，这会在后面解释。

特点：
  1. 根节点的值是最大值。
  2. 每个子树也是一个大根堆。

示例：

1
2
3
4
5
    10
   /  \
  9    8
 / \  / \
7  6 5  4

小根堆（Min Heap）

小根堆是一种完全二叉树，其中每个节点的值都小于或等于其子节点的值。换句话说，小根堆的根节点是整个堆中的最小值。小根堆则用于构建降序排列。

特点：
  1. 根节点的值是最小值。
  2. 每个子树也是一个小根堆。

示例：

1
2
3
4
5
    1
   / \
  3   2
 / \ / \
5  4 6  7

堆排序的基本思想(升序为例)

  1. 构建大根堆
    • 将无序数组构建成一个大根堆。
  2. 交换堆顶元素与末尾元素
    • 将关键字的最大记录与无序区的最后一个元素交换位置。（这里就是为什么大根堆构建升序的原因）
  3. 调整堆
    • 由于交换后的堆顶元素可能不再符合大根堆的性质，需要对堆顶元素进行调整，使其重新满足大根堆的性质。
  4. 重复步骤2和3
    • 对剩余元素 重复步骤2和3，逐步构建有序区

算法实现

构建大根堆代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//arr[0]也存放数据
void HeapAdjust(int arr[], int i, int length) {
    int temp = arr[i];  // 将当前节点的值存储在临时变量中
    int child;
    for (; 2 * i + 1 < length; i = child) {
        child = 2 * i + 1;  // 遍历每一个左子结点
        if (child + 1 < length && arr[child] < arr[child + 1]) {
            child++;  // 找到左右子结点中较大的一个
        }
        if (temp < arr[child]) {
            arr[i] = arr[child];  // 如果子结点大于父结点，则交换
        } else {
            break;  // 如果当前节点的值大于或等于较大的子节点的值，则调整结束
        }
    }
    arr[i] = temp;  // 将临时变量的值赋给当前节点
}

堆排序并且调整堆顶代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
void HeapSort(int arr[], int length) {
    // 构建大根堆
    for (int i = length / 2 - 1; i >= 0; i--) {
        HeapAdjust(arr, i, length);
    }
    // 调整大根堆
    for (int i = length - 1; i > 0; i--) {
        int temp = arr[0];  // 将堆顶元素与末尾元素进行交换
        arr[0] = arr[i];
        arr[i] = temp;
        HeapAdjust(arr, 0, i);  // 重新调整堆
    }
}

时间复杂度

堆排序的时间复杂度可以分为两个部分：构建堆和排序过程。

  1. 构建堆 ：
  • 构建最大堆的过程需要将无序数组转换为堆结构。这个过程的时间复杂度为 O(n)，其中 n 是数组的长度。
  1. 排序过程 ：
  • 在堆构建完成后，堆排序通过反复将堆顶元素（最大值）与堆的最后一个元素交换，然后对剩余的元素重新调整堆。每次调整堆的时间复杂度为 O(log n)，因为堆的高度为 log n。
  • 由于需要进行 n 次这样的调整，所以排序过程的时间复杂度为 O(n log n)。

综合起来，堆排序的总时间复杂度为 O(n log n)。

空间复杂度

堆排序是一种原地排序算法，它只需要常数级别的额外空间来存储临时变量。因此，堆排序的空间复杂度为 O(1)。

稳定性

堆排序不是稳定排序。

归并排序

概念：指将两个或两个以上的同序序列归并成一个序列的操作。

两路归并排序

算法思想：

  1. 将长度为n的序列R看成n个长度为1的有序序列，两两归并，得到[n/2]个长度为2的有序子序列，或最后一个子序列长度为1。
  2. 继续将所有的子序列两两归并，直到只剩下一个有序序列为止。

1734140462887

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
// 归并排序函数
void mergeSort(int arr[], int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
  
        // 递归排序左右两半
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
  
        // 合并已排序的两半
        merge(arr, left, mid, right);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
// 合并两个有序子数组
void merge(int arr[], int left, int mid, int right) {
    int i, j, k;
    int n1 = mid - left + 1;
    int n2 = right - mid;
  
    // 创建临时数组
    int *L = (int*)malloc(n1 * sizeof(int));
    int *R = (int*)malloc(n2 * sizeof(int));
  
    // 复制数据到临时数组
    for (i = 0; i < n1; i++)
        L[i] = arr[left + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[mid + 1 + j];
  
    // 合并临时数组到原数组
    i = 0;
    j = 0;
    k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }
  
    // 复制剩余元素
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
  
    // 释放临时数组
    free(L);
    free(R);
}

时间复杂度

两路归并排序的时间复杂度可以分为两个部分：分解和合并。

  1. 分解过程 ：
  • 每次将数组分成两半，直到每个子数组只有一个元素。
  • 分解过程的时间复杂度为 O(log n)，因为每次分解将数组大小减半。
  1. 合并过程 ：
  • 合并两个有序子数组的时间复杂度为 O(n)，因为需要遍历每个元素一次。
  • 由于需要进行 log n 次合并，所以合并过程的总时间复杂度为 O(n log n)。

综合起来，归并排序的总时间复杂度为 O(n log n)。

空间复杂度

归并排序的空间复杂度主要由以下两部分组成：

  1. 递归调用栈 ：
  • 递归调用的深度为 log n，因此递归调用栈的空间复杂度为 O(log n)。
  1. 临时数组 ：
  • 在合并过程中需要临时数组来存储中间结果，临时数组的大小为 O(n)。

综合起来，归并排序的总空间复杂度为 O(n)

稳定性

两路归并排序是稳定性排序

自然两路归并排序

自然两路归并排序（Natural Merge Sort）是一种改进的归并排序算法，它利用了输入序列中已经存在的有序子序列来减少排序的工作量。其基本思想是：

  1. 识别自然有序子序列 ：
  • 扫描输入序列，识别并分割出已经有序的子序列。
  1. 合并有序子序列 ：
  • 将相邻的有序子序列两两合并，直到整个序列有序。

基数排序(分配排序)

基数排序（Radix Sort）是一种非比较排序算法，它通过逐位处理数字来实现排序。基数排序可以处理整数或字符串。其基本思想是将待排序的元素按位数进行排序，从最低位到最高位，依次进行排序，最终得到有序序列。

两个基本概念：

rd：排序元素的进制。例：排序元素都是十进制数，则rd = 10。

d：排序所有元素中，位数最长的元素的位数。

例如对于10进制数：{ 477 241 467 5 363 81 5 } 进行排序，rd = 10,d = 3。

链式基数排序示例

对于链式基数排序示例，只是通过链表的方式对于各元素进行分类，其具体实现类似链地址法实现的哈希表，我们同样以 { 477 241 467 5 363 81 5 } 为例子进行排序演示：

第一步：根据个位元素进行分配：

1734142727316

分配完成后，在从小到大对于元素进行收集：

1734142765102

第二步：根据十位元素进行分配(此时十进制位相同，但是个位小的会先分配，靠近链表头节点)：

1734142812704

分配完成后再从小到大进行收集(收集时，从每个链表的根结点开始收集，保证十位相同但是个位小的先收集)：

1734142843389

第三步：根据百位的大小进行分配：

1734143018432

分配完成后从小到达进行收集。得到的就是d为三的序列的有序序列，若d越大，则需要进行越多的步骤。

1734143091576

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 基数排序函数
void radixSort(int arr[], int n) {
    struct Node* buckets[10] = {NULL};
    struct Node* tails[10] = {NULL};
    int exp = 1;
    int max = getMax(arr, n);
  
    // 逐位排序
    while (max / exp > 0) {
        distribute(arr, n, buckets, tails, exp);
        collect(arr, n, buckets, tails);
        exp *= 10;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 分配元素到桶中
void distribute(int arr[], int n, struct Node* buckets[], struct Node* tails[], int exp) {
    for (int i = 0; i < n; i++) {
        int bucketIndex = (arr[i] / exp) % 10;
        struct Node* temp = (struct Node*)malloc(sizeof(struct Node));
        temp->data = arr[i];
        temp->next = NULL;
        if (buckets[bucketIndex] == NULL) {
            buckets[bucketIndex] = temp;
            tails[bucketIndex] = temp;
        } else {
            tails[bucketIndex]->next = temp;
            tails[bucketIndex] = temp;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 从桶中收集元素
void collect(int arr[], int n, struct Node* buckets[], struct Node* tails[]) {
    int k = 0;
    for (int i = 0; i < 10; i++) {
        struct Node* temp = buckets[i];
        while (temp != NULL) {
            arr[k++] = temp->data;
            struct Node* del = temp;
            temp = temp->next;
            free(del);
        }
        buckets[i] = NULL;
        tails[i] = NULL;
    }
}

时间复杂度

链式基数排序的时间复杂度主要由以下几个部分组成：

  1. 找到最大值的时间复杂度 ：
  • 需要遍历整个数组找到最大值，时间复杂度为 O(n)。
  1. 逐位排序的时间复杂度 ：
  • 对每一位进行排序，从最低位到最高位。假设最大值有 d 位，每个位上的排序时间复杂度为 O(n)。
  • 总的时间复杂度为 O(d * n)。

空间复杂度

链式基数排序的空间复杂度主要由以下几个部分组成：

  1. 链表节点的空间 ：
  • 每个元素在分配到桶中时需要创建一个链表节点，空间复杂度为 O(n)。
  1. 桶数组的空间 ：
  • 桶数组的大小为固定的 10（基数为 10），空间复杂度为 O(1)。

因此，链式基数排序的总空间复杂度为 O(n)。

稳定性

是稳定排序。

总结

1734145022050

笔记
#数据结构
数据结构排序算法
http://blog.ulna520.com/2024/12/11/数据结构排序算法_20241211_155400/
Veröffentlicht am
December 11, 2024
Urheberrechtshinweis