【数据结构】排序（附测试源码）
插入排序：直接插入排序、希尔排序选择排序：直接选择排序、堆排序交换排序：冒泡排序、快速排序归并排序
·
【数据结构】排序（附测试源码）
本节是数据结构排序版（不完整版，没有C语言版的哈希表）
1.排序概念：
1.1所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
1.2常见排序算法：
-
插入排序：
- 直接插入排序
- 希尔排序
-
选择排序：
- 直接选择排序
- 堆排序
-
交换排序：
- 冒泡排序
- 快速排序
-
归并排序
2.实现常见排序算法：
2.1插入排序：
基本思想：把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列，例如玩扑克牌整理牌牌的时候。
2.1.1直接插入法：
- 概念：直接插入排序是一种简单的排序算法，基本思想是将未排序数据中的元素，依次插入到已排序系列的合适位置，从而逐步构建出一个完整的有序序列。
- 时间复杂度：
- 最好情况：O（n），比如排序序列本身就是有序的
- 最坏情况：O(n^2),比如逆序的待排序序列
- 平均情况：O（n^2）
空间复杂度：O(1)
图片示意：
代码实现（算法）：
void InsertSort(int* arr, int n)
{
for (int i = 0; i < n - 1; i++)
{
int end = i;
int tmp = arr[end + 1];
while (end >= 0)
{
if (arr[end] > tmp)
{
arr[end + 1] = arr[end];
end--;
}
else
{
break;
}
}
arr[end + 1] = tmp;
}
}
由此可观察到：当元素集合越接近有序，直接插入排序的时间算法效率越高。
但如果是不有序的元素集合，时间复杂度就会变得高，那么有没有什么办法能让复杂的元素集合比现在的时间复杂度低呢？
那么就会想到希尔排序，优化直接插入排序。
2.1.2 希尔排序
- 希尔排序又称缩小增量法。其基本思想是先选定一个整数（通常是gap=n/3+1，保证最后一次gap一定是1），把待排序文件所有记录分成各组，所有的距离相等的记录分在同一组内，并对每一组内的记录进行排序，然后gap=gap/3+1得到下一个整数，再将数组分成各组，进行插入排序，当gap=1时，就相当于直接插入排序。
- 时间复杂度：O（n^1.3）
- 特点：当 gap > 1 时都是预排序，目的是让数组更接近于有序。当 gap == 1 时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。
图示：
代码实现（算法）：
void ShellSort(int* arr, 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 = arr[end + gap];
while (end >= 0)
{
if (arr[end] > tmp)
{
arr[end + gap] = arr[end];
end -= gap;
}
else
{
break;
}
}
arr[end + gap] = tmp;
}
}
}
2.2 选择排序
选择排序的基本思想：每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。
2.2.1 直接选择排序
-
基本思想：在元素集合中选择最大（小）的元素，若它不是这组元素中的最后一个（第一个元素），则将它与这组元素中最后一个交换，在剩余的元素组合中重复以上步骤，直到集合剩余一个元素。
-
直接选择排序虽然思路容易理解，但是效率不是很好，实际中很少用到。
-
时间复杂度：O（n^2）
-
空间复杂度：O（1）
图示：
代码实现（算法）：
void SelectSort(int* arr, int n)
{
int begin = 0;
int end = n - 1;
while (begin < end)
{
int mini = begin, maxi = begin;
for (int i = begin+ 1; i <= end; i++)
{
if (arr[i] > arr[maxi])
{
maxi = i;
}
if (arr[i] < arr[mini])
{
mini = i;
}
}
//mini begin
//maxi end
//避免maxi begini都在同一个位置，begin和mini交换之后，maxi数据变成了最小的数据
if (maxi == begin)
{
maxi = mini;
}
Swap(&arr[mini], &arr[begin]);
Swap(&arr[maxi], &arr[end]);
++begin;
--end;
}
}
2.2.2 堆排序
- 堆排序(Heapsort)是指利⽤堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。
- 时间复杂度：O(n*logn)
- 空间复杂度：O(1)
代码实现：
void AdjustDown(int* arr, int parent, int n)
{
int child = parent * 2 + 1;//左孩子
while (child < n)
{
//大堆：找右孩子最大的
if (child + 1 < n && arr[child] > arr[child + 1])
{
child++;
}
if (arr[child] < arr[parent])
{
swap(&arr[child], &arr[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, i, n);
}
//循环将堆顶数据跟最后位置（会变化，每次减少一个数据）的数据进行交换
int end = n - 1;
while (end > 0)
{
swap(&arr[0], &arr[end]);
AdjustDown(arr, 0, end);
end--;
}
}
2.3交换排序：
基本思想：所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置
交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动
2.3.1冒泡排序：
-
冒泡排序是一种最基础的交换排序。之所以叫做冒泡排序，因为每一个元素都可以像小⽓泡⼀样，根据自身大小一点一点向数组的一侧移动。
-
时间复杂度：O(n^2)
-
空间复杂度：O(1)
图示：
代码实现：
void BubbleSort(int* arr, int n)
{
for (int i = 0; i < n; i++)
{
int exchange = 0;
for (int j = 0; j = n - i - 1; j++)
{
if (arr[j] > arr[j + 1])
{
exchange = 1;
swap(&arr[j], &arr[j + 1]);
}
}
if (exchange == 0)
{
break;
}
}
}
2.3.2 快速排序
- 基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列 在相应位置上为止。
- 时间复杂度：O(n*logn)
- 空间复杂度：O(logn)
2.3.2.1 hoare版本
算法思路：
- 创建左右指针，确定基准值
- 从右往左找出比基准值小的数据，从右往左找出比基准值小的数据，从左向右找出比基准值大的数据，左右指针数据交换，进入下次循环
如何找基准值？
- right：从右往左找出比基准值小的数据
- left: 从左向右找出比基准值大的数据
图示：
这个方法有几个特殊的情景，比如集合里全是相同数值的元素，或者是集合里只有一个不同的元素。
代码实现（算法）：
int _QuickSort(int* arr, int left, int right)
{
int keyi = left;
++left;
while (left <= right)//left和right相遇的位置的值比基准值要大
{
while (left <= right && arr[right] > arr[keyi])
{
right--;
}
//right找到比基准值小/ 等于？
while (left <= right && arr[left] < arr[keyi])
{
left++;
}
//right left
if (left <= right)
{
Swap(&arr[left++], &arr[right--]);
}
}
//right keyi交换
Swap(&arr[keyi], &arr[right]);
return right;
}
void QuickSort(int* arr, int left, int right)
{
if (left >= right)
{
return;
}
//[left,right]--->找基准值mid
int keyi = _QuickSort(arr, left, right);
//左子序列：[left,keyi-1]
QuickSort(arr, left, keyi - 1);
//右子序列：[keyi+1,right]
QuickSort(arr, keyi + 1, right);
}
2.3.2.2 挖坑法
算法思路：创建左右指针。⾸先从右向左找出比基准小的数据，找到后立即放入左边坑中，当前位置变为新的"坑"，然后从左向右找出比基准大的数据，找到后立即放入右边坑中，当前位置变为新的"坑"，结束循环后将最开始存储的分界值放入当前的"坑"中，返回当前"坑"下标（即分界值下标）
图示：
代码实现：
//挖坑法
int _QuickSort2(int* arr, int left, int right)
{
int hole = left;
int key = arr[hole];
while (left < right)
{
while (left < right && arr[right] > key)
{
--right;
}
arr[hole] = arr[right];
hole = right;
while (left < right && arr[left] < key)
{
++left;
}
arr[hole] = arr[left];
hole = left;
}
arr[hole] = key;
return hole;
}
2.3.2.3 lomuto指针
算法思想：创建前后指针，从左往右找比基准值小的进行交换，使得小的都排在基准值的左边。
图示：
代码实现（算法）：
//lomuto前后指针法
int _QuickSort(int* arr, int left, int right)
{
int prev = left, cur = left + 1;
int keyi = left;
while (cur <= right)
{
if (arr[cur] < arr[keyi] && ++prev != cur)
{
Swap(&arr[cur], &arr[prev]);
}
cur++;
}
Swap(&arr[keyi], &arr[prev]);
return prev;
}
2.4 归并排序
- 算法思想：将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
- 时间复杂度：O(nlogn)
- 空间复杂度：O(n)
代码实现（算法）：
//归并排序
void _MergeSort(int* arr,int left,int right,int* tmp)
{
if (left >= right)
{
return;
}
int mid = (left + right) / 2;
//[left,mid] [mid+1,right]
_MergeSort(arr, left, mid, tmp);
_MergeSort(arr, mid + 1, right, tmp);
//合并
//[left,mid] [mid+1,right]
int begin1 = left, end1 = mid;
int begin2 = mid + 1, end2 = right;
int index = begin1;
while (begin1 <= end1 && begin2 <= end2)
{
if (arr[begin1] < arr[begin2])
{
tmp[index++] = arr[begin1++];
}
else {
tmp[index++] = arr[begin2++];
}
}
//要么begin1越界但begin2没有越界 要么begin2越界但begin1没有越界
//只有两种结果
while (begin1 <= end1)
{
tmp[index++] = arr[begin1++];
}
while (begin2 <= end2)
{
tmp[index++] = arr[begin2++];
}
//[left,mid] [mid+1,right]
//把tmp中的数据拷贝回arr中
for (int i = left; i <= right; i++)
{
arr[i] = tmp[i];
}
}
2.5 测试代码：排序性能比较
// 测试排序的性能对⽐
void TestOP()
{
srand(time(0));
const int N = 100000;
int* a1 = (int*)malloc(sizeof(int) * N);
int* a2 = (int*)malloc(sizeof(int) * N);
int* a3 = (int*)malloc(sizeof(int) * N);
int* a4 = (int*)malloc(sizeof(int) * N);
int* a5 = (int*)malloc(sizeof(int) * N);
int* a6 = (int*)malloc(sizeof(int) * N);
int* a7 = (int*)malloc(sizeof(int) * N);
int* a8 = (int*)malloc(sizeof(int) * N);
for (int i = 0; i < N; ++i)
{
a1[i] = rand();
a2[i] = a1[i];
a3[i] = a1[i];
a4[i] = a1[i];
a5[i] = a1[i];
a6[i] = a1[i];
a7[i] = a1[i];
a8[i] = a1[i];
}
int begin7 = clock();
BubbleSort(a7, N);
int end7 = clock();
int begin1 = clock();
InsertSort(a1, N);
int end1 = clock();
int begin2 = clock();
ShellSort(a2, N);
int end2 = clock();
int begin3 = clock();
SelectSort(a3, N);
int end3 = clock();
int begin4 = clock();
HeapSort(a4, N);
int end4 = clock();
int begin5 = clock();
QuickSort(a5, 0, N - 1);
//QuickSortNonR(a5, 0, N - 1);
int end5 = clock();
int begin6 = clock();
MergeSort(a6, N);
int end6 = clock();
int begin8 = clock();
CountSort(a8, N);
int end8 = clock();
printf("InsertSort:%d\n", end1 - begin1);
printf("ShellSort:%d\n", end2 - begin2);
printf("SelectSort:%d\n", end3 - begin3);
printf("HeapSort:%d\n", end4 - begin4);
printf("QuickSort:%d\n", end5 - begin5);
printf("MergeSort:%d\n", end6 - begin6);
printf("BubbleSort:%d\n", end7 - begin7);
printf("CountSort:%d\n", end8 - begin8);
free(a1);
free(a2);
free(a3);
free(a4);
free(a5);
free(a6);
free(a7);
free(a8);
}
3.各排序算法复杂度及稳定性
魔乐社区（Modelers.cn) 是一个中立、公益的人工智能社区，提供人工智能工具、模型、数据的托管、展示与应用协同服务，为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作，由全产业链共同建设、共同运营、共同享有，推动国产AI生态繁荣发展。
更多推荐
30
0- 0
已为社区贡献1条内容
所有评论(0)