排序之插入排序
2018-08-25 本文已影响0人
Crazy_Snail
算法
最简单的排序算法之一是插入排序。插入排序由N-1趟排序组成。对于p=1到N-1趟，插入排序保证从位置0到位置p上的元素为排序状态。插入排序利用了这样的事实：已知位置0到位置p-1上的元素已经处于排过序的状态。
| 原始数组 | 56 | 23 | 5 | 21 | 65 | 移动的位置 |
|---|---|---|---|---|---|---|
| p=1趟后 | 23 | 56 | 5 | 21 | 65 | 1 |
| p=2趟后 | 5 | 23 | 56 | 21 | 65 | 2 |
| p=3趟后 | 5 | 21 | 23 | 56 | 65 | 2 |
| p=4趟后 | 5 | 21 | 23 | 56 | 65 | 0 |
Java代码实现
int[] insertionSort(int[] nums) {
int i;
for (int p = 1; p < nums.length; p++) {
int temp = nums[p];
for (i = p; i > 0 && temp < nums[i - 1]; i--) {
nums[i] = nums[i - 1];
}
nums[i] = temp;
}
return nums;
}
分析
由于嵌套循环的每一个花费N次迭代，因此插入排序为O(N2)，而且这个界是精确的，因为以反序的输入可以达到该界限。
Σi = 2 + 3 + 4 +…+ N=O(N2)
