插入排序简介

275次阅读

共计 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)
        }
    }
}

 阿里云 2 核 2G 服务器 3M 带宽 61 元 1 年，有高配 
 腾讯云新客低至 82 元 / 年，老客户 99 元 / 年 
 代金券：在阿里云专用满减优惠券