1.什么是插入排序（Insertion sort）
插入排序降瞳，一般也被稱為直接插入排序。對(duì)于少量元素的排序，它是一個(gè)有效的算法 挣饥。插入排序是一種最簡(jiǎn)單的排序方法除师，它的基本思想是將一個(gè)記錄插入到已經(jīng)排好序的有序表中，從而一個(gè)新的扔枫、記錄數(shù)增1的有序表汛聚。在其實(shí)現(xiàn)過(guò)程使用雙層循環(huán)，外層循環(huán)對(duì)除了第一個(gè)元素之外的所有元素短荐，內(nèi)層循環(huán)對(duì)當(dāng)前元素前面有序表進(jìn)行待插入位置查找倚舀，并進(jìn)行移動(dòng) 。
2.圖解插入排序
插入排序
3.代碼實(shí)現(xiàn)
package demo.sort;
import java.util.Arrays;
public class InsertSort {
//升序排列
public static void main(String[] args) {
int[] arr ={8,6,5,3,2,56,7,8,9,5,4,2,3,4,7};
sort(arr);
System.out.println(Arrays.toString(arr));
}
//插入排序
public static void sort(int[] arr){
//遍歷當(dāng)前位置忍宋，向前已經(jīng)排序好的序列插入
for (int i = 0; i < arr.length - 1; i++) {
//讓當(dāng)前位置和前面的數(shù)據(jù)對(duì)比
for (int j = i+1; j > 0 ; j--) {
if(arr[j] > arr[j-1]){
swap(arr,j,j-1);
}
}
}
}
//交換位置
public static void swap(int[] arr,int j,int i ){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
4.時(shí)間和空間復(fù)雜度
- 時(shí)間復(fù)雜度：在插入排序中痕貌，當(dāng)待排序數(shù)組是有序時(shí)，是最優(yōu)的情況糠排，只需當(dāng)前數(shù)跟前一個(gè)數(shù)比較一下就可以了舵稠，這時(shí)一共需要比較N- 1次，時(shí)間復(fù)雜度為O(N);最壞的情況是待排序數(shù)組是逆序的入宦，此時(shí)需要比較次數(shù)最多哺徊，總次數(shù)記為：1+2+3+…+N-1，所以乾闰，插入排序最壞情況下的時(shí)間復(fù)雜度為O(N2);
- 空間復(fù)雜度：插入排序的空間復(fù)雜度為常數(shù)階O(1);
5.適用場(chǎng)景
插入排序適用于已經(jīng)有部分?jǐn)?shù)據(jù)已經(jīng)排好落追，并且排好的部分越大越好。==一般在輸入規(guī)模大于1000的場(chǎng)合下不建議使用插入排序== 汹忠。
