插入排序(三)

插入排序

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

插入排序和冒泡排序一样,也有一种优化算法,叫做拆半插入。

1. 算法步骤

  1. 将第一待排序序列第一个元素看做一个有序序列,把第二个元素到最后一个元素当成是未排序序列。

  2. 从头到尾依次扫描未排序序列,将扫描到的每个元素插入有序序列的适当位置。(如果待插入的元素与有序序列中的某个元素相等,则将待插入元素插入到相等元素的后面。)

2. 动图演示

动图演示

3. JavaScript 代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function insertionSort(arr) {
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;
}

4. Python 代码实现

1
2
3
4
5
6
7
8
9
def insertionSort(arr):
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

5. Go 代码实现

1
2
3
4
5
6
7
8
9
10
11
12
func insertionSort(arr []int) []int {
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
}

6. java代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static void  insert_sort(int array[],int lenth){

int temp;

for(int i=0;i<lenth-1;i++){
for(int j=i+1;j>0;j--){
if(array[j] < array[j-1]){
temp = array[j-1];
array[j-1] = array[j];
array[j] = temp;
}else{ //不需要交换
break;
}
}
}
}

作者:搜云库技术团队
出处:https://www.souyunku.com
首发微信公众号:搜云库技术团队,微信号ID:souyunku
版权归原创作者所有,任何形式转载请联系作者

# sort

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×