【数据结构与算法】排序算法---探索数据组织的核心技术
【数据结构与算法】排序算法---探索数据组织的核心技术
前言
这是我学习数据结构的第六份笔记。后期我会继续将数据结构知识的笔记补全。 上一期笔记有二叉树，没看过的同学可以去看看：【数据结构与算法】二叉树---探索数据森林的幽径_二叉树模型越往上越大-CSDN博客
https://cloud.tencent.com/developer/article/2464275
排序的概念
排序是指将一组数据，按照特定的顺序进行排列的过程。 这个过程通常是为了使数据更加有序，从而更容易进行搜索、比较或其他操作。
常见的排序算法
插入排序
把待排序的记录，按其关键码值的大小，逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列 。 通俗的来说，就是分为两堆数据，第一堆已经按顺序排列好了，第二堆是无序的，然后从无序数据堆中取出第一个数据插入到第一堆进行排序，一直重复，直到第二堆没有数据。 我们玩扑克牌时，就用了插入排序的思想。
直接插入排序
代码实现
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
void InsertSort(int* arr, int n);
void PrintSort(int* arr, int n);
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;
}
}
end++;
arr[end] = tmp;
}
}
void PrintSort(int* arr, int n)
{
for (int i = 0; i < n; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
}
int main()
{
int arr[] = { 1,5,2,6,8,7,9,3,0,4 };
int n = sizeof(arr) / sizeof(int);
PrintSort(arr, n);
InsertSort(arr, n);
PrintSort(arr, n);
return 0;
}
//1 5 2 6 8 7 9 3 0 4
//0 1 2 3 4 5 6 7 8 9下面是对直接插入排序的总结： 1. 元素集合越接近有序，直接插入排序算法的时间效率越高。 2. 时间复杂度（默认最差的情况）：O(N^2)。数组有序且为降序的情况下时间复杂度最差，所以很难达到最差的情况。 3. 空间复杂度：O(1)。
底层逻辑
直接插入排序本质上是把一个数组分为两部分，前面部分默认已排序，后面部分默认未排序。 直接插入排序依靠两个循环嵌套实现。 外层循环负责找到已排序数组的最后一位和未排序数组的第一位 内层循环负责进行逐个比较，待排序元素和有序数组的倒数第一个元素进行比较，如果符合要求，那么待排序的元素就往有序数组的倒数第一个元素后面插入，如果不符合要求，那么有序数组的倒数第一个元素往后移动一次，然后用待排序元素和有序数组的倒数第二个元素比较，循环往复。
希尔排序
由于直接插入排序在完全逆序的情况下时间复杂度最大，故我们可以进行改进，使用希尔排序降低时间复杂度。 希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数距离（通常是gap = n/3+1），把待排序文件所有记录分成各组，所有的距离相等的记录分在同一组内，并对每一组内的记录进行排序。然后gap=gap/3+1进行迭代得到下一个整数距离，再将数组分成各组，进行插入排序，当gap=1时，就相当于直接插入排序。 它是在直接插入排序算法的基础上进行改进而来的，综合来说它的效率肯定是要高于直接插入排序算法的。 当 gap > 1 时都是预排序，目的是让数组更接近于有序。当 gap == 1 时就是直接插入排序，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。
代码实现
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
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 = end - gap;
}
else
{
break;
}
}
arr[end + gap] = tmp;
}
}
return 0;
}
void PrintSort(int* arr, int n)
{
for (int i = 0; i < n; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
}
int main()
{
int arr[10] = { 5,1,7,3,4,2,6,0,9,8 };
int i = sizeof(arr) / sizeof(arr[0]);
PrintSort(arr, i);
ShellSort(arr, i);
PrintSort(arr, i);
return 0;
}底层逻辑
外层循环的时间复杂度：O(log n)。 内层循环的时间复杂度：O(n)。 希尔排序时间复杂度不好计算，因为 gap 的取值很多（最优为3），导致很难去计算，因此很多书中给出的希尔排序的时间复杂度都不固定。（一般认为是O(n^1.3)）
选择排序
直接选择排序
每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。 在元素集合 array i 到 array n-1 中选择关键码最小的数据元素，若它不是这组元素中的第一个元素，则将它与这组元素中的第一个元素交换，在剩余的array i+1 到 array n-1集合中，重复上述步骤，直到集合剩余 1 个元素。
代码实现
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
void Swap(int* a, int* b)
{
int mid = *a;
*a = *b;
*b = mid;
}
void SelectSort(int* arr, int n)
{
for (int i = 0; i < n; i++)
{
int begin = i;
int mini = i;
for (int j = i + 1; j < n; j++)
{
if (arr[j] < arr[mini])
{
mini = j;
}
}
Swap(&arr[begin], &arr[mini]);
}
}
void PrintSort(int* arr, int n)
{
for (int i = 0; i < n; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
}
int main()
{
int arr[10] = { 5,1,7,3,4,2,6,0,9,8 };
int i = sizeof(arr) / sizeof(arr[0]);
PrintSort(arr, i);
SelectSort(arr, i);
PrintSort(arr, i);
return 0;
}代码改进
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
void Swap(int* a, int* b)
{
int mid = *a;
*a = *b;
*b = mid;
}
void SelectSort(int* arr, int n)
{
int begin = 0, end = n - 1;
while (begin < end)
{
int max = begin, min = begin;
for (int i = begin + 1; i <= end; i++)
{
if (arr[i] < arr[min])
{
min = i;
}
if (arr[i] > arr[max])
{
max = i;
}
}
if (begin == max)
{
max = min;//如果是这样就让end数据自交换
}
Swap(&arr[begin], &arr[min]);
Swap(&arr[end], &arr[max]);
begin++;
end--;
}
}
void PrintSort(int* arr, int n)
{
for (int i = 0; i < n; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
}
int main()
{
int arr[10] = { 5,1,7,3,4,2,6,0,9,8 };
int i = sizeof(arr) / sizeof(arr[0]);
PrintSort(arr, i);
SelectSort(arr, i);
PrintSort(arr, i);
return 0;
}底层逻辑
时间复杂度为：O(N^2)。 空间复杂度为：O(1)。
堆排序
堆排序是指利用堆这种数据结构所设计的⼀种排序算法，它是选择排序的⼀种。它是通过堆来进行选择数据。 需要注意的是排升序要建大堆，排降序建小堆。
代码实现
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
void PrintSort(int* arr, int n);
void Swap(int* a, int* b);
void UpAdjust(int* arr, int child);
void DownAdjust(int* arr, int parent, int n);
void Swap(int* a, int* b)
{
int mid = *a;
*a = *b;
*b = mid;
}
void UpAdjust(int* arr, int child)
{
int parent = (child - 1) / 2;
while (child > 0)
{
if (arr[child] < arr[parent])
{
Swap(&arr[child], &arr[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
void DownAdjust(int* arr, int parent, int n)
{
int child = 2 * parent + 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 = 2 * parent + 1;
}
else
{
break;
}
}
}
void HeapSort(int* arr, int n)
{
for (int i = 0; i < n; i++)
{
UpAdjust(arr, i);//对数组的每一个元素进行建堆
}
int end = n - 1;
while (end > 0)
{
Swap(&arr[0], &arr[end]);
DownAdjust(arr, 0, end);
end--;
}
}
void PrintSort(int* arr, int n)
{
for (int i = 0; i < n; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
}
int main()
{
int arr[] = { 1,5,2,6,8,7,9,3,0,4 };
int n = sizeof(arr) / sizeof(int);
PrintSort(arr, n);
HeapSort(arr, n);
PrintSort(arr, n);
return 0;
}底层逻辑
把数组重建为小堆，那么最后输出的是倒序数组。 数组重建小堆时，是用循环把每一个数组元素进行向上调整算法。（相当于把每一个元素向堆中尾插，查完之后用向上调整算法） 数组进行调整时，交换第一个元素和最后一个元素，然后有效数组元素减一，此时最小的元素就到了队尾，然后再对第一个元素进行向下调整算法，此时又变成了小堆。循环以往，直到有效数组里面只有一个元素。 此时就变成了倒序的数组。 时间复杂度为：O( n*log(n) )。
交换排序
冒泡排序
代码实现
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
void PrintSort(int* arr, int n);
void PopSort(int* arr, int n);
void PopSort(int* arr,int n)
{
int a = 0, b = 0;
for (a = 0; a < n - 1; a++)
{
for (b = 0; b < n - 1 - a; b++)
{
if (arr[b] > arr[b + 1])
{
int mid = 0;
mid = arr[b + 1];
arr[b + 1] = arr[b];
arr[b] = mid;
}
}
}
}
void PrintSort(int* arr, int n)
{
for (int i = 0; i < n; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
}
int main()
{
int arr[] = { 1,5,2,6,8,7,9,3,0,4 };
int n = sizeof(arr) / sizeof(int);
PrintSort(arr, n);
PopSort(arr, n);
PrintSort(arr, n);
return 0;
}底层逻辑
每次都是相邻的两个数进行比较。 一共构造两层循环。 一般都是从前到后进行比较，所以每次确定的数在最后一个。 外层循环（N-1）次。 内层循环（N-1-A）次。（其中A为外层循环的次数） 时间复杂度为：O(N^2)。
致谢
感谢您花时间阅读这篇文章！如果您对本文有任何疑问、建议或是想要分享您的看法，请不要犹豫，在评论区留下您的宝贵意见。每一次互动都是我前进的动力，您的支持是我最大的鼓励。期待与您的交流，让我们共同成长，探索技术世界的无限可能！
腾讯云开发者
