内部排序算法思路与实现【附图解&复杂度分析】

  排序也称排序算法(Sort Algorithm)，排序是将一组数据，依指定的顺序进行排列的过程。排序算法分为两类：

  排序算法根据稳定性可以分为：

插入排序包括直接插入排序和希尔排序。 对于插入排序，特征是进行元素间的比较。

算法思想：   对于待排序的数组，构建有序序列，对于无序序列中的每个元素，在有序序列中从后向前寻找到相应的位置进行插入。   例如，对于有序序列 {38,49,65,97} ，要插入元素 56，显然 56 要插入在 65 之前，则将 {65} , {97} 向后移动一位，将 {56} 插入在 {65} 之前，排序后数组为 {38,49,56,65,97}。

算法图解：对数组 [4,2,2,78,5,45] 进行直接插入排列： 算法稳定性：在直接插入排序中，对于相同的数据，可以设置条件确定插入位置，不必改变先后顺序。比如上例中，两个元素2的相对前后顺序没有变化。算法稳定。

代码实现：

复杂度分析：

时间复杂度 O(N2)   最好情况为数组升序排列，只需要比较 n-1 次即可，时间复杂度 O(N)。   最坏情况为数组降序排列，需要比较 1+2+…+(n-1)=n×(n-1)/2 次，交换 n-1 次,时间复杂度为 O(N2)。   插入排序的平均时间复杂度为 O(N2)。 空间复杂度 O(1)   直接插入排序使用常数级别的额外空间。

算法特征：

算法思想：   希尔排序又称缩小增量排序，是插入排序的改进形式。   考虑到直接插入排序在序列几乎排好序时效率达到线性排序级别，希尔排序依据不断递减的步长将待排序序列划分为若干子序列，对每个子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全部记录依次进行直接插入排序。

算法图解：对数组 [49’,38,65,97,76,13,27,49’’,55,04] 进行希尔排序：

算法稳定性：一次插入排序是稳定的，但是希尔排序对数据进行分组处理，分别进行插入排序，相同元素可能划分在不同组中，从而相对前后顺序会发生改变。比如上例中49’’ 与49’ 划分在不同组中，排序后顺序发生了变化。希尔排序不稳定。

代码实现：

复杂度分析：

时间复杂度 O(N log2 N)   希尔排序可以取不同的增量序列，相应的时间复杂度也不同；希尔排序最后一轮的增量必须为 1，保证排序完成后数组一定有序。   步长序列为 n/2i 时，最坏情况下退化为直接插入排序，时间复杂度为 O(N2)。   步长序列为 2k-1 时，最坏情况下时间复杂度为 O(N3/2)。   步长序列为 2i3j 时，最坏情况下时间复杂度为 O(N log2 N)。   希尔排序的渐进时间复杂度为O(N log2 N)。 空间复杂度 O(1)   希尔排序使用常数级别的额外空间。

选择排序包简单选择排序和堆排序。 对于选择排序，特征是进行元素间的比较与交换。

算法思想：   核心思想是比较，交换。在数组元素的比较中找到一个最小的元素，将其放在起始位置；之后每次从未排序序列中找到最小元素，将其放到已排序序列的末尾（即与未排序序列的首元素进行交换），直到所有元素均排序完毕。

算法图解：对数组 [4,5’,78,5’’,17,1] 进行简单选择排序：

算法稳定性：   在寻找最小元素，进行元素交换的过程中，可能导致相同元素的前后顺序发生变换。   例如：对于序列 (7) 2 5 9 3 4 [7] 1，用直接选择排序算法进行排序时候, (7) 和 1 调换, (7) 就跑到了 [7] 的后面了,原来的次序改变了,这样就不稳定了。如上例中的 5’ 与 5’’ 顺序改变。   选择排序不稳定。

代码实现：