欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

常见的排序算法——插入排序

程序员文章站 2022-06-04 18:32:07
...

插入排序

a. 基本思想

每一次将一个待排序的元素,按其排序码的大小,插入到前边以排好序的合适位置上,直到元素全部插完为止。

直接插入排序

当插入第 i 个元素时,前边的 i - 1 个元素已经排好序,此时用第 i 个元素和 i - 1、i - 2、…..的元素比较,找到插入位置即将第i个元素插入,原来的位置上的元素顺序后移。
常见的排序算法——插入排序

代码如下:
void InsertSort(int array[], int size)
{

    //一张牌的时候不用排,因此i从1开始
    for (int i = 1; i < size; ++i)
    {
        int key = array[i];
        int end = i - 1;

        while(end >= 0 && key < array[end])
        {
            //array[end+1]的值已经给key了,因此可以覆盖
            array[end + 1] = array[end];
            end--;
        }

        array[end + 1] = key;
    }

}

因为直接插入排序,前边的i-1个元素是已经排好的。在查找位置时,我们可以用二分查找对其继续进行优化。

优化后的代码如下


void InsertSort(int array[], int size)
{
    for (int i = 1; i < size; ++i)
    {

        int key = array[i];
        int end = i - 1;
        int left = 0;

        //二分查找先找到位置,

#if 0
        int right = i - 1;
        //这里是左闭右闭区间,因此是小于等于
        while (left <= right)
        {
            int mid = left + ((right - left) >> 1);

            if (array[mid] > key)
                right = mid - 1;
            else
                left = mid + 1;
        }
        //找到元素的位置后,将left及其后边的元素都往后搬一个位置
        while (end >= left)
        {
            array[end + 1] = array[end];
            end--;
        }
#endif
        int right = i;
        //左闭右开区间
        while (left < right)
        {
            int mid = left + ((right - left) >> 1);

            if (array[mid] >key)
            {
                right = mid;
            }
            else
                left = mid + 1;
        }
        //找到元素的位置后,将left及其后边的元素都往后搬一个位置
        while (end >= left)
        {
            array[end + 1] = array[end];
            --end;
        }

        array[end + 1] = key;
    }
}
总结
  • 元素集合越接近有序,直接插入排序算法的时间效率越高
  • 最差情况下:时间效率为O(n)
  • 最差情况下:时间复杂度为O(n^2)
  • 空间复杂度为:O(1)
  • 直接插入排序算法是一种稳定的排序算法
希尔排序

希尔排序又称缩小增量排序,是对直接插入排序的优化,算法先将要排序的一组数按某个增量gap分成若干组,每组中记录的下标相差gap.对每组中全部元素进行排序,然后再用一个较小的增量对它进行,在每组中再进行排序。当增量减到1时,整个要排序的数被分成一组,排序完成。
常见的排序算法——插入排序
代码如下:

void ShellSort(int array[], int size)
{
    int gap = size;

    while (gap > 1)
    {
        gap = gap / 3 + 1;
        for (int i = gap; i < size; i += gap)
        {
            int key = array[i];
            int end = i - gap;

            //这里的end必须大于等于0,否则数组会越界
            while (end >= 0&&array[end] > key)
            {
                array[end + gap] = array[end];
                end -= gap;
            }
            array[end + gap] = key;
        }

    }
}
总结
  • 时间复杂度为O(N^1.25)~O(1.6N^1.25)
  • 空间 复杂度为O(1)
  • 希尔排序时适合数据量大的数据集合排序
  • gap=gap/3+1为最优
相关标签: 插入排序