每日一题之插入排序

插入排序

1、插入排序原理

下面是百度百科的一段解释，我认为很容易被接收这种思想，便直接复制过来

插入排序的工作方式像许多人排序一手扑克牌。开始时，我们的左手为空并且桌子上的牌面向下。然后，我们每次从桌子上拿走一张牌并将它插入左手中正确的位置。为了找到一张牌的正确位置，我们从右到左将它与已在手中的每张牌进行比较。拿在左手上的牌总是排序好的，原来这些牌是桌子上牌堆中顶部的牌。

插入排序是指在待排序的元素中，假设前面n-1(其中n>=2)个数已经是排好顺序的，现将第n个数插到前面已经排好的序列中，然后找到合适自己的位置，使得插入第n个数的这个序列也是排好顺序的。按照此法对所有元素进行插入，直到整个序列排为有序的过程，称为插入排序。

大概意思就是说，将数组分为已排序区间和待排序区间，其中排序是从左边开始进行的，所以左边为已排序区间，右边为待排序区间，最开始的时候，数组中的第一个元素不参与排序，它便是已排序区间的唯一一个元素，插入的思想便是从待排序区间中取出元素进行在左边已排序区间中找到合适的位置进行插入，并且每次从待排序区间取元素，来重复这个过程。

2、插入排序的步骤

作者比较懒，所以就直接在网上巴拉了一张步骤图，以供参考

3、插入排序的代码实现

• Java

import java.util.Arrays;

public class InsertionSort {

    private static void insertionSort(int[] nums) {
        for (int i = 1, j, n = nums.length; i < n; ++i) {
            int num = nums[i];
            for (j = i - 1; j >=0 && nums[j] > num; --j) {
                nums[j + 1] = nums[j];
            }
            nums[j + 1] = num;
        }
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 7, 9, 5, 8};
        insertionSort(nums);
        System.out.println(Arrays.toString(nums));
    }
}

• C++

#include <iostream>
#include <vector>

using namespace std;


void insertsort(vector<int> &vec)
{
    for (int i = 1; i < vec.size(); i++)
    {
        int j = i - 1;
        int num = vec[i];
        for (; j >= 0 && vec[j] > num; j--)
        {
            vec[j + 1] = vec[j];
        }

        vec[j + 1] = num;
    }

    return;
}

int main()
{
    vector<int> vec = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
    insertsort(vec);
    printvec(vec, "after insert sort");
    return (0);
}

4、插入排序的算法分析

时间复杂度

在插入排序中，当待排序数组是有序时，是最优的情况，只需当前数跟前一个数比较一下就可以了，这时一共需要比较N- 1次，时间复杂度为O(N)

最坏的情况是待排序数组是逆序的，此时需要比较次数最多，总次数记为：1+2+3+…+N-1，所以，插入排序最坏情况下的时间复杂度为O(N的平方)

平均来说，A[1..j-1]中的一半元素小于A[j]，一半元素大于A[j]。插入排序在平均情况运行时间与最坏情况运行时间一样，是输入规模的二次函数

空间复杂度

插入排序的空间复杂度为常数阶O(1)

稳定性分析

如果待排序的序列中存在两个或两个以上具有相同关键词的数据，排序后这些数据的相对次序保持不变，即它们的位置保持不变，通俗地讲，就是两个相同的数的相对顺序不会发生改变，则该算法是稳定的；如果排序后，数据的相对次序发生了变化，则该算法是不稳定的。关键词相同的数据元素将保持原有位置不变，所以该算法是稳定的。