老青菜

插入排序

2019-05-01

插入排序是一种简单直观的排序算法,属于比较类排序,内部是通过比较元素大小,决定每个元素需要插入哪个位置。
常见的主要有两种:

  1. 直接插入排序(InsertSort)
  2. 希尔排序(ShellSort)


直接插入排序

核心思想如下:

  1. 列表分为有序和无序两部分,一般假设第一个元素是有序列表,从第二个元素开始都是无序列表。
  2. 依次遍历无序列表的元素,在有序列表中找到要插入的位置。
  3. 直到整个序列的待插入元素为0,则整个序列全部有序。

代码实现

// objc 版本
- (void)insertSort:(int[] )arr withLength:(int )length {
    //第一个元素是有序序列,遍历无序的序列,一个个插入元素
    for (int i=1; i<length; i++) {
        //遍历有序序列,和 待插入的元素比较
        int insertVar = arr[i];
        int j = i;
        //如果 待插入元素比 有序序列的元素小,把有序的元素往后移
        while (j-1>=0 && insertVar<=arr[j-1]) {
            arr[j] = arr[j-1];
            j--;
        }
        //找到要插入的位置,插入元素
        arr[j] = insertVar;
    }
}

算法分析

最好时间复杂度:若文件的初始状态是正序的,一趟扫描即可完成排序,时间复杂度是 O(n)
最坏时间复杂度:若初始文件是反序的,比较和移动次数均达到最大值,时间复杂度是 O(n²)
平均时间复杂度: O(n²)
空间复杂度:O(1)
稳定性:稳定。




希尔排序

希尔排序(ShellSort)是对直接插入排序的一种改进。
核心思想如下:

  1. 先取一个小于n步长d1,把距离为d1的元素,放在一组,列表最后分成d1组,并对各组进行直接插入排序。
  2. 然后取步长d2,重复上述过程,把间隔为d2的元素放在一组,每组做插入排序。
  3. 以此类推,取步长d3步长d4,分组,组内做插入排序,直到步长dn = 1,整个列表是一组,这时候已经足够有序。

代码实现

// objc 版本
- (void)shellSort:(int[] )arr withLength:(int )length {
    //选择一个步长step, 每次步长减半
    for (int step = floorl(length/2.0); step>0; step=floorl(step/2.0)) {
        //把间隔为step的元素放在一组,做插入排序
        for (int i=step; i<length; i++) {
            int insertVar = arr[i];
            int j = i;
            //如果 待插入元素比 有序序列的元素小,把有序的元素往后移
            while (j-step>=0 && insertVar <= arr[j-step]) {
                arr[j] = arr[j-step];
                j-=step;
            }
            //找到要插入的位置,插入元素
            arr[j] = insertVar;
        }
    }
}

算法分析

最快时间复杂度:若文件的初始状态是正序的,一趟扫描即可完成排序,时间复杂度是 O(n)
最坏时间复杂度:若初始文件是反序的,比较和移动次数均达到最大值,时间复杂度是 O(n²)
平均时间复杂度: O(n^1.3)
空间复杂度:O(1)
稳定性:不稳定。

使用支付宝打赏
使用微信打赏

若你觉得我的文章对你有帮助,欢迎点击上方按钮对我打赏

扫描二维码,分享此文章