C++中插入排序算法的示例分析-创新互联
这篇文章主要介绍C++中插入排序算法的示例分析,文中介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们一定要看完!
成都一家集口碑和实力的网站建设服务商,拥有专业的企业建站团队和靠谱的建站技术,十余年企业及个人网站建设经验 ,为成都上千余家客户提供网页设计制作,网站开发,企业网站制作建设等服务,包括成都营销型网站建设,品牌网站建设,同时也为不同行业的客户提供成都做网站、成都网站制作的服务,包括成都电商型网站制作建设,装修行业网站制作建设,传统机械行业网站建设,传统农业行业网站制作建设。在成都做网站,选网站制作建设服务商就选成都创新互联。具体内容如下
基本思想
每次将一个待排序的元素,按其大小插入到已经排好序的子序列的适当位置,知道全部元素插入完成为止。
直接插入排序
1.排序思路
arr[0...i-1]为有序区(刚开始时i=1,有序区只有arr[0]一个元素),arr[i...size]为待排序区,每次将待排序区的第一个元素arr[i]插入到有序区中的适当位置,每趟操作都使有序区增加一个元素,待排序区减少一个元素。
2.排序算法
void InsertSort(int* arr, int size) { if (arr == NULL) return; for (int i = 1; i < size; i++) { //1.保存要排序的数 int tmp = arr[i]; //2.去有序区寻找该数应该插入的位置 int j = i - 1; while (j >= 0 && tmp < arr[j]) { //3.把有序区的位置一个一个往后移 arr[j + 1] = arr[j]; j--; } arr[j + 1] = 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.排序算法
void InsertSort1(int* arr, int size) { if (arr == NULL) return; int i, j, low, high; //1.保存要插入的数 for (i = 1; i < size; i++) { int tmp = arr[i]; low = 0; high = i - 1; //2.折半查找插入位置(插入位置为high+1) while (low <= high) { int mid = low + ((high - low) >> 1); if (tmp < arr[mid]) high = mid - 1; else low = mid + 1; } //3.元素后移,插入 for (j = i - 1; j >= 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.排序算法
void ShellSort(int* arr, int size) { if (arr == NULL) return; int i, j, gap; //1.取gap gap = size / 2; while (gap > 0) { //2.分组比较 for (i = gap; i < size; i++) { int tmp = arr[i]; //3.移动元素,插入 j = i - gap; while (j >= 0 && tmp < arr[j]) { arr[j + gap] = arr[j]; j -= gap; } arr[j + gap] = tmp; } gap = gap / 2; } }
3.算法分析
希尔排序算法的性能分析是一个复杂的问题,它的时间复杂度与所取gap有关,一般认为其时间复杂度为O(N^1.3),空间复杂度为O(1)。
希尔排序是一种不稳定的算法。
以上是“C++中插入排序算法的示例分析”这篇文章的所有内容,感谢各位的阅读!希望分享的内容对大家有帮助,更多相关知识,欢迎关注创新互联网站建设公司行业资讯频道!
另外有需要云服务器可以了解下创新互联建站www.cdcxhl.com,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。
新闻标题:C++中插入排序算法的示例分析-创新互联
文章分享:http://pwwzsj.com/article/gojop.html