数据结构初阶：排序

概述：本篇博客主要介绍关于排序的算法。

目录

1.排序概念及应用

1.1 概念

1.2 运用

1.3 常见的排序算法

2. 实现常见排序算法 

 2.1 插入排序

 2.1.1 直接插入排序

2.1.2 希尔排序 

2.2 选择排序

2.2.1 直接选择排序

 2.2.2 堆排序

2.3 交换排序

2.3.1 冒泡排序 

2.3.2 快速排序 

 2.3.2.1 hoare版本

2.3.3.2 挖坑法

 2.3 归并排序

3. 非比较排序 --计数排序

4. 总结 

---

1.排序概念及应用

1.1 概念

排序： 所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作

1.2 运用

 在生活中我们也会有用到各种各样的排序，譬如：在网上购物商店中根据某个商品进行排序。

譬如：高等院校之间的排名 

1.3 常见的排序算法

---

2. 实现常见排序算法 

 以该序列为例子：5,3,9,6,2,4,7,1,8

 2.1 插入排序

• 基本思想 ：                                                                                                                                     直接插入排序是一种简单的插入排序法，其基本思想是：把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列

 

 实际中我们玩扑克牌，就使用了插入排序的思想。

 2.1.1 直接插入排序

当插入第i(i>=1)个元素时，前面的 array[0], array[1], …, array[i - 1]已经排好序，此时用 array[i]的排序码与 array[i - 1], array[i - 2], … 的排序码顺序进行比较，找到插入位置即将 array[i]插入，原来位置上的元素顺序后移。 

 

 代码实现：

//直接插入排序
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;}
}

 逻辑概述：

 直接插入排序的函数InsertSort，用于对整数数组进行排序。

函数的参数为整数数组arr和数组的长度n。

在函数内部，通过一个循环遍历数组的前n - 1个元素。对于每个元素，设置一个变量end初始值为当前循环的索引i，并将下一个元素arr[end + 1]的值赋给变量tmp。

然后，通过一个while循环，只要end大于或等于0，并且当前end位置的元素arr[end]大于tmp，就将arr[end]的值向后移动一位（即arr[end + 1] = arr[end]），并将end减1。当找到一个位置，使得arr[end]小于或等于tmp时，循环结束。

最后，将tmp的值插入到end + 1的位置，完成一次插入操作。

这样，通过每次将未排序的元素插入到已排序的部分，逐步完成整个数组的排序。

2.1.2 希尔排序 

希尔排序法又称缩小增量法。其基本思想是：先选定一个整数（通常是 gap = n / 3 + 1），把待排序文件所有记录分成各组，所有距离相等的记录分在同一组内，并对每一组内的记录进行排序，然后 gap = gap / 3 + 1 得到下一个整数，再将数组分成各组，进行插入排序，当 gap = 1 时，就相当于直接插入排序。

希尔排序是在直接插入排序算法的基础上进行改进的一种高效的排序算法，也称“缩小增量排序”。它通过使用一个逐渐减小的增量序列，将数组分成若干个子序列，并对每个子序列进行插入排序。随着增量逐渐减小，每组包含的元素越来越多，当增量减至 1 时，对整个数组进行一次完整的插入排序，确保数组完全有序。

代码实现： 

