插入排序

插入排序

插入排序是一种简单直观的排序算法，它也是一种稳定排序算法。它的工作原理是通过构建有序序列，对于未排序的数据，在已排序序列中从后向前扫描，找到相应位置并插入，直到全部插入为止。

算法描述

1、将序列的第一个元素看成是有序的，把第二个元素到最后一个元素看成是无序的。
2、取出下一个元素(待插入元素)，在已经排序的元素中从后向前扫描。
3、如果该元素(已排序)大于待插入元素，将该元素移动到下一位置。
4、重复步骤3，直到找到已排序的元素不大于待插入元素的位置。
5、将待插入元素插入到该位置。
6、重复步骤2~5。

动图演示

代码实现

Java

package com.test;

import java.util.Arrays;

public class MySorts {

    public static void insertionSort(int[] arr){
        for(int i=1;i<arr.length;i++){//从第二个元素开始
            int tmp = arr[i];//待插入元素
            int j;//待插入位置
            for(j=i;j>0&&tmp<arr[j-1];j--){
                arr[j] = arr[j-1];//后移
            }
            //内循环结束说明找到了插入位置
            arr[j] = tmp;
        }
    }
    public static void main(String[] args) {
        int[] arr = new int[]{23,20,32,45,6,8,9,15,13,14};
        insertionSort(arr);
        System.out.println("排序結果："+ Arrays.toString(arr));
    }
}

排序結果：[6, 8, 9, 13, 14, 15, 20, 23, 32, 45]

JavaScript

function insertionSort(arr) {
	for(var i=1;i<arr.length;i++){
		var tmp = arr[i];
		var j;
		for(j=i;j>0&&tmp<arr[j-1];j--){
			arr[j] = arr[j-1];
		}
		arr[j] = tmp;
	}
	return arr;
}
var arr = [23,20,32,45,6,8,9,15,13,14];
var arrSorted = insertionSort(arr);
console.log(arrSorted);

(10) [6, 8, 9, 13, 14, 15, 20, 23, 32, 45]