插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴，但它的原理应该是最容易理解的了，因为只要打过扑克牌的人都应该能够秒懂。插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
插入排序和冒泡排序一样，也有一种优化算法，叫做拆半插入。
1. 算法步骤
将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）
2. 动图演示
代码实现
JavaScript
实例
var len = arr.length;
var preIndex, current;
for (var i = 1; i len; i++) {
preIndex = i – 1;
current = arr[i];
while(preIndex >= 0 && arr[preIndex] > current) {
arr[preIndex+1] = arr[preIndex];
preIndex–;
}
arr[preIndex+1] = current;
}
return arr;
}
Python
实例
for i in range(len(arr)):
preIndex = i-1
current = arr[i]
while preIndex >= 0 and arr[preIndex] > current:
arr[preIndex+1] = arr[preIndex]
preIndex-=1
arr[preIndex+1] = current
return arr
Go
实例
for i := range arr {
preIndex := i – 1
current := arr[i]
for preIndex >= 0 && arr[preIndex] > current {
arr[preIndex+1] = arr[preIndex]
preIndex -= 1
}
arr[preIndex+1] = current
}
return arr
}
Java
实例
@Override
public int[] sort(int[] sourceArray) throws Exception {
// 对 arr 进行拷贝，不改变参数内容
int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
// 从下标为1的元素开始选择合适的位置插入，因为下标为0的只有一个元素，默认是有序的
for (int i = 1; i arr.length; i++) {
// 记录要插入的数据
int tmp = arr[i];
// 从已经排序的序列最右边的开始比较，找到比其小的数
int j = i;
while (j > 0 && tmp arr[j – 1]) {
arr[j] = arr[j – 1];
j–;
}
// 存在比其小的数，插入
if (j != i) {
arr[j] = tmp;
}
}
return arr;
}
}
PHP
实例
{
$len = count($arr);
for ($i = 1; $i $len; $i++) {
$preIndex = $i – 1;
$current = $arr[$i];
while($preIndex >= 0 && $arr[$preIndex] > $current) {
$arr[$preIndex+1] = $arr[$preIndex];
$preIndex–;
}
$arr[$preIndex+1] = $current;
}
return $arr;
}
C
实例
int i,j,key;
for (i=1;ilen;i++){
key = arr[i];
j=i–1;
while((j>=0) && (arr[j]>key)) {
arr[j+1] = arr[j];
j–;
}
arr[j+1] = key;
}
}
C++
实例
for(int i=1;ilen;i++){
int key=arr[i];
int j=i–1;
while((j>=0) && (keyarr[j])){
arr[j+1]=arr[j];
j—;
}
arr[j+1]=key;
}
}
C#
实例
{
for(int i = 1;i array.length;i++)
{
int temp = array[i];
for(int j = i – 1;j >= 0;j—)
{
if(array[j] > temp)
{
array[j + 1] = array[j];
array[j] = temp;
}
else
break;
}
}
}
Swift
实例
let temp = arr[i]
for j in (0..).reversed() {
if arr[j] > temp {
arr.swapAt(j, j+1)
}
}
}
原文地址：https://github.com/hustcc/JS-Sorting-Algorithm/blob/master/3.insertionSort.md
参考地址：https://zh.wikipedia.org/wiki/%E6%8F%92%E5%85%A5%E6%8E%92%E5%BA%8F
评论(0)