和第一次编程从输出"hello world"开始一样，该篇就从最简单的冒泡排序开始。
1. 冒泡排序
从序列第一个元素开始，依次比较相邻两个元素的大小，如果i比i+1个元素大，就交换他们。我们可以把序列想象成两部分，一部分是左边还未处理的元素，一部分是右边通过冒泡冒出来的元素，举个🌰：
原始序列：3，2，5，1，8
第一趟比较
第一次：[2，3]，5，1，8 |
第二次：2，[3，5]，1，8 |
第三次：2，3，[1，5]，8 |
第四次：2，3，1，[5 , 8] |
结果: 2，3，1，5 | 8 ----- 这一趟比较把最大元素8冒出来
第二趟比较：
第一次：[2，3]，1，5 | 8
第二次：2，[1，3]，5 | 8
第三次：2，1，[3，5] | 8
结果：2，1，3 | 5，8 ----- 这一趟比较把2，3，1，5中最大元素5冒出来
.......
这样，每一趟比较都能把序列中剩余元素中的最大值冒出来。直到序列中全部元素通过比较冒到 | 的右边，整个序列就排序好了。代码如下：
-(void)bubbleSortWithArr:(NSMutableArray *)unSortedArr {
NSLog(@"排序前: %@", unSortedArr);
BOOL didSwap;
for (NSInteger i=unSortedArr.count-1; i>0; i--) {
didSwap = NO;
// 里层for循环用来依次比较相邻两个元素，并将最大元素冒出
for (NSInteger j=0; j<i; j++) {
if ([unSortedArr[j] intValue] > [unSortedArr[j + 1] intValue]) {
NSNumber *temp = unSortedArr[j];
unSortedArr[j] = unSortedArr[j + 1];
unSortedArr[j + 1] = temp;
didSwap = YES;
}
}
if (!didSwap) {
break;
}
}
NSLog(@"排序后: %@", unSortedArr);
}
时间复杂度
最坏时间复杂度O(n²)，最好时间复杂度O(n)
因为有两层循环，所以最坏是O(n²)，我们在循环中加了一个didSwap标志位，如果序列一开始是有序的，内层循环第一趟比较的时候发现没有元素需要交换，也就是两两相邻的元素都是有序的，即整个序列有序，则直接退出即可，所以有序情况下，只走了一次循环，时间复杂度降低为O(n)
2. 选择排序
选择排序是一种相对比较直观的排序，它每次都从未排序的序列中找出最大（小）的元素，放到已经排好序的序列末尾。举个🌰：
这里，|| 左边表示已经排好序的，右边表示未排好序的
原始序列：3，2，5，1，8
第一次，从3，2，5，1，8中拿出最小元素： 1 || 3，2，5，8
第二次，从3，2，5，8中拿出最小元素：1，2 || 3，5，8
.......
直到||右侧未排序的元素全部移到||左侧，整个序列就排好了。
示例代码：
-(void)selectionSortWithArr:(NSMutableArray *)unSortedArr {
NSLog(@"排序前: %@", unSortedArr);
NSInteger len = unSortedArr.count;
NSInteger minIndex;
for (NSInteger i=0; i<len - 1; i++) {
minIndex = i;
// 里层for循环来找到未排序序列中的最小元素
for (NSInteger j=i+1; j<len; j++) {
if ([unSortedArr[j] intValue] < [unSortedArr[minIndex] intValue]) {
minIndex = j;
}
}
if (minIndex != i) {
NSNumber *temp = unSortedArr[i];
unSortedArr[i] = unSortedArr[minIndex];
unSortedArr[minIndex] = temp;
}
}
NSLog(@"排序后: %@", unSortedArr);
}
时间复杂度：
最好时间复杂度和最坏时间复杂度都是O(n²)
不管什么数据进去，都要走两层循环，所以参与排序的数据规模越小越好
3. 插入排序
插入排序和选择排序有点类似，它把序列分成两部分，左边是排好序的元素，右边是未排序的元素。逐次从右侧序列中拿出第一个元素，将该元素和左侧排好序的序列逐个比较，找到合适的位置插入。
举个🌰：
这里，|| 左边表示已经排好序的，右边表示未排好序的
原始序列：3，2，5，1，8
第一次： 3 || 2，5，1，8
第二次：2，3 || 5，1，8
第三次：2，3，5 || 1，8
第四次：1，2，3，5 || 8
插入排序有个硬伤就是每次从右侧拿出元素插入到左侧排好序的序列中时，都要将插入位置后面的元素后移，给新插入的元素移出一个位置。
实例代码如下：
-(void)insertionSortWithArr:(NSMutableArray *)unSortedArr {
NSLog(@"排序前: %@", unSortedArr);
NSInteger len = unSortedArr.count;
NSInteger preIndex;
for (NSInteger i=1; i<len; i++) {
// 里层循环用来找到合适的插入位置，并将插入位置及后面的元素后移
NSInteger current = [unSortedArr[i] intValue];
preIndex = i - 1;
while (preIndex >= 0 && [unSortedArr[preIndex] intValue] > current) {
unSortedArr[preIndex + 1] = unSortedArr[preIndex];
preIndex --;
}
unSortedArr[preIndex + 1] = @(current);
}
NSLog(@"排序后: %@", unSortedArr);
}
时间复杂度:
最坏时间复杂度O(n²)，最好时间复杂度O(n)
当整个序列是排好序的时候，里层的while循环直接不需要执行，也就是所有的元素都不需要后移，其实只执行了外层的for循环而已。
4. 归并排序
归并排序是分治法应用的经典案例，通俗说就是大事化小，小事化了。具体到排序上来说就是将无序的数组一直划分，当数组中有只有一个元素的时候，它就是有序的了。然后再把有序的子数组们逐个合并成有序数组。下面用图示来展示下归并法的思想：
归并分治法
示例代码如下:
@interface MergeSort : NSObject
+(void)sortWithArr:(NSMutableArray *)unSortedArr;
@end
@implementation MergeSort
// 归并排序
+(void)sortWithArr:(NSMutableArray *)unSortedArr {
if (unSortedArr == nil || unSortedArr.count < 2) {
return;
}
NSLog(@"排序前： %@", unSortedArr);
[MergeSort mergeSortWithArr:unSortedArr l:0 r:unSortedArr.count - 1];
NSLog(@"排序后： %@", unSortedArr);
}
+(void)mergeSortWithArr:(NSMutableArray *)arr l:(NSInteger)l r:(NSInteger)r {
// 直到分割到单个元素为止
if (l == r) {
return;
}
// 将数组一半一半的分割
NSInteger mid = (l + r) / 2;
[MergeSort mergeSortWithArr:arr l:l r:mid];
[MergeSort mergeSortWithArr:arr l:mid + 1 r:r];
// 分割完之后，合并两个数组（这里其实是通过左中右三个索引划分成了两个数组）
[MergeSort mergeWithArr:arr l:l mid:mid r:r];
}
// 合并两个有序数组
+(void)mergeWithArr:(NSMutableArray *)arr l:(NSInteger)l mid:(NSInteger)mid r:(NSInteger)r {
// 如果左数组的最后一个元素小于等于右数组的第一个元素。说明元素组中[l, r]范围内的元素都是有序的。
if ([arr[mid] intValue] <= [arr[mid + 1] intValue]) {
return;
}
NSMutableArray *help = [NSMutableArray array];
NSInteger p1 = l;
NSInteger p2 = mid + 1;
// 依次比较从最左侧索引和从中间索引开始的两个元素，并把最小的放入结果数组中
while (p1 <= mid && p2 <= r) {
NSNumber *minValue = [arr[p1] intValue] <= [arr[p2] intValue] ? arr[p1 ++] : arr[p2++];
[help addObject:minValue];
}
// 将剩余的数加入到数组中
while (p1 <= mid) {
[help addObject:arr[p1 ++]];
}
while (p2 <= r) {
[help addObject:arr[p2 ++]];
}
// 将临时数组中的内容覆盖掉原数组中内容
for (int i=0; i<help.count; i++) {
arr[l + i] = help[i];
}
}
@end
我们可以在
// 分割完之后，合并两个数组（这里其实是通过左中右三个索引划分成了两个数组）
[MergeSort mergeWithArr:arr l:l mid:mid r:r];
这句前面打印下，看看程序具体是怎么把最终划分的单个元素合并并排序的：
NSLog(@"[%lu,%lu]",l, r);
// 分割完之后，合并两个数组（这里其实是通过左中右三个索引划分成了两个数组）
[MergeSort mergeWithArr:arr l:l mid:mid r:r];
打印结果如下:
2019-08-29 10:10:36.795659+0800 Algorithm[1031:614926] [0,1]
2019-08-29 10:10:36.795751+0800 Algorithm[1031:614926] [0,2]
2019-08-29 10:10:36.795779+0800 Algorithm[1031:614926] [3,4]
2019-08-29 10:10:36.795802+0800 Algorithm[1031:614926] [0,4]
2019-08-29 10:10:36.795827+0800 Algorithm[1031:614926] [5,6]
2019-08-29 10:10:36.795850+0800 Algorithm[1031:614926] [7,8]
2019-08-29 10:10:36.795873+0800 Algorithm[1031:614926] [5,8]
2019-08-29 10:10:36.795896+0800 Algorithm[1031:614926] [0,8]
这里打印的结果和我们图示中的过程有点不一样。这是因为程序中是按步骤来的，它是先合并了左边的子数组，然后合并右边的子数组，最后再把左数组和右数组合并（这也是递归划分数组后再合并时执行的顺序）。而图示中我为了直观演示，左数组和右数组中的元素合并是同时展示的。这点大家不要疑惑。
时间复杂度:
最坏时间复杂度O(nlog₂n)，最好时间复杂度O(n)
最好时间复杂度是因为我们在合并子数组的时候做了判断，如果之前已经是有序的，就不需要排序合并了。所以如果整个序列本来就是有序的，时间复杂度就只是划分数组的O(n)而已了。归并排序的空间复杂度是O(n)，因为我们在合并排序的时候引入了新的数组。
5. 希尔排序
希尔排序是对插入排序的优化，插入排序在小规模数据或者有序数据排序的时候效率比较高，如果是无序的大规模数据，效率就会下降；
希尔排序的思想就是将大的序列划分成小序列，然后对小序列进行插入排序，这时候插入排序的效率就会很高。下面用图示来展示下希尔排序的过程：
希尔排序
简单的代码实现：
+(void)shellSortWithArr:(NSMutableArray *)unSortedArr {
NSLog(@"排序前: %@", unSortedArr);
NSInteger len = unSortedArr.count;
// 进行分组，最开始的增量(gap)为数组长度的一半
for (NSInteger gap = len/2; gap > 0; gap /= 2) {
// 对各个分组进行插入排序
for (NSInteger i=gap; i<len; i+=gap) {
// 将a[i]插入到所在分组正确的位置上
[ShellSort insertItemAtIndex:i withGap:gap intoArr:unSortedArr];
}
}
NSLog(@"排序后: %@", unSortedArr);
}
+(void)insertItemAtIndex:(NSInteger)i withGap:(NSInteger)gap intoArr:(NSMutableArray *)arr {
NSInteger inserted = [arr[i] integerValue];
NSInteger j;
// 插入的时候按组进行插入（组内元素两两相隔gap）
for (j = i-gap; j >= 0 && inserted < [arr[j] integerValue]; j -= gap) {
arr[j + gap] = arr[j];
}
arr[j + gap] = @(inserted);
}
时间复杂度
希尔排序的时间复杂度和增量序列有关，比如上面我们用的增量序列，也就是gap序列是通过减半得到的，{1, 2, 5}；这是比较简单的增量序列，它的最坏时间复杂度是O(n²)，最好是O(n)，还有一些效率更高的增量序列，他们的复杂度比较难计算，了解一下就可以了。
6. 桶排序
桶排序是将序列中的每个元素按照一定的计算规则分别放入固定数量的桶中，然后再对桶中的元素进行排序，最后将所有桶中的元素合并，下面用图示来展示下桶排序的操作流程：
桶排序
示例代码如下：
+(void)sortWithArr:(NSMutableArray *)unSortedArr {
NSLog(@"排序前: %@", unSortedArr);
[BucketSort bucketSortWithArr:unSortedArr bucketSize:5];
NSLog(@"排序后: %@", unSortedArr);
}
+(void)bucketSortWithArr:(NSMutableArray *)arr bucketSize:(NSInteger)size {
if (arr.count == 0) {
return;
}
// 1.找到序列中的最大最小值
NSInteger minValue = [arr[0] integerValue];
NSInteger maxValue = [arr[0] integerValue];
for (NSNumber *item in arr) {
if ([item integerValue] < minValue) {
minValue = [item integerValue];
} else if ([item integerValue] > maxValue) {
maxValue = [item integerValue];
}
}
// 根据计算结果得到一定数量的桶
NSInteger bucketCount = floor((maxValue - minValue)/size) + 1;
NSMutableArray *buckets = [NSMutableArray arrayWithCapacity:bucketCount];
for (NSInteger i=0; i<bucketCount; i++) {
NSMutableArray *arrInBuckets = [NSMutableArray array];
[buckets addObject:arrInBuckets];
}
// 将元素按照计算结果放到对应的桶中
for (NSNumber *item in arr) {
NSInteger value = [item integerValue];
NSInteger index = floor((value - minValue)/size);
[BucketSort addValue:value toBuckets:buckets withIndex:index];
}
[arr removeAllObjects];
for (NSMutableArray *arrInBuckets in buckets) {
if (arrInBuckets == nil || arrInBuckets.count <=0) {
continue;
}
[arr addObjectsFromArray:arrInBuckets];
}
}
// 将元素放入对应的桶中
+(void)addValue:(NSInteger)value toBuckets:(NSMutableArray *)buckets withIndex:(NSInteger)index {
NSMutableArray *arrInBuckets = buckets[index];
[arrInBuckets addObject:@(value)];
if (arrInBuckets.count > 1) {
// 通过插入排序，将元素插入桶中
NSInteger insertIndex = 0;
for (NSInteger i=arrInBuckets.count-2; i>=0; i--) {
NSInteger currentValue = [arrInBuckets[i] integerValue];
if (currentValue > value) {
arrInBuckets[i + 1] = @(currentValue);
} else {
insertIndex = i + 1;
break;
}
}
arrInBuckets[insertIndex] = @(value);
}
}
这里为了方便，我就直接在把元素放入桶中的时候就使用插入排序的方式插入。在某些情况下，这里是需要进行改进的。比如有一个序列: 1,2,6,3,5,9,10,4,8,12,11,200。像这种序列，你会发现第一个桶中的元素数量比较多，像这种情况桶排序的效率就会降低。怎么解决呢？只有将桶中的元素再重新分桶，所以我们上面的代码就要改进了，先把所有元素添加进去，然后根据数据规模来重新分桶。最终分桶完毕后再进行排序并合并。
时间复杂度
极限情况下，一个桶中只有一个元素，时间复杂度最好，O(n + B)，这里n是待排序元素个数，B是桶数。最坏的情况，如果某些桶中的数据量过大，时间复杂度就会降为 O(nlog₂n)，这时候可以采用将大桶再分桶的方式优化。
7. 计数排序
计数排序是通过将序列中的值转换为另外开辟空间的数组的下标索引，并记录他们在原始序列出现的次数来进行排序的。
计数排序
示例代码如下：
+(void)sortWithArr:(NSMutableArray *)unSortedArr {
NSLog(@"排序前: %@", unSortedArr);
if (unSortedArr.count <= 0) {
return;
}
// 1.得到最大值和最小值，并计算bucket的大小
NSInteger minValue = [[CountSort getMinAndMaxValueInArr:unSortedArr][0] integerValue];
NSInteger maxValue = [[CountSort getMinAndMaxValueInArr:unSortedArr][1] integerValue];
NSInteger bucketSize = maxValue - minValue + 1;
// 2. 初始化bucket，每项的初始次数都是0
NSMutableArray *bucket = [NSMutableArray arrayWithCapacity:bucketSize];
for (NSInteger j = 0; j<bucketSize; j++) {
[bucket addObject:@(0)];
}
// 3.遍历原始序列，按照 索引=当前值-最小值 存放每个值出现的次数
for (NSNumber *item in unSortedArr) {
NSInteger value = [item integerValue];
NSInteger count = [bucket[value - minValue] integerValue];
bucket[value - minValue] = @(count + 1);
}
NSInteger sortedIndex = 0;
for (NSInteger i=0; i<bucketSize; i++) {
// 当前索引中存的次数是几就遍历几次
while ([bucket[i] integerValue] > 0) {
// 当前索引 + 最小值 = 当前索引对应的原始序列中的值
unSortedArr[sortedIndex ++] = @(i + minValue);
bucket[i] = @([bucket[i] integerValue] - 1);
}
}
NSLog(@"排序后: %@", unSortedArr);
}
// 获取最大最小值
+(NSArray *)getMinAndMaxValueInArr:(NSMutableArray *)arr {
NSInteger minValue = [arr[0] integerValue];
NSInteger maxValue = [arr[0] integerValue];
for (NSNumber *item in arr) {
if ([item integerValue] < minValue) {
minValue = [item integerValue];
}
if ([item integerValue] > maxValue) {
maxValue = [item integerValue];
}
}
return @[@(minValue), @(maxValue)];
}
时间复杂度
计数排序的时间复杂度是O(n + k)，k是整数的范围。同时计数排序开辟了新的数组，所以空间复杂度也是O(n + k);
8. 堆排序
这里的堆排序是利用大小堆来完成的，开始之前，先来了解下什么是大小堆，以及怎么构建大小堆：
大小堆
大顶堆：父节点键值永远大于左右孩子节点的键值
小顶堆：父节点 键值永远小于左右孩子节点的键值
从数组构建大小顶堆也很简单，以构建大顶堆为例，依次从数组中顺序拿出一个元素作为当前节点，如果当前节点比父元素小，则不需要变动；如果比父元素大，则交换它和父元素的值，然后把父元素设为当前节点再重新比较交换。
代码如下：
// 根据当前元素的索引，将当前元素及之前的元素重新构建成小顶堆
+(void)buildMinHeapWithArr:(NSMutableArray *)arr withCurrentIndex:(NSInteger)index {
if (index <= 0) {
return;
}
NSInteger parentIndex;
if (index % 2 == 0) { // 当前节点是右孩子
parentIndex = floor((index - 2)/2);
} else { // 当前节点是左孩子
parentIndex = floor((index - 1)/2);
}
if ([arr[parentIndex] integerValue] > [arr[index] integerValue]) {
[HeapSort swapItemAtIndex:parentIndex andIndex:index inArr:arr];
[HeapSort buildMinHeapWithArr:arr withCurrentIndex:parentIndex];
}
}
// 根据当前元素的索引，将当前元素及之前的元素重新构建成大顶堆
+(void)buildMaxHeapWithArr:(NSMutableArray *)arr withCurrentIndex:(NSInteger)index {
if (index <= 0) {
return;
}
NSInteger parentIndex;
if (index % 2 == 0) { // 当前节点是右孩子
parentIndex = floor((index - 2)/2);
} else { // 当前节点是左孩子
parentIndex = floor((index - 1)/2);
}
if ([arr[parentIndex] integerValue] < [arr[index] integerValue]) {
[HeapSort swapItemAtIndex:parentIndex andIndex:index inArr:arr];
// 如果当前节点比父节点大，就交换他们的值，并把父节点当作当前节点，继续向上比较
[HeapSort buildMaxHeapWithArr:arr withCurrentIndex:parentIndex];
}
}
+(void)swapItemAtIndex:(NSInteger)indexa andIndex:(NSInteger)indexb inArr:(NSMutableArray *)arr {
NSNumber *temp = arr[indexa];
arr[indexa] = arr[indexb];
arr[indexb] = temp;
}
// 创建一个大顶堆和小顶堆
for (NSInteger i=0; i<unSortedArr.count; i++) {
[HeapSort buildMinHeapWithArr:unSortedArr withCurrentIndex:i];
[HeapSort buildMaxHeapWithArr:unSortedArr withCurrentIndex:i];
}
堆排序：
每次把堆顶的元素和堆中最后元素交换，交换后把堆中最后元素隔离在堆外(相当于从堆中移除)，然后把堆重新调整为大顶堆或者小顶堆；重复上面的操作，直到最后堆中只有一个元素为止，这样序列就变得有序了。
图示如下：
堆排序
全部示例代码如下：
+(void)sortWithArr:(NSMutableArray *)unSortedArr {
NSLog(@"排序前: %@", unSortedArr);
// 创建一个大顶堆或者小顶堆，这里我们创建一个小顶堆
for (NSInteger i=0; i<unSortedArr.count; i++) {
[HeapSort buildMinHeapWithArr:unSortedArr withCurrentIndex:i];
}
// 每次将小顶堆的根节点和小顶堆最后一个节点交换。交换后把小顶堆最后一个元素隔离到小顶堆之外
// 这里通过len长度来控制小顶堆的范围。交换后肯定不符合小顶堆的特质了，所以需要调整修复小顶堆
NSInteger len = unSortedArr.count;
while (len > 1) {
[HeapSort swapItemAtIndex:0 andIndex:len-1 inArr:unSortedArr];
len--;
// 修复小顶堆
[HeapSort heapFixUpWithArr:unSortedArr withCurrentIndex:0 withLen:len];
}
NSLog(@"排序后: %@", unSortedArr);
}
+(void)heapFixUpWithArr:(NSMutableArray *)arr
withCurrentIndex:(NSInteger)currentIndex
withLen:(NSInteger)len {
NSInteger left = currentIndex * 2 + 1;
NSInteger right = currentIndex * 2 + 2;
NSInteger minIndex = currentIndex;
// 在左右节点中找到最小的一个
if (left < len && right < len) {
if ([arr[left] integerValue] < [arr[right] integerValue]) {
minIndex = left;
} else {
minIndex = right;
}
} else if (left < len) {
minIndex = left;
} else if (right < len) {
minIndex = right;
}
// 找到最小的节点后，如果最小节点比当前节点小，交换最小节点和当前节点的值，然后把最小节点作为当前节点，继续往下调整
if (minIndex != currentIndex &&
[arr[currentIndex] integerValue] > [arr[minIndex] integerValue]) {
[HeapSort swapItemAtIndex:minIndex andIndex:currentIndex inArr:arr];
[HeapSort heapFixUpWithArr:arr withCurrentIndex:minIndex withLen:len];
}
}
// 根据当前元素的索引，将当前元素及之前的元素重新构建成小顶堆
+(void)buildMinHeapWithArr:(NSMutableArray *)arr withCurrentIndex:(NSInteger)index {
if (index <= 0) {
return;
}
NSInteger parentIndex;
if (index % 2 == 0) { // 当前节点是右孩子
parentIndex = floor((index - 2)/2);
} else { // 当前节点是左孩子
parentIndex = floor((index - 1)/2);
}
if ([arr[parentIndex] integerValue] > [arr[index] integerValue]) {
[HeapSort swapItemAtIndex:parentIndex andIndex:index inArr:arr];
[HeapSort buildMinHeapWithArr:arr withCurrentIndex:parentIndex];
}
}
// 根据当前元素的索引，将当前元素及之前的元素重新构建成大顶堆
+(void)buildMaxHeapWithArr:(NSMutableArray *)arr withCurrentIndex:(NSInteger)index {
if (index <= 0) {
return;
}
NSInteger parentIndex;
if (index % 2 == 0) { // 当前节点是右孩子
parentIndex = floor((index - 2)/2);
} else { // 当前节点是左孩子
parentIndex = floor((index - 1)/2);
}
if ([arr[parentIndex] integerValue] < [arr[index] integerValue]) {
[HeapSort swapItemAtIndex:parentIndex andIndex:index inArr:arr];
// 如果当前节点比父节点大，就交换他们的值，并把父节点当作当前节点，继续向上比较
[HeapSort buildMaxHeapWithArr:arr withCurrentIndex:parentIndex];
}
}
+(void)swapItemAtIndex:(NSInteger)indexa andIndex:(NSInteger)indexb inArr:(NSMutableArray *)arr {
NSNumber *temp = arr[indexa];
arr[indexa] = arr[indexb];
arr[indexb] = temp;
}
时间复杂度:
堆排序的时间复杂度是O(nlog₂n)
9. 快速排序
快速排序也算是一种分治法的应用，通过一趟排序将数组分成两部分，一部分都比另一部分小。然后再对这两个小数组重新排序再分割，直到最后分割成单个元素为止，即排序完成。图示如下：
快速排序
示例代码如下：
+(void)sortWithArr:(NSMutableArray *)unSortArr {
NSLog(@"排序前: %@", unSortArr);
NSInteger right = unSortArr.count - 1;
[QuickSort sortArr:unSortArr withLeft:0 right:right];
NSLog(@"排序后: %@", unSortArr);
}
+(void)sortArr:(NSMutableArray *)arr withLeft:(NSInteger)left right:(NSInteger)right {
// 如果左边索引大于等于右边的索引就代表已经整理完成一个组了
if (left > right) {
return;
}
NSInteger i = left;
NSInteger j = right;
NSInteger key = [arr[left] integerValue];
// 在当前组中遍历一遍
while (i < j) {
// 先从小数组的右边往左边找，找到第一个比key小的值
while (i < j && key <= [arr[j] integerValue]) {
// 向前寻找
j --;
}
// 把这个比key小的数和key交换，现在key的索引是i
[QuickSort swapItemAtIndex:i withIndex:j inArr:arr];
// 再从左往右找，找到第一个比key大的值
while (i < j && key >= [arr[i] integerValue]) {
i ++;
}
// 把这个比key大的值和key交换，现在key的索引是j;
[QuickSort swapItemAtIndex:j withIndex:i inArr:arr];
}
// 递归： 遍历左边的小数组
[QuickSort sortArr:arr withLeft:left right:i - 1];
// 递归： 遍历右边的小数组
[QuickSort sortArr:arr withLeft:i + 1 right:right];
}
+(void)swapItemAtIndex:(NSInteger)indexa withIndex:(NSInteger)indexB inArr:(NSMutableArray *)arr {
NSNumber *temp = arr[indexa];
arr[indexa] = arr[indexB];
arr[indexB] = temp;
}
时间复杂度：
如果序列本身是有序的，快速排序效率就会降为O(n²)，快排的最好时间复杂度是O(nlog₂n);
10. 基数排序
如果要对手机号这样类似的大量数据做排序该选择哪个算法呢？经过上面的学习，我们知道比较快的有归并、快速，计数和桶排更快一些。这里假如你决定使用桶排的话，一定是个糟糕的选择，哪得用多少个桶啊，吓死人，桶排表示干不了。基数排序表示是时候让我出场了。
基数排序是非比较型排序算法，它的发明可以追溯到1887年赫尔曼·何乐礼在打孔卡片制表机(Tabulation Machine)上的贡献。它是这样实现的：将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。这里，跟桶排序相似，我们先固定10个桶(因为每一位上只有0~9 10个数字)，比如有下面一个数组：
基数排序
这里要注意，如果要取的位上没有，则按0算，比如2没有十位，百位，则都按0算。
具体代码实现：
+(void)sortWithArr:(NSMutableArray *)unSortedArr {
NSLog(@"排序前:%@", unSortedArr);
NSInteger maxDigit = [RadixSort maxDigitInArr:unSortedArr];
[RadixSort sortWithArr:unSortedArr withMaxDigit:maxDigit];
NSLog(@"排序后:%@", unSortedArr);
}
+(void)sortWithArr:(NSMutableArray *)arr withMaxDigit:(NSInteger)maxDigit {
NSInteger bucketSize = 10; // 10个桶
NSMutableArray<NSMutableArray *> *allBuckets = [NSMutableArray array];
for (NSInteger i=1; i <= maxDigit; i++) { // 循环遍历比较每个位数
// 清空桶
[allBuckets removeAllObjects];
for (NSInteger i=0; i<bucketSize; i++) {
[allBuckets addObject:[NSMutableArray array]];
}
// 1234
// 第一位上的数字 = 1234%10 = 4;
// 第二位上的数字 = 1234%100 = 34/10 = 3;
// 第三位上的数字 = 1234%1000 = 234/100 = 2；
// 公式为 (value % pow(10,i)) / pow(10, i-1);
// 遍历每一位上的数字，并放入对应的桶中
for (NSInteger j=0; j<arr.count; j++) {
NSInteger numberInThisDigit = [arr[j] integerValue] % ((NSInteger)pow(10, i));
if (i > 1) {
numberInThisDigit = numberInThisDigit / pow(10, i-1);
}
[allBuckets[numberInThisDigit] addObject:arr[j]];
}
// 将桶中数据按顺序拿出
[arr removeAllObjects];
for (NSInteger m=0; m<bucketSize; m++) {
if (allBuckets[m].count > 0) {
[arr addObjectsFromArray:allBuckets[m]];
}
}
}
}
// 获取数组中最大数的位数
+(NSInteger)maxDigitInArr:(NSMutableArray *)arr {
NSInteger maxValue = [RadixSort maxValueInArr:arr];
return [RadixSort lengthOfNum:maxValue];
}
// 获取最大数的长度
+(NSInteger)lengthOfNum:(NSInteger)number {
if (number == 0) {
return 1;
}
NSInteger len = 0;
for (NSInteger i = number; i != 0; i /= 10) {
len ++;
}
return len;
}
// 获取最大数
+(NSInteger)maxValueInArr:(NSMutableArray *)arr {
NSInteger maxValue = [arr[0] integerValue];
for (NSNumber *item in arr) {
if ([item integerValue] > maxValue) {
maxValue = [item integerValue];
}
}
return maxValue;
}
时间复杂度
桶排序的时间复杂度是O(n + B)，n是待排序元素个数，B是桶数，但是基数排序是基于多趟桶排序实现的，所以时间复杂度是O(P(n + B))，P是桶排序的趟数。
经过上面的学习比较，各个算法的时间复杂度总结如下：
算法时间复杂度.png
