【数据结构】排序算法

所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。 稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中 ，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。 内部排序：数据元素全部放在内存中的排序。 外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序

排序在生活中应用非常广泛，对各种各样的东西进行排序，比如价格的排序，成绩的排序等。

 这里是编程语言排行榜：

插入排序 （ I n s e r t i o n S o r t ） （Insertion Sort） （InsertionSort）是一种简单直观的排序算法，其基本思想是通过构建有序序列，对未排序的元素逐个进行插入，从而达到排序的目的。插入排序的核心思想是将未排序的元素逐个插入已排序序列的正确位置，直到所有元素都被插入完成，最终得到一个完全有序的序列

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

就像我们打扑克牌时，洗牌一样：

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

对于直接选择排序，有一下特性：

代码实现：

  希尔排序法 （ S h e l l S o r t ） （Shell Sort） （ShellSort）又称缩小增量法。在上述直接选择排序的基础上，相当于把每个记录的间隔变为 g a p gap gap.先选定一个整数 g a p gap gap，把待排序文件中所有记录分成个 g a p gap gap个组，所有距离为 g a p gap gap的记录分在同一组内，并对每一组内的记录进行排序。然后取重复上述分组和排序的工作。当到达 g a p gap gap=1时，所有记录在统一组内排好序，相当于前面 g a p gap gap不为1时，进行预排序，当 g a p gap gap缩小到1时，进行直接插入排序。

希尔排序是对直接插入排序的优化。当 g a p gap gap > 1时都是预排序，目的是让数组更接近于有序。当 g a p gap gap 等于 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。希尔排序每趟后， g a p gap gap可以变为 g a p / 2 gap/2 gap/2，也可以变为 g a p / 3 + 1 gap/3+1 gap/3+1，直到 g a p = 1 gap = 1 gap=1为止。 希尔排序的时间复杂度不好计算，因为 g a p gap gap的取值方法很多，导致很难去计算。 基本上时间复杂度大约在O(N1.25) ~ O(1.6N1.25)之间，这里记作O(N1.3)

代码实现：

选择排序 （ s e l e c t i o n S o r t ） （selection Sort） （selectionSort）的思想是：每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完

  直接选择排序是在元素集合 a r r a y [ i ] − a r r a y [ n − 1 ] array[i]-array[n-1] array[i]−array[n−1]中选择关键码最大(小)的数据元素，若它不是这组元素中的最后一个(第一个)元素，则将它与这组元素中的最后一个（第一个）元素交换，在剩余的 a r r a y [ i ] − a r r a y [ n − 2 ] （ a r r a y [ i + 1 ] − a r r a y [ n − 1 ] ） array[i]-array[n-2]（array[i+1]-array[n-1]） array[i]−array[n−2]（array[i+1]−array[n−1]）集合中，重复上述步骤，直到集合剩余1个元素。

  这里我们做一个优化，同时选择最大的和最小的，再进行交换。 注意：有一个特殊状况，当最大的数出现在开始时，最小的数和开始的数交换后，会将最大的数的位置做了改变。这里我们做一下特殊处理。 代码实现：

  堆排序 ( H e a p s o r t ) (Heapsort) (Heapsort)是指利用堆这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。 堆在前面已经介绍过了，这里不做详述，详见请看链接: https://blog.csdn.net/weixin_64906519/article/details/133035385

堆排序是每次将堆顶的数，也就是最大的数和最后一个数交换，相当于选出最大的放最后，再对前面没有放好的数再进行向下调整

代码实现：

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

  对于交换排序，我们最熟悉的就是冒泡排序了，冒泡排序就是将相邻的元素进行比较，再不断交换相邻元素，将较大(较小)的元素渐渐 ’浮‘ 到序列的末尾。 代码实现：

这里我们做一个优化，如果序列有序的话就不再进行判断

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

快排递归时，很像二叉树的前序遍历，后序只要分析如何按照基准值比较就可以

这里注意一个问题：当待排序列接近有序时，每次选第一个位置的元素作为 K e y Key Key的话，递归左区间时的长度可能为0，而右区间的长度为 n − 1 n-1 n−1，这样可能导致递归的深度变为 n n n，当数据量太大时，会导致加粗样式递归太深而出现栈溢出，所以我们用三数取中的办法来做优化。

代码实现：

1.霍尔 （ H o a r e ） （Hoare） （Hoare）版本的快速排序：   霍尔版本的思想是：选则第一个数据作为基准值 K e y Key Key，再定义两个指针 L L L和 R R R， L L L从左边开始走，负责找大于 K e y Key Key的数据， R R R从右边开始走，负责找小于 K e y Key Key的数据，再将这两个数据进行交换， L L L和 R R R再继续遍历，直到 L L L和 R R R重合。最后交换 K e y Key Key和 R R R所指的数据。 注意：这里要求选定左边第一个数为 K e y Key Key的时候，一定要 R R R指针先走，在最后 k e y key key和 R R R交换的时候，才能保证 R R R处左边的数据都小于 K e y Key Key，右边的都大于 K e y Key Key。 代码实现：

最后可以分别调用这三种快排；

代码实现：

这里可以做一个小优化，对小区间不再进行递归，而是直接进行插入排序

代码实现：

归并排序 （ M E R G E − S O R T ） （MERGE-SORT） （MERGE−SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法 （ D i v i d e a n d C o n q u e r ） （Divide and Conquer） （DivideandConquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

代码实现：

非比较排序中，计数排序是一种比较高效和常用的排序，而桶排序和基数排序在实际的应用中不是很多。这里以计数排序为例。

  计数排序的基本思想是统计每个元素出现的次数，然后根据统计信息将元素放回相对的位置。计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。

代码实现：