- 算法简介
直接插入排序（Straight Insertion Sort）是一种最简单的排序方法，其基本操作是将一条记录插入到已排好的有序表中，从而得到一个新的、记录数量增1的有序表。
直接插入排序是由两层嵌套循环组成的。外层循环标识并决定待比较的数值。内层循环为待比较数值确定其最终位置。直接插入排序是将待比较的数值与它的前一个数值进行比较，所以外层循环是从第二个数值开始的。当前一数值比待比较数值大的情况下继续循环比较，直到找到比待比较数值小的并将待比较数值置入其后一位置，结束该次循环。
将待插入记录R[i]的关键字从右向左依次与有序区中记录R[j] (j=i-1，i-2，…，1)的关键字进行比较：
① 若R[j]的关键字大于R[i]的关键字，则将R[j]后移一个位置；
②若R[j]的关键字小于或等于R[i]的关键字，则查找过程结束，j+1即为R[i]的插入位置。
关键字比R[i]的关键字大的记录均已后移，所以j+1的位置已经腾空，只要将R[i]直接插入此位置即可完成一趟直接插入排序。
- C语言实现
void straightInsertionSort(int numbers[],int count) {
int i,j;
for (i = 1; i < count; i++) {//7 8 9 3 5 6
if (numbers[i - 1] > numbers[i]) {//前面一位大于后面一位
int temp = numbers[i];
for (j = i - 1; j >= 0 && numbers[j] > temp; j--) {//循环将temp的值和它之前的值比较
numbers[j + 1] = numbers[j];
}
numbers[j + 1] = temp;//将待插入的值插入到j位置，（j+1：因为j在上面for中最后做了减操作，所以加1）
}
}
}
//调用
int number1[7] = {2, 2, 23, 11, 9, 43, 18};
straightInsertionSort(number1, 7);
for (i = 0; i < 7; i++) {
printf("%d\n", number1[i]);
}
- OC实现
- (void)straightInsertionSortWithNumbers:(NSMutableArray *)numbers {
for (int i = 1; i < numbers.count; i++) {
if ([numbers[i - 1] intValue] > [numbers[i] intValue]) {//前面一位大于后面一位
int temp = [numbers[i] intValue];
for (int j = i - 1; j >= 0 && [numbers[j] intValue] > temp; j--) {
[numbers exchangeObjectAtIndex:j + 1 withObjectAtIndex:j];
}
}
}
NSLog(@"%@",numbers);
}
//调用
NSMutableArray *array = [NSMutableArray arrayWithObjects:@(10),@(4),@(8),@(6),@(16),@(19),@(3), nil];
[self straightInsertionSortWithNumbers:array];
- 时间复杂度
最好情况(初始情况就是正序)下时间复杂度是O(n)
平均情况和最坏情况时间复杂度是O(n²)
