“算法基础知识”
前言
排序算法
插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据序列。
基本思想是每步将一个待排序的纪录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。
插入排序算法对于少量元素的排序是一个有效的算法。
可以将其看作是大家排序一手扑克牌，开始时我们的左手为空，然后每次从牌堆里拿出一张牌并且按照一定顺序插入左手中正确位置，为了得到这个正确位置，我们需要从右到左将其与已在手中的每张牌进行对比。
正文
伪代码表示
INSERTION-SORT(A)
for i = 1 to A.length
temp = A[i]
j = i - 1;
while j > 0 and A[j] > temp
A[j + 1] = A[j]
j = j - 1
A[j + 1] = temp
Java代码
public static int[] sort(int[] queue) {
if (queue == null || queue.length < 2) {
return queue;
}
int temp;
for (int i = 1; i < queue.length; i++) {
for (int j = i; j > 0; j--) {
if (queue[j] < queue[j - 1]) {
temp= queue[j];
queue[j] = queue[j - 1];
queue[j - 1] = temp;
}
}
}
return queue;
排序过程大致为
| 数组编号 | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| 初始状态 | 5 | 2 | 4 | 6 | 1 | 3 |
| 第一次排序 | 2 | 5 | 4 | 6 | 1 | 3 |
| 第二次排序 | 2 | 4 | 5 | 6 | 1 | 3 |
| 第三次排序 | 2 | 4 | 5 | 6 | 1 | 3 |
| 第四次排序 | 1 | 2 | 4 | 5 | 6 | 3 |
| 第五次排序 | 1 | 2 | 3 | 4 | 5 | 6 |
插入排序的时空复杂度
时间复杂度
- 在最坏情况下，数组完全逆序，插入第2个元素时要考察前1个元素，插入第3个元素时，要考虑前2个元素，……，插入第N个元素，要考虑前N-1个元素。因此，最坏情况下的比较次数是 1 + 2 + 3 + … + (N - 1)，等差数列求和，结果为 N^2 / 2，所以最坏情况下的复杂度为 O(N^2)。
- 时间复杂度，在最好情况下，数组已经是有序的，每插入一个元素，只需要考查前一个元素，因此最好情况下，插入排序的时间复杂度为O(N)。
空间复杂度
- 插入排序算法的空间复杂度为一个常量，即不随被处理数据量n的大小而改变时，可表示为O(1)。
后记
插入排序算法实现简单，效率相对较高，并且是一种稳定排序。
