排序大全

Kingdom_Tears · 2025-08-13 21:00:58 · 算法·理论

冒泡排序

冒泡排序是一种简单直观的排序算法。它通过重复地遍历要排序的数列，一次比较两个相邻的元素，如果它们的顺序错误就交换它们的位置。这个过程会一直重复，直到没有需要交换的元素为止，从而使整个数列有序

代码示例：

#include <iostream>
using namespace std;

void print(int arr[], int n) {
  for (int j = 0; j < n; j++) {
    cout << arr[j] << " ";
}
  cout << endl;
}

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

int main() {
  int s[10] = {8, 1, 9, 7, 2, 4, 5, 6, 10, 3};
  cout << "初始序列：";
  print(s, 10);
  BubbleSort(s, 10);
  cout << "排序结果：";
  print(s, 10);
  return 0;
}

时间复杂度：冒泡排序的时间复杂度为O(n^2)，其中n是数组的长度。在最坏情况下（即数组是逆序的），需要进行\frac{n(n-1)}{2}次比较和交换

空间复杂度：冒泡排序的空间复杂度为O(1)，因为它只需要一个额外的临时变量来交换元素的位置

稳定性：冒泡排序是稳定的排序算法，因为它不会改变相同元素的相对位置

插入排序

插入排序是一种简单直观的排序算法，其工作原理是通过构建有序序列，对未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。这种算法在数据量小或者部分数据已经有序的情况下效率较高，是稳定的排序方法

代码示例：

#include <iostream>
using namespace std;

void insertSort(int a[], int n) {
  for (int i = 1; i < n; i++) { // 从第二个元素开始
  int key = a[i]; // 当前待插入的元素
  int j = i - 1;
  // 从后向前扫描已排序序列，找到插入位置
  while (j >= 0 && a[j] > key) {
    a[j + 1] = a[j]; // 将大于key的元素后移
    j--;
  }
  a[j + 1] = key; // 将key插入到正确位置
  }
}

void printArray(int a[], int n) {
  for (int i = 0; i < n; i++) {
  cout << a[i] << " ";
  }
  cout << endl;
}

int main() {
  int a[] = {8, 1, 9, 7, 2, 4, 5, 6, 10, 3};
  int n = sizeof(a) / sizeof(a[0]);
  insertSort(a, n);
  printArray(a, n);
  return 0;
}

最优时间复杂度：当待排序数组已经是有序的情况下，每个元素只需与前一个元素比较一次，无需移动其他元素。此时，比较次数为 n-1，移动次数为 0，时间复杂度为 O(n)

最坏时间复杂度：当待排序数组是完全逆序时，每次插入都需要将当前元素与前面所有已排序的元素进行比较，并将这些元素逐一后移。此时，比较次数和移动次数均为 \frac{n(n-1)}{2}，时间复杂度为 O(n²)

平均时间复杂度：在一般情况下，插入排序的比较和移动次数介于最优和最坏之间，其平均时间复杂度为 O(n²)

空间复杂度：插入排序只需要常量级的辅助空间（如临时变量），因此空间复杂度为 O(1)

稳定性：插入排序是一种稳定的排序算法，因为在插入过程中不会改变相同元素的相对顺序

选择排序

选择排序是一种简单直观的排序算法，其工作原理是在未排序序列中找到最小（或最大）元素，将其存放到排序序列的起始位置，然后再从剩余未排序元素中继续寻找最小（或最大）元素，以此类推

代码示例：

#include<iostream>
using namespace std;

void select_sort(int* a, int n) {
  for (int i = 0; i < n - 1; i++) {
    int min_index = i;
    for (int j = i + 1; j < n; j++) {
      if (a[j] < a[min_index])
        min_index = j;
    }
    if(min_index != i) {
      swap(a[i], a[min_index]);
    }
  }
}

int main() {
  int arr[] = {64, 25, 12, 22, 11};
  int n = sizeof(arr)/sizeof(arr[0]);
  select_sort(arr, n);
  cout << "Sorted array: \n";
  for (int i = 0; i < n; i++)
  cout << arr[i] << " ";
  cout << endl;
}

