1971594626768_.pic_hd.jpg

交换排序--->冒泡排序 O(n²)

1、比较相邻的元素。如果第一个比第二个大（小），就交换他们两个。
2、对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大（小）的数。
3、针对所有的元素重复以上的步骤，除了最后已经选出的元素（有序）。
4、持续每次对越来越少的元素（无序元素）重复上面的步骤，直到没有任何一对数字需要比较，则序列最终有序。

- (void)moPaoPaiXu:(NSMutableArray *) array{
    for (int i= 0; i < array.count - 1; i++) {
        for (int j = 0; j<array.count - 1 - i; j++) {
            NSInteger a = [array [j] integerValue];
            NSInteger b = [array [j+1] integerValue];
            if (a > b) {
                [array exchangeObjectAtIndex:j withObjectAtIndex:j+1];
            }
        }
    }
}

交换排序--->快速排序 O(n²)

通过一趟排序将数据分割成两部分，其中一部分的所有数据都比另一部分的所有数据都小，但是两部分数据是无序的。然后再对两部分的数据分别进行第一趟的排序，直到最后的数据是有序的。
排序步骤：
1.选择所有数据中的第一个数据作为一个比较的标准。(左侧数据下标i 右侧数据下标j。最开始i = 0,j = 数据个数-1)
2.从数据的最右端开始找比这个标准数据小的一个数据（j–），找到后，将其赋值给第i个数据。（为了让左侧数据都小于这个比较的数据）
3.从数据的最左侧开始找比这个标准数据大的一个数据（i ++），找到后，将其赋值给第j个数据。（为了让右侧数据都大于这个比较的数据）
4.直到i和j相等，然后再分别对左右侧数据进行第3、4步的比较。最终得到的数据是一组递增有序数据。

- (void)quickSortArray:(NSMutableArray *)array withLeftIndex:(NSInteger)leftIndex andRightIndex:(NSInteger)rightIndex {
    if (leftIndex >= rightIndex) {//如果数组长度为0或1时返回
        return ;
    }
    NSInteger i = leftIndex;
    NSInteger j = rightIndex;
    NSInteger key = [array[i] integerValue];//记录比较基准数
    while (i < j) {
        /**** 首先从右边j开始查找比基准数小的值 ***/
        while (i < j && [array[j] integerValue] >= key) {//如果比基准数大，继续查找
            j--;
        }
        //如果比基准数小，则将查找到的小值调换到i的位置
        array[i] = array[j];
        /**** 当在右边查找到一个比基准数小的值时，就从i开始往后找比基准数大的值 ***/
        while (i < j && [array[i] integerValue] <= key) {//如果比基准数小，继续查找
            i++;
        }
        //如果比基准数大，则将查找到的大值调换到j的位置
        array[j] = array[i];
    }
    //将基准数放到正确位置
    array[i] = @(key);
    /**** 递归排序 ***/
    //排序基准数左边的
    [self quickSortArray:array withLeftIndex:leftIndex andRightIndex:i - 1];
    //排序基准数右边的
    [self quickSortArray:array withLeftIndex:i + 1 andRightIndex:rightIndex];
}

插入排序--->直接插入排序 O(n²)

将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序。
1,从第一个元素开始，认为该元素已经是排好序的。
2,取下一个元素，在已经排好序的元素序列中从后向前扫描。
3,如果已经排好序的序列中元素大于新元素，则将该元素往右移动一个位置。
4,重复上一步骤，直到已排好序的元素小于或等于新元素。
5,在当前位置插入新元素。
6,重复"取下一个元素，在已经排好序的元素序列中从后向前扫描"过程。

- (void)insertPaiXu:(NSMutableArray *) array{
    for (int i = 1; i < array.count; i++) {
        NSNumber *temp = array[i];
        //temp 为待排元素 i为其位置 j为已排元素最后一个元素的位置（即取下一个元素，在已经排好序的元素序列中从后向前扫描）
        int j = i-1;
        //当j < 0 时， i 为第一个元素 该元素认为已经是排好序的 所以不进入while循环
        while (j >= 0 && [array[j] floatValue] > [temp floatValue]) {
            //如果已经排好序的序列中元素大于新元素，则将该元素往右移动一个位置
            [array replaceObjectAtIndex:j+1 withObject:array[j]];
            j--;
        }
        //跳出while循环时，j的元素小于或等于i的元素(待排元素)。插入新元素 i= j+1
        [array replaceObjectAtIndex:j+1 withObject:temp];
    }
}

插入排序--->希尔排序。 最坏O(n²),最优O(n²⁄³)

