前言
插入排序算法任然需要O(N^2)的時(shí)間总处，但是一般情況下细燎，他要比冒泡排序快一倍腾供，比選擇排序要快一點(diǎn)罢坝。
[圖片上傳失敗...(image-39380d-1628999776603)]
一、插入排序
假定排序從中間開始搭独，可以更好的理解插入排序婴削。此時(shí)，隊(duì)列左邊已經(jīng)排好序牙肝，在隊(duì)列中間標(biāo)記一個(gè)元素唉俗，在這個(gè)作為標(biāo)記的元素左邊已經(jīng)是局部有序，（注意配椭，局部有序在冒泡排序和選擇排序中不會(huì)出現(xiàn)）這個(gè)被標(biāo)記的元素右邊是未排序的虫溜。我們需要做的是在左邊有序的隊(duì)列中的適當(dāng)位置插入被標(biāo)記的元素。這意味著左邊有序的隊(duì)列需要先向右移騰出空間股缸。而被標(biāo)記的元素需要出列衡楞，以提供位移空間。
插入排序的代碼如下：
public void insertionSort(){
int left , right;
for (right = 1;right<arr.length;right++){
int temp = arr[right];
left = right;
while (left>0&&arr[left-1] >=temp){
arr[left] = arr[left-1];
left--;
}
arr[left] = temp;
System.out.println("排序前："+ Arrays.toString(arr));
}
}
測試
public class Main {
public static void main(String[] args) {
Random random = new Random();
int[] arr = new int[10];
for (int i = 0; i < arr.length; i++) {
arr[i] = random.nextInt(100);
}
System.out.println("排序前："+Arrays.toString(arr));
InsertSort insertSort = new InsertSort(arr);
insertSort.insertionSort();
System.out.println("排序后："+Arrays.toString(arr));
}
}
結(jié)果:
排序前：[45, 92, 15, 27, 45, 18, 8, 24, 43, 56]
排序前：[45, 92, 15, 27, 45, 18, 8, 24, 43, 56]
排序前：[15, 45, 92, 27, 45, 18, 8, 24, 43, 56]
排序前：[15, 27, 45, 92, 45, 18, 8, 24, 43, 56]
排序前：[15, 27, 45, 45, 92, 18, 8, 24, 43, 56]
排序前：[15, 18, 27, 45, 45, 92, 8, 24, 43, 56]
排序前：[8, 15, 18, 27, 45, 45, 92, 24, 43, 56]
排序前：[8, 15, 18, 24, 27, 45, 45, 92, 43, 56]
排序前：[8, 15, 18, 24, 27, 43, 45, 45, 92, 56]
排序前：[8, 15, 18, 24, 27, 43, 45, 45, 56, 92]
排序后：[8, 15, 18, 24, 27, 43, 45, 45, 56, 92]
總結(jié)
在每趟結(jié)束時(shí)龄捡，在將temp位置項(xiàng)插入后卓嫂，比right變量下標(biāo)小的數(shù)據(jù)項(xiàng)都是局部有序的。
在第一趟中聘殖，它對(duì)多比較一次晨雳，第二趟最多比較兩次行瑞，一次類推。最后一趟最多餐禁，比較N-1次血久。因此有
然而，因?yàn)槊刻伺判虬l(fā)現(xiàn)插入插入點(diǎn)之前帮非，平均只有全體數(shù)據(jù)項(xiàng)的一半真的進(jìn)行了比較氧吐，我們chuyi2得到
復(fù)制的次數(shù)大致等于比較次數(shù)，然而末盔，一次復(fù)制與一次交換的事件耗費(fèi)不同筑舅，所以相對(duì)于隨機(jī)數(shù)據(jù)，這個(gè)算法比冒泡排序快一倍陨舱，比選擇排序略快翠拣。