//希尔排序
void ShellSort(int* arr, int n)
{int gap = n;while (gap > 1){//5 2 1gap = 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;}}
}

 逻辑概述： 

 这段 C 语言代码实现了希尔排序的算法。希尔排序是一种插入排序的改进算法，通过按照一定的间隔（初始为数组长度）进行分组插入排序，逐步缩小间隔，直到间隔为 1 时完成整个数组的排序。

具体逻辑如下：

1. 首先设定初始间隔 gap 为数组长度 n。
2. 在每次循环中，通过 gap = gap / 3 + 1 计算新的间隔，直到 gap 小于等于 1。
3. 对于每个间隔 gap，进行插入排序。从数组的第 gap 个元素开始，将当前元素与前面间隔为 gap 的元素进行比较，如果前面的元素大于当前元素，则将前面的元素后移 gap 位，直到找到合适的位置插入当前元素。

 

2.2 选择排序

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

2.2.1 直接选择排序

1. 在元素集合 array[i]--array[n-1] 中选择关键码最⼤(小)的数据元素

2. 若它不是这组元素中的最后一个(第一个)元素，则将它与这组元素中的最后⼀个（第⼀个）元素 交换

3. 在剩余的 array[i]--array[n-2]（array[i+1]--array[n-1]） 集合中，重复上述步 骤，直到集合剩余 1 个元素

 

 代码实现：

//直接选择排序
void SelectSort(int* arr, int n)
{int begin = 0, end = n - 1;while (begin < end){int mini = begin, maxi = begin;for (int i = begin + 1; i <= end; i++){if (arr[i] < arr[mini]){mini = i;}if (arr[i] > arr[maxi]){maxi = i;}}//mini begin//maxi endSwap(&arr[mini], &arr[begin]);Swap(&arr[maxi], &arr[end]);begin++;end--;}
}

逻辑概述： 

这段 C 语言代码实现了直接选择排序的算法。其逻辑概述如下：

1. 定义两个指针begin和end，分别指向数组的起始位置和末尾位置。
2. 在每次循环中，通过遍历从begin + 1到end的元素，找到最小元素的索引mini和最大元素的索引maxi。
3. 将最小元素与begin位置的元素交换，将最大元素与end位置的元素交换。
4. 然后将begin指针向后移动一位，end指针向前移动一位，继续下一轮的选择和交换，直到begin大于等于end，完成整个数组的排序。

 2.2.2 堆排序

堆排序由博主的上篇博客有详细介绍，这里不过多赘述。 

https://blog.csdn.net/2401_87194328/article/details/147310043?spm=1001.2014.3001.5502 

2.3 交换排序

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

 

2.3.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;}}
}

逻辑概述： 

 这段 C 语言代码实现了冒泡排序的算法：

1. 外层循环控制排序的轮数，共进行n轮。
2. 内层循环用于每一轮的比较和交换操作。在每一轮中，从数组的第一个元素开始，依次比较相邻的两个元素，如果前一个元素大于后一个元素，则进行交换。每一轮结束后，最大的元素会“浮”到数组的末尾。
3. 在内层循环中，设置一个标志变量exchange，用于判断在本轮循环中是否进行了交换操作。如果没有进行交换，说明数组已经是有序的，此时可以提前结束排序。

 

2.3.2 快速排序 

 快速排序（Quick Sort）是 Hoare 于 1962 年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后对左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

 2.3.2.1 hoare版本