时间复杂度：选择排序的时间复杂度主要取决于比较和交换操作的次数。无论输入序列的初始状态如何，选择排序的比较次数都是固定的，即： [ (n-1) + (n-2) + ... + 2 + 1 = \frac{n(n-1)}{2} ] 因此，选择排序的比较次数为 (O(n^2)) 。 对于交换操作，最好的情况下（序列已经有序），交换次数为 0；最坏的情况下（序列完全逆序），交换次数为 (n-1)。但由于交换次数相对于比较次数较少，因此选择排序的总时间复杂度仍然为 (O(n^2))

稳定性：选择排序是不稳定的排序算法。原因在于，在排序过程中，如果一个元素比当前元素小，而该小的元素又出现在一个和当前元素相等的元素后面，那么交换后稳定性就被破坏了。例如，在序列 [5, 8, 5, 2, 9] 中，第一次选择时，第一个 5 会与 2 交换位置，这样原序列中两个 5 的相对顺序就被破坏了

归并排序

归并排序是一种高效的排序算法，它采用分治法的策略，将问题分解为一些小问题然后递归求解，而后将解决的部分合并成整体的解决方案

代码示例：

#include <iostream>
using namespace std;

// 合并函数，将两个有序数组合并为一个有序数组
void merge(int* a, int low, int mid, int high) {
  int* b = new int[high - low + 1];
  int i = low, j = mid + 1, k = 0;
  while (i <= mid && j <= high) {
    if (a[i] <= a[j]) {
    b[k++] = a[i++];
    } else {
    b[k++] = a[j++];
    }
  }
  while (i <= mid) {
    b[k++] = a[i++];
  }
  while (j <= high) {
    b[k++] = a[j++];
  }
  for (int i = low; i <= high; i++) {
    a[i] = b[i - low];
  }
  delete[] b;
}

// 归并排序函数
void mergeSort(int* a, int low, int high) {
  if (low < high) {
  int mid = (low + high) / 2;
  mergeSort(a, low, mid);
  mergeSort(a, mid + 1, high);
  merge(a, low, mid, high);
  }
}

int main() {
  int a[] = {42, 15, 20, 6, 8, 38, 50, 12};
  int n = sizeof(a) / sizeof(a[0]);
  mergeSort(a, 0, n - 1);
  for (int i = 0; i < n; i++) {
    cout << a[i] << " ";
  }
  cout << endl;
  return 0;
}

时间复杂度：归并排序的时间复杂度主要由两个部分组成：数组分割和数组合并。在分割阶段，数组被递归地分成两半，直到每个子数组只有一个元素，这个过程的时间复杂度是 O(log_n)，因为每次分割都将数组的大小减半。在合并阶段，每个元素都需要被比较和移动以合并两个子数组，这个过程的时间复杂度是 O(n)。 因此，归并排序的总体时间复杂度是 O(nlog_n)，这是因为每个分割步骤都需要一次完整的元素合并。这个时间复杂度适用于最好、最坏和平均情况，因为无论数组的初始顺序如何，分割和合并的步骤都是固定的

空间复杂度：归并排序的空间复杂度是 O(n)，这是因为合并过程需要与原始数组相同数量的额外空间来存储合并后的数组。这个额外的空间通常是通过一个临时数组来实现的，临时数组在整个排序过程中用于存储合并的结果

稳定性：归并排序通过递归将序列分割成小段，然后合并成有序序列。在合并过程中，如果两个元素相等，优先选择左侧的元素，因此归并排序是稳定的

快速排序

快速排序是一种高效的排序算法，它使用分治法的策略来对一个数组进行排序。其核心思想是选择一个基准元素，通过一趟排序将待排数组分割成独立的两部分，其中一部分的所有数据都比另一部分的所有数据要小，然后再对这两部分数据分别进行快速排序

代码示例：

#include<iostream>
using namespace std;

