【进阶】2、排序（二）

2014-03-02 | 阅读：

插入排序（Insertion Sort）

一、插入排序原理

插入排序非常类似于扑克牌的排序

执行流程
① 在执行过程中，插入排序会将序列分为2部分
✓ 头部是已经排好序的，尾部是待排序的
② 从头开始扫描每一个元素
✓ 每当扫描到一个元素，就将它插入到头部合适的位置，使得头部数据依然保持有序

二、代码实现

//时间复杂度:最好O(n)、最坏O(n^2)、平均O(n^2)
//空间复杂度O(1)
-(void)sort{
    for (int begin = 1; begin<self.array.count; begin++) {
        int current = begin;
        while(current>0 &&[self compareWitnIndex1:current index2:current-1]<0){
            [self swapWitnIndex1:current index2:current-1];
            current--;
        }
    }
}

三、插入排序-逆序对

什么是逆序对？
数组 <2,3,8,6,1> 的逆序对为：<2,1> <3,1> <8,1> <8,6> <6,1>，共5个逆序对

插入排序的时间复杂度与逆序对的数量成正比关系
逆序对的数量越多，插入排序的时间复杂度越高

最坏、平均时间复杂度：O(n^2) 最好时间复杂度：O(n)
空间复杂度：O(1)
属于稳定排序

当逆序对的数量极少时，插入排序的效率特别高甚至速度比 O(nlogn) 级别的快速排序还要快,数据量不是特别大的时候，插入排序的效率也是非常好的

四、插入排序-优化

思路是将【交换】转为【挪动】
① 先将待插入的元素备份
② 头部有序数据中比待插入元素大的，都朝尾部方向挪动1个位置
③ 将待插入元素放到最终的合适位置

//时间复杂度:最好O(n)、最坏O(n^2)、平均O(n^2)
//空间复杂度O(1)
-(void)sort{
    for (int begin = 1; begin<self.array.count; begin++) {
        
        int current = begin;
        id curValue = self.array[current];
        while(current>0 &&[self compareWithValue1:curValue value2:self.array[current-1]]<0){
            
            //将交换替换为挪动
            //[self swapWitnIndex1:current index2:current-1];
            self.array[current] = self.array[current-1];
            current--;
        }
        
        self.array[current] = curValue;
    }
}

二分搜索（Binary Search）

一、介绍

如何确定一个元素在数组中的位置？（假设数组里面全都是整数）
如果是无序数组，从第 0 个位置开始遍历搜索，平均时间复杂度：O(n)

0	1	2	3	4	5	6	7	8	9
31	66	17	15	28	20	59	88	45	56

如果是有序数组，可以使用二分搜索，最坏时间复杂度：O(logn)

0	1	2	3	4	5	6	7	8	9
15	17	20	28	31	45	56	59	66	88

二、思路

假设在 [begin, end) 范围内搜索某个元素 v，mid == (begin + end) / 2
如果 v < m，去 [begin, mid) 范围内二分搜索
如果 v > m，去 [mid + 1, end) 范围内二分搜索
如果 v == m，直接返回 mid

三、示例分析

四、代码实现

/// 二分搜索返回index，未找到返回-1
/// @param array 要搜索的数组
/// @param element 要搜索的元素
-(int)binarySearch:(NSArray*)array element:(id)element{
    
    if (array == nil || array.count == 0) return -1;
    
    //前闭后开
    int begin = 0;
    int end = (int)array.count;
    while (begin < end) {
        int mid = (begin + end)>>1;
        if ([array[mid] compare:element] == -1) {
            begin = mid+1;
        }else if([array[mid] compare:element] == 1){
            end = mid;
        }else{
            return mid;
        }
    }
    return -1;
}

插入排序优化

一、优化思路

在元素 v 的插入过程中，可以先二分搜索出合适的插入位置，然后再将元素 v 插入

0	1	2	3	4	5	6	7
2	4	8	8	8	12	14	v

要求二分搜索返回的插入位置：第1个大于 v 的元素位置
如果 v 是 5，返回 2
如果 v 是 1，返回 0
如果 v 是 15，返回 7
如果 v 是 8，返回 5

假设在 [begin, end) 范围内搜索某个元素 v，mid == (begin + end) / 2
如果 v < m，去 [begin, mid) 范围内二分搜索
如果 v ≥ m，去 [mid + 1, end) 范围内二分搜索

二、示例分析1

三、示例分析2

四、示例分析3

五、代码实现

//时间复杂度:最好O(n)、最坏O(n^2)、平均O(n^2)
//空间复杂度O(1)

-(void)sort{
    for (int begin = 1; begin<self.array.count; begin++) {
        [self insertSourceIndex:begin desIndex:[self searchIndex:begin]];
    }
}



/// 插入元素
/// @param sourceIndex 原始索引
/// @param desIndex 插入到的索引
-(void)insertSourceIndex:(int)sourceIndex desIndex:(int)desIndex{
    id element = self.array[sourceIndex];
    
    for (int i = sourceIndex; i>desIndex; i--) {
        //self.array[i] = self.array[i-1];
        [self moveWithFromIndex:i-1 toIndex:i];
    }
    
    self.array[desIndex] = element;
}



/// 获取index位置的元素将要出入到的位置索引
/// @param index 元素的索引
-(int)searchIndex:(int)index{
    if(self.array == nil || self.array.count == 0 ) return -1;
    
    id element = self.array[index];
    int beigin = 0;
    int end = index;
    while (beigin<end) {
        int mid = (beigin + end) >>1;
        if ([self compareWithValue1:element value2:self.array[mid]] == -1) {
            end = mid;
        }else{
            beigin = mid+1;
        }
    }
    return beigin;
}

需要注意的是，使用了二分搜索后，只是减少了比较次数，但插入排序的平均时间复杂度依然是 O(n^2)

行者常至，为者常成！

JHHK

JHHK

【进阶】2、排序（二）

目录

插入排序（Insertion Sort）

二分搜索（Binary Search）

插入排序优化