排序算法

排序算法

• 冒泡排序
• 选择排序
• 直接插入排序
• 希尔排序
• 快速排序

冒泡排序

冒泡排序是一种交换排序，基本思想是两两相邻的记录的关键字，如果反序则交换，知道没有反序为止。

冒泡排序的复杂度是n(n-1)/2,就是o(n²)。

/*对顺序列表排序*/
-(void)sort:(NSMutableArray *)list{
    NSInteger i , j;
    for (i = 0; i < list.count; i ++) {
        for (j = list.count-1; j>=i; j --) {
            if (list[j] > list[i]) {
                /*
                 交换obj
                 */
                [list exchangeObjectAtIndex:i withObjectAtIndex:j];
            }
        }
    }
}

选择排序

简单选择排序法是通过n-i次关键字间的比较，从n-i+1个记录选出关键字最小的记录，并和第i（1=《i《=n）交换之。

选择排序复杂度是n（n-1）/2,就是o（n²），性能略优于冒泡。

-(void)sort:(NSMutableArray *)list{
    NSInteger i , j , min;
    for (i = 1; i < list.count; i ++) {
        min = i; //默认最小值是第一个
        for (j = i + 1; j <= list.count; j ++) {
            if (list[min]  >  list[j] ) {
                min = j; //记录最小值的索引
                
            }
        }
        if (min != i) {// 出现最小的值的时候 和上个最小的值交换位置
            /*
             交换obj
             */
            [list exchangeObjectAtIndex:i withObjectAtIndex:j];
        }
        
    }
}

###直接插入排序算法

直接插入排序的基本操作是将一个记录插入到已经排好的有序表中，从而得到一个新的，记录增加1的有序表。

直接插入排序时间复杂度是（n+4）（n-1）/2，就是o（n²）。
性能略优于选择排序。

-(void)sort2:(NSMutableArray *)list{
    NSInteger i , j ;
    for (i = 1; i < list.count; i ++) {
       
        if (list[i-1] < list[i]) {// i-1 小于 i
             NSInteger data = [list[i] integerValue];//设置哨兵
            for (j = i - 1; j >= 0 && [list[j] integerValue] < data  ; j --) {
                list[j+1] = list[j];//向后移动一位
            }
            if (data) {
                 list[j+1] =@(data);//哨兵赋值
            }
        }
    }
}

希尔排序

希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

//希尔排序算法
-(void)shellSort:(NSMutableArray *)list{
    NSInteger i , j ;
    NSInteger inrement = list.count;
    do {
        inrement = inrement/3 + 1;//增量序列
        for (i = inrement+1; i < list.count; i ++) {
            if (list[i]<list[i-inrement]) {
                //需将list[i] 插入有序增量字表
                NSNumber  * data = list[i];
                for (j = i - inrement; j >0 && data < list[j]; j-= inrement) {
                    list[j+inrement] = list[j];//记录后移
                }
                list[j+inrement] = data;//插入
            }
        }
    }while (inrement > 1);
}

希尔排序和直接插入排序有异曲同工之妙，都是记录后移，都是插入排序。不过希尔用的条件是步长，步长越来越短，直到是1，而直接插入排序是直接是1，循环次数多。
时间复杂度是o(n的二分之三次方)，优于o（n²）。

快速排序

基本思想是:通过一趟排序将带排序记录分割成独立的两部分，其中一部分记录的关键字均比另外一部分的关键字小，则可分别对着两部分重新排序，以达到整个序列的有序的目的。

// 快速排序
-(void)quickSort:(NSMutableArray *)list{
    [self qsort:list low:0 hight:list.count-1];
}
-(void)qsort:(NSMutableArray *)list low:(NSInteger)low hight:(NSInteger ) hight{
    NSInteger pt;
    if (low < hight) {
        pt =[self partition:list low:low high:hight];//将整个序列一分为二
        [self qsort:list low:low hight:pt -1];//对低子表递归排序
        [self qsort:list low:pt + 1 hight:hight];//对高字表递归排序
    }
}
//返回在他前后记录均不大（小）与他。
-(NSInteger)partition:(NSMutableArray *)list low:(NSInteger)low high:(NSInteger)high{
    NSNumber * data = list[low];
    while (low < high) {
        while (low < high && list[high] >= data)// 倒叙 找出比data小的 并交换位置
            high --;
            [list exchangeObjectAtIndex:low withObjectAtIndex:high];
        
        while (low < high && list[low] <= data)//正序 找出比data大的 并交换位置
            low ++;
         [list exchangeObjectAtIndex:low withObjectAtIndex:high];
        
    }
    return low;
}

时间复杂度是o（n²）空间复杂度是o（log n）。

优化选择枢轴
三数取中发，就是取三个关键字排序，将中间的数作为枢轴，一般是取左，右，中间三个数。

  data = list[low];

将上面的一行改成下边的：

NSNumber * data;
    NSInteger m = low + (high + low)/2;
    if (list[low] > list[high]) {
        [list exchangeObjectAtIndex:low withObjectAtIndex:high];
    }
    if (list[m] > list[high]) {
        [list exchangeObjectAtIndex:m withObjectAtIndex:high];
    }
    if (list[m] > list[low]) {
        [list exchangeObjectAtIndex:m withObjectAtIndex:low];
    }
    data = list[low];

优化不必要的交换

//返回在他前后记录均不大（小）与他。
-(NSInteger)partition:(NSMutableArray *)list low:(NSInteger)low high:(NSInteger)high{
    NSNumber * data;
    NSInteger m = low + (high - low)/2;
    if (list[low] > list[high]) {
        [list exchangeObjectAtIndex:low withObjectAtIndex:high];
    }
    if (list[m] > list[high]) {
        [list exchangeObjectAtIndex:m withObjectAtIndex:high];
    }
    if (list[m] > list[low]) {
        [list exchangeObjectAtIndex:m withObjectAtIndex:low];
    }
    data = list[low];//取出来适当的关键字
    while (low < high) {
        while (low < high && list[high] >= data)// 倒叙 找出比data小的 并交换位置
            high --;
        list[low] = list[high];  //将 上面的交换改成直接赋值
        
        while (low < high && list[low] <= data)//正序 找出比data大的 并交换位置
            low ++;
         list[high ] = list[low];   //将 上面的交换改成直接赋值
        
    }
    list[low] = data; //最后 将关键字 赋值给low的位置
    return low;
}