1、冒泡排序：

　　冒泡算法是一种基础的排序算法，这种算法会重复的比较数组中相邻的两个元素。如果一个元素比另一个元素大（小），那么就交换这两个元素的位置。重复这一比较直至最后一个元素。这一比较会重复n-1趟，每一趟比较n-j次，j是已经排序好的元素个数。每一趟比较都能找出未排序元素中最大或者最小的那个数字。这就如同水泡从水底逐个飘到水面一样。冒泡排序是一种时间复杂度较高，效率较低的排序方法。其空间复杂度是O(n)。

　　1, 最差时间复杂度 O(n^2)

　　2, 平均时间复杂度 O(n^2)

　　实现思路

　　1，每一趟比较都比较数组中两个相邻元素的大小

　　2，如果i元素小于i-1元素，就调换两个元素的位置

　　3，重复n-1趟的比较

 

　　

C 语言写法：

//*********** 冒泡降序排序 **********//int array[10] = {24, 17, 85, 13, 9, 54, 76, 45, 5, 63};int num = sizeof(array)/sizeof(int);for(int i = 0; i < num-1; i++) {    for(int j = 0; j < num - 1 - i; j++) {        if(array[j] < array[j+1]) {            int tmp = array[j];            array[j] = array[j+1];            array[j+1] = tmp;        }    }}for(int i = 0; i < num; i++) {    printf("%d\t", array[i]);}

Objective-C 写法：

#pragma mark - 冒泡降序排序- (void)bubbleDescendingOrderSortWithArray:(NSMutableArray *)descendingArr{    for (int i = 0; i < descendingArr.count; i++) {        for (int j = 0; j < descendingArr.count - 1 - i; j++) {            if ([descendingArr[j] intValue] < [descendingArr[j + 1] intValue]) {                int tmp = [descendingArr[j] intValue];                descendingArr[j] = descendingArr[j + 1];                descendingArr[j + 1] = [NSNumber numberWithInt:tmp];            }        }    }    NSLog(@"冒泡降序排序后结果：%@", descendingArr);}#pragma mark - 冒泡升序排序- (void)bubbleAscendingOrderSortWithArray:(NSMutableArray *)ascendingArr{    for (int i = 0; i < ascendingArr.count; i++) {        for (int j = 0; j < ascendingArr.count - 1 - i;j++) {            if ([ascendingArr[j+1]intValue] < [ascendingArr[j] intValue]) {                int temp = [ascendingArr[j] intValue];                ascendingArr[j] = ascendingArr[j + 1];                ascendingArr[j + 1] = [NSNumber numberWithInt:temp];            }        }    }    NSLog(@"冒泡升序排序后结果：%@", ascendingArr);}

　　2、选择排序：

　　实现思路：

　　 

1. 设数组内存放了n个待排数字，数组下标从1开始，到n结束。

　　 

2. i=1

　　 

3. 从数组的第i个元素开始到第n个元素，寻找最小的元素。（具体过程为:先设arr[i]为最小，逐一比较，若遇到比之小的则交换）

　　 

4. 将上一步找到的最小元素和第i位元素交换。

　　 

5. 如果i=n－1算法结束，否则回到第3步

 

  　复杂度：

　　平均时间复杂度：O(n^2)

　　

平均空间复杂度：O(1)

 

#pragma mark - 选择升序排序- (void)selectionAscendingOrderSortWithArray:(NSMutableArray *)ascendingArr{    for (int i = 0; i < ascendingArr.count; i ++) {        for (int j = i + 1; j < ascendingArr.count; j ++) {            if ([ascendingArr[i] integerValue] > [ascendingArr[j] integerValue]) {                int temp = [ascendingArr[i] intValue];                ascendingArr[i] = ascendingArr[j];                ascendingArr[j] = [NSNumber numberWithInt:temp];            }        }    }    NSLog(@"选择升序排序后结果：%@", ascendingArr);}#pragma mark - 选择降序排序- (void)selectionDescendingOrderSortWithArray:(NSMutableArray *)descendingArr{    for (int i = 0; i < descendingArr.count; i ++) {        for (int j = i + 1; j < descendingArr.count; j ++) {            if ([descendingArr[i] integerValue] < [descendingArr[j] integerValue]) {                int temp = [descendingArr[i] intValue];                descendingArr[i] = descendingArr[j];                descendingArr[j] = [NSNumber numberWithInt:temp];            }        }    }    NSLog(@"选择降序排序后结果：%@", descendingArr);}

 

