归并排序和插入排序理解记录

归并排序和插入排序

排序

排序:顾名思义就是对一系列数值型数据进行有序化,常见的有消费金额,成绩排名,学号排名等。

升序和降序

升序:数值由低到高进行排列。比如1, 2, 5, 9 等
降序:数值由高到低进行排列。比如9, 5, 2, 1等

插入排序

对数据进行插入排序。比如有数据[1, 3, 4, 6, 1, 6, 9]需进行插入排序。
基本思想:设置第一个元素为R0岗哨,如该值为1. 依次从原数组取出数据进行插入排序
如原数组Array=[3, 4, 6, 1, 6, 9],新数组NewArray=[1]; 并且设置k=i
判断 Array[i] >= NewArray[k], 则直接插入并且i加1;否则进一步k-1继续进行比较,直至迭代完所有数据
插入排序

合并排序

合并排序,又称为归并排序,是应用‘分治法’思想的典型方式。
核心思想是将若干个有序子序列进行合并,产生一个有序序列。一般是进行两两合并操作,迭代完成所有合并操作。
第一步对数据[1, 3, 4, 6, 1, 6, 9]进行分割有序单一数组,[1],[3],[4],[6],[1],[6],[9]
第二步,两两合并(升序)。w[i] <=x[j], 条件满足,w[i]写入新的数组r[k]中并且i和k分别加1;否则x[j]值写入新的数组r[k]中并且j和k分别加1,直至遍历完数组
第三步,对合并和有序数组,重复进行第二步操作。直至完成所有数据排序。
合并排序

总结

排序关键在于如何比较。
插入排序:用旧数组数据对新数组数据从后往前(倒插入)进行比较,提高比较效率。
合并排序:关键在于如何合并。两个数组进行比较合并成新的数组更加有效。

    原文作者:qq_21956177
    原文地址: https://blog.csdn.net/qq_21956177/article/details/89021170
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