共计 1871 个字符,预计需要花费 5 分钟才能阅读完成。
导读 | 插入排序是一种最简单直观的排序算法,它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。 |
插入排序和冒泡排序一样,也有一种优化算法,叫做拆半插入。
算法步骤
将第一待排序序列第一个元素看做一个有序序列,把第二个元素到最后一个元素当成是未排序序列。
从头到尾依次扫描未排序序列,将扫描到的每个元素插入有序序列的适当位置。(如果待插入的元素与有序序列中的某个元素相等,则将待插入元素插入到相等元素的后面。)
动图演示
代码实现
JavaScript
实例
function insertionSort(arr) {
var len = arr.length;
var preIndex, current;
for (var i = 1; i = 0 && arr[preIndex] > current) {arr[preIndex+1] = arr[preIndex];
preIndex--;
}
arr[preIndex+1] = current;
}
return arr;
}
Python
实例
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
Go
实例
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
}
Java
实例
public class InsertSort implements IArraySort {
@Override
public int[] sort(int[] sourceArray) throws Exception {
// 对 arr 进行拷贝,不改变参数内容
int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
// 从下标为 1 的元素开始选择合适的位置插入,因为下标为 0 的只有一个元素,默认是有序的
for (int i = 1; i 0 && tmp
PHP
实例
function insertionSort($arr)
{$len = count($arr);
for ($i = 1; $i = 0 && $arr[$preIndex] > $current) {$arr[$preIndex+1] = $arr[$preIndex];
$preIndex--;
}
$arr[$preIndex+1] = $current;
}
return $arr;
}
C
实例
void insertion_sort(int arr[], int len){
int i,j,key;
for (i=1;i=0) && (arr[j]>key)) {arr[j+1] = arr[j];
j--;
}
arr[j+1] = key;
}
}
C++
实例
void insertion_sort(int arr[],int len){
for(int i=1;i<len;i++){
int key=arr[i];
int j=i-1;
while((j>=0) && (key<arr[j])){
arr[j+1]=arr[j];
j--;
}
arr[j+1]=key;
}
}
C#
实例
public static void InsertSort(int[] array)
{for(int i = 1;i = 0;j--)
{if(array[j] > temp)
{array[j + 1] = array[j];
array[j] = temp;
}
else
break;
}
}
}
Swift
实例
for i in 1..<arr.endIndex {let temp = arr[i]
for j in (0..<i).reversed() {if arr[j] > temp {arr.swapAt(j, j+1)
}
}
}
正文完
星哥说事-微信公众号
![post-qrcode](https://www.xgss.net/wp-content/uploads/2023/07/二维码-微信公众号256x256.jpg)