void quickSort(int a[], int low, int high) {
  if (low < high) {
    int i = low, j = high;
    int pivot = a[low];
    while (i < j) {
      while (i < j && a[j] >= pivot) j--;
      if (i < j) a[i++] = a[j];
      while (i < j && a[i] <= pivot) i++;
      if (i < j) a[j--] = a[i];
    }
    a[i] = pivot;
    quickSort(a, low, i - 1);
    quickSort(a, i + 1, high);
  }
}

int main() {
  int a[10] = {8, 1, 9, 7, 2, 4, 5, 6, 10, 3};
  cout << "初始序列：";
  for (int j = 0; j < 10; j++) cout << a[j] << " ";
  cout << endl;

  quickSort(a, 0, 9);

  cout << "排序结果：";
  for (int j = 0; j < 10; j++) cout << a[j] << " ";
  cout << endl;

  system("pause");
}

最优时间复杂度： 在理想情况下，每次划分都能将数组均匀分成两部分。此时递归深度为 log_n，每层需要遍历 n 个元素，因此时间复杂度为 O(nlog_n)

最差时间复杂度： 如果每次选择的基准值是当前数组的最大值或最小值，划分会极不均匀，导致递归深度为 n，每层仍需遍历 n 个元素。因此，最差时间复杂度为 O(n²)

平均时间复杂度： 在随机分布的情况下，快速排序的平均时间复杂度为 O(nlog_n)，这是其实际应用中最常见的表现

稳定性：在分区时，枢轴元素的交换可能导致相等元素的顺序被打乱，因此是不稳定的

希尔排序

希尔排序，也称为缩小增量排序，是一种基于插入排序的排序算法。它通过将整个序列分割成若干子序列分别进行插入排序，从而提高排序效率

代码示例：

#include <iostream>
using namespace std;

void ShellSort(int *arr, int len) {
  int grp = len / 2; // 计算增量
  while (grp > 0) {
    for (int i = grp; i < len; i++) {
      int cur = arr[i]; // 当前元素
      int j = i - grp;
      while (j >= 0 && arr[j] > cur) {
        arr[j + grp] = arr[j]; // 移动元素
        j -= grp;
      }
      arr[j + grp] = cur; // 插入元素
    }
    grp /= 2; // 缩小增量
  }
}

int main() {
  int arr[] = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
  int len = sizeof(arr) / sizeof(arr[0]);
  ShellSort(arr, len);
  for (int i = 0; i < len; i++) {
    cout << arr[i] << ", ";
  }
  cout << endl;
  return 0;
}

复杂度：希尔排序的时间复杂度并不是一个固定的值，而是根据增量序列的不同而有所变化。在最好的情况下，希尔排序的时间复杂度可以达到 O(nlog_n)，而在平均和最坏的情况下，时间复杂度通常被认为是O(n^{1.3})。然而，由于增量序列的选择对希尔排序的性能有着重要影响，因此在实际应用中需要根据具体情况选择合适的增量序列

稳定性：希尔排序是一种基于插入排序的改进算法，通过分组和逐步缩小间隔来对数据进行排序。然而，它并不是一种稳定的排序算法。 在排序过程中，希尔排序会根据不同的步长对数据进行多次插入排序。虽然单次插入排序是稳定的，但在不同步长的插入排序中，相同的元素可能会被移动到不同的位置，从而打乱它们的相对顺序。这种特性导致了希尔排序的不稳定性

堆排序

堆排序是一种基于堆数据结构的比较排序算法。在堆排序中，我们首先将待排序的序列构建成一个大顶堆，然后将堆顶元素与序列末尾元素交换，再调整剩余元素构成新的大顶堆。这个过程重复进行，直到整个序列变成有序序列。

代码示例：

#include <iostream>
using namespace std;

// 调整大顶堆
void adjustHeap(int arr[], int i, int length) {
  int temp = arr[i];
  for (int k = i * 2 + 1; k < length; k = k * 2 + 1) {
    if (k + 1 < length && arr[k] < arr[k + 1]) {
      k++;
    }
    if (arr[k] > temp) {
      arr[i] = arr[k];
      i = k;
    } else {
      break;
    }
  }
  arr[i] = temp;
}

