插入排序

基本思想

插入排序显然是稳定排序算法。
假设最终结果是递增有序。默认数组的首个元素是有序的，这部分看成部分有序的子数组，后面看成无序的子数组。从无序子数组后面开始的元素与有序子数组的倒数第一个比较，如果元素比有序子数组中的元素小，则有序子数组倒数第一个元素往后移一位。然后指针往前移动一位，再比较有序子数组的前两个元素，依次类推，直到该元素不比有序子数组某个位置的元素小为止，然后将该元素值放到该位置后一位的位置上。重复n-1次循环，则数组整体有序。

C/C++实现

# include <iostream>
# include <vector>

using namespace std;

class Solution {
public:
    void insert_sort(vector<int> &nums) {
        int n = nums.size();
        int temp;
        for (int i = 1; i < n; i++) {
            temp = nums[i];
            int j = i - 1;
            for (; j >= 0 && temp < nums[j]; j--) {
                nums[j + 1] = nums[j];
            }
            nums[j + 1] = temp;
        }
    }
};

int main() {
    vector<int> a = {2, 1, 3, 4, 7, 5, 4, 6};
    Solution s;
    s.insert_sort(a);
    for (int i : a)
        cout << i << " ";
    cout << endl;
    return 0;
}

Python3实现

class Solution(object):
    def insert_sort(self, nums):
        n = len(nums)
        for i in range(1, n):
            temp = nums[i]
            j = i - 1
            while j >= 0:
                if temp < nums[j]:
                    nums[j + 1] = nums[j]
                else:
                    break
                j -= 1
            nums[j + 1] = temp


a = [2, 1, 3, 4, 7, 5, 4, 6]
s = Solution()
s.insert_sort(a)
print(a)