当前位置：首页 > news >正文

数据结构之排序

news 来源：原创 2025/6/27 2:26:24

排序

一.比较排序
1.插入排序
- 基本思想
- 1.1直接插入排序
- 1.2希尔排序
2.选择排序
- 直接选择排序
- 堆排序
3.交换排序
- 冒泡排序
- 快速排序
- - hoare版本
  - 挖坑法
  - lomuto前后指针
  - 非递归版本
- 4.归并排序
- - 非递归的归并排序
非比较排序
- 1.计数排序
排序算法复杂度及稳定性分析

一.比较排序

1.插入排序

基本思想

直接插⼊排序是⼀种简单的插⼊排序法，其基本思想是：把待排序的记录按其关键码值的⼤⼩逐个插⼊到⼀个已经排好序的有序序列中，直到所有的记录插⼊完为⽌，得到⼀个新的有序序列。

1.1直接插入排序

内层循环从已排序部分的最后一个元素开始，向前遍历。
如果当前元素 a[end] 大于 tmp，则将 a[end] 向后移动一位（即 a[end + 1] = a[end]），并将 end 减 1，继续比较前一个元素。如此就会使最大的数放置在最后一位，如此反复。
如果遇到一个不大于 tmp 的元素，或者已经遍历到数组的开头（end < 0），则退出循环。

void InsertSort(int* a, int n)
{for (int i = 0; i < n- 1;i++){int end = i;int tmp = a[end + 1];while (end >= 0){if (a[end] > tmp){a[end+1] = a[end];end--;}elsebreak;}a[end + 1] = tmp;}
}

直接插⼊排序的特性总结

元素集合越接近有序，直接插⼊排序算法的时间效率越⾼
时间复杂度：O(N^2)
空间复杂度：O(1)

1.2希尔排序

希尔排序可以看作是直接插入排序的优化版，希尔排序法⼜称缩⼩增量法。希尔排序法的基本思想是：先选定⼀个整数（通常是gap=n/3+1），把待排序⽂件所有记录分成各组，所有的距离相等的记录分在同⼀组内，并对每⼀组内的记录进⾏排序，然后gap=gap/3+1得到下⼀个整数，再将数组分成各组，进⾏插⼊排序，当gap=1时，就相当于直接插⼊排序。

void ShellSort(int* a, int n)
{int gap = n;while (gap > 1){gap = gap / 3 + 1;for (int i = 0;i < n-gap; i++){int end = i;int tmp = a[end + gap];while (end >= 0){if (a[end] > tmp){a[end + gap] = a[end];end = end - gap;}elsebreak;}a[end + gap] = tmp;}}
}

希尔排序的特性总结

希尔排序是对直接插⼊排序的优化。
当 gap > 1 时都是预排序，⽬的是让数组更接近于有序。当 gap == 1 时，数组已经接近有序的了，这样就会很快。这样整体⽽⾔，可以达到优化的效果。
关于希尔排序的时间复杂度：

2.选择排序

选择排序的基本思想：
每⼀次从待排序的数据元素中选出最⼩（或最⼤）的⼀个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。

直接选择排序

void SelectSort(int* a, int n)
{int begin = 0;int end = n - 1;while (begin < end){int max = end;int min = begin;for (int i = begin; i <= end;i++){if (a[i] > max)max = i;if (a[i] < min)min = i;}if (max == begin){max = min;}swap(&a[begin], &a[min]);swap(&a[end], &a[max]);begin++;end--;}
}

设立两个下标，分别表示最大和最小，遍历数组，并且记录下该数组最大数下标和最小数的下标。遍历完之后，将最小的数据换到最前，最大的换到最后。
但要注意的是，有一种情况，就是begin == max ,end == min 的情况，这时如若不经过特殊处理，将会换两次，导致方法失效，所以进行判断，将max = min 这样就能正确使用。（注意两次交换不能颠倒）
直接选择排序的特性总结：

时间复杂度：O(N的平方 )
空间复杂度：O(1)

堆排序

void AdjustDwon(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[parent] < a[child])swap(&a[parent], &a[child]);elsebreak;parent = child;child = parent * 2 + 1;}
}
void HeapSort(int* a, int n)
{for (int i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDwon(a, n, i);}int end = n - 1;while (end > 0){swap(&a[0], &a[end]);AdjustDwon(a, end, 0);end--;}
}

堆排序用到了adjust down函数，主要有建堆和排序两个步骤，具体操作请看堆排序。

3.交换排序

交换排序基本思想：
所谓交换，就是根据序列中两个记录键值的⽐较结果来对换这两个记录在序列中的位置
交换排序的特点是：
将键值较⼤的记录向序列的尾部移动，键值较⼩的记录向序列的前部移动

冒泡排序

