1. 冒泡排序

冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

算法分析

比较相邻的元素。如果第一个比第二个大，就交换他们两个。对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。针对所有的元素重复以上的步骤，除了最后一个。持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

原始待排序数组| 6 | 2 | 4 | 1 | 5 | 9 |

第一趟排序(外循环)
第一次两两比较6 > 2交换(内循环)
交换前状态| 6 | 2 | 4 | 1 | 5 | 9 |
交换后状态| 2 | 6 | 4 | 1 | 5 | 9 |

第二次两两比较,6 > 4交换
交换前状态| 2 | 6 | 4 | 1 | 5 | 9 |
交换后状态| 2 | 4 | 6 | 1 | 5 | 9 |

第三次两两比较,6 > 1交换
交换前状态| 2 | 4 | 6 | 1 | 5 | 9 |
交换后状态| 2 | 4 | 1 | 6 | 5 | 9 |

第四次两两比较,6 > 5交换
交换前状态| 2 | 4 | 1 | 6 | 5 | 9 |
交换后状态| 2 | 4 | 1 | 5 | 6 | 9 |

第五次两两比较,6 < 9不交换
交换前状态| 2 | 4 | 1 | 5 | 6 | 9 |
交换后状态| 2 | 4 | 1 | 5 | 6 | 9 |

第二趟排序(外循环)
第一次两两比较2 < 4不交换
交换前状态| 2 | 4 | 1 | 5 | 6 | 9 |
交换后状态| 2 | 4 | 1 | 5 | 6 | 9 |

第二次两两比较,4 > 1交换
交换前状态| 2 | 4 | 1 | 5 | 6 | 9 |
交换后状态| 2 | 1 | 4 | 5 | 6 | 9 |

第三次两两比较,4 < 5不交换
交换前状态| 2 | 1 | 4 | 5 | 6 | 9 |
交换后状态| 2 | 1 | 4 | 5 | 6 | 9 |

第四次两两比较,5 < 6不交换
交换前状态| 2 | 1 | 4 | 5 | 6 | 9 |
交换后状态| 2 | 1 | 4 | 5 | 6 | 9 |

第三趟排序(外循环)
第一次两两比较2 > 1交换
交换后状态| 2 | 1 | 4 | 5 | 6 | 9 |
交换后状态| 1 | 2 | 4 | 5 | 6 | 9 |

第二次两两比较,2 < 4不交换
交换后状态| 1 | 2 | 4 | 5 | 6 | 9 |
交换后状态| 1 | 2 | 4 | 5 | 6 | 9 |

第三次两两比较,4 < 5不交换
交换后状态| 1 | 2 | 4 | 5 | 6 | 9 |
交换后状态| 1 | 2 | 4 | 5 | 6 | 9 |

第四趟排序(外循环)无交换
第五趟排序(外循环)无交换

排序完毕,输出最终结果1 2 4 5 6 9

