1.排序的概念及其运用

1.1 排序的概念

1.2 排序的应用

1.3

2.常见排序算法的实现

2.1 插入排序

2.1.1 基本思想

直接插入排序是一种简单的插入排序法，其基本思想是：把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列 。实际中我们玩扑克牌时，就用了插入排序的思想

(相关资料图)

2.1.2 直接插入排序

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

代码实现

先写单趟的，再写多趟的。要注意的是：外层循环是i<n-1,否则end+1会越界。

直接插入排序的特性总结：

元素集合越接近有序，直接插入排序算法的时间效率越高

时间复杂度：O(N^2)

空间复杂度：O(1)，它是一种稳定的排序算法

稳定性：稳定

2.1.3 希尔排序(缩小增量排序)

希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数N，把待排序文件中所有记录分成N个组，所有距离为N的记录分在同一组内，并对每一组内的记录进行排序。然后取 (N/2或者N/3+1) 重复上述分组和排序的工作。当到达N=1时，所有记录在统一组内排好序。

希尔排序步骤：1.与排序，目的：是数组接近有序，间隔为gap的数据分为一组，插入排序。2.直接插入排序。升序：gap越大，大的数据可以越快跳到后面，小的越快跳到前面，不是很接近有序。gap越小，跳动越慢，越接近有序。

希尔排序的特性总结：

希尔排序是对直接插入排序的优化。

当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。

希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些树中给出的希尔排序的时间复杂度都不固定:

《数据结构(C语言版)》— 严蔚敏

————————————————

希尔排序的特性总结：

希尔排序是对直接插入排序的优化。

当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。

希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些树中给出的希尔排序的时间复杂度都不固定:

《数据结构(C语言版)》— 严蔚敏

2.2 选择排序

2.2.1基本思想

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

2.2.2 直接选择排序

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

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

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

如果不加修正maxi的话，当begin为最大数时候，首先begin所指的值会与mini所指的值换成最小的，再与end所指的指换，那么end所指的值就成最小了，begin所指的值就不是最小的了，那么永远达不到排序效果。

直接选择排序的特性总结：

直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用

时间复杂度：O(N^2)

空间复杂度：O(1)

稳定性：不稳定

直接选择排序不管是否有序，时间复杂度都是O(N2)。效率比直接插入排序还满。

2.2.3 堆排序

堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。

堆排序的特性总结：

堆排序使用堆来选数，效率就高了很多。

时间复杂度：O(N*logN)

空间复杂度：O(1)

稳定性：不稳定

3.写在最后

那么八大排序的上半部分就到这里了   我致力于学习 zy1999_shui

————————————————

版权声明：本文为「沐曦希」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。

原文链接：https://blog.csdn.net/m0_68931081/article/details/126331527