由于冒泡排序较为基础，这里不做过多赘述。
冒泡排序通过重复遍历待排序的数组，比较每对相邻元素，如果它们的顺序错误（即前一个元素大于后一个元素），就将它们交换。这个过程会不断重复，直到数组完全有序。
每一轮遍历都会将当前未排序部分的最大值“冒泡”到数组的末尾，因此数组的有序部分会逐渐增长，而未排序部分会逐渐缩短。

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

快速排序

快速排序是Hoare于1962年提出的⼀种⼆叉树结构的交换排序⽅法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两⼦序列，左⼦序列中所有元素均⼩于基准值，右⼦序列中所有元素均⼤于基准值，然后最左右⼦序列重复该过程，直到所有元素都排列在相应位置上为⽌。
快速排序框架：

//快速排序 void QuickSort(int* a, int left, int right) 
{if (left >= right) {return;}//_QuickSort⽤于按照基准值将区间[left,right)中的元素进⾏划分 int meet = _QuickSort(a, left, right);QuickSort(a, left, meet - 1);QuickSort(a, meet + 1, right);
}

我们要具体实现的是_QuickSort函数。

hoare版本

算法思路：

1）创建左右指针，确定基准值
2）从右向左找出⽐基准值⼩的数据，从左向右找出⽐基准值⼤的数据，左右指针数据交换，进⼊下次循环

int _QuickSort(int* a, int left, int right)
{int key = left;left++;while (left <= right){while (left <= right && a[right] > a[key]){right--;}while (left <= right && a[left] < a[key]){left++;}if(left<=right)swap(&a[left++], &a[right--]);}swap(&a[key], &a[right]);return right;
}

挖坑法

创建左右指针。⾸先从右向左找出⽐基准⼩的数据，找到后⽴即放⼊左边坑中，当前位置变为新的"坑"，然后从左向右找出⽐基准⼤的数据，找到后⽴即放⼊右边坑中，当前位置变为新的"坑"，结束循环后将最开始存储的分界值放⼊当的"坑"中，返回当前"坑"下标（即分界值下标）

int _QuickSort(int* a, int left, int right)
{int hole = left;int key = a[hole];while (left < right){while (left < right && a[right] > key){right--;}a[hole] = a[right];hole = right;while (left < right && a[left] < key){left++;}a[hole] = a[left];hole = left;}a[hole] = key;return hole;
}

lomuto前后指针

创建前后指针，从左往右找⽐基准值⼩的进⾏交换，使得⼩的都排在基准值的左边。

定义两个指针，cur 和prev cur 作为探路指针，找比基准值小的数据。
若找到了prev++ ，交换数据 cur++（++prev != cur 是用于避免无用的操作）
若未找到则cur++。
现在prev及左边的数，都要比基准值小，右边的数据都比基准值大。
循环结束后，将基准值与prev的数据交换，返回prev。

int _QuickSort(int* a, int left, int right)
{int prev = left;int cur = left + 1;int key = left;while (cur <= right){if (a[cur] < a[key] && ++prev != cur){swap(&a[prev], &a[cur]);}cur++;}swap(&a[key], &a[prev]);return prev;
}

快速排序特性总结：

时间复杂度：O(nlogn)
空间复杂度：O(logn)

非递归版本

⾮递归版本的快速排序需要借助数据结构：栈。
基本算法思路可以参考lomuto前后指针法。

先将数组的最左和最右的数据入栈，进入循环后依次取栈顶，删除栈的操作，得到了我们所处理数据的begin 和end
依旧创建prev 和 cur ，cur作探路指针
得到最后的基准值，再次将新划分的数据入栈。重复循环操作，就实现了排序算法。

