具体的8种排序算法的实现，请前往我的GitHub。点我过去

1、冒泡排序：

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

实现思路
　　1，每一趟比较都比较数组中两个相邻元素的大小
　　2，如果i元素小于i-1元素，就调换两个元素的位置
　　3，重复n-1趟的比较

冒泡排序代码实现

+ (void) bubbleSort:(NSMutableArray *)array{
//遍历`数组的个数`次
/*
 i = 0 的时候，j的相邻两个位置都要比较排一下位置：  第1次i循环冒泡出arr_M中最小的
 j = 0 的时候：arr_M = 41235
 j = 1 的时候：arr_M = 42135
 j = 2 的时候：arr_M = 42315
 j = 3 的时候：arr_M = 42351
 i = 1;         第2次i循环冒泡出剩余最小的  以此类推
 ……  ……
 */
for (int i = 0; i < array.count; ++i) {
    
    //遍历数组的每一个`索引`（不包括最后一个,因为比较的是j+1）
    for (int j = 0; j < array.count-1 - i; ++j) {
        
        //根据索引的`相邻两位`进行`比较`
        if (array[j] < array[j+1]) {
            
            [array exchangeObjectAtIndex:j withObjectAtIndex:j+1];
        }
        
    }
} NSLog(@"冒泡排序：%@",array);}

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)

选择排序代码实现

+ (void)selectSort:(NSMutableArray *)array{
for (int i=0; i<array.count; i++) {
    
    for (int j=i+1; j<array.count; j++) {
        
        if (array[i]<array[j]) {
            
            [array exchangeObjectAtIndex:i withObjectAtIndex:j];
            
        }
    }
}
NSLog(@"选择排序：%@",array);}

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)

快速排序代码实现：

> + (void)quickSort:(NSMutableArray *)array low:(int)low high:(int)high{
if(array == nil || array.count == 0 || low >= high){
    NSLog(@"注意快速排序条件");
    return;
}

//取中值
int middle = low + (high - low)/2;
NSNumber *prmt = array[middle];
int i = low;
int j = high;

//开始排序，使得left<prmt 同时right>prmt
while (i <= j) {
    //        while ([array[i] intValue] < [prmt intValue]) {
    //该行与下一行作用相同
    
    while ([array[i] compare:prmt] == NSOrderedAscending) {
        i++;
    }
    //        while ([array[j] intValue] > [prmt intValue]) {
    //该行与下一行作用相同
    
    while ([array[j] compare:prmt] == NSOrderedDescending) {
        j--;
    }
    
    if(i <= j){
        [array exchangeObjectAtIndex:i withObjectAtIndex:j];
        i++;
        j--;
    }
    NSLog(@"快速排序排序中:%@",array);
}
if (low < j) {
    [self quickSort:array low:low high:j];
}
if (high > i) {
    [self quickSort:array low:i high:high];
}}

4、插入排序：

实现思路：
　　1. 从第一个元素开始，认为该元素已经是排好序的。
　　2. 取下一个元素，在已经排好序的元素序列中从后向前扫描。
　　3. 如果已经排好序的序列中元素大于新元素，则将该元素往右移动一个位置。
　　4. 重复步骤3，直到已排好序的元素小于或等于新元素。
　　5. 在当前位置插入新元素。
　　6. 重复步骤2。
　　复杂度：
　　平均时间复杂度：O(n^2)
　　平均空间复杂度：O(1)

+ (void)inserSort:(NSMutableArray *)array{
for (int i = 0; i < array.count; i++) {
    NSNumber *temp = array[i];
    int j = i-1;
     while (j >= 0 && [array[j] compare:temp] == NSOrderedDescending) {
        [array replaceObjectAtIndex:j+1 withObject:array[j]];
        j--;
    }
    [array replaceObjectAtIndex:j+1 withObject:temp];
    NSLog(@"插入排序排序中:%@",array);
}}

5、归并排序：

归并排序是建立在归并操作上的一种有效的排序算法，算法主要采用分治法（Divide and Conquer）的一个非常典型的应用。归并排序的算法复杂度为O（N*logN），需要的额外的空间跟数组的长度N有关系，实现归并排序最简单的方法是将两个数组重新整合到第三个数组中。通常对于一个数组我们对前半部分进行排序，然后进行后半部分进行排序，实现原地归并操作，不过需要额外的空间存储数组。假设数据中有8个元素，先分为四组进行比较，之后分为两组进行比较，最后分为一组进行比较，这样就衍生出来两种方法，一种是自顶向下的归并排序，一种是自底向上的归并排序。

实现思路:
1.把序列分成元素尽可能相等的两半。
2.把两半元素分别进行排序。
3.把两个有序表合并成一个。

6.希尔排序

希尔排序是以插入排序为基础的一种快速的排序算法。因为在大规模乱序数组中使用插入排序很慢，因为它只会交换相邻的两个元素，因此，如果越小的元素越是靠后，那么操作的复杂度将会大大提升，所以，人们把插入排序进行了改良，变成了希尔排序。
希尔排序的思想：希尔排序的思想是使数组中任意间隔为 h 的元素都是有序的。这样的数组为 h 有序数组。换句话说,一个 h 有序数组就是 h 个互相独 的有序数组编织在一起 成的一个数组。在进行排序时,如果 h 很大,我们就能将元素动到很远的地方,为实现更小的 h 有序创造方便。用这种方式,对于任意以 1 结尾的 h 序列,我们都能够将数组排序。这就是希尔排序。
如果您还想了解更多的希尔排序，可参看 点我链接

7.基数排序

原理实现：
基数排序是另外一种比较有特色的排序方式，它是怎么排序的呢？我们可以按照下面的一组数字做出说明：12、 104、 13、 7、 9
（1）按个位数排序是12、13、104、7、9
（2）再根据十位排序104、7、9、12、13
（3）再根据百位排序7、9、12、13、104
这里注意，如果在某一位的数字相同，那么排序结果要根据上一轮的数组确定，举个例子来说：07和09在十分位都是0，但是上一轮排序的时候09是排在07后面的；同样举一个例子，12和13在十分位都是1，但是由于上一轮12是排在13前面，所以在十分位排序的时候，12也要排在13前面。
所以，一般来说，10基数排序的算法应该是这样的？
（1）判断数据在各位的大小，排列数据；
（2）根据1的结果，判断数据在十分位的大小，排列数据。如果数据在这个位置的余数相同，那么数据之间的顺序根据上一轮的排列顺序确定；
（3）依次类推，继续判断数据在百分位、千分位......上面的数据重新排序，直到所有的数据在某一分位上数据都为0。

复杂度分析.jpg

其中，d 为位数，r 为基数，n 为原数组个数。
在基数排序中，因为没有比较操作，所以在复杂上，最好的情况与最坏的情况在时间上是一致的，均为 O(d * (n + r))。

8.堆排序

堆排序的空间复杂度为O(1),时间复杂度为O(nlogn)。
如果你想了解更多关于堆排序，可参考点击链接

附

具体的8种排序算法的实现demo，请前往我的GitHub。点我前往