十种经典排序算法深入剖析
目录
一、冒泡排序:
二、插入排序:
三、选择排序:
四、希尔排序:
五、堆排序:
六、快速排序:
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