// 堆排序
void heapSort(int arr[], int length) {
  // 构建大顶堆
  for (int i = length / 2 - 1; i >= 0; i--) {
    adjustHeap(arr, i, length);
  }
  // 排序
  for (int j = length - 1; j > 0; j--) {
    swap(arr[0], arr[j]); // 将堆顶元素与末尾元素交换
    adjustHeap(arr, 0, j); // 重新调整堆
  }
}

int main() {
  int arr[] = {9, 79, 46, 30, 58, 49};
  int n = sizeof(arr) / sizeof(arr[0]);
  heapSort(arr, n);
  for (int i = 0; i < n; ++i) {
    cout << arr[i] << " ";
  }
  cout << endl;
  return 0;
}

时间复杂度：堆排序的时间复杂度主要包括两个部分：建立初始堆和每次选取最大数后重新建堆的过程。 建立初始堆的时间复杂度：在调整堆时，每交换一次节点，最多比较关键字 2 次。假设一颗完全二叉树，树高为h，最后一层节点无需进行调整。根据计算，建立初始堆的时间复杂度为 O(n) 。 重建堆的时间复杂度：每次将堆顶元素与堆底元素进行交换后，需要将剩余待排序元素重新建堆。此时处理的是堆顶元素，即根节点。根节点位于第一层，关键字最多比较次数为 2×(h−1) 次。上述过程共需进行 n-1 次，故重建堆的时间复杂度为 O(nlog_n)

综上所述，堆排序的总时间复杂度为O(nlog_n)

空间复杂度：堆排序是一种就地排序算法，即在排序过程中只需要常数级别的额外空间。因此，堆排序的空间复杂度为 O(1)

稳定性：堆排序是一种基于堆数据结构的排序算法，其不稳定性主要源于排序过程中元素位置的调整和交换操作。 在建堆阶段，堆排序会将待排序的元素构建成一个堆（大顶堆或小顶堆）。从最后一个非叶子节点开始，逐步向上调整以满足堆的性质。在这个过程中，可能需要交换节点的位置。如果两个元素的键值相同，交换操作可能会改变它们在原始数组中的相对顺序，从而导致不稳定性。 在排序阶段，堆排序通过反复从堆顶取出最大（或最小）元素，将其放置到已排序部分的末尾。然后对剩余未排序部分重新调整堆结构。这一过程中同样涉及交换操作，进一步破坏了相同键值元素的相对顺序。 堆排序的不稳定性归因于其核心操作——通过交换调整堆结构。这种交换可能导致相同键值的元素在排序后顺序发生变化。如果需要稳定的排序算法，可以选择冒泡排序、插入排序或归并排序等稳定算法

计数排序

计数排序是一种非比较型的排序算法，它的基本思想是统计待排序数组中每个元素的出现次数，然后根据统计信息将元素放置到正确的位置上，从而实现排序。这种算法特别适用于整数排序，尤其是当输入数据范围不是很大时，其性能表现非常出色

代码示例：

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 计数排序函数
// 参数：待排序数组，排序结果将存储在原数组中
void countingSort(vector<int>& arr) {
    if (arr.empty()) return;

    // 找到数组中的最大值和最小值，确定数据范围
    int min_val = *min_element(arr.begin(), arr.end());
    int max_val = *max_element(arr.begin(), arr.end());

    // 计算计数数组的大小
    int range = max_val - min_val + 1;

    // 创建计数数组并初始化
    vector<int> count(range, 0);
    vector<int> output(arr.size());

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

    // 计算前缀和，确定每个元素在输出数组中的位置
    for (int i = 1; i < count.size(); i++) {
        count[i] += count[i - 1];
    }

    // 构建输出数组（从后往前遍历，保持稳定性）
    for (int i = arr.size() - 1; i >= 0; i--) {
        output[count[arr[i] - min_val] - 1] = arr[i];
        count[arr[i] - min_val]--;
    }

    // 将排序结果复制回原数组
    arr = output;
}

