C++插入排序算法实例详解
本文实例为大家分享了C++插入排序算法实例的具体代码,供大家参考,具体内容如下
基本思想
每次将一个待排序的元素,按其大小插入到已经排好序的子序列的适当位置,知道全部元素插入完成为止。
直接插入排序
1.排序思路
arr[0...i-1]为有序区(刚开始时i=1,有序区只有arr[0]一个元素),arr[i...size]为待排序区,每次将待排序区的第一个元素arr[i]插入到有序区中的适当位置,每趟操作都使有序区增加一个元素,待排序区减少一个元素。
2.排序算法
voidInsertSort(int*arr,intsize) { if(arr==NULL) return; for(inti=1;i=0&&tmp 3.算法分析
直接插入排序由两重循环构成,外循环进行n-1次。
若初始数据序列递增有序即为正序时,每一趟排序不进入内循环,仅进行一次大小比较。此时元素移动次数为2次(tmp=arr[i]和arr[j+1]=tmp)。所以正序时比较次数和元素移动次数均达到最小值Cmin和Mmin:
Cmin=n-1
Mmin=2(n-1)
若初始数据序列递减有序即为逆序时,因当前有序区的元素均大于待排序区的元素,所以需要将待插入元素与arr[0...i-1]中全部元素进行比较,这需要进行i次比较;内循环中需将arr[0...i-1]中所有元素后移(i-1)-0+1=i次,外加tmp=arr[i]和arr[j+1]=tmp的两次移动,一趟排序所需的元素移动次数为i+2次。所以逆序时比较次数和元素移动次数均达到最da值Cmax和Mmax:
Cmax=n(n-1)/2
Mmax=(n-1)(n+4)/2
正序时直接插入排序算法的时间复杂度为O(N),逆序时直接插入排序算法的时间复杂度为O(N^2)。
故直接插入排序算法的时间复杂度为O(N^2)。由于只使用了i、j、tmp三个辅助变量,故空间复杂度为O(1)。
当i>j且arr[i]=arr[j]时,直接将arr[i]插入到arr[j]后,故直接插入排序是稳定的。
折半插入排序(二分插入排序)
1.排序思路
采用折半查找方法先在arr[0...i-1]中找到插入位置,再通过移动元素进行插入
2.排序算法
voidInsertSort1(int*arr,intsize) { if(arr==NULL) return; inti,j,low,high; //1.保存要插入的数 for(i=1;i>1); if(tmp =high+1;j--) { arr[j+1]=arr[j]; } arr[j+1]=tmp; } } 3.算法分析
当初始数据序列为正序时,比较次数并不能减少;当为逆序时,比较次数也不会增加。元素移动次数与直接插入排序相同。
故折半插入排序的时间复杂度为O(N^2),空间复杂度为O(1),是稳定的。
就平均性能而言,折半查找优于顺序查找,所以折半插入排序优于直接插入排序。
希尔排序
1.排序思路
希尔排序是一种分组插入排序。先取一个小于n的整数d1,作为第一个增量,序列被分为d1组,所有相互之间距离为d1的倍数的元素放在同一个组中,在各组内进行直接插入排序;然后取第二个增量d2(
希尔排序每趟并不产生有序区,在最后一趟排序结束之前,所有元素并不一定归位,每趟排完之后,数据越来越接近有序。
2.排序算法
voidShellSort(int*arr,intsize) { if(arr==NULL) return; inti,j,gap; //1.取gap gap=size/2; while(gap>0) { //2.分组比较 for(i=gap;i=0&&tmp 3.算法分析
希尔排序算法的性能分析是一个复杂的问题,它的时间复杂度与所取gap有关,一般认为其时间复杂度为O(N^1.3),空间复杂度为O(1)。
希尔排序是一种不稳定的算法。以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持毛票票。