Michael

写写代码,说说人生

您好,我是Michael,欢迎来到我的个人家园。
代码搬运工,目前就职于XX证券,努力修行中。


H5 / Java / Objc / Swift / Vue / RN

算法-插入排序

生活总是充满了惊喜,无论是惊还是喜。

核心思想

有一个已经有序的数据序列,要求在这个已经排好的数据序列中插入一个数,但要求插入后此数据序列仍然有序,这个时候就要用到一种新的排序方法——插入排序法,插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中,从而得到一个新的、个数加一的有序数据,算法适用于少量数据的排序。

示例

对于长度为n的数组,全部完成排序需要经过n-1轮的查找,首先我们从第二个数开始,向前比较,如果比前面的数小,则继续向前对比,直至遇见大于前置位数字时,或者到了数组的最前端,选择正确的位置插入。下面是图解: 插入排序-第一轮.png

经过第一轮,前面两个数据已经有序,第二轮从第三个值开始: 插入排序-第二轮.png 每一轮都是从后向前对比,找到合适的位置插入,其中被越过的数值向后移一位,第三轮: 插入排序-第三轮.png

整个排序过程:

原始长度10
100	5	3	11	33	6	8	7	1	3	
第2轮
5	100	3	11	33	6	8	7	1	3	
第3轮
3	5	100	11	33	6	8	7	1	3	
第4轮
3	5	11	100	33	6	8	7	1	3	
第5轮
3	5	11	33	100	6	8	7	1	3	
第6轮
3	5	6	11	33	100	8	7	1	3	
第7轮
3	5	6	8	11	33	100	7	1	3	
第8轮
3	5	6	7	8	11	33	100	1	3	
第9轮
1	3	5	6	7	8	11	33	100	3	
第10轮
1	3	3	5	6	7	8	11	33	100	

C语言代码

#pragma mark - 插入排序
void insertSort(int arr[] ,int len) {
    printf("原始长度%d\n",len);
    printfArr(arr, len);
    for (int i = 1; i < len; i++) {
        printf("第%d轮\n",i+1);
        // 顺序不对 需要进行移位
        if (arr[i] < arr[i-1]) {
            int currentNum = arr[i];
            int target = i;
            for (int j = i; j >= 0; j--) {
                int compareNum = arr[j-1];
                if (currentNum < compareNum) {
                    arr[j] = arr[j-1];
                    target = j-1;
                }else{
                    break;
                }
            }
            arr[target] = currentNum;
        }
        printfArr(arr, len);
    }
}

时间复杂度

插入排序使用了两层循环来进行排序,因此时间复杂度仍为 O ( n^2 )

结语

由于最前方的有序区本身是有序的,在寻找插入位置的逻辑上还有优化的空间,所以插入排序还有个升级版:折半插入排序(⊙o⊙)…,折中插入不同的地方在于:和有序区对比的时候是从有序区中间的值开始对比的,根据对比结果来决定往左半区或者右半区继续使用同样的折半查找,直至找到相应位置。

最近的文章

算法-快速排序

这个排序算法的命名有点随意啊,这种态度怎么行前言这个算法感觉脱离了简单算法的范畴,脑袋稍微要转那么一点儿弯,排序代码倒是多了不少。核心思想通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。示例 首先,我们枪打出头鸟,把第一个数10给拎出来,留下一个坑位(坑位很重要*),做参照物:基数。 有了基数之后,我们建立左右指针各...…

算法设计继续阅读
更早的文章

算法-选择排序

这几乎是最简单的排序方法…核心思想选择排序的思想其实和冒泡排序有点类似,都是在一次排序后把最小的元素放到最前面,或者将最大值放在最后面。但是过程不同,冒泡排序是通过相邻的比较和交换。而选择排序是通过对整体的选择,每一趟从前往后查找出无序区最小值,将最小值交换至无序区最前面的位置。示例第一轮过程: 初始化一个minIndex=0,i=0~9,依次将arr[i]与arr[minIndex]进行对比,如果arr[minIndex]的值较小则无操作,如果arr[i]的值较小,则将minInde...…

算法设计继续阅读