常见的五类排序算法图解和实现(插入类:直接插入排序,折半插入排序,希尔排序)-阿里云开发者社区

开发者社区> 人工智能> 正文

常见的五类排序算法图解和实现(插入类:直接插入排序,折半插入排序,希尔排序)

简介:

基本的五类排序算法(插入,选择,交换,归并,基数排序)。排序:将数据元素的一个任意序列,重新排列成一个按关键字有序的序列。

排序的稳定性:待排序列中有大于等于2个相同的项,且排序前后,相同项的相对位置是否发生了变化(如果变化了就是不稳定的排序,不变化就是稳定的)

内部排序:若整个排序过程不需要访问外存便能完成,则称此类排序问题为内部排序;(待排序列全部放入内存)

插入累排序:(直接插入,折半插入,希尔排序)

直接插入排序:

先将序列中第 1 个记录看成是一个有序子序列, 然后从第 2 个记录开始,逐个进行插入,直至整个序列有序。

通常是先把第一个记录看成是一个有序的序列,然后从第二个记录开始依次进行比较

r2处的38比第一个记录 r1处的49小,那么38插入到49的前面,把插入位置之后的记录顺次的后移一位,同时把带插入记录临时保存在 r0处(复制监视哨)。

然后把38插入到 r1处

下面是整个过程,一共7趟排序过程

特点:在最后一趟排序前,此序列没有一个记录到其最终位置。(所有的插入类排序的特点)

复制代码
 1 //递增排序
 2 void insertSort(int list[])
 3 {
 4     int j = 0;
 5     int i = 0;
 6     int temp = 0;
 7     //对待排序列直接插入排序
 8     //一般把第一个记录先看成是有序子序列,然后从第二个记录开始,逐个的和前面去比较,插入
 9     for (i = 1; i <= 8; i++) {
10         //和前面的有序子序列的记录,逐个的比较,直接插入
11         if (list[i] < list[i - 1]) {
12             //复制为监视哨
13             temp = list[i];
14             //移位
15             list[i] = list[i - 1];
16             //继续顺次的和前面的记录进行比较,如果还有不小于它的,那么继续后移,直接插入排序
17             for (j = i - 1; temp <= list[j]; j--) {
18                 //记录后移
19                 list[j + 1] = list[j];
20                 //插入
21                 list[j] = temp;
22             }
23         }
24     }
25 }
26 
27 int main(void)
28 {
29     int source[8] = {49, 38, 65, 97, 76, 13, 27, 49};
30     
31     insertSort(source);
32     
33     for (int i = 0; i < 8; i++) {
34         printf(" %d ", source[i]);
35     }
36     
37     return 0;
38 }
复制代码

13  27  38  49  49  65  76  97 Program ended with exit code: 0

算法评价

最好的情况:待排序记录按关键字从小到大排列(正序)

比较次数:移动次数:0 

最坏的情况:待排序记录按关键字从大到小排列(逆序) 

比较次数:移动次数: 

一般情况:待排序记录是随机的,取平均值。 比较次数和移动次数均约为: n^2/4

时间复杂度:T(n)=O(n²) (最坏情况下),最好的情况是O(n),平均时间复杂度是O(n²)

空间复杂度:S(n)=O(1) ,且直接插入排序是稳定排序

 

折半插入排序

用折半查找方法确定插入位置的排序。思想类似直接插入排序,只不过,要设置 mid=不大于(low+high)/2的最大整数,当插入到 mid 左边(做半区),则改变 high(mid-1),如果插入到 mid 右边,则改变 low(mid+1)。

初试序列,同样是把第一个记录看成是有序的子序列,然后从第二个记录开始,依次进行比较

假设只有最后的20这个记录了

mid=(0+6)/2=3,指向39处,20比mid 的值小,插入到 mid 左边,改变 high=mid-1

重新计算 mid=1,指向13处,继续和20比较,20比 mid的值大,插入到 mid 右边,改变 low=mid+1

计算 mid=2,指向30,20比 mid 的值30小,插入到 mid 左边,改变 high=mid-1

直到low>high时,由折半查找得到的插入位置为low或high+1。

复制代码
//递增排序
void insertHalfSort(int list[])
{
    int j = 0;
    int i = 0;
    int low = 0;
    int high = 0;
    int mid = 0;
    int temp = 0;//临时监视哨
    //一般把第一个记录先看成是有序子序列,然后从第二个记录开始,前面去比较,折半插入
    for (i = 1; i <= 8; i++) {
        //复制为监视哨
        temp = list[i];
        low = 0;
        high = i - 1;
        //当 low>high,则找到了插入位置,为 low或者 high+1
        while (low <= high) {
            //循环计算 mid 的值
            mid = (int)((low + high) / 2);
            //待插入记录和 mid进行比较
            if (temp < list[mid]) {
                //改变 high
                high = mid - 1;
            }else{
                //改变 low
                low = mid + 1;
            }
        }
        //循环结束,说明找到了插入位置,进行移位
        for (j = i - 1; j >= low; j--) {
            list[j + 1] = list[j];
        }
        //插入
        list[low] = temp;
    }
}
复制代码

折半插入,适用于记录较多的场景,但是记录的移动次数和直接插入排序一样,故时间复杂度一样。

最好是 o(n),最差是 O(n²),平均是 O(n²)。空间复杂度是 o(1)。

特点:折半插入排序的比较次数和初始的序列无关,因为折半的次数一定,折一次比较一次。和直接插入比较,仅减少了比较次数,移动次数不变。折半插入排序是稳定排序

 

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

基本思想:对待排序列先作“宏观”调整,再作“微观”调整。先取一个正整数 d1 < n,把所有相隔 d1 的记录放在一组内,组内进行直接插入排序;然后取 d2 < d1,重复上述分组和排序操作,直至 di = 1,即所有记录放进一个组中排序为止。其中 di 称为增量。且增量 d逐渐变小。

增量d 的取法:最后一个值一定为1,且其余的值没有除1之外的公因子。

如图,增量为5,把相隔5的记录放到一组内,组内进行直接插入排序

分别把增量为5的记录找出,放在一组内,每组内直接插入排序

分别对子序列进行插入排序

缩小增量d=3

分别把增量 为3的记录找出

找完之后,缩小增量d=1,进行插入排序

直接插入排序适用于基本有序的情况,而希尔排序会使整个序列更加的有序。

特点:希尔排序是不稳定的排序方法

 

增量序列取法;

如何选择增量序列以产生最好的排序效果,至今仍没有从数学上得到解决。

     1)、没有除 1 以外的公因子;

     2)、最后一个增量值必须为 1。

记住:分组不是简单的“逐段分割”,而是将相隔某个增量的记录组成一个子序列。

 

希尔排序可提高排序速度

     1)、记录跳跃式前移,在进行最后一趟排序时,已基本有序。 

     2)、分组后 n 值减小,n^2 更小,而 T(n)=O(n^2),所以 T(n) 从总体上看是减小了。时间复杂度为 O(n log2(n)),控件复杂度为 o(1)

 

辛苦的劳动,转载请注明出处,谢谢……
http://www.cnblogs.com/kubixuesheng/p/4353575.html

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
人工智能
使用钉钉扫一扫加入圈子
+ 订阅

了解行业+人工智能最先进的技术和实践,参与行业+人工智能实践项目

其他文章