希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
希尔排序在插入排序的基础上增加一个叫增量的概念。那什么增量？插入排序只能与相邻的元素进行比较，而希尔排序则是进行跳跃比较，而增量就是步长。比如增量为3时，
下标为0的元素与下标为3的元素比较，3再与6比较，1与4比较，4再与7比较……比较完后，再去减少增量，重复之前步骤，直到增量为1，此时只有一个分组了，
再对这一个分组进行插入排序，整个希尔排序就结束了。

- (void)xierPaiXu:(NSMutableArray *) array{
    int gap = (int)array.count / 2;
    while (gap > 0) {
        //参考 直接插入排序
        for (int i = gap; i < array.count; i++) {
            NSNumber *temp = array[i];
            int j = i;
            while (j >= gap && [array[j - gap] floatValue] > [temp floatValue]) {
                [array replaceObjectAtIndex:j withObject:array[j - gap]];
                j -= gap;
            }
            [array replaceObjectAtIndex:j withObject:temp];
        }
        //步长/2 > 0
        gap = gap / 2;
    }
}

选择排序--->选择排序 O(n²) 比冒泡排序快

1,在待排序记录r[1]~r[n]中选出最小的记录，将它与r[1]交换；
2,在待排序记录r[2]~r[n]中选出最小的记录，将它与r[2]交换；
3,第i趟在待排序记录r[i]~r[n]中选出最小的记录，将它与r[i]交换，使有序序列不断增长直到全部排序完毕。

- (void)logChoosePaiXun:(NSMutableArray *) array {
    for (int i=0;i<array.count;i++) {
        //先设数组最小值下标为i；
        NSInteger min = i;
        for (int j=i+1; j<array.count; j++) {
            if ([array[j] floatValue] < [array[min] floatValue]) {
                min = j;
            }
        }
        //交换数据
        if (min != i) {
            [array exchangeObjectAtIndex:i withObjectAtIndex:min];
        }
    }
}

选择排序--->堆排序 O(n)

堆排序(Heap Sort) 就是利用堆(假设利用大堆顶)进行排序的方法。它的基本思想是，将待排序的序列构成一个大顶堆。此时，整个序列的最大值就是堆顶的根节点。将它移走
(其实就是将其与堆数组的末尾元素交换，此时末尾元素就是最大值)，然后将剩余的n-1个序列重新构造成一个堆，这样就会得到n个元素中的次小值。如此反复执行，便能得到一个有序序列了。

- (void)heapSort:(NSMutableArray *)list
{
    NSInteger i ,size;
    size = list.count;
    //找出最大的元素放到堆顶
    for (i= list.count/2; i>=0; i--) {
        [self createBiggesHeap:list withSize:size beIndex:i];
    }
    
    while(size > 0){
        [list exchangeObjectAtIndex:size-1 withObjectAtIndex:0]; //将根(最大) 与数组最末交换
        size -- ;//树大小减小
        [self createBiggesHeap:list withSize:size beIndex:0];
    }
}

- (void)createBiggesHeap:(NSMutableArray *)list withSize:(NSInteger) size beIndex:(NSInteger)element {
    NSInteger lchild = element *2 + 1,rchild = lchild+1; //左右子树
    while (rchild < size) { //子树均在范围内
        if ([list[element] floatValue]>=[list[lchild] floatValue] && [list[element] floatValue]>=[list[rchild] floatValue]) return; //如果比左右子树都大，完成整理
        if ([list[lchild] floatValue]> [list[rchild] floatValue]) { //如果左边最大
            [list exchangeObjectAtIndex:element withObjectAtIndex:lchild]; //把左面的提到上面
            element = lchild; //循环时整理子树
        }else{//否则右面最大
            [list exchangeObjectAtIndex:element withObjectAtIndex:rchild];
            element = rchild;
        }
        
        lchild = element * 2 +1;
        rchild = lchild + 1; //重新计算子树位置
    }
    //只有左子树且子树大于自己
    if (lchild < size && list[lchild] > list[element]) {
        [list exchangeObjectAtIndex:lchild withObjectAtIndex:element];
    }
}

归并排序 O(nlogn)

把序列分成元素尽可能相等的两半。把两半元素分别进行排序。把两个有序表合并成一个。

- (void)mergeSortArray:(NSMutableArray *)array {
    NSMutableArray * auxiliaryArray = [[NSMutableArray alloc]initWithCapacity:array.count];
    [self mergeSort:array auxiliary:auxiliaryArray low:0 high:(int)(array.count-1)];
}

