插入排序.md

插入排序

简介

构建有序序列, 对于未排序数据, 在已排序序列中从后向前扫描, 找到相应位置并插入.

代码

PHP

<?php

class InsertSort
{
    /**
     * 排序
     *
     * @param $arr
     * @return bool
     */
    public static function sort(&$arr)
    {
        if ($arr == null || count($arr) < 2) {
            return false;
        }

        for ($i = 1; $i < count($arr); $i++) {
            for ($j = $i - 1; $j >= 0 && $arr[$j] > $arr[$j + 1]; $j--) {
                list($arr[$j], $arr[$j + 1]) = [$arr[$j + 1], $arr[$j]];
            }
        }
    }
}

// Test
$arr = [3, 6, 4, 2, 7];
InsertSort::sort($arr);
// [2, 3, 4, 6, 7]
print_r($arr);

java

import java.util.Arrays;

public class InsertSort {
	public static void insertSort(int[] arr) {
		if (arr == null || arr.length < 2) {
			return;
		}
		for (int i = 1; i < arr.length; i++) {
			for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {
				swap(arr, j, j + 1);
			}
		}
	}
	
	public static void swap(int[] arr, int i, int j) {
		int tmp = arr[i];
		arr[i] = arr[j];
		arr[j] = tmp;
	}
	
	public static void main(String[] args) {
		int[] arr = {3, 6, 4, 2, 7};
		insertSort(arr);
		// [2, 3, 4, 6, 7]
		System.out.println(Arrays.toString(arr));
	}
}

时间复杂度

最好情况(已经排好序, 比如[1, 2, 3, 4, 5]): O(N)
最坏情况(倒序, 比如[5, 4, 3, 2, 1]): O(N^2)
因为排序需要按照最坏情况来计算时间复杂度, 所以插入排序的时间复杂度为O(N^2)