插入排序

作者:原创时间:2022-05-25
文档

排序算法是《数据结构与算法》中最基本的算法之一。排序算法可以分为内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。常见的内部排序算法有:插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。以下是插入排序算法:

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

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

1. 算法步骤

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

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

2. 动图演示


代码实现

JavaScript

实例

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;
}

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 < 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

实例

function insertionSort($arr)
{
    $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

实例

void insertion_sort(int arr[], int len){
        int i,j,key;
        for (i=1;i<len;i++){
                key = arr[i];
                j=i-1;
                while((j>=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 < 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

实例

for i in 1..{
    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

以下是热心网友对插入排序算法的补充,仅供参考:

热心网友提供的补充1:

我编写了Lua的版本:

-- 插入排序
function insert_sort(tab)
    len = maxn_ex(tab)
    for i=1,len-1 do
      local j = i+1
      while( j > 1 )  do
        if(tab[j] < tab[j-1]) then
          tab[j],tab[j-1] = tab[j-1],tab[j]
        end
        j = j -1
      end 
    end
    return tab
end
以上为插入排序算法详细介绍,插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等排序算法各有优缺点,用一张图概括:

关于时间复杂度

平方阶 (O(n2)) 排序 各类简单排序:直接插入、直接选择和冒泡排序。

线性对数阶 (O(nlog2n)) 排序 快速排序、堆排序和归并排序;

O(n1+§)) 排序,§ 是介于 0 和 1 之间的常数。 希尔排序

线性阶 (O(n)) 排序 基数排序,此外还有桶、箱排序。

关于稳定性

稳定的排序算法:冒泡排序、插入排序、归并排序和基数排序。

不是稳定的排序算法:选择排序、快速排序、希尔排序、堆排序。

名词解释:

n:数据规模

k:"桶"的个数

In-place:占用常数内存,不占用额外内存

Out-place:占用额外内存

稳定性:排序后 2 个相等键值的顺序和排序之前它们的顺序相同

显示全文
选择排序 基数排序 冒泡排序python代码 写与风筝有关的诗 桶排序 如何按照计数进行排序 描写元宵节的唯美诗词 堆排序怎么排 关于兰花的诗句两句 java快速排序 关于写小动物的诗 描写夏天的诗句简单 踏青诗句最出名诗句 描写燕子的古诗绝句 归并排序python 希尔排序 选择排序法 基数排序怎么排 冒泡排序python 关于放风筝的古诗 java希尔排序算法 归并排序c语言 积累描写燕子的诗句 出门踏青的诗句 5首夏天的古诗简单 描写小动物的古诗 快速排序java 兰花的诗词佳句 元宵节代表诗词 托尔斯泰的名言 列宁的名言 关于乐观的名言 有关友谊的名言 关于交友的名言警句 关于家的名言 叶圣陶的名言 关于保护环境的名言 激励自己的名言 陶渊明的名句 关于爱国的名言