算法基础 - 排序

上半年换工作后变懒散了，好久没更新了，最近在读道长写的《iOS 面试之道》这本书的算法部分，可以在小专栏上阅读电子书，也可以在京东上购买实体书，写这篇文章文章记录一下常用的算法知识。

基本排序

1.1 冒泡排序

冒泡排序 :是一种简单的排序算法,它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。

冒泡排序算法的运作如下：

• 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
• 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
• 针对所有的元素重复以上的步骤，除了最后一个。

• 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

  
  冒泡排序.png

/**
 * 冒泡排序
 */
- (NSArray *)bubbleSort:(NSArray *)arr{
    NSMutableArray *tmpArray = [[NSMutableArray alloc]initWithArray:arr];
    int arrCount = (int)arr.count;
    
    for (int i = arrCount - 1; i > 0; i--) {
        for (int j = 0; j < i; j++) {
            //比较前后连个元素大小，如果是逆序的就交换两个元素的位置
            NSNumber *numI = tmpArray[j];
            NSNumber *numJ = tmpArray[j+1];
            if ([numI floatValue] > [numJ floatValue]) {
                tmpArray[j] = numJ;
                tmpArray[j + 1] = numI;
            }
        }
    }
    return tmpArray;
}

1.2 选择排序

选择排序: 选择出数组中的最小元素，将它与数组的第一个元素交换位置。再从剩下的元素中选择出最小的元素，将它与数组的第二个元素交换位置。不断进行这样的操作，直到将整个数组排序。

选择排序.png

/**
 * 选择排序
 */
- (NSArray *)sortValue:(NSArray *)arr{
    NSMutableArray *tmpArray = [[NSMutableArray alloc]initWithArray:arr];
    NSInteger count = arr.count;
    NSInteger minIndex = 0;
    for (int i = 0; i < count; i++) {
        minIndex = I;
        for (int j = i + 1; j < count; j++) {
            //从剩余数组中找找出最小的元素索引
            if ([tmpArray[minIndex] floatValue] > [tmpArray[j] floatValue]) {
                minIndex = j;
            }
        }
        NSNumber *numI = tmpArray[I];
        NSNumber *numMin = tmpArray[minIndex];
        tmpArray[i] = numMin;
        tmpArray[minIndex] = numI;
    }
    return tmpArray;
}

1.3 插入排序

插入排序: 它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

插入排序.gif

/**
 插入排序
 */
- (NSArray *)insertSort:(NSArray *)arr{
    NSMutableArray *tmpArray = [[NSMutableArray alloc]initWithArray:arr];
    NSInteger count = arr.count;
    for (int i = 1; i < count; i++) {
        for (int j = i; j > 0; j--) {
            NSNumber *currentNum = tmpArray[j];
            NSNumber *compareNum = tmpArray[j - 1];
            if ([currentNum floatValue] < [compareNum floatValue]) {
                tmpArray[j] = compareNum;
                tmpArray[j-1] = currentNum;
            }else{
                break;
            }
        }
    }
    return tmpArray;
}

1.4希尔排序

希尔排序: 也称递减增量排序算法，是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。希尔排序通过将比较的全部元素分为几个区域来提升插入排序的性能。这样可以让一个元素可以一次性地朝最终位置前进一大步。然后算法再取越来越小的步长进行排序。

例如，假设有这样一组数[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ]，如果我们以步长为5开始进行排序，我们可以通过将这列表放在有5列的表中来更好地描述算法，这样他们就应该看起来是这样：

13 14 94 33 82
25 59 94 65 23
45 27 73 25 39
10

然后我们对每列进行排序：

10 14 73 25 23
13 27 94 33 39
25 59 94 65 82
45

将上述四行数字，依序接在一起时我们得到：[ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ].这时10已经移至正确位置了，然后再以3为步长进行排序：

10 14 73
25 23 13
27 94 33
39 25 59
94 65 82
45

排序之后变为：

10 14 13
25 23 33
27 25 59
39 65 73
45 94 82
94

最后以1步长进行排序（此时就是简单的插入排序了）。

/**
 希尔排序
 */
- (NSArray *)chilleSort:(NSArray *)arr{
    NSMutableArray *tmpArray = [[NSMutableArray alloc]initWithArray:arr];
    NSInteger length = arr.count;
    int h = 1;
    
    //计算步长
    while (h < length / 3) {
        h  = 3 * h + 1; //h = 4,7,10,13,16
    }
    
    while (h >= 1) {
        for (int i = h; i < length ; i++) {
            for (int j = i; j >= h && (tmpArray[j] < tmpArray[j - h]); j-=h) {
                NSNumber *numOne = tmpArray[j];
                NSNumber *numTwo = tmpArray[j - h];
                tmpArray[j] = numTwo;
                tmpArray[j-h] = numOne;
            }
        }
        h = h / 3;
    }
    return tmpArray;
}

1.5归并排序 (还没搞明白)

归并排序: 是建立在归并操作上的一种有效的排序算法,该算法是采用分治法
归并排序的思想是将数组分成两部分，分别进行排序，然后归并起来。

归并排序.gif

/**
 归并排序
 */

/***--------------自上而下进行排序---------------**/
- (void)mergeSortArray:(NSMutableArray *)array{
    //创建一个辅助数组
    NSMutableArray *auxArray = [[NSMutableArray alloc]initWithCapacity:array.count];
    
    //对数组进行第一次二分
    [self mergeSort:array auxArray:auxArray low:0 high:(int)(array.count - 1)];
}


//对数组进行拆分
- (void)mergeSort:(NSMutableArray *)arr auxArray:(NSMutableArray *)auxArray low:(int)low high:(int)high{
    if (high <= low) {
        return;
    }
    int middel = low + (high - low) / 2;
    [self mergeSort:arr auxArray:auxArray low:low high:middel];
    [self mergeSort:arr auxArray:auxArray low:middel + 1 high:high];
    
    [self merge:arr auxArray:auxArray low:low middel:middel high:high];
}

//将数组中两个已经排序的部分归并成一个
- (void)merge:(NSMutableArray *)array auxArray:(NSMutableArray *)auxArray low:(int)low middel:(int)middle high:(int)high {
    
    int i = low;
    int j = middle + 1;
   
    for (int k = low; k <= high; k++) {
        //将数据复制到辅助数组
        auxArray[k] = array[k];
    }

    for (int k = low; k <= high; k++) {
        if (i > middle) {
            array[k] = auxArray[j++];
        }else if (j > high){
            array[k] = auxArray[i++];
        }else if (auxArray[i] <= array[j]){
            array[k] = auxArray[i++];
        }else{
            array[k] = auxArray[j++];
        }
    }
    
}

/**--------------自下而上进行排序----------------*/
- (void)mergeIteration:(NSMutableArray *)arr{
    int N = (int)arr.count;
    NSMutableArray *auxArray = [[NSMutableArray alloc]initWithCapacity:arr.count];
    for (int sz = 1; sz < N; sz += sz) {
        for (int i = 0; i < N - sz; i += sz + sz) {
            [self merge:arr auxArray:auxArray low:i middel:i + sz - 1 high:MIN(i + sz + sz - 1, N - 1)];
        }
    }
}