void QuicSortNoR(int* arr, int left, int right)
{ST st;StackInit(&st);StackPush(&st, left);StackPush(&st, right);while (!StackEmpty(&st)){//取栈顶两次int end = StackTop(&st);StackPop(&st);int begin = StackTop(&st);StackPop(&st);//[begin,end]找基准值int keyi = begin;int prev = begin, cur = prev + 1;while (cur <= end){if (arr[cur] < arr[keyi] && ++prev != cur){Swap(&arr[prev], &arr[cur]);}cur++;}Swap(&arr[keyi], &arr[prev]);keyi = prev;//begin keyi end//左序列：[begin,keyi-1]  右序列：[keyi+1,end];if (keyi + 1 < end){StackPush(&st, keyi + 1);StackPush(&st, end);}if (begin < keyi - 1){StackPush(&st, begin);StackPush(&st, keyi - 1);}}StackDestroy(&st);
}

4.归并排序

归并排序算法思想：
归并排序（MERGE-SORT）是建⽴在归并操作上的⼀种有效的排序算法,该算法是采⽤分治法（Divideand Conquer）的⼀个⾮常典型的应⽤。将已有序的⼦序列合并，得到完全有序的序列；即先使每个⼦序列有序，再使⼦序列段间有序。若将两个有序表合并成⼀个有序表，称为⼆路归并。归并排序核⼼步骤：在这里插入图片描述

思路是将数据分成一个一个的数组，然后将这一个个的数组重新排序组合。赋值给tmp数组之中，最后将有序的数组重新传给a数组，实现排序的算法.
代码涉及到了合并两个有序数组。

void _MergeSort(int* arr, int left, int right, int* tmp)
{if (left >= right)return;int mid = (left + right) / 2;_MergeSort(arr, left, mid, tmp);_MergeSort(arr, mid + 1, right, tmp);int begin1 = left; int end1 = mid;int begin2 = mid + 1;int end2 = right;int index = left;while (begin1 <= end1 && begin2 <= end2){if (arr[begin1] < arr[begin2]){tmp[index++] = arr[begin1++];}else{tmp[index++] = arr[begin2++];}}while (begin1 <= end1){tmp[index++] = arr[begin1++];}while (begin2 <= end2){tmp[index++] = arr[begin2++];}for (int i = left;i < right;i++){arr[i] = tmp[i];}
}// 归并排序递归实现
void MergeSort(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);_MergeSort(a, 0, n - 1, tmp);free(tmp);tmp == NULL;
}

归并排序特性总结：

时间复杂度：O(nlogn)
空间复杂度：O(n)

非递归的归并排序

非递归归并排序的核心思想是逐步增加归并的子数组大小，从最小的子数组开始逐步合并，直到整个数组被排序。具体步骤如下：
初始化：将数组分成若干个大小为 1 的子数组。
逐步合并：每次迭代中，将相邻的两个子数组合并成一个有序的子数组，子数组的大小逐步翻倍。
重复上述过程：直到所有子数组合并成一个完整的有序数组。

void MergeSortNonR(int* arr, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);int gap = 1;while (gap < n){for (int i = 0;i <n;i = i+2*gap){int begin1 = i;int end1 = i + gap - 1;int begin2 = i + gap; int end2 = i + 2 * gap - 1;int index = i;if (begin2 >= n)break;if (end2 >= n){end2 = n - 1;}while (begin1 <= end1 && begin2 <= end2){if (arr[begin1] < arr[begin2]){tmp[index++] = arr[begin1++];}else{tmp[index++] = arr[begin2++];}}while (begin1 <= end1){tmp[index++] = arr[begin1++];}while (begin2 <= end2){tmp[index++] = arr[begin2++];}memcpy(arr + i, tmp + i, sizeof(int) * 2*gap);}gap *= 2;}}

详细步骤
假设数组长度为 n，以下是详细的实现步骤：

步骤1：初始化
创建一个临时数组 tmp，大小与原数组 arr 相同，用于存储归并后的结果。
初始化子数组大小 gap 为 1。
步骤2：逐步归并
使用一个 while 循环，条件是 gap < n，表示还有未排序的部分。
在每次迭代中，使用一个 for 循环，以 2 * gap 为步长遍历数组，将相邻的两个子数组合并。
确定每个子数组的起始和结束索引。
使用双指针方法将两个子数组合并到临时数组 tmp 中。
如果某个子数组已经遍历完，将另一个子数组的剩余部分复制到 tmp 中。
将临时数组 tmp 中的有序部分复制回原数组 arr。
将子数组大小 gap 翻倍。
步骤3：重复上述过程
重复步骤2，直到 gap >= n，此时整个数组已经排序完成。

非比较排序

1.计数排序

计数排序⼜称为鸽巢原理，是对哈希直接定址法的变形应⽤。
操作步骤：
1）统计相同元素出现次数
2）根据统计的结果将序列回收到原来的序列中在这里插入图片描述

计数排序的特性：
计数排序在数据范围集中时，效率很⾼，但是适⽤范围及场景有限。
时间复杂度：O(N + range)
空间复杂度：O(range)
稳定性：稳定

void CountSort(int* a, int n)
{int min = a[0];int max = a[0];for (int i = 0;i < n;i++){if (a[i] < min)min = a[i];if (a[i] > max)max = a[i];}int range = max - min + 1;int* count = (int*)calloc(0,sizeof(int) * range);for (int i = 0;i < n;i++){count[a[i] - min]++;}int index = 0;for (int i = 0;i < range;i++){while (count[i]--)a[index++] = i+min;}
}

排序算法复杂度及稳定性分析

稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的
相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，⽽在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。

稳定的排序算法：冒泡排序，直接插入排序，归并排序。
不稳定的排序算法：直接选择排序，希尔排序，堆排序，快速排序。

排序