// 测试函数
int main() {
    // 测试用例1
    vector<int> arr1 = {4, 2, 2, 8, 3, 3, 1};
    cout << "排序前: ";
    for (int num : arr1) {
        cout << num << " ";
    }
    cout << endl;

    countingSort(arr1);

    cout << "排序后: ";
    for (int num : arr1) {
        cout << num << " ";
    }
    cout << endl << endl;

    // 测试用例2（包含负数）
    vector<int> arr2 = {-2, 5, 3, -5, 2, 8, -1};
    cout << "排序前: ";
    for (int num : arr2) {
        cout << num << " ";
    }
    cout << endl;

    countingSort(arr2);

    cout << "排序后: ";
    for (int num : arr2) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}

时间复杂度：O(n + k)

其中 n 是元素数量，k 是数据范围（max_val - min_val + 1）。主要由查找最值O (n)、统计次数 O (n)、计算前缀和 O(k)、构建输出数组 O (n) 等步骤构成，整体呈线性增长

空间复杂度：O(n + k)

需额外占用两个数组：大小为 k 的计数数组（存储元素出现次数）和大小为 n的输出数组（存储排序结果）

桶排序

桶排序是一种分布式排序算法，它通过将数组分成多个区间，即“桶”，来组织数据。每个桶代表一个值范围的集合，然后单独对每个桶进行排序，最后将它们合并以得到排序完成的数组

代码示例：

#include <bits/stdc++.h>
using namespace std;

void bucketSort(vector<int>& arr) {
  int n = arr.size();
  if (n <= 1) return;

  int maxVal = *max_element(arr.begin(), arr.end());
  int minVal = *min_element(arr.begin(), arr.end());
  int bucketSize = maxVal - minVal + 1;
  int bucketCount = 10; // 桶的数量
  vector<vector<int>> bucket(bucketCount);

  // 将元素分配到桶中
  for (int num : arr) {
    int index = (num - minVal) * bucketCount / bucketSize;
    bucket[index].push_back(num);
  }

  // 对每个桶中的元素进行排序
  for (auto& b : bucket) {
    sort(b.begin(), b.end());
  }

  // 将排序后的元素依次放回原数组
  int index = 0;
  for (auto& b : bucket) {
    for (int num : b) {
      arr[index++] = num;
    }
  }
}

int main() {
  vector<int> arr = {61, 17, 29, 22, 34, 60, 72, 21, 50, 1, 62};
  bucketSort(arr);
  for (int nums : arr) {
    printf("%d ", nums);
  }
  return 0;
}

最优时间复杂度： 假设有 n 个元素，恰好均匀地分配到 k 个桶中。分配过程我们需要消耗 O(n) 的时间，对每个桶单独排序，消耗了 kO(\frac{n}{k}log_\frac{n}{k}) 的时间，化简可得 nO(log_\frac{n}{k})。我们一般设 c = log_\frac{n}{k}， 由此的时间复杂度为 O(n + c) 。在极端情况下，我们的元素个数和桶的个数十分接近时，即 n = k 时，我们都不需要进行桶内排序，此时的时间复杂度为 O(n)

最坏时间复杂度： 如果 n 个元素分配到 k 个桶中非常地不均匀，我们的每一个桶之间，有的桶中元素非常多，有的则非常少，那么对于那个元素非常多的桶，我们需要很多时间去进行桶内排序。极端情况下，假设有两个桶，其中一个有10000个元素，另一个只有一个元素，那么我们的时间消耗几乎和使用的桶内排序算法的时间复杂度几乎无异。O(n + log_{\frac{n}{k}}) 其中 n远大于k，那么时间复杂度几乎就是 O(nlog_n) 了

稳定性：桶排序是稳定的排序算法，只要内部排序是稳定的，并且在放入桶中时不改变元素间的相对顺序

小结

排序算法在C++中的实现通常涉及数组操作和递归调用。选择合适的排序算法取决于数据的大小、数据的结构和性能要求