插入排序
插入排序是一种简单直观的排序算法,它也是一种稳定排序算法。它的工作原理是通过构建有序序列,对于未排序的数据,在已排序序列中从后向前扫描,找到相应位置并插入,直到全部插入为止。
算法描述
1、将序列的第一个元素看成是有序的,把第二个元素到最后一个元素看成是无序的。
2、取出下一个元素(待插入元素),在已经排序的元素中从后向前扫描。
3、如果该元素(已排序)大于待插入元素,将该元素移动到下一位置。
4、重复步骤3,直到找到已排序的元素不大于待插入元素的位置。
5、将待插入元素插入到该位置。
6、重复步骤2~5。
动图演示
代码实现
Java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
| 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
1 2 3 4 5 6 7 8 9 10 11 12 13 14
| 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]