排序算法可以分为内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。
常见的内部排序算法有：冒泡排序、快速排序、插入排序、希尔排序、选择排序、堆排序、归并排序、基数排序等。
算法一：冒泡排序
冒泡排序.gif
算法步骤：
1.比较相邻的元素。如果第一个比第二个大，就交换他们两个
2.对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数
3.针对所有的元素重复以上的步骤，除了最后一个
4.持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较
//冒泡排序
-(void)bubbleSort:(NSMutableArray *)mtArr
{
if (mtArr.count == 0 || mtArr == nil) {
return;
}
for (int i = 0; i < mtArr.count; i ++) {
for (int j = 0; j < mtArr.count; j ++) {
if ([mtArr[i] compare:mtArr[j]] == NSOrderedAscending )
{
[mtArr exchangeObjectAtIndex:i withObjectAtIndex:j];
}
}
}
}
算法二：快速排序
快速排序.gif
算法步骤：
1.从数列中挑出一个元素，称为 “基准”（pivot）。
2.重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
3.递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
4.递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递归下去，但是这个算法总会退出，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。
//快速排序
-(void)quickSort:(NSMutableArray *)mtArr withLeftIndex:(int)leftIndex andRightIndex:(int)rightIndex
{
if (leftIndex >= rightIndex ) {
return;
}
int i = leftIndex;
int j = rightIndex;
int number = [mtArr[i] intValue];
while (i < j) {
while (i < j && ([mtArr[j] intValue] >= number)){
j --;
}
[mtArr replaceObjectAtIndex:i withObject:mtArr[j]];
while (i < j && ([mtArr[i] intValue] <= number)) {
i ++;
}
[mtArr replaceObjectAtIndex:j withObject:mtArr[i]];
}
mtArr[i] = @(number);
[self quickSort:mtArr withLeftIndex:leftIndex andRightIndex:i -1];
[self quickSort:mtArr withLeftIndex:i + 1 andRightIndex:rightIndex];
}
详细介绍：
算法三：插入排序
插入排序.gif
算法步骤：
1.将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列
2.从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面）
//插入排序
-(void)insertSort:(NSMutableArray *)mtArr
{
if (mtArr == nil || mtArr.count == 0) {
return;
}
for (int i = 0; i < mtArr.count; i ++) {
NSNumber * number = mtArr[i];
int j = i -1;
while (j >= 0 && [mtArr[j] compare:number] == NSOrderedDescending) {
[mtArr replaceObjectAtIndex:j + 1 withObject:mtArr[j]];
j --;
}
[mtArr replaceObjectAtIndex:j + 1 withObject:number];
}
}
算法四：希尔排序
希尔排序.gif
算法步骤：
1.选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1
2.按增量序列个数k，对序列进行k 趟排序
3.每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度
//希尔排序
-(void)shellSort:(NSMutableArray *)mtArr
{
NSInteger bs = mtArr.count/2 ;
while (bs > 0) {
for (NSInteger i = bs; i < mtArr.count; i ++) {
NSInteger temp = [mtArr[i] integerValue];
NSInteger j = i;
while (j >= bs && temp < [mtArr[j - bs] integerValue]) {
[mtArr replaceObjectAtIndex:j withObject:mtArr[j - bs]];
j -= bs;
}
[mtArr replaceObjectAtIndex:j withObject:[NSNumber numberWithInteger:temp]];
}
bs = bs/2;
}
}
算法五：选择排序
选择排序.gif
算法步骤：
1.首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
2.再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾
3.重复第二步，直到所有元素均排序完毕
//选择排序
-(void)selectionSort:(NSMutableArray *)mtArr
{
if (mtArr == nil || mtArr.count == 0) {
return;
}
int minIndex; //最小值索引
for (int i = 0; i < mtArr.count; i ++) {
minIndex = i;
for (int j = i +1; j < mtArr.count; j ++) {
if (mtArr[minIndex] > mtArr[j]) {
minIndex = j;
}
}
[mtArr exchangeObjectAtIndex:i withObjectAtIndex:minIndex];
}
}
算法六：堆排序
堆排序.gif
堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
堆排序的平均时间复杂度为Ο(nlogn) 。
算法步骤：
1.创建一个堆H[0..n-1]
2.把堆首（最大值）和堆尾互换
3.把堆的尺寸缩小1，并调用shift_down(0),目的是把新的数组顶端数据调整到相应位置
4.重复步骤2，直到堆的尺寸为1
算法七：归并排序
归并排序.gif
归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
算法步骤：
1.申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
2.设定两个指针，最初位置分别为两个已经排序序列的起始位置
3.比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
4.重复步骤3直到某一指针达到序列尾
5.将另一序列剩下的所有元素直接复制到合并序列尾
算法八：基数排序
总结：
各种排序的时间复杂度、空间复杂度、稳定性如下图：
关于时间复杂度：
1.平方阶(O(n2))排序：各类简单排序:直接插入、直接选择和冒泡排序
2.线性对数阶(O(nlog2n))排序：快速排序、堆排序和归并排序。
O(n1+§))排序：§是介于0和1之间的常数
3.线性阶(O(n))排序：基数排序，此外还有桶、箱排序
关于稳定性：
1.稳定的排序算法：冒泡排序、插入排序、归并排序和基数排序
2.不是稳定的排序算法：选择排序、快速排序、希尔排序、堆排序
参考:
http://blog.csdn.net/hguisu/article/details/7776068
http://www.jianshu.com/p/481c26283d33
网友评论