- (void)mergeSort:(NSMutableArray *)array auxiliary:(NSMutableArray *)auxiliaryArray low:(int)low high:(int)high {
    if (low>=high) {//递归跳出判断
        return;
    }
    //对分组进行二分
    int middle = (high - low)/2 + low;
    [self mergeSort:array auxiliary:auxiliaryArray low:low high:middle]; //左边
    [self mergeSort:array auxiliary:auxiliaryArray low:middle + 1 high:high];//右边
    //对每个有序数组进行回归合并
    [self merge:array auxiliary:auxiliaryArray low:low middel:middle high:high];
}

- (void)merge:(NSMutableArray *)array auxiliary:(NSMutableArray *)auxiliaryArray low:(int)low middel:(int)middle high:(int)high {
    //将数组元素复制到副本
    for (int i=low; i<=high; i++) {
        auxiliaryArray[i] = array[i];
    }
    //左侧数组标记
    int leftIndex = low;
    //右侧数组标记
    int rightIndex = middle + 1;
    //比较完成后比较小的元素要放的位置标记
    int currentIndex = low;
    while (leftIndex <= middle && rightIndex <= high) {
        //此处是使用NSNumber进行的比较，你也可以转成NSInteger再比较
        if ([auxiliaryArray[leftIndex] compare:auxiliaryArray[rightIndex]]!=NSOrderedDescending) {
            //左侧标记的元素小于等于右侧标记的元素
            array[currentIndex] = auxiliaryArray[leftIndex];
            currentIndex++;
            leftIndex++;
        }else{
            //右侧标记的元素小于左侧标记的元素
            array[currentIndex] = auxiliaryArray[rightIndex];
            currentIndex++;
            rightIndex++;
        }
    }
    //如果完成后左侧数组有剩余
    if (leftIndex <= middle) {
        for (int i = 0; i<=middle - leftIndex; i++) {
            array[currentIndex +i] = auxiliaryArray[leftIndex +i ];
        }
    }
}

基数排序 O(nlogn)

适用范围：正整数，或者可以提供正整数排序的类（对象）
核心思想（以整数为例）：依次对数组中元素的个位十位百位千位进行计数排序。

1. 按照个位数进行排序。
2. 按照十位数进行排序。
3. 按照百位数进行排序。
   排序后，数列就变成了一个有序序列。

- (void)radixAscendingOrderSort:(NSMutableArray *)ascendingArr
{
    NSMutableArray *buckt = [self createBucket];
    NSNumber *maxnumber = [self listMaxItem:ascendingArr];
    NSInteger maxLength = numberLength(maxnumber);
    for (int digit = 1; digit <= maxLength; digit++) {
        // 入桶
        for (NSNumber *item in ascendingArr) {
            NSInteger baseNumber = [self fetchBaseNumber:item digit:digit];
            NSMutableArray *mutArray = buckt[baseNumber];
            [mutArray addObject:item];
        }
        NSInteger index = 0;
        for (int i = 0; i < buckt.count; i++) {
            NSMutableArray *array = buckt[i];
            while (array.count != 0) {
                NSNumber *number = [array objectAtIndex:0];
                ascendingArr[index] = number;
                [array removeObjectAtIndex:0];
                index++;
            }
        }
    }
}

//创建0-9个空桶
- (NSMutableArray *)createBucket {
    NSMutableArray *bucket = [NSMutableArray array];
    for (int index = 0; index < 10; index++) {
        NSMutableArray *array = [NSMutableArray array];
        [bucket addObject:array];
    }
    return bucket;
}

//最大的数字
- (NSNumber *)listMaxItem:(NSArray *)list {
    NSNumber *maxNumber = list[0];
    for (NSNumber *number in list) {
        if ([maxNumber integerValue] < [number integerValue]) {
            maxNumber = number;
        }
    }
    return maxNumber;
}

//找到对应位置的数字(个,十,百,千....)
- (NSInteger)fetchBaseNumber:(NSNumber *)number digit:(NSInteger)digit {
    if (digit > 0 && digit <= numberLength(number)) {
        NSMutableArray *numbersArray = [NSMutableArray array];
        NSString *string = [NSString stringWithFormat:@"%ld", [number integerValue]];
        for (int index = 0; index < numberLength(number); index++) {
            [numbersArray addObject:[string substringWithRange:NSMakeRange(index, 1)]];
        }
        NSString *str = numbersArray[numbersArray.count - digit];
        return [str integerValue];
    }
    return 0;
}

//数字的长度
NSInteger numberLength(NSNumber *number) {
    NSString *string = [NSString stringWithFormat:@"%ld", (long)[number integerValue]];
    return string.length;
}