Objective-c各种排序算法
Objective-C排序算法
快排
快速排序是面试中经常会被问的一个排序算法。一般要求手写。
快排是对冒泡排序的一种改进。
平均时间复杂度O（nlogn），最坏时间复杂度O（n*n）
因为二分查找的时间复杂度是o(logn), 每次分成两段，那么分的次数就是logn了，每一次处理需要n次计算，那么时间复杂度就是nlogn了！
最坏是O(n^2). 这种情况就是数组刚好的倒序，然后每次去中间元的时候都是取最大或者最小。
稳定性：不稳定。
+ (void)quickSort:(NSMutableArray *)arr low:(NSInteger)low high:(NSInteger)high {
if (arr.count == 0 || low >= high) {
return;
}
NSInteger i = low, j = high;
NSInteger key = [arr[low] integerValue];
while (i < j && [arr[j] integerValue] >= key) {
j--;
}
arr[i] = arr[j];
while (i < j && [arr[i] integerValue] <= key) {
i++;
}
arr[j] = arr[i];
NSLog(@"一次排序结果：%@", arr);
arr[i] = @(key);
[[self class] quickSort:arr low:low high:i-1];
[[self class] quickSort:arr low:i+1 high:high];
}
堆排序
堆排序是一种选择排序，其时间复杂度为O(nlogn)。
定义：
定义
堆的存储
堆的存储
其基本思想为(大顶堆)：
- 将初始待排序关键字序列(R1,R2....Rn)构建成大顶堆，此堆为初始的无序区；
- 将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,......Rn-1)和新的有序区(Rn),且满足R[1,2...n-1]<=R[n];
- 由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,......Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2....Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。
因此对于堆排序，最重要的两个操作就是构造初始堆和调整堆，其实构造初始堆事实上也是调整堆的过程，只不过构造初始堆是对所有的非叶节点都进行调整。
由于堆也是用数组模拟的，故堆化数组后，第一次将A[0]与A[n - 1]交换，再对A[0…n-2]重新恢复堆。第二次将A[0]与A[n – 2]交换，再对A[0…n - 3]重新恢复堆，重复这样的操作直到A[0]与A[1]交换。由于每次都是将最大的数据并入到后面的有序区间，故操作完成后整个数组就有序了。
已知一棵完全二叉树各节点的编号为0到n，如何得出其第一个非叶子节点的编号
最后一个叶子节点的索引值是n-1，它的父节点索引值是[(n-1)-1]/2 = n/2 -1
/* (最大)堆的向下调整算法
*
* 注：数组实现的堆中，第N个节点的左孩子的索引值是(2N+1)，右孩子的索引是(2N+2)。
* 其中，N为数组下标索引值，如数组中第1个数对应的N为0。
*
* 参数说明：
* a -- 待排序的数组
* start -- 被下调节点的起始位置(一般为0，表示从第1个开始)
* end -- 截至范围(一般为数组中最后一个元素的索引)
*/
- (void)heapAdjust:(NSMutableArray *)marr start:(int)start end:(int)end {
int lchild = 2*start; //i的左孩子节点序号
int rchild = 2*start+1; //i的右孩子节点序号
int max = start; //临时变量
if (start <= end/2) { //如果i是叶节点就不用进行调整
if (lchild <= end && [marr[lchild] integerValue] > [marr[max] integerValue]) {
max = lchild;
}
if (rchild <= end && [marr[rchild] integerValue] > [marr[max] integerValue] ) {
max = rchild;
}
if (max != start) {
[marr exchangeObjectAtIndex:start withObjectAtIndex:max];
// 避免调整之后以max为父节点的子树不是堆
[self heapAdjust:marr start:max end:end];
}
}
}
// 建大根堆
- (void)buildHeap:(NSMutableArray *)marr {
int size = (int)marr.count;
// 最后一个叶子节点的索引值是n-1，它的父节点索引值是[(n-1)-1]/2 = n/2 -1
for (int i = size/2-1; i >= 0; --i) {
[self heapAdjust:marr start:i end:size-1];
}
}
- (void)heapSort:(NSMutableArray *)marr {
[self buildHeap:marr];
NSLog(@"build after: %@", marr);
int len = (int)marr.count-1;
for (int i = len; i >= 0; i--) {
// 交换堆顶和最后一个元素，即每次将剩余元素中的最大者放到最后面
[marr exchangeObjectAtIndex:0 withObjectAtIndex:i];
// 重新调整堆顶节点成为大顶堆
[self heapAdjust:marr start:0 end:i-1];
}
}
int main(int argc, const char * argv[]) {
@autoreleasepool {
NSArray *arr = @[@(12), @(14), @(100), @(29), @(8), @(21), @(15), @(59), @(50), @(99)];
NSMutableArray *marr = [NSMutableArray arrayWithArray:arr];
SGSort *sort = [[SGSort alloc] init];
[sort heapSort:marr];
NSLog(@"heapsort result =%@", marr);
}
return 0;
}
// 输出结果
2017-08-27 19:55:04.657 SuanFaXueXi[3487:106882] build after: (
100,
99,
50,
59,
14,
21,
15,
29,
12,
8
)
2017-08-27 19:55:07.151 SuanFaXueXi[3487:106882] heapsort result =(
8,
12,
14,
15,
21,
29,
50,
59,
99,
100
)
由于每次重新恢复堆的时间复杂度为O(logN)，共N - 1次重新恢复堆操作，再加上前面建立堆时N / 2次向下调整，每次调整时间复杂度也为O(logN)。二次操作时间相加还是O(N * logN)。故堆排序的时间复杂度为O(N * logN)
堆排序适合于数据量非常大的场合（百万数据）。
堆排序不需要大量的递归或者多维的暂存数组。这对于数据量非常巨大的序列是合适的。比如超过数百万条记录，因为快速排序，归并排序都使用递归来设计算法，在数据量非常大的时候，可能会发生堆栈溢出错误。
归并排序
希尔排序
基本思想是：先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录基本有序时再对全体记录进行一次直接插入排序。
计数排序
如果在面试中有面试官要求你写一个O(n)时间复杂度的排序算法，你千万不要立刻说：这不可能！虽然前面基于比较的排序的下限是O(nlogn)。但是确实也有线性时间复杂度的排序，只不过有前提条件，就是待排序的数要满足一定的范围的整数，而且计数排序需要比较多的辅助空间。其基本思想是，用待排序的数作为计数数组的下标，统计每个数字的个数。然后依次输出即可得到有序序列。
今天学习了计数排序，貌似计数排序的复杂度为o(n)。很强大。他的基本思路为：
-
我们希望能线性的时间复杂度排序，如果一个一个比较，显然是不实际的，书上也在决策树模型中论证了，比较排序的情况为nlogn的复杂度。
-
既然不能一个一个比较，我们想到一个办法，就是如果我在排序的时候就知道他的位置，那不就是扫描一遍，把他放入他应该的位置不就可以了嘛。
3.要知道他的位置，我们只需要知道有多少不大于他不就可以了吗？
-
以此为出发点，我们怎么确定不大于他的个数呢？我们先来个约定，如果数组中的元素都比较集中，都在[0, max]范围内。我们开一个max的空间b数组，把b数组下标对应的元素和要排序的A数组下标对应起来。这样不就可以知道不比他大的有多少个了吗？我们只要把比他小的位置元素个数求和，就是不比他大的。例如：A={3,5,7};我们开一个大小为8的数组b，把a[0] = 3 放入b[3]中，使b[3] = 0; 同理 b[5] = 1; b[7] = 2;其他我们都设置为-1，哈哈我们只需要遍历一下b数组，如果他有数据，就来出来，铁定是当前最小的。如果要知道比a[2]小的数字有多少个，值只需要求出b[0] – b[6]的有数据的和就可以了。这个0(n)的速度不是盖得。
-
思路就是这样咯。但是要注意两个数相同的情况A = {1,2,3,3,4}，这种情况就不可以咯，所以还是有点小技巧的。
6.处理小技巧：我们不把A的元素大小与B的下标一一对应，而是在B数组对应处记录该元素大小的个数。这不久解决了吗。哈哈。例如A = {1,2,3,3,4}我们开大小为5的数组b;记录数组A中元素值为0的个数为b[0] = 0, 记录数组A中元素个数为1的b[1] = 1,同理b[2] = 1, b[3] = 2, b[4] = 1;好了，这样我们就知道比A4小的元素个数是多少了：count = b[0] + b[1] + b[2] + b[3] = 4;他就把A[4]的元素放在第4个位置。
桶排序
基数排序
总结
在前面的介绍和分析中我们提到了冒泡排序、选择排序、插入排序三种简单的排序及其变种快速排序、堆排序、希尔排序三种比较高效的排序。后面我们又分析了基于分治递归思想的归并排序还有计数排序、桶排序、基数排序三种线性排序。我们可以知道排序算法要么简单有效，要么是利用简单排序的特点加以改进，要么是以空间换取时间在特定情况下的高效排序。
1. 从平均时间来看，快速排序是效率最高的，但快速排序在最坏情况下的时间性能不如堆排序和归并排序。而后者相比较的结果是，在n较大时归并排序使用时间较少，但使用辅助空间较多。
2. 上面说的简单排序包括除希尔排序之外的所有冒泡排序、插入排序、简单选择排序。其中直接插入排序最简单，但序列基本有序或者n较小时，直接插入排序是好的方法，因此常将它和其他的排序方法，如快速排序、归并排序等结合在一起使用。
3. 基数排序的时间复杂度也可以写成O(d*n)。因此它最使用于n值很大而关键字较小的的序列。若关键字也很大，而序列中大多数记录的最高关键字均不同，则亦可先按最高关键字不同，将序列分成若干小的子序列，而后进行直接插入排序。
4. 从方法的稳定性来比较，基数排序是稳定的内排方法，所有时间复杂度为O(n^2)的简单排序也是稳定的。但是快速排序、堆排序、希尔排序等时间性能较好的排序方法都是不稳定的。稳定性需要根据具体需求选择。
5. 上面的算法实现大多数是使用线性存储结构，像插入排序这种算法用链表实现更好，省去了移动元素的时间。具体的存储结构在具体的实现版本中也是不同的。