- (NSMutableArray *)bubbleSortArray:(NSMutableArray *)arr
{
    id temp;
    int i, j;
    for (i=0; i < [arr count] - 1; ++i) {
        for (j=0; j < [arr count] - i - 1; ++j) {
            if (arr[j] > arr[j+1]) { // 升序排列
                temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
    return arr;
}

2.插入排序

插入排序就是每一步都将一个待排数据按其大小插入到已经排序的数据中的适当位置，直到全部插入完毕。 插入排序方法分直接插入排序和折半插入排序两种。

时间复杂度与空间复杂度

时间复杂度：O（n^2)
空间复杂度：O（1）

最少比较次数：（已排序的数组）n-1次
最多比较次数：（降序的数组）n(n-1)/2次

数组在已排序或者是“近似排序”时，插入排序效率的最好情况运行时间为O(n)；插入排序最坏情况运行时间和平均情况运行时间都为O（n^2) 。

插入排序不适合对大量数据排序，适合对接近排序的数据排序。插入排序是稳定排序。通常，插入排序呈现出二次排序算法中的最佳性能。对于具有较少元素（如n<=15）的列表来说，二次算法十分有效。在列表已被排序时，插入排序是线性算法O(n)。在列表“近似排序”时，插入排序仍然是线性算法。在列表的许多元素已位于正确的位置上时，就会出现“近似排序”的条件。

算法描述

假定n是数组的长度，首先假设第一个元素被放置在正确的位置上，这样仅需从1到n-1范围内对剩余元素进行排序。对于每次遍历，从0到i-1范围内的元素已经被排好序，每次遍历的任务是：通过扫描前面已排序的子列表，将位置i处的元素定位到从0到i的子列表之内的正确的位置上。

将arr[i]复制为一个名为target的临时元素。向下扫描列表，比较这个目标值target与arr[i-1]、arr[i-2]的大小，依次类推。这个比较过程在小于或等于目标值的第一个元素(arr[j])处停止，或者在列表开始处停止（j=0）。在arr[i]小于前面任何已排序元素时，后一个条件（j=0）为真，因此，这个元素会占用新排序子列表的第一个位置。在扫描期间，大于目标值target的每个元素都会向右滑动一个位置（arr[j]=arr[j-1]）。一旦确定了正确位置j，目标值target（即原始的arr[i]）就会被复制到这个位置。与选择排序不同的是，插入排序将数据向右滑动，并且不会执行交换

- (NSMutableArray *)insertSortArray:(NSMutableArray *)dataArr
{
    
    for (int i = 0; i < dataArr.count; i++) {
        for (int j = i; j > 0; j--) {
            if ([dataArr[j] intValue] < [dataArr[j - 1] intValue]) {
                [dataArr exchangeObjectAtIndex:j withObjectAtIndex:j-1];
            }
        }
    }
    return dataArr;
    
}
   

3.快速排序

快速排序（Quicksort）是对冒泡排序的一种改进。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。在平均状况下，排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较，但这种状况并不常见。快速排序使用分治法(Divide and conquer)策略来把一个串行(list)分为两个子串行(sub-lists)。

算法步骤：

从数列中挑出一个元素，称为 “基准”(pivot)，重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区(partition)操作。递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递归下去，但是这个算法总会退出，因为在每次的迭代(iteration)中，它至少会把一个元素摆到它最后的位置去。

一趟快速排序的算法

1）设置两个变量i、j，排序开始的时候：i=0，j=N-1；
2）以第一个数组元素作为关键数据，赋值给key，即key=A[0]；
3）从j开始向前搜索，即由后开始向前搜索(j--)，找到第一个小于key的值A[j]，将A[j]和A[i]互换；
4）从i开始向后搜索，即由前开始向后搜索(i++)，找到第一个大于key的A[i]，将A[i]和A[j]互换；
5）重复第3、4步，直到i=j； (3,4步中，没找到符合条件的值，即3中A[j]不小于key,4中A[i]不大于key的时候改变j、i的值，使得j=j-1，i=i+1，直至找到为止。找到符合条件的值，进行交换的时候i， j指针位置不变。另外，i==j这一过程一定正好是i+或j-完成的时候，此时令循环结束）

- (void)quickSortWithArray:(NSMutableArray *)array withLeft:(NSInteger)left andRight:(NSInteger)right{
    if (left >= right) return;
    
    NSInteger i = left;
    NSInteger j = right;
    NSInteger key = [array[left] integerValue];
    
    while (i < j) {
        while (i < j && key <= [array[j] integerValue]) {
            j--;
        }
        array[i] = array[j];
        while (i < j && key >= [array[i] integerValue]) {
            i++;
        }
        array[j] = array[i];
    }
    array[i] = [NSNumber numberWithInteger:key];
    
    [self quickSortWithArray:array withLeft:left andRight:i - 1];
    [self quickSortWithArray:array withLeft:i + 1 andRight:right];
}

以上算法的调用示范

- (void)viewDidLoad {
    [super viewDidLoad];
    NSMutableArray *dataArr = [NSMutableArray arrayWithObjects:@3,@6,@4,@1,@7,@3,@9,@5, nil];
   
    
//    NSMutableArray *bubbleArray = [self bubbleSortArray:dataArr];
//    NSLog(@"冒泡排序 %@ \n",bubbleArray);
//
//    NSMutableArray *insertArray = [self insertSortArray:dataArr];
//    NSLog(@"插入排序 %@ \n",insertArray);
//
    
//   NSMutableArray *selectArray = [self selectSortArray:dataArr];
//    NSLog(@"选择排序 %@ \n",selectArray);
//
    
//    [self quickSortWithArray:dataArr withLeft:0 andRight:dataArr.count -1];
//    NSLog(@"快速排序 %@ \n",dataArr);
  
}