算法 | 基础排序算法：插入排序、选择排序、交换排序、归并排序

排序算法

在计算机科学中，排序是一项基础且重要的任务。不同的排序算法适用于不同的场景，了解各种排序算法的原理和特点对于优化程序性能至关重要。

一、排序概念及运用

1. 概念

排序是使一串记录按照其中的某个或某些关键字的大小，递增或递减地排列起来的操作。

2. 运用

在日常生活中，购物筛选排序和院校排名等场景都用到了排序算法。

3. 常见排序算法

常见的排序算法有插入排序、选择排序、交换排序、归并排序等。

二、实现常见排序算法

1. 插入排序

1.1 基本思想

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

1.2 直接插入排序

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

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

• 特性总结：
  • 元素集合越接近有序，直接插入排序算法的时间效率越高。
  • 时间复杂度：O(N^2)。
  • 空间复杂度：O(1)。

1.3 希尔排序

• 希尔排序法又称缩小增量法。先选定一个整数（通常是gap = n/3 + 1），把待排序文件所有记录分成各组，所有距离相等的记录分在同一组内，并对每一组内的记录进行排序，然后gap = gap / 3 + 1得到下一个整数，再将数组分成各组，进行插入排序，当gap = 1时，就相当于直接插入排序。

void ShellSort(int* a, int n) {
    int gap = n;
    while (gap > 1) {
        gap = gap / 3 + 1;
        for (int i = 0; i < n - gap; i++) {
            int end = i;
            int tmp = a[end + gap];
            while (end >= 0) {
                if (a[end] > tmp) {
                    a[end + gap] = a[end];
                    end -= gap;
                } else {
                    break;
                }
            }
            a[end + gap] = tmp;
        }
    }
}

• 特性总结：
  • 希尔排序是对直接插入排序的优化。
  • 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序，这样整体而言，可以达到优化的效果。

2. 选择排序

2.1 基本思想

每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。

2.2 直接选择排序

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

void SelectSort(int* a, int n) {
    int begin = 0, end = n - 1;
    while (begin < end) {
        int mini = begin, maxi = begin;
        for (int i = begin; i <= end; i++) {
            if (a[i] > a[maxi]) {
                maxi = i;
            }
            if (a[i] < a[mini]) {
                mini = i;
            }
        }
        if (begin == maxi) {
            maxi = mini;
        }
        swap(&a[mini], &a[begin]);
        swap(&a[maxi], &a[end]);
        ++begin;
        --end;
    }
}

• 特性总结：
  • 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用。
  • 时间复杂度：O(N^2)。
  • 空间复杂度：O(1)。

2.3 堆排序

堆排序是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。通过堆来进行选择数据。排升序要建大堆，排降序建小堆。

3. 交换排序

3.1 基本思想

根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置。交换排序的特点是将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。

3.2 冒泡排序

• 代码实现：

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

• 特性总结：
  • 时间复杂度：O(N^2)。
  • 空间复杂度：O(1)。

3.3 快速排序

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

//快速排序
void QuickSort(int* a, int left, int right) {
    if (left >= right) {
        return;
    }
    int meet = _QuickSort(a, left, right);
    QuickSort(a, left, meet - 1);
    QuickSort(a, meet + 1, right);
}

• _QuickSort方法有多种实现方式，如 hoare 版本、挖坑法、lomuto 前后指针等。
• 特性总结：
  • 时间复杂度：O(nlogn)。
  • 空间复杂度：O(logn)。

3.4 非递归版本

非递归版本的快速排序需要借助数据结构栈。

4. 归并排序

4.1 算法思想

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

4.2 代码实现

void _MergeSort(int* a, int left, int right, int* tmp) {
    if (left >= right) {
        return;
    }
    int mid = (right + left) / 2;
    _MergeSort(a, left, mid, tmp);
    _MergeSort(a, mid + 1, right, tmp);
    int begin1 = left, end1 = mid;
    int begin2 = mid + 1, end2 = right;
    int index = begin1;
    while (begin1 <= end1 && begin2 <= end2) {
        if (a[begin1] < a[begin2]) {
            tmp[index++] = a[begin1++];
        } else {
            tmp[index++] = a[begin2++];
        }
    }
    while (begin1 <= end1) {
        tmp[index++] = a[begin1++];
    }
    while (begin2 <= end2) {
        tmp[index++] = a[begin2++];
    }
    for (int i = left; i <= right; i++) {
        a[i] = tmp[i];
    }
}

void MergeSort(int* a, int n) {
    int* tmp = new int[n];
    _MergeSort(a, 0, n - 1, tmp);
    delete[] tmp;
}

• 特性总结：
  • 时间复杂度：O(nlogn)。
  • 空间复杂度：O(n)。

5. 测试代码：排序性能对比

通过生成随机数组，分别使用不同的排序算法进行排序，并记录运行时间，以比较各种排序算法的性能。

6. 非比较排序

6.1 计数排序

计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。操作步骤包括统计相同元素出现次数，然后根据统计结果将序列回收到原来的序列中。

void CountSort(int* a, int n) {
    int min = a[0], max = a[0];
    for (int i = 1; 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) {
        perror("malloc fail");
        return;
    }
    memset(count, 0, sizeof(int) * range);
    for (int i = 0; i < n; i++) {
        count[a[i] - min]++;
    }
    int j = 0;
    for (int i = 0; i < range; i++) {
        while (count[i]--) {
            a[j++] = i + min;
        }
    }
}

• 特性：计数排序在数据范围集中时，效率很高，但是适用范围及场景有限。时间复杂度：O(N + range)，空间复杂度：O(range)，稳定性：稳定。

三、排序算法复杂度及稳定性分析

稳定性是指在待排序的记录序列中，存在多个具有相同关键字的记录时，经过排序后，这些记录的相对次序保持不变。不同的排序算法在平均情况、最好情况、最坏情况、辅助空间和稳定性方面有所不同。

例如：

• 冒泡排序：时间复杂度O(n^2)，最好情况O(n)，最坏情况O(n^2)，辅助空间O(1)，稳定。
• 直接选择排序：时间复杂度O(n^2)，最好情况O(n^2)，最坏情况O(n^2)，辅助空间O(1)，不稳定。
• 直接插入排序：时间复杂度O(n^2)，最好情况O(n)，最坏情况O(n^2)，辅助空间O(1)，稳定。
• 希尔排序：时间复杂度在O(nlog n) ~ O(n^2)之间，最好情况O(n^1.3)，最坏情况O(n^2)，辅助空间O(1)，不稳定。
• 堆排序：时间复杂度O(nlog n)，最好情况、最坏情况都是O(nlog n)，辅助空间O(1)，不稳定。
• 归并排序：时间复杂度O(nlog n)，最好情况、最坏情况都是O(nlog n)，辅助空间O(n)，稳定。
• 快速排序：时间复杂度O(nlog n)，最好情况O(nlog n)，最坏情况O(n^2)，辅助空间O(log n) ~ O(n)，不稳定。

通过稳定性验证案例可以更直观地理解不同排序算法的稳定性特点。

总之，了解各种排序算法的原理、特性和适用场景，可以帮助我们在实际编程中选择合适的排序算法，提高程序的性能和效率。