点击蓝色“
五分钟学算法
”关注我哟
加个“
星标
”，一起学算法
作者 | Lefex
来源 | 超越技术
整理 | 程序员小吴
冒泡排序是通过比较两个相邻元素的大小实现排序，如果前一个元素大于后一个元素，就交换这两个元素。这样就会让每一趟冒泡都能找到最大一个元素并放到最后。
以 [ 8, 1, 4, 6, 2, 3, 5, 7 ] 为例，对它进行冒泡排序：
代码实现：
+ (NSArray *)bubbleSort:(NSArray *)unsortDatas {
NSMutableArray *unSortArray = [unsortDatas mutableCopy];
for (int i = 0; i -1 ; i++) {
BOOL isChange = NO;
for (int j = 0; j 1 - i; j++) {
if ([unSortArray[j] integerValue] > [unSortArray[j+1] integerValue]) {
NSNumber *data = unSortArray[j+1];
unSortArray[j+1] = unSortArray[j];
unSortArray[j] = data;
isChange = YES;
}
}
if (!isChange) {
break;
}
}
return [unSortArray copy];
}
特点
稳定性
：它是指对同样的数据进行排序，会不会改变它的相对位置。比如 [ 1, 3,
2
, 4,
2
] 经过排序后，两个相同的元素 2 位置会不会被交换。冒泡排序是比较相邻两个元素的大小，显然不会破坏稳定性。
空间复杂度
：由于整个排序过程是在原数据上进行操作，故为 O(1);
时间复杂度
：由于嵌套了 2 层循环，故为 O(n*n);
选择排序的思想是，依次从「无序列表」中找到一个最小的元素放到「有序列表」的最后面。以 arr = [ 8, 1, 4, 6, 2, 3, 5, 4 ] 为例，排序开始时把 arr 分为有序列表 A = [ ], 无序列表 B = [ 8, 1, 4, 6, 2, 3, 5, 4 ]，依次从 B 中找出最小的元素放到 A 的最后面。这种排序也是逻辑上的分组，实际上不会创建 A 和 B，只是用下标来标记 A 和 B。
以 arr = [ 8, 1, 4, 6, 2, 3, 5, 4 ] 为例，第一次找到最小元素 1 与 8 进行交换，这时有列表 A = [1], 无序列表 B = [8, 4, 6, 2, 3, 5, 4]；第二次从 B 中找到最小元素 2，与 B 中的第一个元素进行交换，交换后 A = [1，2]，B = [4, 6, 8, 3, 5, 4]；就这样不断缩短 B，扩大 A，最终达到有序。
代码实现：
+ (NSArray
*)seelectSort:(NSArray *)unsortDatas {
NSMutableArray *unSortArray = [unsortDatas mutableCopy];
for (int i = 0; i int mindex = i;
for (int j = i; j
if ([unSortArray[j] integerValue] mindex = j;
}
}
NSNumber *data = unSortArray[i];
unSortArray[i] = unSortArray[mindex];
unSortArray[mindex] = data;
}
return [unSortArray copy];
}
特点
稳定性
：排序过程中元素是按顺序进行遍历，相同元素相对位置不会发生变化，故稳定。
空间复杂度
：在原序列进行操作，故为 O( 1 );
时间复杂度
：需要 2 次循环遍历，故为 O( n * n );
在整个排序过程如图所示，以 arr = [ 8, 1, 4, 6, 2, 3, 5, 7] 为例，它会把 arr 分成两组 A = [ 8 ] 和 B = [ 1, 4, 6, 2, 3, 5, 7] ，逐步遍历 B 中元素插入到 A 中，最终构成一个有序序列：
代码实现：
+ (NSArray *)insertionSort:(NSArray *)unsortDatas {
NSMutableArray *unSortArray = [unsortDatas mutableCopy];
int preindx = 0;
NSNumber *current;
for (int i = 1; i preindx = i - 1;
current = unSortArray[i];
while (preindx >= 0 && [current integerValue]
unSortArray[preindx+1] = unSortArray[preindx];
preindx -= 1;
}
unSortArray[preindx+1] = current;
}
return [unSortArray copy];
}
特点
稳定性
：它是从后往前遍历已排序好的序列，相同元素不会改变位置，故为稳定排序；
空间复杂度
：它是在原序列进行排序，故为 O ( 1 );
时间复杂度
：排序的过程中，首先要遍历所有的元素，然后在已排序序列中找到合适的位置并插入。共需要 2 层循环，故为 O ( n * n );
希尔排序，它是由 D.L.Shell 于1959 年提出而得名。根据它的名字很难想象算法的核心思想。[ 所以只能死记硬背了，面试官问：希尔排序的思想是什么？]。它的核心思想是把一个序列分组，对分组后的内容进行
插入排序
，这里的分组只是逻辑上的分组，不会重新开辟存储空间。它其实是插入排序的优化版，插入排序对基本有序的序列性能好，希尔排序利用这一特性把原序列分组，对每个分组进行排序，逐步完成排序。
以 arr = [ 8, 1, 4, 6, 2, 3, 5, 7 ] 为例，通过 floor(8/2) 来分为 4 组，8 表示数组中元素的个数。分完组后，对组内元素进行插入排序。
「 第1次分组 」
「 利用第 1 次分组结果进行第 2 次分组 」
「 利用第 2 次分组结果进行最后一次分组
」
代码实现：
+ (NSArray *)shellSort:(NSArray *)unsortDatas {
NSMutableArray *unSortArray = [unsortDatas mutableCopy];
int len = (int)unSortArray.count;
for (int gap = floor(len / 2); gap > 0; gap = floor(gap/2)) {
for (int i = gap; i
for (int j = i - gap; j >= 0 && [unSortArray[j] integerValue] > [unSortArray[j+gap] integerValue]; j-=gap) {
NSNumber *temp = unSortArray[j];
unSortArray[j] = unSortArray[gap+j];
unSortArray[gap+j] = temp;
}
}
}
return [unSortArray copy];
}
特点
稳定性
：它可能会把相同元素分到不同的组中，那么两个相同的元素就有可能调换相对位置，故不稳定。
空间复杂度
：由于整个排序过程是在原数据上进行操作，故为 O(1);
时间复杂度
：
希尔排序的时间复杂度与增量序列的选取有关，例如希尔增量时间复杂度为O(n²)，而Hibbard增量的希尔排序的时间复杂度为O(log n的3/2)，希尔排序时间复杂度的下界是n*log2n
快速排序的核心思想是对待排序序列通过一个
「支点」
（支点就是序列中的一个元素，别把它想的太高大上）进行拆分，使得左边的数据小于支点，右边的数据大于支点。然后把左边和右边再做一次递归，直到递归结束。支点的选择也是一门大学问，我们以 （左边index + 右边index）/ 2 来选择支点。
以 arr = [ 8, 1, 4, 6, 2, 3, 5, 7 ] 为例，选择一个支点, index= (L+R)/2 = (0+7)/2=3, 支点的值 pivot = arr[index] = arr[3] = 6，接下来需要把 arr 中小于 6 的移到左边，大于 6 的移到右边。
快速排序使用一个高效的方法做数据拆分。
用一个指向左边的游标 i，和指向右边的游标 j，逐渐移动这两个游标，直到找到 arr[i] > 6 和 arr[j] < 6, 停止移动游标，交换 arr[i] 和 arr[j]，交换完后 i++，j--（对下一个元素进行比较），直到 i>=j，停止移动。
图中的 L，R 是指快速排序开始时序列的起始和结束索引，在一趟快速排序中，它们的值不会发生改变，直到下一趟排序时才会改变。
一趟快速排序完成后，分别对小于6和大于等于6的部分进行快速排序，递归就好了。对 [ 5, 1, 4, 3, 2 ] 进行一趟快速排序。
代码实现：
+ (NSArray *)quickSort:(NSMutableArray *)unSortArray leftIndex:(NSInteger)lindex rightIndex:(NSInteger)rIndex {
NSInteger i = lindex; NSInteger j = rIndex;
NSNumber *pivot = unSortArray[(lindex + rIndex) / 2];
while (i <= j) {
while ([unSortArray[i] integerValue] i++;
}
while ([unSortArray[j] integerValue] > [pivot integerValue]) {
j--;
}
if (i <= j) {
if (i != j) {
NSNumber *temp = unSortArray[i];
unSortArray[i] = unSortArray[j];
unSortArray[j] = temp; }
i++;
j--;
}
}
if (lindex [self quickSort:unSortArray leftIndex:lindex rightIndex:j];
}
if (i [self quickSort:unSortArray leftIndex:i rightIndex:rIndex];
}
return [unSortArray copy];
}
归并排序，采用分治思想，先把待排序序列拆分成一个个子序列，直到子序列只有一个元素，停止拆分，然后对每个子序列进行边排序边合并。其实，从名字「归并」可以看出一丝「拆、合」的意思（妄加猜测）。
以 arr = [ 8, 1, 4, 6, 2, 3, 5, 7 ] 为例，排序需要分两步：
a、「
拆
」，以 length/2 拆分为 A = [ 8, 1, 4, 6 ] ，B = [ 2, 3, 5, 7 ]，继续对 A 和 B 进行拆分，A1 = [ 8, 1 ] 、A2 = [ 4, 6 ]、B1 = [ 2, 3 ]、B2 = [ 5, 7 ]，继续拆分，直到只有一个元素，A11 = [ 8 ] , A12= [ 1 ] 、A21 = [ 4 ]、A22 = [ 6 ]、B11 = [ 2 ]、B12 = [ 3 ]、B21 = [ 5 ]、B22 = [ 7 ]。
b、「
合
」，对单个元素的序列进行合并，A11和A12合并为[ 1, 8 ], A21 和 A22 合并为 [ 4, 6 ]，等等。在合并的过程中也需要排序。
代码实现：
+ (NSArray *)mergeSort:(NSArray *)unSortArray {
NSInteger len = unSortArray.count;
if (len <= 1) {
return unSortArray;
}
NSInteger mid = len / 2;
NSArray *lList = [self mergeSort:[unSortArray subarrayWithRange:NSMakeRange(0, mid)]];
NSArray *rList = [self mergeSort:[unSortArray subarrayWithRange:NSMakeRange(mid, len-mid)]];
NSInteger lIndex = 0;
NSInteger rIndex = 0;
NSMutableArray *results = [NSMutableArray array];
while (lIndex if ([lList[lIndex] integerValue] [results addObject:lList[lIndex]];
lIndex += 1;
} else {
[results addObject:rList[rIndex]];
rIndex += 1;
}
}
if (lIndex [results addObjectsFromArray:[lList subarrayWithRange:NSMakeRange(lIndex, lList.count-lIndex)]];
}
if (rIndex [results addObjectsFromArray:[rList subarrayWithRange:NSMakeRange(rIndex, rList.count-rIndex)]];
}
return results;
}
特点
稳定性
：在元素拆分的时候，虽然相同元素可能被分到不同的组中，但是合并的时候相同元素相对位置不会发生变化，故稳定。
空间复杂度
：需要用到一个数组保存排序结果，也就是合并的时候，需要开辟空间来存储排序结果，故为 O ( n );
时间复杂度
：最好最坏都为 O(nlogn);
前面所讲的 6 种排序都是基于「比较」的思想，总是在比较两个元素的大小，然后交换位置。
现在来换个“口味”，来看看计数排序。
计数排序的核心思想是把一个无序序列 A 转换成另一个有序序列 B，从 B 中逐个“取出”所有元素，取出的元素即为有序序列「没看明白，不急，后面来张图就搞明白了」。这种算法比快速排序还要快「特定条件下」，它适用于待排序序列中元素的取值范围比较小。比如对某大型公司员工按年龄排序，年龄的取值范围很小，大约在（10-100）之间。
对数组 arr = [ 8, 1, 4, 6, 2, 3, 5, 4 ] 进行排序，使用计数排序需要找到与其对应的一个有序序列，可以使用数组的下标与 arr 做一个映射「数组的下标恰好是有序的」。
遍历 arr，把 arr 中的元素放到 counArr 中，counArr 的大小是由 arr 中最大元素和最小元素决定的。
图中有个技巧，为了让 countArr 尽可能地小，countArr 的长度使用了 arr 中的最大值 max - arr 中的最小值 min + 1 （max - min + 1），arr[i] - min 恰好是 countArr 的下标。countArr 中记录了某个值出现的次数，比如 8 出现过 1 次，则在 countArr 中的值为 1；4 出现过 2 次，则在 countArr 中的值为 2。
代码实现：
+ (NSArray *)countingSort:(NSArray *)datas {
// 1.找出数组中最大数和最小数
NSNumber *max = [datas firstObject];
NSNumber *min = [datas firstObject];
for (int i = 0; i NSNumber *item = datas[i];
if ([item integerValue] > [max integerValue]) {
max = item;
}
if ([item integerValue] min = item;
}
}
// 2.创建一个数组 countArr 来保存 datas 中元素出现的个数
NSInteger sub = [max integerValue] - [min integerValue] + 1;
NSMutableArray *countArr = [NSMutableArray arrayWithCapacity:sub];
for (int i = 0; i sub; i++) {
[countArr addObject:@(0)];
}
// 3.把 datas 转换成 countArr，使用 datas[i] 与 countArr 的下标对应起来
for (int i = 0; i NSNumber *aData = datas[i];
NSInteger index = [aData integerValue] - [min integerValue];
countArr[index] = @([countArr[index] integerValue] + 1);
}
// 4.从countArr中输出结果
NSMutableArray *resultArr = [NSMutableArray arrayWithCapacity:datas.count];
for (int i = 0; i NSInteger count = [countArr[i] integerValue];
while (count > 0) {
[resultArr addObject:@(i + [min integerValue])];
count -= 1;
}
}
return [resultArr copy];
}
特点
稳定性
：在元素往 countArr 中记录时按顺序遍历，从 countArr 中取出元素也是按顺序取出，相同元素相对位置不会发生变化，故稳定。
空间复杂度
：需要额外申请空间，复杂度为“桶”的个数，故为 O ( k )， k 为“桶”的个数，也就是 countArr 的长度;
时间复杂度
：最好最坏都为 O(n+k)， k 为“桶”的个数，也就是 countArr 的长度;
以 arr = [ 8, 1, 4, 6, 2, 3, 5, 7 ] 为例，排序前需要确定桶的个数，和确定桶中元素的取值范围：
代码实现：
+ (NSArray *)bucketSort:(NSArray *)datas {
NSNumber *max = [datas firstObject];
NSNumber *min = [datas firstObject];
for (int i = 0; i NSNumber *item = datas[i];
if ([item integerValue] > [max integerValue]) {
max = item;
}
if ([item integerValue] min = item;
}
}
int maxBucket = 3;
NSMutableArray *buckets = [NSMutableArray arrayWithCapacity:maxBucket];
for (int i = 0; i NSMutableArray *aBucket = [NSMutableArray array];
[buckets addObject:aBucket];
}
float space = ([max integerValue] - [min integerValue] + 1
