插入排序
一个有序的数组,往里面添加一个新的数据后,如何继续保持数据有序呢?很简单,只要遍历数组,找到数据应该插入的位置将其插入即可。
这是一个动态排序的过程,即动态地往有序集合中添加数据,可以通过这种方法保存集合中数据一直有序。而对于一组静态数据,也可以借鉴上面讲的插入方法,来进行排序,于是就有了插入排序算法。
那插入排序具体是如何借助上面的思想来实现排序的呢?
首先,将数组中的数据分为两个区间,已排序区间和未排序区间。初始已排序区间只有一个元素,就是数组的第一个元素。插入算法的核心思想是取未排序区间中的元素,在已排序区间中找到合适的插入位置将其插入,并保证已排序区间数据一直有序。重复这个过程,直到未排序区间中元素位空,算法结束。
如图所示,要排序的数据是4,5,6,1,3,2,其中左侧为已排序区间,右侧是未排序区间。
插入排序也包含两种操作,一种是元素的比较,一种是元素的移动。当需要将一个数据a插入到已排序区间时,需要拿a与已排序区间的元素依次比较大小,找到合适的插入位置。找到插入点之后,还需要将插入点之后的元素顺序往后移动一位,这样才能腾出位置给元素a插入。
对于不同的查找插入点算法(从头到尾、从尾到头),元素的比较次数是有区别的。但对于一个给定的初始序列,移动操作的次数总是固定的,就等于逆序度。
为什么说移动次数就等于逆序度呢?拿刚才的例子画个表,一看就明白了。满有序度是n * (n - 1) / 2 = 15,初始序列的有序度是5,所以逆序度是10.插入排序中,数据移动的个数总和也等于10 = 3 + 3 + 4。
代码实现如下
@interface DMInsertionSort : NSObject
// 插入排序
- (void)insertionPort:(NSMutableArray *)array;
@end
@implementation DMInsertionSort
- (void)insertionPort:(NSMutableArray *)array
{
NSInteger moveCount = 0;
NSLog(@"插入排序前数据:%@", array);
if ([array count] > 1) {
for (NSInteger i = 1; i < [array count]; i++) {
NSNumber *num = [array objectAtIndex:i];
NSInteger j = i - 1;
// 查找插入位置
for (; j >= 0; j--) {
NSNumber *preNum = [array objectAtIndex:j];
if ([preNum integerValue] > [num integerValue]) {
// 后移数据
[array replaceObjectAtIndex:j + 1 withObject:preNum];
moveCount += 1;
} else {
break;
}
}
// 插入数据
[array replaceObjectAtIndex:j + 1 withObject:num];
}
}
NSLog(@"插入排序后数据:%@", array);
NSLog(@"移动总次数:%ld",(long)moveCount);
}
@end
@interface DMSortDemo : NSObject
@end
@implementation DMSortDemo
- (void)demo
{
DMInsertionSort *insertionSort = [[DMInsertionSort alloc] init];
{
NSMutableArray *dataArray = [[NSMutableArray alloc] init];
[dataArray addObject:[NSNumber numberWithInteger:4]];
[dataArray addObject:[NSNumber numberWithInteger:5]];
[dataArray addObject:[NSNumber numberWithInteger:6]];
[dataArray addObject:[NSNumber numberWithInteger:1]];
[dataArray addObject:[NSNumber numberWithInteger:3]];
[dataArray addObject:[NSNumber numberWithInteger:2]];
[insertionSort insertionPort:dataArray];
}
{
NSMutableArray *dataArray = [[NSMutableArray alloc] init];
[dataArray addObject:[NSNumber numberWithInteger:3]];
[dataArray addObject:[NSNumber numberWithInteger:5]];
[dataArray addObject:[NSNumber numberWithInteger:4]];
[dataArray addObject:[NSNumber numberWithInteger:1]];
[dataArray addObject:[NSNumber numberWithInteger:2]];
[dataArray addObject:[NSNumber numberWithInteger:6]];
[insertionSort insertionPort:dataArray];
}
}
@end
第一,插入排序是原地排序算法吗?
从实现过程可以很明显地看出,插入排序算法的运行并不需要额外的存储空间,所以空间复杂度是O(1),也就是说,这是一个原地排序算法。
第二,插入排序是稳定的排序算法吗?
在插入排序中,对于值相同的元素,可以选择将后面出现的元素,插入到前面出现元素的后面,这样就可以保持原有的前后顺序不变,所以插入排序是稳定的排序算法。
第三,插入排序的时间复杂度是多少?
如果要排序的数据已经是有序的,并不需要搬移任何数据。如果从尾到头在有序数据组里面查找插入位置,每次只需要比较一个数据就能确定插入的位置。所以这种情况下,最好时间复杂度为O(n)。注意,这里是从尾到头遍历已经有序的数组。
如果数组是倒序的,每次插入都相当于在数组的第一个位置插入新的数据,所以需要移动大量的数据,所以最坏情况时间复杂度为O(n * n)。
在数组中插入一个数据的平均时间复杂度是O(n)。对于插入排序来说,每次插入操作都相当于在数组中插入一个数据,循环执行n次插入操作,所以平均时间复杂度为O(n * n)。
网友评论