目录

• • 7种排序算法的时间复杂度和稳定性及其稳定性
  • • 不稳定排序算法巧妙记法
    • 不稳定排序算法的定义
  • 7种排序算法的C++实现（以数组为例）
  • • 1. **冒泡排序**（Bubble Sort）
    • 2. **选择排序**（Selection Sort）
    • 3. **插入排序**（Insertion Sort）
    • 4. **希尔排序**（Shell Sort）
    • 5. **归并排序**（Merge Sort）
    • 6. **快速排序**（Quick Sort）
    • 7. **堆排序**（Heap Sort）

7种排序算法的时间复杂度和稳定性及其稳定性

不稳定排序算法巧妙记法

一堆希尔快选择！
一堆（堆排序）希尔（希尔排序）快（快速排序）选择（选择排序）

不稳定排序算法的定义

在排序过程中，相等的元素在最终排序完成后可能会改变它们原始的相对顺序。换句话说，如果两个元素在原始数组中是相邻的，并且它们的值相同，但在排序后的数组中它们的相对顺序发生了变化，那么这个排序算法就是不稳定的。

举个例子来说明不稳定排序算法：

假设我们有一个数组

[5, 3, 4, 5, 5]

并且我们使用快速排序算法对其进行排序。

在快速排序的过程中，我们选择第一个元素 5 作为基准。
然后我们对数组进行分区，使得所有小于 5 的元素都在 5 的左边，所有大于 5 的元素都在 5 的右边。
分区后，数组变为

[ 3, 5, 4, 5, 5]

此时两个 5 的相对位置发生了变化。

7种排序算法的C++实现（以数组为例）

1. 冒泡排序（Bubble Sort）

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])                 swap(arr[j], arr[j+1]); } 

2. 选择排序（Selection Sort）

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[i], arr[min_idx]);     } } 

3. 插入排序（Insertion Sort）

void insertionSort(int arr[], int n) {     int i, key, j;     for (i = 1; i < n; i++) {         key = arr[i];         j = i - 1;         while (j >= 0 && arr[j] > key) {             arr[j + 1] = arr[j];             j = j - 1;         }         arr[j + 1] = key;     } } 

4. 希尔排序（Shell Sort）

void shellSort(int arr[], int n) {     for (int gap = n/2; gap > 0; gap /= 2) {         for (int i = gap; i < n; i++) {             int temp = arr[i];             int j;             for (j = i; j >= gap && arr[j - gap] > temp; j -= gap)                 arr[j] = arr[j - gap];             arr[j] = temp;         }     } } 

5. 归并排序（Merge Sort）

void merge(int arr[], int l, int m, int r) {     int n1 = m - l + 1, n2 = r - m;     int L[n1], R[n2];     for (int i = 0; i < n1; i++)         L[i] = arr[l + i];     for (int j = 0; j < n2; j++)         R[j] = arr[m + 1 + j];     int i = 0, j = 0, k = l;     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++;     } }  void mergeSort(int arr[], int l, int r) {     if (l < r) {         int m = l + (r - l) / 2;         mergeSort(arr, l, m);         mergeSort(arr, m + 1, r);         merge(arr, l, m, r);     } } 

6. 快速排序（Quick Sort）

int partition(int arr[], int low, int high) {     int pivot = arr[high];     int i = (low - 1);     for (int j = low; j <= high - 1; j++) {         if (arr[j] < pivot) {             i++;             swap(arr[i], arr[j]);         }     }     swap(arr[i + 1], arr[high]);     return (i + 1); }  void quickSort(int arr[], int low, int high) {     if (low < high) {         int pi = partition(arr, low, high);         quickSort(arr, low, pi - 1);         quickSort(arr, pi + 1, high);     } } 

7. 堆排序（Heap Sort）

void heapify(int arr[], int n, int i) {     int largest = i;     int l = 2 * i + 1;     int r = 2 * i + 2;     if (l < n && arr[l] > arr[largest])         largest = l;     if (r < n && arr[r] > arr[largest])         largest = r;     if (largest != i) {         swap(arr[i], arr[largest]);         heapify(arr, n, largest);     } }  void heapSort(int arr[], int n) {     for (int i = n / 2 - 1; i >= 0; i--)         heapify(arr, n, i);     for (int i = n - 1; i >= 0; i--) {         swap(arr[0], arr[i]);         heapify(arr, i, 0);     } }