程序猿小白进阶之路，一天学习一个算法:插入排序

插入排序（Insertion Sort）是一种简单直观的排序算法。它的基本思想是将待排序的元素逐个插入到已排序的序列中的合适位置，直到所有元素都排好序为止。下面是插入排序的步骤：

1. 将待排序序列的第一个元素视为已排序序列。
2. 取出下一个元素，在已排序序列中从后往前进行比较。
3. 如果已排序序列中的元素大于取出的元素，则将该元素后移一位。
4. 重复步骤3，直到找到已排序序列中的元素小于或等于取出的元素的位置。
5. 将取出的元素插入到该位置。
6. 重复步骤2到步骤5，直到所有元素都排好序。

插入排序的时间复杂度为O(n^2)，其中n是待排序序列的长度。它是一种稳定的排序算法，因为相同元素的相对顺序不会改变

PHP

function insertionSort($arr) {
    $n = count($arr);
    
    for ($i = 1; $i < $n; $i++) {
        $key = $arr[$i];
        $j = $i - 1;
        
        while ($j >= 0 && $arr[$j] > $key) {
            $arr[$j + 1] = $arr[$j];
            $j = $j - 1;
        }
        
        $arr[$j + 1] = $key;
    }
    
    return $arr;
}

// 示例用法
$array = [64, 34, 25, 12, 22, 11, 90];
$sortedArray = insertionSort($array);
print_r($sortedArray);

Java

public class InsertionSort {
    public static void insertionSort(int[] arr) {
        int n = arr.length;

        for (int i = 1; i < n; i++) {
            int key = arr[i];
            int j = i - 1;

            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j = j - 1;
            }

            arr[j + 1] = key;
        }
    }

    // 示例用法
    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90};
        insertionSort(arr);
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }
}

Python

def insertion_sort(arr):
    n = len(arr)

    for i in range(1, n):
        key = arr[i]
        j = i - 1

        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j = j - 1

        arr[j + 1] = key

    return arr

# 示例用法
arr = [64, 34, 25, 12, 22, 11, 90]
sorted_arr = insertion_sort(arr)
print(sorted_arr)

Go

package main

import "fmt"

func insertionSort(arr []int) {
    n := len(arr)

    for i := 1; i < n; i++ {
        key := arr[i]
        j := i - 1

        for j >= 0 && arr[j] > key {
            arr[j+1] = arr[j]
            j = j - 1
        }

        arr[j+1] = key
    }
}

// 示例用法
func main() {
    arr := []int{64, 34, 25, 12, 22, 11, 90}
    insertionSort(arr)
    fmt.Println(arr)
}

#头条文章养成计划#