插入排序(Insertion Sort)的核心思想是:从数组中第二个元素开始,查找其适合放到该元素之前的数组中哪个位置最合适。
方式一:
最简单粗暴的方式就是直接倒叙遍历当前待插入元素前边的数组,如果比当前数据大就进行交换。
- (void)sort
{
NSInteger arrayCount = self.sortArray.count;
for (NSInteger begain = 1; begain < arrayCount; begain++) {
for (NSInteger end = begain; end >= 1 && [self compareObjcet:self.sortArray[end] anotherObject:self.sortArray[end - 1]]; end--) {
[self swapObjectWithIndex:end anotherIndex:end - 1];
}
}
}
方式二:
此种方式类似方式一,只是减少交换次数,首先需要备份待插入元素,倒序依次比较其与前边元素的值大小,如果当前元素小,就让其前边元素后移,直到找到比当前元素小或者相等的元素,记录此处位置,即为待插入元素,然后插入即可。
- (void)sort
{
NSInteger arrayCount = self.sortArray.count;
for (NSInteger begain = 1; begain < arrayCount; begain++) {
NSInteger insertIndex = begain;
id currentObject = self.sortArray[begain];
for (NSInteger current = begain; current >= 1 && [self compareObjcet:currentObject anotherObject:self.sortArray[current - 1]]; current--) {
self.sortArray[current] = self.sortArray[current - 1];
insertIndex = current - 1;
}
self.sortArray[insertIndex] = currentObject;
}
}
方式三:
这种方式跟玩扑克牌抓牌及其相似。
第一步:查找到待插入元素适合插入的位置(快速查找插入位置中又利用了二分查找算法)
// [0, index) 范围内找到 index的插入位置
- (NSInteger)searchIndexInArrayWithWaitIndex:(NSInteger)index
{
if (self.sortArray.count < 1 || index >= self.sortArray.count) {
return -1;
}
NSInteger begain = 0;
NSInteger end = index;
// 二分查找
while (begain < end) {
NSInteger mid = (begain + end) >> 1;
if ([self compareObjcet:self.sortArray[index] anotherObject:self.sortArray[mid]]) {
end = mid;
} else {
begain = mid + 1;
}
}
return begain;
}
第二步:将待插入元素放入该位置,同时数组中剩余元素依次后移(此处应先移动最后一个数组元素)
- (void)insertObjectIndex:(NSInteger)currentIndx intoIndex:(NSInteger)index
{
if (currentIndx <= index) {
return;
}
id currentObjcet = self.sortArray[currentIndx];
for (NSInteger begain = currentIndx; begain > index; begain--) {
self.sortArray[begain] = self.sortArray[begain - 1];
}
self.sortArray[index] = currentObjcet;
}
第三步:整体的排序过程就是个遍历调用上述两步的过程
- (void)sort
{
NSInteger arrayCount = self.sortArray.count;
for (NSInteger begain = 1; begain < arrayCount; begain++) {
NSInteger insertIndex = [self searchIndexInArrayWithWaitIndex:begain];
[self insertObjectIndex:begain intoIndex:insertIndex];
}
}
网友评论