插入排序就是把當(dāng)前待排序的元素插入到一個已經(jīng)排好序的列表里面。 一個非常形象的例子就是右手抓取一張撲克牌，并把它插入左手拿著的排好序的撲克里面。
插入排序的最壞運(yùn)行時間是O(n2)， 所以并不是最優(yōu)的排序算法。
如果輸入數(shù)組已經(jīng)是排好序的話，插入排序出現(xiàn)最佳情況，其運(yùn)行時間是輸入規(guī)模的一個線性函數(shù)。
如果輸入數(shù)組是逆序排列的，將出現(xiàn)最壞情況。平均情況與最壞情況一樣，其時間代價是Θ(n2)。
簡單例子：
java" id="highlighter_107893">
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
public class Demo6 { public static void main(String[] args) { //定義一個整型數(shù)組 int[] nums = new int[]{4,3,-1,9,2,1,8,0,6}; //打印沒有進(jìn)行排序的數(shù)組 System.out.println("沒有排序之前的結(jié)果:" + Arrays.toString(nums)); for(int index=0; index<nums.length; index++) { //獲得需要插入的數(shù)值 int key = nums[index]; //取得下標(biāo)值 int position = index; /循環(huán)比較之前排序好的數(shù)據(jù)，找到合適的地方插入 while(position >0 && nums[position-1] > key) { nums[position] = nums[position-1]; position--; } nums[position] = key; } //打印排序后的結(jié)果 System.out.println("排序后的結(jié)果:" + Arrays.toString(nums)); } } |
以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持服務(wù)器之家。
