排序算法详细总结

算法

定义：算法是解决特定问题的明确步骤集合。算法的效率通常用时间复杂度和空间复杂度来衡量。

排序算法

定义：排序算法是计算机科学中用于对元素序列进行排序的一系列算法。排序算法在各种应用中都非常常见，从简单的数据处理到复杂的数据库和搜索引擎优化。
分类：冒泡排序（Bubble Sort）、选择排序（Selection Sort）、插入排序（Insertion Sort）、归并排序（Merge Sort）、快速排序（Quick Sort）、堆排序（Heap Sort）、希尔排序（Shell Sort）、计数排序（Counting Sort）、桶排序（Bucket Sort）、基数排序（Radix Sort）等等。

冒泡排序 Bubble Sort

定义：冒泡排序（Bubble Sort）是一种简单的排序算法，它通过重复遍历要排序的数列，比较每对相邻元素，并在顺序错误的情况下交换它们。这个过程会重复进行，直到没有再需要交换的元素为止，这意味着数列已经排序完成。冒泡排序的名字来源于较小的元素会逐渐“冒泡”到数列的顶端（开始位置）。
步骤：
- 比较相邻的元素：从数列的开始位置比较每对相邻元素，如果第一个比第二个大，则交换它们的位置。
- 遍历数列：继续比较下一对相邻元素，直到到达数列的末尾。
- 重复遍历：重复上述步骤，但每次遍历都从上一次遍历停止的位置开始，因为最后的元素已经是最大的，不需要再比较。
- 优化：在每次遍历中，如果一次完整的遍历都没有发生交换，说明数列已经排序完成，可以提前结束排序。
复杂度：
- 时间复杂度：冒泡排序的平均和最坏情况时间复杂度都是 (O(n^2))，其中 (n) 是数列的长度。这是因为算法需要进行多次遍历和比较。
- 空间复杂度：冒泡排序的空间复杂度是 (O(1))，因为它只需要一个额外的空间来存储交换的元素。
示例

