插入排序

插入排序

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

算法描述

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]