　　3、快速排序：

　　实现思路：

　　1. 从数列中挑出一个元素，称为 "基准"（pivot），

　　2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分割之后，该基准是它的最后位置。这个称为分割（partition）操作。

　　3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。 

　　快速排序是基于分治模式处理的，对一个典型子数组A[p...r]排序的分治过程为三个步骤：

　　　　1.分解：

　　　　A[p..r]被划分为俩个（可能空）的子数组A[p ..q-1]和A[q+1 ..r]，使得

　　　　A[p ..q-1] <= A[q] <= A[q+1 ..r]

　　　　2.解决：通过递归调用快速排序，对子数组A[p ..q-1]和A[q+1 ..r]排序。

　　　　3.合并。

　　递回的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递回下去，但是这个算法总会结束，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。

　　复杂度：

　　平均时间复杂度：O(n^2)

　　平均空间复杂度：O(nlogn)       O(nlogn)~O(n^2)

　　伪代码：

QUICK_SORT(A,p,r)    if(p
     
      A[j]    exchange A[i+1]<——>A[r]return i+1
     

 

　　C 语言实现：

#include 
     
      int partition(int *arr, int low, int high){    int pivot = arr[high];    int i = low - 1;    int j, tmp;    for(j = low; j< high; ++j)        if(arr[j] < pivot) {            tmp = arr[++i];            arr[i] = arr[j];            arr[j] = tmp;        }    tmp = arr[i+1];    arr[i+1] = arr[high];    arr[high] = tmp;    return i+1;}void quick_sort(int *arr, int low, int high){    if(low < high){        int mid = partition(arr, low, high);        quick_sort(arr, low, mid-1);        quick_sort(arr, mid+1, high);    }}//testint main(){    int arr[10]={1,4,6,2,5,8,7,6,9,12};    quick_sort(arr,0,9);    int i;    for(i=0;i<10;++i)        printf("%d ",arr[i]);}
     

 

　　Objective-C 实现：

#pragma mark - 快速升序排序- (void)quickAscendingOrderSort:(NSMutableArray *)arr leftIndex:(NSInteger)left rightIndex:(NSInteger)right{    if (left < right) {        NSInteger temp = [self getMiddleIndex:arr leftIndex:left rightIndex:right];        [self quickAscendingOrderSort:arr leftIndex:left rightIndex:temp - 1];        [self quickAscendingOrderSort:arr leftIndex:temp + 1 rightIndex:right];    }    NSLog(@"快速升序排序结果：%@", arr);}- (NSInteger)getMiddleIndex:(NSMutableArray *)arr leftIndex:(NSInteger)left rightIndex:(NSInteger)right{    NSInteger tempValue = [arr[left] integerValue];    while (left < right) {        while (left < right && tempValue <= [arr[right] integerValue]) {            right --;        }        if (left < right) {            arr[left] = arr[right];        }        while (left < right && [arr[left] integerValue] <= tempValue) {            left ++;        }        if (left < right) {            arr[right] = arr[left];        }    }    arr[left] = [NSNumber numberWithInteger:tempValue];    return left;}

 

　　4、插入排序：　　

　　实现思路：

　　1. 从第一个元素开始，认为该元素已经是排好序的。

　　

2. 取下一个元素，在已经排好序的元素序列中从后向前扫描。

　　

3. 如果已经排好序的序列中元素大于新元素，则将该元素往右移动一个位置。

　　

4. 重复步骤3，直到已排好序的元素小于或等于新元素。

　　

5. 在当前位置插入新元素。

　　

6. 重复步骤2。

　　复杂度：

　　平均时间复杂度：O(n^2)

　　

平均空间复杂度：O(1)

　　

#pragma mark - 插入升序排序- (void)insertionAscendingOrderSort:(NSMutableArray *)ascendingArr{    for (NSInteger i = 1; i < ascendingArr.count; i ++) {        NSInteger temp = [ascendingArr[i] integerValue];        for (NSInteger j = i - 1; j >= 0 && temp < [ascendingArr[j] integerValue]; j --) {            ascendingArr[j + 1] = ascendingArr[j];            ascendingArr[j] = [NSNumber numberWithInteger:temp];        }    }    NSLog(@"插入升序排序结果：%@",ascendingArr);}

 

　　五、堆排序： 

　　

#pragma mark - 堆排序- (void)heapsortAsendingOrderSort:(NSMutableArray *)ascendingArr{    NSInteger endIndex = ascendingArr.count - 1;    ascendingArr = [self heapCreate:ascendingArr];    while (endIndex >= 0) {//        NSLog(@"将list[0]:\%@与list[\(endIndex)]:\%@交换", ascendingArr[0], ascendingArr[endIndex]);        NSNumber *temp = ascendingArr[0];        ascendingArr[0] = ascendingArr[endIndex];        ascendingArr[endIndex] = temp;        endIndex -= 1;        ascendingArr = [self heapAdjast:ascendingArr withStartIndex:0 withEndIndex:endIndex + 1];    }    NSLog(@"堆排序结果：%@", ascendingArr);}- (NSMutableArray *)heapCreate:(NSMutableArray *)array{    NSInteger i = array.count;    while (i > 0) {        array = [self heapAdjast:array withStartIndex:i - 1 withEndIndex:array.count];        i -= 1;    }    return array;}- (NSMutableArray *)heapAdjast:(NSMutableArray *)items withStartIndex:(NSInteger)startIndex withEndIndex:(NSInteger)endIndex{    NSNumber *temp = items[startIndex];    NSInteger fatherIndex = startIndex + 1;    NSInteger maxChildIndex = 2 * fatherIndex;    while (maxChildIndex <= endIndex) {        if (maxChildIndex < endIndex && [items[maxChildIndex - 1] floatValue] < [items[maxChildIndex] floatValue]) {            maxChildIndex++;        }        if ([temp floatValue] < [items[maxChildIndex - 1] floatValue]) {            items[fatherIndex - 1] = items[maxChildIndex - 1];        } else {            break;        }        fatherIndex = maxChildIndex;        maxChildIndex = fatherIndex * 2;    }    items[fatherIndex - 1] = temp;    return items;}

 

　　六、归并排序：

　　把序列分成元素尽可能相等的两半。

　　把两半元素分别进行排序。

　　把两个有序表合并成一个。

　　

#pragma mark - 归并升序排序- (void)megerSortAscendingOrderSort:(NSMutableArray *)ascendingArr{    NSMutableArray *tempArray = [NSMutableArray arrayWithCapacity:1];    for (NSNumber *num in ascendingArr) {        NSMutableArray *subArray = [NSMutableArray array];        [subArray addObject:num];        [tempArray addObject:subArray];    }    while (tempArray.count != 1) {        NSInteger i = 0;        while (i < tempArray.count - 1) {            tempArray[i] = [self mergeArrayFirstList:tempArray[i] secondList:tempArray[i + 1]];            [tempArray removeObjectAtIndex:i + 1];                        i++;        }    }    NSLog(@"归并升序排序结果：%@", ascendingArr);}- (NSArray *)mergeArrayFirstList:(NSArray *)array1 secondList:(NSArray *)array2 {    NSMutableArray *resultArray = [NSMutableArray array];    NSInteger firstIndex = 0, secondIndex = 0;    while (firstIndex < array1.count && secondIndex < array2.count) {        if ([array1[firstIndex] floatValue] < [array2[secondIndex] floatValue]) {            [resultArray addObject:array1[firstIndex]];            firstIndex++;        } else {            [resultArray addObject:array2[secondIndex]];            secondIndex++;        }    }    while (firstIndex < array1.count) {        [resultArray addObject:array1[firstIndex]];        firstIndex++;    }    while (secondIndex < array2.count) {        [resultArray addObject:array2[secondIndex]];        secondIndex++;    }    return resultArray.copy;}

　　七、希尔排序：

　　

#pragma mark - 希尔排序- (void)shellAscendingOrderSort:(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++;            }        }    }    NSLog(@"希尔升序排序结果：%@", ascendingArr);}- (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 numberLength(NSNumber *number) {    NSString *string = [NSString stringWithFormat:@"%ld", (long)[number integerValue]];    return string.length;}- (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;}

 

　　8、基数排序：

　　

#pragma mark - 基数排序- (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++;            }        }    }    NSLog(@"基数升序排序结果：%@", ascendingArr);}