插入排序

插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴，但它的原理应该是最容易理解的了，因为只要打过扑克牌的人都应该能够秒懂。插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序和冒泡排序一样，也有一种优化算法，叫做拆半插入。

1. 代码实现

C++代码实现

#include <iostream>
#include <vector> 

using namespace std;

void insertion_sort(vector<int> &nums, int n);

int main(){
    vector<int> nums = {1,3,5,2,6,4,8,9,2,7,6,0};
    for(int i = 0;i < nums.size();++i){
        cout << nums[i] << " ";
    }
    cout << endl;
    insertion_sort(nums, nums.size());
    for(int i = 0;i < nums.size();++i){
        cout << nums[i] << " ";
    }
}
void insertion_sort(vector<int> &nums, int n) {
    for (int i = 0; i < n; ++i) {
        for (int j = i; j > 0 && nums[j] < nums[j-1]; --j) {
            swap(nums[j], nums[j-1]);
        }
    }
}

PHP代码实现

<?php

function insertion_sort($params) {
    $len = count($params);
    for ($i = 0; $i < $len; $i++) {
        for ($j = $i; $j > 0 && $params[$j] < $params[$j -1]; --$j) {
            $tmp = $params[$j];
            $params[$j] = $params[$j-1];
            $params[$j -1] = $tmp;
        }     
    }
    return $params;
}

$data = [1,3,5,7,2,6,4,8,9,2,8,7,6,0,3,5,9,4,1];
var_dump(insertion_sort($data));

JavaScript 代码实现

function insertion_sort(params) {
    for (let i = 0; i < params.length; i++) {
        for (let j = i; j > 0 && params[j] < params[j -1]; --j) {
            let tmp = params[j];
            params[j] = params[j-1];
            params[j -1] = tmp;
        }     
    }
    return params;
}

var data = [1,3,5,7,2,6,4,8,9,2,8,7,6,0,3,5,9,4,1]
console.log(insertion_sort(data))

2. 小结

1. 时间复杂度：O(n²)，其中n为数组的长度。
2. 空间复杂度：O(1)