插入排序實作--圖解/執行個體/java/php

插入排序

在一個有序的數組中，插入新的資料，實作這種的操作就是插入排序

概念

• 原理：從第一個元素開始，左邊視為已排序數組，右邊視為待排序數組，從左往右依次取元素，插入左側已排序數組，對插入新元素的左側數組重新生成有序數組
• 需要注意的是，在往有序數組插入一個新元素的過程中，我們可以采用按順序循環比較，也可以通過折半查找法來找到新元素的位置，兩種方式的效率取決于數組的資料量

最壞時間複雜度O(n^2)

最好時間複雜度O(n)

平均時間複雜度O(n^2)

• 插入排序是一種穩定排序算法

圖解

以初始數組 = {2,5,1,3,6}為例，對其排序得到一個升序數組

1. 左側數組為{2}，插入新元素5，5與2比較，不交換位置

   

2. 繼續插入1，先和5比較，小于5交換位置，再與2比較，交換位置

   

3. 插入3，3小于5但大于2，是以與5交換位置

   

4. 最終插入6，6大于5，至此，得到了最終的排序數組

執行個體

采用簡單的順序比較

Java實作

/**
* java 插入排序升序
*/
public static int[] insertSort(int[] arr)
{
	if (arr.length < 2)
		return arr;
		
	for (int i = 1;i < arr.length;i++) {
		for (int j = i;j > 0;j--) {
			if (arr[j-1] > arr[j]) {
				int temp = arr[j];
				arr[j] = arr[j-1];
				arr[j-1] = temp;
			} else {
				break;//插入新的元素
			}
		}
	}

	return arr;
}
           

PHP實作

/*
* php 插入排序升序
*/
public function insertSort(array $arr)
{
	if (count($arr) < 2)
		return $arr;
		
	for ($i = 1;$i < count($arr);$i++) {
		for ($j = $i;$j > 0;$j--) {
			if ($arr[$j-1] > $arr[$j]) {
				list($arr[$j], $arr[$j-1]) = [$arr[$j-1], $arr[$j]];
			} else {
				break;
			}
		}
	}

	return $arr;
}
           

采用折半查找法，較為複雜，感興趣的同學可以百度