如何讓百度快速收錄網(wǎng)站惠州百度關(guān)鍵詞優(yōu)化
核心思想
插入排序是一種基于元素比較的原地排序算法，其核心思想是將數(shù)組分為“已排序”和“未排序”兩部分，逐個(gè)將未排序元素插入到已排序部分的正確位置。
例如撲克牌在理牌的時(shí)候，一般會(huì)將大小王、2、A、花牌等按大小順序插入到左邊，3、4等小牌會(huì)往右邊靠，這和插入排序是同一個(gè)原理
復(fù)雜度
時(shí)間復(fù)雜度
| 場(chǎng)景 | 時(shí)間復(fù)雜度 | 具體說明 |
|---|---|---|
| ?最佳情況? | O(n) | 數(shù)組已完全有序，每次只需比較一次（無需移動(dòng)元素） |
| ?最差情況? | O(n2) | 數(shù)組完全逆序，每個(gè)元素需比較并移動(dòng)所有已排序元素（如?[5,4,3,2,1]） |
| ?平均情況? | O(n2) | 部分有序數(shù)組的插入操作需要約 n2/4 次比較和移動(dòng) |
空間復(fù)雜度
O(1)：原地排序算法，僅需固定數(shù)量的額外空間（如?key?和索引變量?j）
代碼實(shí)現(xiàn)（Java）
//插入排序，升序排序舉例
void insertionSort(int[] arr) {int n = arr.length;for (int i = 1; i < n; ++i) {int key = arr[i];int j = i - 1;//不斷向左移動(dòng)，直到找到自己的位置while (j >= 0 && arr[j] > key) {arr[j + 1] = arr[j];j = j - 1;}arr[j + 1] = key;}
}