排序_插入排序_希尔排序

直接插入排序算法(参考本人博文https://www.cnblogs.com/KeithTee/p/15186334.html)的时间复杂度为O(n²),但是,如果待排序列为“正序”时,时间复杂度可以提高到O(n),由此可见,它更适用于基本有序的排列表和数据量不大的排列表。

希尔排序是基于上述两点对直接插入排序改进而来。又称缩小增量排序。

 1 void ShellSort(ElemType A[] , int n){
 2     //A[0]是暂存单元,不是哨兵,当j <= 0时,插入位置已到
 3     
 4     for (dk = n/2 ; dk >= 1 ;dk /= 2)        //步长变化
 5         for(i = dk + 1 ; i <= n ;  ++ i)
 6             if(A[i] < A[i -dk] ){        //需将A[i]插入有序增量子表
 7                 A[0] = A [i];    //暂存在A[0]
 8                 for( j = j -dk ; j>= && A[0]< A [j] ; j -= dk)
 9                     A[j + dk] = A [j];        //记录后移,查找插入的位置
10                 A[j + dk] = A[0];            //插入
11             }
12 }

空间效率:同直接插入算法,O(1)。

时间效率:最坏的情况下O(n²)。

稳定性:不稳定。(当相同关键字的记录被划分到不同的子表时,可能会改变他们之间的相对次序)

适用性:仅适用于线性表为顺序存储的情况。

上一篇:基于visual Studio2013解决面试题之1408桶排序


下一篇:ax-qt987只输一顿的方法