十种经典排序算法深入剖析
目录
一、冒泡排序：
二、插入排序：
三、选择排序：
四、希尔排序：
五、堆排序：
六、快速排序：
6.1 挖坑法：
6.2 左右指针法
6.3 前后指针法：
七、归并排序：
八、桶排序：
九、计数排序：
9.1 绝对映射：
9.2 相对映射：
十、基数排序：
一、冒泡排序：
1、核心思路：
通过对待排序的序列进行从前往后的遍历（从下标较小的元素起始），依次对相邻的两个元素的值进行两两比较，若发现前一个数大于后一个数则进行交换操作，使得值较大的元素逐步从前部向尾部移动，恰似水底的气泡缓缓向上升腾。
2、实例讲解与代码示例：
以数组[3, 9, -1, 10, 20]为例进行说明：
第一轮排序：
- 3与9比较，无需交换；
- 9与-1比较，因9大于-1，两者交换，序列变为[3, -1, 9, 10, 20]；
- 9与10比较，无需交换；
- 10与20比较，无需交换。第一轮结束后，最大的元素20被固定在末尾位置。
第二轮排序：
由于20已处于正确位置，只需对前4个元素进行排序：
- -1与3比较，因3大于-1，两者交换，序列变为[-1, 3, 9, 10, 20]；
- 3与9比较，无需交换；
- 9与10比较，无需交换。第二轮结束后，第二大的元素10被固定在倒数第二个位置。
第三轮排序：
此时10和20已各就其位，只需对前3个元素进行排序：
- -1与3比较，无需交换；
- 3与9比较，无需交换。第三轮结束后，第三大的元素9被固定在相应位置。
第四轮排序：
仅需对前两个元素进行排序：
- -1与3比较，无需交换。第四轮结束后，所有元素排序完成。
小结：
设待排序元素的总数为n，那么排序过程具有以下特点：
1. 总共需要进行(n-1)轮排序，即(n-1)次大循环；
2. 每一轮排序中比较的次数逐轮递减；
3. 若在某一趟排序中，未发生任何一次交换操作，则可提前终止冒泡排序；
4. 时间复杂度为O(N²)，在序列有序时，由于有exchange变量进行优化，执行速度较快；但在序列无序时，效率较低。
#include<stdio.h>
void swap(int* a, int* b) {
int tmp = *a;
*a = *b;
*b = tmp;
}
void BubbleSort(int* a, int n) {
int end = n - 1; // 避免越界
while (end) {
int exchange = 0; // 用于优化，若未发生交换则提前结束循环
for (int i = 0; i < end; i++) {
if (a[i] < a[i + 1]) {
swap(&a[i], &a[i + 1]);
exchange++;
}
}
if (exchange == 0) break;
end--;
}
}
二、插入排序：
1、思路阐述：
假定待排序的元素中，前n-1个元素已然有序，现在将第n个元素插入到前面已经排好序的序列之中，使得前n个元素也呈现有序状态。按照这样的方式对所有元素依次进行插入操作，直至整个序列完全有序。需要注意的是，我们初始并不能确定待排元素中哪一部分是有序的，所以一开始默认第一个元素是有序的，然后依次将其后的元素插入到这个有序序列当中，最终使整个序列有序。
2、示例说明：
如同插入扑克牌的过程，当摸到数字7时，会自然而然地与前面已有的牌面数字进行比较，如果遇到比7大的牌，就将其向后挪动（通过交换操作），然后在第一个比7小的牌的后面插入7。
void InsertSort(int* a, int n) {
for (int i = 1; i < n; i++) {
if (a[i] < a[i - 1]) { // 若当前元素小于前一个元素，则进入插入流程
int tmp = a[i];
int j;
for (j = i - 1; j >= 0 && a[j] > tmp; j--) {
a[j + 1] = a[j]; // 将较大的元素后移
}
a[j + 1] = tmp; // 将当前元素插入到合适的位置
}
}
}
三、选择排序：
思路解析：
- 在内层循环中，找出当前未排序部分的最小值的下标，然后将其与未排序部分的第一个元素进行交换。重复进行寻找最小值和交换的操作。
- 实际上，我们可以在一趟排序中同时找出一个最大值和一个最小值，分别将它们放置在序列的开头和末尾位置，这样能使选择排序的效率提高一倍。不过，其时间复杂度依然为O(N²)，效率相对不高。
void SelectSort(int* a, int n) {
for (int i = 0; i < n - 1; i++) { // 当处理到最后一个元素时，无需再进行交换操作
int min = i;
for (int j = i; j < n; j++) {
if (a[j] < a[min]) {
min = j; // 记录最小值的下标
}
}
swap(&a[i], &a[min]); // 交换当前元素与最小值元素
}
}
四、希尔排序：
思路解读：
- 希尔排序是插入排序的优化版本，存在一个预排序的阶段。通过该阶段，使得较大的数能够快速地移动到序列的后面，较小的数能够快速地移动到序列的前面。
- 其目的是让待排序的序列尽可能接近有序状态，之后再对这个接近有序的序列进行一次插入排序。
- 本质上，希尔排序相当于将直接插入排序中的步长1替换成了gap。
void ShellSort(int* a, int n) {
int gap = n;
while (gap > 1) {
gap = gap / 3 + 1; // 动态调整步长
for (int i = gap; i < n; i++) {
if (a[i] < a[i - gap]) {
int tmp = a[i];
int j;
for (j = i - gap; j >= 0 && a[j] > tmp; j -= gap) { // 按照步长进行移动
a[j + gap] = a[j];
}
a[j + gap] = tmp;
}
}
}
}
五、堆排序：
堆的基本认知：
- 堆的定义：
- 大堆：父节点的值大于子节点的值；
- 小堆：父节点的值小于子节点的值（这里的父节点和子节点是基于二叉树结构而言的）。
- 堆的物理与逻辑结构：
- 物理结构：采用数组来存储；
- 逻辑结构：是一棵完全二叉树。
堆排序的步骤：
堆排序包含建堆（通过向下调整算法结合循环实现）和堆排序（通过交换操作结合向下调整算法实现）两个主要阶段。
1. 建堆：要构建大堆时，将堆顶元素与最后一个元素进行交换，然后减小堆的有效大小，这样可以保证堆的结构不被破坏。
2. 向下调整算法：比较当前父节点的两个子节点的大小，选出较大的子节点，若子节点的值大于父节点，则进行交换操作。然后将父节点指针指向子节点，子节点指针指向下一层子节点，如此循环，向下调整算法一共会进行h-1次调整（h为堆的高度）。
void AdjustDown(int* a, int n, int root) {
int parent = root;
int child = parent * 2 + 1;
while (child < n) {
if (child + 1 < n && a[child] < a[child + 1]) {
child++; // 指向较大的子节点
}
if (a[child] > a[parent]) {
swap(&a[child], &a[parent]);
parent = child;
child = parent * 2 + 1;
} else {
break;
}
}
}
void HeapSort(int* arr, int n) {
// 构建大堆
for (int i = (n - 1 - 1) / 2; i >= 0; i--) { // 从最后一个非叶子节点开始调整
AdjustDown(arr, n, i);
}
// 排序过程
for (int i = n; i > 1; i--) {
swap(&arr[0], &arr[i - 1]);
AdjustDown(arr, i - 1, 0);
}
}
六、快速排序：
快速排序包含三种常见的实现方法：挖坑法、左右指针法和前后指针法。
6.1 挖坑法：
- 核心思想：选取第一个元素作为key值，通过调整key值的位置，使得key值左边的所有元素都小于key值，右边的所有元素都大于key值。
- 具体步骤：
- 选定第一个元素作为key值，并将其存储到key变量中，此时该元素的位置形成一个“坑”；
- 定义left和right两个指针，left从左向右移动（当遇到大于key值的元素时停下），right从右向左移动（当遇到小于key值的元素时停下）。若从最左边开始挖坑，则需要先移动right指针；若从最右边开始挖坑，则需要先移动left指针；
- 将right指针所指的较小元素填入坑中，然后将left指针所指的元素填入right指针所指的位置，形成新的坑；
- 重复上述操作，直到left和right指针相遇，此时将key值填入相遇位置，完成一趟排序；
- 采用分治思想，将序列分为left到pivot-1和pivot+1到right两个部分，分别对这两个子序列进行递归排序。
void QuickSort(int* a, int left, int right) {
if (left >= right) {
return;
}
int begin = left, end = right;
int key = a[begin]; // 确定key值并挖坑
int pivot = begin;
while (begin < end) {
// 先从右边找小于key的元素
while (begin < end && a[end] >= key) {
end--;
}
a[pivot] = a[end]; // 将较小元素填入坑
pivot = end;
// 再从左边找大于key的元素
while (begin < end && a[begin] <= key) {
begin++;
}
a[pivot] = a[begin]; // 将较大元素填入坑
pivot = begin;
}
a[pivot] = key; // 将key值放入正确位置
QuickSort(a, left, pivot - 1); // 递归处理左子序列
QuickSort(a, pivot + 1, right); // 递归处理右子序列
}
6.2 左右指针法：
- 思路流程：
- 选取第一个元素作为key值；
- 定义begin和end两个指针，begin从左向右移动，end从右向左移动。若选取最左边的元素作为key值，则需要先移动end指针；若选取最右边的元素作为key值，则需要先移动begin指针（这是为了保证最后相遇位置能够正确与key值交换）；
- 在移动过程中，当end指针遇到小于key值的元素时停下，begin指针遇到大于key值的元素时停下，然后交换begin和end指针所指的元素；
- 重复上述操作，直到begin和end指针相遇，此时交换相遇位置与key值的元素；
- 采用分治思想，对key值左右的子序列分别进行递归排序。
void QuickSort(int* a, int left, int right) {
if (left >= right) {
return;
}
int begin = left, end = right;
int key = begin; // 以左边元素作为key值
while (begin < end) {
while (begin < end && a[end] >= a[key]) {
end--;
}
while (begin < end && a[begin] <= a[key]) {
begin++;
}
Swap(&a[begin], &a[end]); // 交换元素
}
Swap(&a[begin], &a[key]); // 将key值放到正确位置
QuickSort(a, left, begin - 1); // 递归处理左子序列
QuickSort(a, begin + 1, right); // 递归处理右子序列
}
6.3 前后指针法：
- 思路概述：
- 选取第一个元素作为key值；
- 初始化prev指针指向序列起始位置，cur指针指向prev+1的位置；
- 让cur指针一直向前移动，当遇到小于a[key]的元素时，将prev指针向前移动一格（此时prev指针所指元素一定大于a[key]），然后交换a[cur]和a[prev]的值；
- 经过一趟排序后，key值左边的元素都小于key值，右边的元素都大于key值；
- 采用分治思想，对key值左右的子序列分别进行递归排序。
void QuickSort(int* a, int left, int right) {
if (left >= right) {
return;
}
int index = GetMidIndex(a, left, right); // 三数取中优化
swap(&a[left], &a[index]);
int key = left;
int prev = left;
int cur = left + 1;
while (cur <= right) {
if (a[cur] < a[key]) {
prev++;
swap(&a[cur], &a[prev]);
}
cur++;
}
swap(&a[prev], &a[key]);
QuickSort(a, left, prev - 1); // 递归处理左子序列
QuickSort(a, prev + 1, right); // 递归处理右子序列
}
// 三数取中函数
int GetMidIndex(int* a, int left, int right) {
int mid = (left + right) / 2;
if (a[mid] >= a[left]) {
if (a[mid] <= a[right]) {
return mid;
} else {
if (a[right] >= a[left]) {
return right;
} else {
return left;
}
}
} else {
if (a[right] >= a[left]) {
return left;
} else {
if (a[right] >= a[mid]) {
return right;
} else {
return mid;
}
}
}
}
文章整理自互联网，只做测试使用。发布者：Lomu，转转请注明出处：https://www.it1024doc.com/12852.html