int _QuickSort(int* arr, int left, int right)
{int keyi = left;++left;while (left <= right){//right:从右往左找比基准值要小的数据while (left <= right && arr[right] > arr[keyi]){--right;}//left:从左往右找比基准值要大的数据while (left <= right && arr[left] < arr[keyi]){++left;}//left和right交换if (left <= right){Swap(&arr[left++], &arr[right--]);}}Swap(&arr[keyi], &arr[right]);return right;
}

逻辑概述： 

 该代码实现了快速排序的一个函数_QuickSort。快速排序的基本思想是分治和递归。

在这个函数中，首先选择一个基准元素arr[keyi]，然后通过两个指针left和right从待排序序列的两端向中间扫描。

对于右指针right，从右往左找比基准值小的数据；对于左指针left，从左往右找比基准值大的数据。当找到这样的数据且left小于等于right时，交换这两个元素的位置。

当left和right相遇后，将基准元素与right指针所在位置的元素交换。

最后，函数返回right指针的位置，并对基准元素左边和右边的子序列分别进行快速排序，直至子序列长度为1（已经有序）。

 

2.3.3.2 挖坑法

 思路： 创建左右指针。首先从右向左找出比基准值小的数据，找到后立即放入左边坑中，当前位置变为新的“坑”，然后从左到右找出比基准值大的数据，找到后立即放入右边坑中，当前位置变为新的“坑”，结束循环后将住开始存储的分界值放入当前的“坑”中，返回当前“坑”下标（即分界值下标）。

 代码实现：

//快速排序法  挖坑法
void QuickSort1(int* arr, int begin, int end)
{if (begin >= end)return;int left = begin,right = end;int key = arr[begin];while (begin < end){//找小while (arr[end] >= key && begin < end){--end;}//小的放到左边的坑里arr[begin] = arr[end];//找大while (arr[begin] <= key && begin < end){++begin;}//大的放到右边的坑里arr[end] = arr[begin];}arr[begin] = key;int keyi = begin;//[left,keyi-1]keyi[keyi+1,right]QuickSort1(arr, left, keyi - 1);QuickSort1(arr, keyi + 1, right);
}

逻辑概述 ：

 该代码实现了快速排序的一种方法——挖坑法。函数QuickSort1用于对给定的整数数组进行快速排序。

首先，进行边界条件判断，如果起始索引begin大于或等于结束索引end，则直接返回。

然后，设置左右指针left和right，分别指向起始索引begin和结束索引end，并选取arr[begin]作为基准值key。

接下来，通过两个循环进行元素的交换和调整。在第一个循环中，从右往左找到比基准值小的元素，将其放到左边的“坑”（当前begin位置）中；在第二个循环中，从左往右找到比基准值大的元素，将其放到右边的“坑”（当前end位置）中。当begin和end相遇时，将基准值放入该位置。

最后，以基准值所在位置keyi为界，对左右子序列分别递归调用QuickSort1函数进行排序。

 2.3 归并排序

•  算法思想：                                                                                                                                        归并排序（MERGE-SORT）是建立在归并操作上的⼀种有效的排序算法,该算法是采用分治法（Divide and Conquer）的⼀个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个 子序列有序，再使子序列段间有序。若将两个有序表合并成⼀个有序表，称为二路归并。归并排序核心步骤：

 

代码实现： 

 

void _MergeSort(int* arr, int left, int right, int* tmp)
{//分解if (left >= right){return;}int mid = (left + right) / 2;//根据mid划分左右两个序列:[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++];}}//左序列数据没有全部放到tmp数组中//右序列数据没有全部放到tmp数组中while (begin1 <= end1){tmp[index++] = arr[begin1++];}while (begin2 <= end2){tmp[index++] = arr[begin2++];}//tmp中有序的数据导入到原数组for (int i = left; i <= right; i++){arr[i] = tmp[i];}
}
//归并排序
void MergeSort(int* arr, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);_MergeSort(arr, 0, n - 1, tmp);free(tmp);tmp = NULL;
}

 逻辑概述：

这段代码是一个使用归并排序算法对整数数组进行排序的 C 语言实现。以下是对代码的详细解释：

• _MergeSort 函数：
  • 这是归并排序的核心函数，用于对数组的特定子区间进行排序和合并。
  • 如果子区间的左边界大于或等于右边界，函数直接返回，这是递归的终止条件。
  • 通过计算中间索引 mid，将数组划分为两个子区间：[left, mid] 和 [mid + 1, right]，然后对这两个子区间分别进行递归调用 _MergeSort 进行排序。
  • 接下来，将两个已排序的子区间合并到一个临时数组 tmp 中。通过两个指针 begin1 和 begin2 分别遍历两个子区间，将较小的元素依次放入 tmp 数组中。当其中一个子区间遍历完后，将另一个子区间剩余的元素全部放入 tmp 数组中。
  • 最后，将 tmp 数组中的有序数据复制回原数组 arr。
• MergeSort 函数：
  • 这个函数用于启动整个归并排序过程。
  • 首先，分配一个与原数组大小相同的临时数组 tmp。
  • 然后，调用 _MergeSort 函数对整个数组进行排序和合并。
  • 排序完成后，释放临时数组的内存，并将其指针置为 NULL。

3. 非比较排序 --计数排序

 计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。操作步骤：                                       

1.)统计相同元素出现次数。      2.）根据统计的结果将序列回收到原来的序列。

 代码实现：

//非比较排序 -- 计数排序
void CountSort(int* arr, int n)
{int min = arr[0], max = arr[0];for (int i = 1; i < n; i++){if (arr[i] < min){min = arr[i];}if (arr[i] > max){max = arr[i];}}//max minint range = max - min + 1;int* count = (int*)malloc(sizeof(int) * range);if (count == NULL){perror("malloc fail!");}memset(count, 0, sizeof(int) * range);//直接用calloc也是可以的for (int i = 0; i < n; i++){count[arr[i] - min]++;}//将次数还原到原数组中int index = 0;for (int i = 0; i < range; i++){//数据出现的次数count[i]//下标———源数据 i+minwhile (count[i]--){arr[index++] = i + min;}}
}

 逻辑概述：

 这段代码是一个使用计数排序算法对整数数组进行排序的函数 CountSort 。

1. 首先，函数通过遍历数组找到数组中的最小值 min 和最大值 max 。
2. 然后，计算数组值的范围 range ，并使用 malloc 函数分配一个大小为 range 的整数数组 count ，用于记录每个值出现的次数。如果 malloc 分配内存失败，会输出错误信息。
3. 接下来，通过遍历原始数组，将每个值出现的次数记录在 count 数组中。
4. 最后，通过遍历 count 数组，将每个值按照出现的次数还原到原始数组中，从而实现排序。

 

4. 总结 

 以上便是本篇博客的所有内容，如果大家学到了知识，还请给博主点点赞！！！