#include <iostream>
#include <vector>
#include <algorithm> // 用于std::swap// 冒泡排序函数
void bubbleSort(std::vector<int>& arr) {int n = arr.size();bool swapped;for (int i = 0; i < n - 1; i++) {swapped = false;for (int j = 0; j < n - i - 1; j++) {if (arr[j] > arr[j + 1]) {// 使用std::swap交换两个元素std::swap(arr[j], arr[j + 1]);swapped = true;}}// 如果在这一轮排序中没有发生交换，说明数组已经有序，可以提前结束if (!swapped) {break;}}
}// 打印数组的函数
void printArray(const std::vector<int>& arr) {for (int num : arr) {std::cout << num << " ";}std::cout << std::endl;
}// 主函数
int main() {std::vector<int> arr = {64, 34, 25, 12, 22, 11, 90};std::cout << "Original array:\n";printArray(arr);bubbleSort(arr);std::cout << "Sorted array:\n";printArray(arr);return 0;
}

快速排序 Quick Sort

定义：由英国计算机科学家托尼·霍尔（Tony Hoare）在1960年提出。它的基本思想是分治法（Divide and Conquer），通过一个称为“基准”（pivot）的元素将数组分成两个子数组，使得左边子数组的所有元素都比基准小，右边子数组的所有元素都比基准大，然后递归地对这两个子数组进行快速排序。
基本步骤：
- 选择基准：从数组中选择一个元素作为基准（pivot）。选择基准的方法可以有多种，例如选择第一个元素、最后一个元素、中间元素，或者随机选择一个元素。
- 分区操作（Partitioning）：重新排列数组，使得所有比基准小的元素都在基准的左边，所有比基准大的元素都在基准的右边。这个过程结束后，基准元素就处于其最终位置。
- 递归排序：递归地对基准左边和右边的子数组进行快速排序。
- 返回：当子数组的大小减少到1或0时，递归结束，整个数组变为有序。
复杂度：平均时间复杂度为 O(nlogn)，但在最坏情况下（例如，数组已经是有序的，或者所有元素都相等）时间复杂度会退化到 O(n^2)。
示例：

#include <iostream>
#include <vector>// 交换两个元素
void swap(int* a, int* b) {int t = *a;*a = *b;*b = t;
}// 选择基准并进行分区
int partition(std::vector<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(std::vector<int>& arr, int low, int high) {if (low < high) {// pi 是分区后的基准索引，可以直接选择 （low+high）/2 位置作为分区索引int pi = partition(arr, low, high);// 分别对基准左边和右边的子数组进行快速排序quickSort(arr, low, pi - 1);quickSort(arr, pi + 1, high);}
}// 打印数组
void printArray(const std::vector<int>& arr) {for (int num : arr) {std::cout << num << " ";}std::cout << std::endl;
}// 主函数
int main() {std::vector<int> arr = {10, 7, 8, 9, 1, 5};int n = arr.size();std::cout << "Original array: ";printArray(arr);quickSort(arr, 0, n - 1);std::cout << "Sorted array: ";printArray(arr);return 0;
}

选择排序 Selection Sort

定义：是一种简单直观的排序算法。它的工作原理是：首先在未排序的元素中找到最小（或最大）的元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（或最大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
基本步骤：
- 从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置。
- 从剩余未排序元素中寻找最小（或最大）元素，然后放到已排序序列的末尾。
- 重复第二步，直到所有元素均排序完毕。
示例：

#include <iostream>
#include <vector>
#include <algorithm> // For std::swap()void selectionSort(std::vector<int>& arr) {int n = arr.size();for (int i = 0; i < n - 1; ++i) {// 找到从i到数组末尾部分的最小元素的索引int min_idx = i;for (int j = i + 1; j < n; ++j) {if (arr[j] < arr[min_idx]) {min_idx = j;}}// 交换当前位置i和找到的最小元素的位置std::swap(arr[i], arr[min_idx]);}
}int main() {std::vector<int> arr = {64, 25, 12, 22, 11};selectionSort(arr);std::cout << "Sorted array: ";for (int num : arr) {std::cout << num << " ";}std::cout << std::endl;return 0;
}

插入排序 Insertion Sort

定义：是一种简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为新元素提供插入空间。
基本步骤：
- 从第一个元素开始，该元素可以认为已经被排序。
- 取出下一个元素，在已经排序的元素序列中从后向前扫描。
- 如果该元素（已排序）小于新元素，将该元素移到下一位置。
- 重复步骤3，直到找到已排序元素小于或者等于新元素的位置。
- 将新元素插入到该位置后。
- 重复步骤2~5。
复杂度：时间复杂度是O(n^{2)，在小规模数据或基本有序的数据中，插入排序可以表现得非常好，因为它的最好情况和平均情况时间复杂度分别为O(n)和O(n}2)。此外，插入排序是稳定的排序算法，这意味着相等的元素之间的相对顺序不会改变。
示例：

#include <iostream>
#include <vector>void insertionSort(std::vector<int>& arr) {int n = arr.size();for (int i = 1; i < n; ++i) {int key = arr[i];int j = i - 1;// 将比key大的元素向后移动一位while (j >= 0 && arr[j] > key) {arr[j + 1] = arr[j];j = j - 1;}// 将key插入到正确的位置arr[j + 1] = key;}
}
/* 推算
n = 5
第一次循环
for(i=1; i<5; i++>)
{key=arr[i]=arr[1]=5j=i-1 = 1-1 = 0while(0>=0 && 9>5){arr[j+1]=arr[1]=a[0]=9j = j-1 = -1}arr[j+1] = arr[0] = key = 5
}
第二次循环
for(i=2; i<5; i++)
{key = arr[i] = arr[2] = 1j = i-1 = 2-1 =1//第一次whilewhile(1>=0 && arr[1]>1){arr[j+1]=arr[2] = arr[1] = 9j = j-1=0}//第二次whilewhile(0>=0 && arr[0] > 1){arr[1] = arr[0] = 5j = j-1 = -1}arr[j+1] = arr[0] = key = 1
}
...以此类推...*/int main() {std::vector<int> arr = {9, 5, 1, 4, 3};insertionSort(arr);std::cout << "Sorted array: ";for (int num : arr) {std::cout << num << " ";}std::cout << std::endl;return 0;
}

归并排序 Merge Sort

定义：是一种分治算法，其基本思想是将两个已经排序的序列合并成一个排序的序列。归并排序的效率很高，对于大数据集来说，归并排序通常比插入排序和选择排序更快。归并排序是稳定的排序算法，这意味着相等的元素之间的相对顺序不会改变。
基本步骤：
- 将当前序列分成两个等长的部分。
- 对两个部分分别进行归并排序。
- 将两个已排序的部分合并成一个排序的序列。
复杂度：归并排序的时间复杂度是O(n log n)，其中n是数组的长度。由于归并排序需要额外的存储空间来存储临时数组，因此它的空间复杂度是O(n)。
示例：

#include <iostream>
#include <vector>// 合并两个子序列的函数
void merge(std::vector<int>& arr, int left, int mid, int right) {int n1 = mid - left + 1; // 左子序列的长度int n2 = right - mid;   // 右子序列的长度// 创建临时数组std::vector<int> L(n1), R(n2);// 拷贝数据到临时数组 L[] 和 R[]for (int i = 0; i < n1; i++)L[i] = arr[left + i];for (int j = 0; j < n2; j++)R[j] = arr[mid + 1 + j];// 合并临时数组回到 arr[left..right]int i = 0; // 初始索引第一个子数组int j = 0; // 初始索引第二个子数组int k = left; // 初始索引合并的子数组while (i < n1 && j < n2) {if (L[i] <= R[j]) {arr[k] = L[i];i++;} else {arr[k] = R[j];j++;}k++;}// 拷贝 L[] 的剩余元素while (i < n1) {arr[k] = L[i];i++;k++;}// 拷贝 R[] 的剩余元素while (j < n2) {arr[k] = R[j];j++;k++;}
}// l 是数组的左边界，r 是右边界
void mergeSort(std::vector<int>& arr, int left, int right) {if (left < right) {// 同 [left, mid] 和 [mid+1, right] 两个子序列int mid = left + (right - left) / 2;// 分别对两个子序列进行归并排序mergeSort(arr, left, mid);mergeSort(arr, mid + 1, right);// 合并两个子序列merge(arr, left, mid, right);}
}int main() {std::vector<int> arr = {12, 11, 13, 5, 6};int arr_size = arr.size();mergeSort(arr, 0, arr_size - 1);std::cout << "Sorted array: ";for (int i = 0; i < arr_size; i++) {std::cout << arr[i] << " ";}std::cout << std::endl;return 0;
}

堆排序 Heap Sort

定义：是一种基于比较的排序算法，使用二叉堆数据结构。堆排序分为两个阶段：建立堆（Build Max Heap）和排序（Heapsort）。堆是一个满足以下性质的完全二叉树：对于最大的堆（大顶堆），父节点的键值总是大于或等于其子节点的键值；对于最小的堆（小顶堆），父节点的键值总是小于或等于其子节点的键值。
基本步骤：
- 建立最大堆：将无序序列构建成一个最大堆，即每个父节点的值都大于或等于其子节点的值。
- 排序：交换堆顶元素（当前最大值）和数组末尾元素，然后对堆进行调整（堆化），使其满足最大堆的性质。重复这个过程，直到数组完全有序。
复杂度：堆排序的时间复杂度是O(n log n)，其中n是数组的长度。堆排序是原地排序，不需要额外的存储空间，因此空间复杂度是O(1)。
示例：

#include <iostream>
#include <vector>
#include <algorithm> // For std::swap()// 调整堆，保持最大堆性质
void heapify(std::vector<int>& arr, int n, int i) {int largest = i;       // 初始化最大元素为根int left = 2 * i + 1;  // 左子节点int right = 2 * i + 2; // 右子节点// 如果左子节点比根大，则更新最大元素if (left < n && arr[left] > arr[largest])largest = left;// 如果右子节点比最大元素大，则更新最大元素if (right < n && arr[right] > arr[largest])largest = right;// 如果最大元素不是根，交换它们，并继续调整堆if (largest != i) {std::swap(arr[i], arr[largest]);heapify(arr, n, largest);}
}// 堆排序
void heapSort(std::vector<int>& arr) {int n = arr.size();// 构建最大堆for (int i = n / 2 - 1; i >= 0; i--)heapify(arr, n, i);// 一个个从堆顶取出元素for (int i = n - 1; i >= 0; i--) {// 将当前最大元素（堆顶）与末尾元素交换std::swap(arr[0], arr[i]);// 调整堆heapify(arr, i, 0);}
}int main() {std::vector<int> arr = {12, 11, 13, 5, 6};heapSort(arr);std::cout << "Sorted array: ";for (int num : arr) {std::cout << num << " ";}std::cout << std::endl;return 0;
}

希尔排序 Shell Sort

定义：是插入排序的一种优化版本，也称为缩小增量排序。它的基本思想是将原始数据分成若干子序列，这些子序列中的元素之间存在一定的间隔（称为增量），对每个子序列分别进行插入排序。随着增量逐渐减小，整个序列最终变为有序序列。
基本步骤：
- 选择一个增量序列：增量序列的选择对算法的性能有很大影响。常见的增量序列有原始长度的一半、原始长度除以某个常数等。
- 对子序列进行插入排序：以增量为间隔将原始序列分割成多个子序列，并对每个子序列进行插入排序。
- 减小增量：减小增量的值，重复步骤2，直到增量为1，此时对整个序列进行插入排序。
复杂度：时间复杂度在平均情况下是O(n log n)，但在最坏情况下是O(n^2)。希尔排序是不稳定的排序算法.
示例:

#include <iostream>
#include <vector>
#include <algorithm> // For std::swap()// 希尔排序
void shellSort(std::vector<int>& arr) {int n = arr.size();// 增量序列，可以自定义增量序列std::vector<int> gaps = {1, 4, 10, 23, 57, 132, 316};// 也可以使用动态计算增量序列，例如：gaps[i] = n/2^ifor (int gap : gaps) {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;}}
}int main() {std::vector<int> arr = {12, 11, 13, 5, 6, 7, 2, 3, 4, 1};shellSort(arr);std::cout << "Sorted array: ";for (int num : arr) {std::cout << num << " ";}std::cout << std::endl;return 0;
}

计数排序 Counting Sort

定义：是一种非比较型排序算法，适用于一定范围内的整数排序。它的基本思想是使用一个额外的数组来统计每个值的出现次数，然后根据这些计数来确定每个元素在排序后数组中的位置。
基本步骤：
- 找出待排序数组中的最大值和最小值：确定排序的范围。
- 创建计数数组：初始化计数数组，长度为最大值和最小值之差再加1。
- 填充计数数组：遍历待排序数组，对于每个元素，增加计数数组中对应位置的计数。
- 调整计数数组：将计数数组中的每个值调整为累积计数，这将给出每个元素在排序后数组中的位置。
- 构建排序数组：根据调整后的计数数组构建排序后的数组。
复杂度：计数排序的时间复杂度是O(n + k)，其中n是数组的长度，k是数值的范围。计数排序是稳定的排序算法，并且由于它不需要比较，所以在处理大量数据且数值范围不大时非常高效。然而，当数值范围非常大时，计数排序可能会消耗大量内存
示例:

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>// 计数排序
void countingSort(std::vector<int>& arr) {int n = arr.size();int maxVal = *std::max_element(arr.begin(), arr.end());int minVal = *std::min_element(arr.begin(), arr.end());// 计数数组的大小int range = maxVal - minVal + 1;std::vector<int> count(range, 0);// 填充计数数组for (int num : arr) {count[num - minVal]++;}// 调整计数数组为累积计数for (int i = 1; i < count.size(); i++) {count[i] += count[i - 1];}// 构建排序数组std::vector<int> sortedArr(n);for (int num : arr) {sortedArr[count[num - minVal] - 1] = num;count[num - minVal]--;}// 将排序后的数组复制回原数组for (int i = 0; i < n; i++) {arr[i] = sortedArr[i];}
}int main() {std::vector<int> arr = {4, 2, 2, 8, 3, 3, 1};countingSort(arr);std::cout << "Sorted array: ";for (int num : arr) {std::cout << num << " ";}std::cout << std::endl;return 0;
}

桶排序 Bucket Sort

定义：是一种分布式排序算法，其基本思想是将数组分为多个“桶”，每个桶负责排序数组中的一部分数据。桶排序通常用于数据服从均匀分布的情况，它通过将数据分散到有限数量的桶里，每个桶内使用其他排序算法（如插入排序）进行排序，最后按顺序合并各个桶中的数据以得到有序的序列。
基本步骤：
- 确定桶的数量：根据数据的范围和数据个数确定桶的数量。
- 分配数据到桶：遍历待排序数组，将每个数据分配到对应的桶中。
- 对每个桶内的数据进行排序：通常使用插入排序或其他排序算法对桶内数据进行排序。
- 合并桶中的数据：按顺序合并各个桶中的数据，得到最终的有序序列。
复杂度：时间复杂度取决于桶的数量和使用的排序算法，平均情况下是O(n+k)，其中n是数组的长度，k是桶的数量。桶排序是稳定的排序算法，并且由于它不需要比较，所以在处理大量数据且数值范围不大时非常高效。然而，桶排序的性能依赖于数据的分布，如果数据分布不均匀，性能可能会下降.
示例:

#include <iostream>
#include <vector>
#include <algorithm>void bucketSort(std::vector<int>& arr) {if (arr.empty()) {return;}// 找出最大值和最小值int maxVal = *std::max_element(arr.begin(), arr.end());int minVal = *std::min_element(arr.begin(), arr.end());// 计算桶的数量int bucketCount = (maxVal - minVal) / (arr.size() + 1) + 1;// 创建桶std::vector<std::vector<int>> buckets(bucketCount);// 分配数据到桶for (int num : arr) {int index = (num - minVal) / (arr.size() + 1);buckets[index].push_back(num);}// 对每个桶内的数据进行排序int idx = 0; // 用于结果数组的索引for (auto& bucket : buckets) {std::sort(bucket.begin(), bucket.end()); // 对每个桶进行排序for (int num : bucket) {arr[idx++] = num;}}
}int main() {std::vector<int> arr = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3};bucketSort(arr);std::cout << "Sorted array: ";for (int num : arr) {std::cout << num << " ";}std::cout << std::endl;return 0;
}

基数排序 Radix Sort

定义：是一种非比较型整数排序算法，其基本思想是将整数按位数切割成不同的数字，然后按每个位数分别比较。排序过程从最低位开始，依次对每一位进行排序，直到最高位排序完成。
基本步骤：
- 找到最大数：确定数组中的最大数，以确定最大位数。
- 按位排序：从最低位到最高位，对每一位进行排序。
- 使用稳定的排序算法：通常使用计数排序或桶排序来对每一位进行排序。
- 合并结果：经过每一位的排序后，整个数组变为有序。
复杂度：时间复杂度是O(nk)，其中n是数组的长度，k是数值的最大位数。基数排序是稳定的排序算法，并且由于它不需要比较，所以在处理大量数据且数值范围不大时非常高效。基数排序适用于整数排序，对于非整数数据，需要进行适当的转换。
示例:

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>// 计数排序辅助函数，对特定位数进行排序
void countSort(std::vector<int>& arr, int exp) {const int kMax = 10; // 0-9std::vector<int> output(arr.size());std::vector<int> count(kMax, 0);// 统计每个数字的出现次数for (int i = 0; i < arr.size(); ++i) {int index = (arr[i] / exp) % kMax;count[index]++;}// 计算累积出现次数for (int i = 1; i < kMax; ++i) {count[i] += count[i - 1];}// 填充输出数组for (int i = arr.size() - 1; i >= 0; --i) {int index = (arr[i] / exp) % kMax;output[count[index] - 1] = arr[i];count[index]--;}// 将输出数组复制回原数组for (int i = 0; i < arr.size(); ++i) {arr[i] = output[i];}
}// 基数排序
void radixSort(std::vector<int>& arr) {// 找到最大数，确定最大位数int maxVal = *std::max_element(arr.begin(), arr.end());int exp = 1; // 从最低位开始while (maxVal / exp > 0) {countSort(arr, exp); // 对每一位进行排序exp *= 10; // 移动到下一位}
}int main() {std::vector<int> arr = {170, 45, 75, 90, 802, 24, 2, 66};radixSort(arr);std::cout << "Sorted array: ";for (int num : arr) {std::cout << num << " ";}std::cout << std::endl;return 0;
}