常见排序算法
算法概述
常见排序算法可以分为两大类：
1.算法分类
- 比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此也称为非线性时间比较类排序。
- 非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。
2.算法复杂度
3.相关概念
稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。
时间复杂度：对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律。
空间复杂度：是指算法在计算机内执行时所需存储空间的度量，它也是数据规模n的函数。
一、冒泡排序（Bubble Sort）
冒泡排序是通过比较两个相邻元素的大小实现排序，如果前一个元素大于后一个元素，就交换这两个元素。这样就会让每一趟冒泡都能找到最大一个元素并放到最后。
以 [ 8, 1, 4, 6, 2, 3, 5, 7 ] 为例，对它进行冒泡排序：
代码实现：
// 打印数组
- (void)logArr:(NSMutableArray * )array {
NSString * str = @"";
for (NSNumber * value in array) {
str = [str stringByAppendingString:[NSString stringWithFormat:@"%zd ",[value integerValue]]];
}
NSLog(@"%@",str);
}
- (void)bubbleSort:(NSArray *)unsortDatas {
NSMutableArray *unSortArray = [unsortDatas mutableCopy];
for (int i = 0; i < unSortArray.count -1 ; i++) {
for (int j = 0; j < unSortArray.count - 1 - i; j++) {
// 比较相邻两个元素的大小，后一个大于前一个就交换
if ([unSortArray[j] integerValue] > [unSortArray[j+1] integerValue]) {
[unSortArray exchangeObjectAtIndex:j withObjectAtIndex:j+1];
}
}
[self logArr:unSortArray];
}
}
NSArray *unsortDatas = @[@"8", @"1", @"4", @"6", @"2", @"3", @"5", @"7"];
[self bubbleSort:unsortDatas];
//每次循环打印结果如下
1 4 6 2 3 5 7 8
1 4 2 3 5 6 7 8
1 2 3 4 5 6 7 8
1 2 3 4 5 6 7 8
1 2 3 4 5 6 7 8
1 2 3 4 5 6 7 8
1 2 3 4 5 6 7 8
动画演示
特点
稳定性 ：它是指对同样的数据进行排序，会不会改变它的相对位置。比如 [ 1, 3, 2, 4, 2] 经过排序后，两个相同的元素 2 位置是不会被交换。冒泡排序是比较相邻两个元素的大小，显然不会破坏稳定性。
空间复杂度 ：由于整个排序过程是在原数据上进行操作，故为 O(1);
时间复杂度 ：由于嵌套了 2 层循环，故为 O(n*n);
二、选择排序（Selection Sort）
选择排序的思想是，首先,找到数组中最小的那个元素 ,其次,将它和数组的第一个元素交换位置。再次,在剩下的元素中找到最小的元素, 将它与数组的第二个元素交换位置。如此反复, 到将整个数组排序。这种方法叫做做选择排序,因为它在不断地选择剩余元素之中的最小者。排序时间只与数组长度有关系，与数组是否有序无关
代码实现：
- (void)selectSort:(NSArray *)unsortDatas {
NSMutableArray *unSortArray = [unsortDatas mutableCopy];
for (int i = 0; i < unSortArray.count; i++) {
int mindex = i;
for (int j = i; j < unSortArray.count; j++) {
// 找到最小元素的index
if ([unSortArray[j] integerValue] < [unSortArray[mindex] integerValue]) {
mindex = j;
}
}
// 交换位置
if (i != mindex) { /*若min不等于i，说明找到最小值，交换*/
[unSortArray exchangeObjectAtIndex:i withObjectAtIndex:mindex];
}
[self logArr:unSortArray];
}
}
//每次循环打印结果如下
1 8 4 6 2 3 5 7
1 2 4 6 8 3 5 7
1 2 3 6 8 4 5 7
1 2 3 4 8 6 5 7
1 2 3 4 5 6 8 7
1 2 3 4 5 6 8 7
1 2 3 4 5 6 7 8
1 2 3 4 5 6 7 8
动画演示
特点
稳定性 ：排序过程中元素是按顺序进行遍历，相同元素相对位置不会发生变化，故稳定。（???）
空间复杂度 ：在原序列进行操作，故为 O( 1 );
时间复杂度 ：需要 2 次循环遍历，故为 O( n * n );
三、插入排序（Insertion Sort）
插入排序是将待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列，从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面
对于有序数组或部分有序数组，此排序方法是十分高效的，很适合小规模的数组，很多高级的排序算法都会利用到插入排序。
代码实现：
- (void)insertionSort:(NSArray *)unsortDatas {
NSMutableArray *unSortArray = [unsortDatas mutableCopy];
for (int i = 1; i < unSortArray.count; i++) {
int preindx = i - 1;
// 必须记录这个元素，不然会被覆盖掉
NSNumber *current = unSortArray[i];
// 逆序遍历已经排序好的数组
// 当前元素小于排序好的元素，就移动到下一个位置
while (preindx >= 0 && [current integerValue] < [unSortArray[preindx] integerValue] ) {
// 元素向后移动
unSortArray[preindx+1] = unSortArray[preindx];
preindx -= 1;
}
// 找到合适的位置，把当前的元素插入
unSortArray[preindx+1] = current;
[self logArr:unSortArray];
}
}
//每次循环打印结果如下
1 8 4 6 2 3 5 7
1 4 8 6 2 3 5 7
1 4 6 8 2 3 5 7
1 2 4 6 8 3 5 7
1 2 3 4 6 8 5 7
1 2 3 4 5 6 8 7
1 2 3 4 5 6 7 8
动画演示
特点
稳定性 ：它是从后往前遍历已排序好的序列，相同元素不会改变位置，故为稳定排序；
空间复杂度 ：在原序列进行操作，故为 O( 1 );
时间复杂度 ：排序的过程中，首先要遍历所有的元素，然后在已排序序列中找到合适的位置并插入。共需要 2 层循环，故为 O ( n * n );
四、希尔排序（Shell Sort）
希尔排序为什么产生：希尔排序是以插入排序为基础的一种快速的排序算法。因为在大规模乱序数组中使用插入排序很慢，因为它只会交换相邻的两个元素，因此，如果越小的元素越是靠后，那么操作的复杂度将会大大提升，所以，人们把插入排序进行了改良，变成了希尔排序。
希尔排序的思想：希尔排序实质上是一种分组插入方法。它的基本思想是：对于n个待排序的数列，取一个小于n的整数gap(gap被称为步长)将待排序元素分成若干个组子序列，所有距离为gap的倍数的记录放在同一个组中；然后，对各组内的元素进行直接插入排序。 这一趟排序完成之后，每一个组的元素都是有序的。然后减小gap的值，并重复执行上述的分组和排序。重复这样的操作，当gap=1时，整个数列就是有序的
排序时间复杂度的下界是n*log2n。希尔排序没有快速排序算法快 O(n(logn))，因此中等大小规模表现良好，对规模非常大的数据排序不是最优选择
以 arr = [ 8, 1, 4, 6, 2, 3, 5, 7 ] 为例，通过 floor(8/2) 来分为 4 组，8 表示数组中元素的个数。分完组后，对组内元素进行插入排序。
「 第1次分组 」[8,2],[1,3],[4,5],[6,7]
「 利用第 1 次分组结果进行第 2 次分组 」[2,4,8,5],[1,6,3,7]
「 利用第 2 次分组结果进行最后一次分组 」[2,1,4,3,5,6,8,7]
代码实现：
- (void)shellSort:(NSArray *)unsortDatas {
NSMutableArray *unSortArray = [unsortDatas mutableCopy];
// len = 8
int len = (int)unSortArray.count;
// floor 向下取整，所以 gap的值为：4，2，1
for (int gap = floor(len / 2); gap > 0; gap = floor(gap/2)) {
// i=4;i<9;i++ (4,5,6,7,8)
for (int i = gap; i < len; i++) {
// j=0,1,2,3,4
// [0]-[4] [1]-[5] [2]-[6] [3]-[7] [4]-[8]
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;
}
}
[self logArr:unSortArray];
}
}
//每次循环打印结果如下
2 1 4 6 8 3 5 7
2 1 4 3 5 6 8 7
1 2 3 4 5 6 7 8
动画演示
特点
稳定性 ：它可能会把相同元素分到不同的组中，那么两个相同的元素就有可能调换相对位置，故不稳定；
空间复杂度 ：在原序列进行操作，故为 O( 1 );
时间复杂度 ：希尔排序的时间复杂度与增量序列的选取有关，例如希尔增量时间复杂度为O(n²)，而Hibbard增量的希尔排序的时间复杂度为O(log n的3/2)，希尔排序时间复杂度的下界是n*log2n;
五、快速排序（Quick Sort）
快速排序的基本思想是：选择一个基准数，通过一趟排序将要排序的数据分割成独立的两部分；其中一部分的所有数据都比另外一部分的所有数据都要小。然后，再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
快速排序流程： (1) 从数列中挑出一个基准值。 (2) 将所有比基准值小的摆放在基准前面，所有比基准值大的摆在基准的后面(相同的数可以到任一边)；在这个分区退出之后，该基准就处于数列的中间位置。 (3) 递归地把”基准值前面的子数列”和”基准值后面的子数列”进行排序。
以 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 ] 进行一趟快速排序。
代码实现：
- (void)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] < [pivot integerValue]) {
i++;
}
// 向右移动，直到找到小于支点的元素
while ([unSortArray[j] integerValue] > [pivot integerValue]) {
j--;
}
// 交换两个元素，让左边的大于支点，右边的小于支点
if (i <= j) {
// 如果 i== j，交换个啥？
if (i != j) {
NSNumber *temp = unSortArray[i];
unSortArray[i] = unSortArray[j];
unSortArray[j] = temp;
}
i++;
j--;
}
[self logArr:unSortArray];
}
// 递归左边，进行快速排序
if (lindex < j) {
[self quickSort:unSortArray leftIndex:lindex rightIndex:j];
}
// 递归右边，进行快速排序
if (i < rIndex) {
[self quickSort:unSortArray leftIndex:i rightIndex:rIndex];
}
}
//每次循环打印结果如下
5 1 4 6 2 3 8 7
5 1 4 3 2 6 8 7
5 1 4 3 2 6 8 7
2 1 4 3 5 6 8 7
2 1 3 4 5 6 8 7
1 2 3 4 5 6 8 7
1 2 3 4 5 6 8 7
1 2 3 4 5 6 8 7
1 2 3 4 5 6 7 8
1 2 3 4 5 6 7 8
动画演示
特点
稳定性 ：不稳定
空间复杂度 ：O(log2n)
时间复杂度 ：O(log2n)
六、归并排序 (Merge sort)
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。
以 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 < lList.count && rIndex < rList.count) {
if ([lList[lIndex] integerValue] < [rList[rIndex] integerValue]) {
[results addObject:lList[lIndex]];
lIndex += 1;
} else {
[results addObject:rList[rIndex]];
rIndex += 1;
}
}
// 把左边剩余元素加到排序结果中
if (lIndex < lList.count) {
[results addObjectsFromArray:[lList subarrayWithRange:NSMakeRange(lIndex, lList.count-lIndex)]];
}
// 把右边剩余元素加到排序结果中
if (rIndex < rList.count) {
[results addObjectsFromArray:[rList subarrayWithRange:NSMakeRange(rIndex, rList.count-rIndex)]];
}
[self logArr:results.mutableCopy];
return results;
}
//每次循环打印结果如下
1 8
4 6
1 4 6 8
2 3
5 7
2 3 5 7
1 2 3 4 5 6 7 8
动画演示
特点
稳定性 ：在元素拆分的时候，虽然相同元素可能被分到不同的组中，但是合并的时候相同元素相对位置不会发生变化，故稳定。
空间复杂度 ：需要用到一个数组保存排序结果，也就是合并的时候，需要开辟空间来存储排序结果，故为 O ( n );
时间复杂度 ：最好最坏都为 O(nlogn);
七、计数排序（Counting Sort）
计数排序不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。
这种算法「特定条件下」比快速排序还要快，它适用于待排序序列中元素的取值范围比较小。比如对某大型公司员工按年龄排序，年龄的取值范围很小，大约在（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 < datas.count; i++) {
NSNumber *item = datas[i];
if ([item integerValue] > [max integerValue]) {
max = item;
}
if ([item integerValue] < [min 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 < datas.count; i++) {
NSNumber *aData = datas[i];
NSInteger index = [aData integerValue] - [min integerValue];
countArr[index] = @([countArr[index] integerValue] + 1);
[self logArr:countArr.mutableCopy];
}
// 4.从countArr中输出结果
NSMutableArray *resultArr = [NSMutableArray arrayWithCapacity:datas.count];
for (int i = 0; i < countArr.count; i++) {
NSInteger count = [countArr[i] integerValue];
while (count > 0) {
[resultArr addObject:@(i + [min integerValue])];
count -= 1;
}
}
return [resultArr copy];
}
//每次循环打印结果如下
0 0 0 0 0 0 0 1
1 0 0 0 0 0 0 1
1 0 0 1 0 0 0 1
1 0 0 1 0 1 0 1
1 1 0 1 0 1 0 1
1 1 1 1 0 1 0 1
1 1 1 1 1 1 0 1
1 1 1 2 1 1 0 1
动画演示
特点
稳定性 ：在元素往 countArr 中记录时按顺序遍历，从 countArr 中取出元素也是按顺序取出，相同元素相对位置不会发生变化，故稳定。
空间复杂度 ：需要额外申请空间，复杂度为“桶”的个数，故为 O ( k )， k 为“桶”的个数，也就是 countArr 的长度;
时间复杂度 ：最好最坏都为 O(n+k)， k 为“桶”的个数，也就是 countArr 的长度;
八、桶排序（Bucket Sort）
桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排）。
代码实现：
- (NSArray *)bucketSort:(NSArray *)datas {
// 1.找出数组中最大数和最小数
NSNumber *max = [datas firstObject];
NSNumber *min = [datas firstObject];
for (int i = 0; i < datas.count; i++) {
NSNumber *item = datas[i];
if ([item integerValue] > [max integerValue]) {
max = item;
}
if ([item integerValue] < [min integerValue]) {
min = item;
}
}
// 2.创建桶，桶的个数为 3
int maxBucket = 3;
NSMutableArray *buckets = [NSMutableArray arrayWithCapacity:maxBucket];
for (int i = 0; i < maxBucket; i++) {
NSMutableArray *aBucket = [NSMutableArray array];
[buckets addObject:aBucket];
}
// 3.把数据分配到桶中，桶中的数据是有序的
// a.计算桶中数据的平均值，这样分组数据的时候会把数据放到对应的桶中
float space = ([max integerValue] - [min integerValue] + 1) / (maxBucket*1.0);
for (int i = 0; i < datas.count; i++) {
// b.根据数据值计算它在桶中的位置
int index = floor(([datas[i] integerValue] - [min integerValue]) / space);
NSMutableArray *bucket = buckets[index];
int maxCount = (int)bucket.count;
NSInteger minIndex = 0;
for (int j = maxCount - 1; j >= 0; j--) {
if ([datas[i] integerValue] > [bucket[j] integerValue]) {
minIndex = j+1;
break;
}
}
[bucket insertObject:datas[i] atIndex:minIndex];
}
// 4.把桶中的数据重新组装起来
NSMutableArray *results = [NSMutableArray array];
[buckets enumerateObjectsUsingBlock:^(NSArray *obj, NSUInteger idx, BOOL * _Nonnull stop) {
[results addObjectsFromArray:obj];
[self logArr:obj.mutableCopy];
}];
return results;
}
//每次循环打印结果如下
1 2 3
4 5 6
7 8
动画演示
[加载中…]
特点
稳定性 ：在元素拆分的时候，相同元素会被分到同一组中，合并的时候也是按顺序合并，故稳定。
空间复杂度 ：桶的个数加元素的个数，为 O ( n + k );
时间复杂度 ：最好为 O( n + k )，最坏为 O（n * n）;
九、基数排序（Radix Sort）
基数排序是从待排序序列找出可以作为排序的「关键字」，按照「关键字」进行多次排序，最终得到有序序列。比如对 100 以内的序列 arr = [ 3, 9, 489, 1, 5, 10, 2, 7, 6, 204 ]进行排序，排序关键字为「个位数」、「十位数」和「百位数」这 3 个关键字，分别对这 3 个关键字进行排序，最终得到一个有序序列。
以 arr = [ 3, 9, 489, 1, 5, 10, 2, 7, 6, 204 ] 为例，最大为 3 位数，分别对个、十、百位进行排序，最终得到的序列就是有序序列。可以把 arr 看成 [ 003, 009, 489, 001, 005, 010, 002, 007, 006, 204 ]，这样理解起来比较简单。
数字的取值范围为 0-9，故可以分为 10 个桶。
代码实现：
- (NSArray *)radixSort:(NSArray *)datas {
NSMutableArray *tempDatas;
NSInteger maxValue = 0;
int maxDigit = 0;
int level = 0;
do {
// 1.创建10个桶
NSMutableArray *buckets = [NSMutableArray array];
for (int i = 0; i < 10; i++) {
NSMutableArray *array = [NSMutableArray array];
[buckets addObject:array];
}
// 2.把数保存到桶中
for (int i = 0; i < datas.count; i++) {
NSInteger value = [datas[i] integerValue];
// 求一个数的多次方
int xx = (level < 1 ? 1 : (pow(10, level)));
// 求个位数、十位数....
int mod = value / xx % 10;
[buckets[mod] addObject:datas[i]];
// 求最大数为了计算最大数
if (maxDigit == 0) {
if (value > maxValue) {
maxValue = value;
}
}
}
// 3.把桶中的数据重新合并
tempDatas = [NSMutableArray array];
for (int i = 0; i < 10; i++) {
NSMutableArray *aBucket = buckets[i];
[tempDatas addObjectsFromArray:aBucket];
[self logArr:tempDatas.mutableCopy];
}
// 4.求出数组中最大数的位数, 只需计算一次
if (maxDigit == 0) {
while(maxValue > 0){
maxValue = maxValue / 10;
maxDigit++;
}
}
// 5.继续下一轮排序
datas = tempDatas;
level += 1;
} while (level < maxDigit);
return tempDatas;
}
//每次循环打印结果如下
10
10 1
10 1 2
10 1 2 3
10 1 2 3 204
10 1 2 3 204 5
10 1 2 3 204 5 6
10 1 2 3 204 5 6 7
10 1 2 3 204 5 6 7
10 1 2 3 204 5 6 7 9 489
1 2 3 204 5 6 7 9
1 2 3 204 5 6 7 9 10
1 2 3 204 5 6 7 9 10
1 2 3 204 5 6 7 9 10
1 2 3 204 5 6 7 9 10
1 2 3 204 5 6 7 9 10
1 2 3 204 5 6 7 9 10
1 2 3 204 5 6 7 9 10
1 2 3 204 5 6 7 9 10 489
1 2 3 204 5 6 7 9 10 489
1 2 3 5 6 7 9 10
1 2 3 5 6 7 9 10
1 2 3 5 6 7 9 10 204
1 2 3 5 6 7 9 10 204
1 2 3 5 6 7 9 10 204 489
1 2 3 5 6 7 9 10 204 489
1 2 3 5 6 7 9 10 204 489
1 2 3 5 6 7 9 10 204 489
1 2 3 5 6 7 9 10 204 489
1 2 3 5 6 7 9 10 204 489
动画演示
特点
稳定性 ：在元素拆分的时候，相同元素会被分到同一组中，合并的时候也是按顺序合并，故稳定。
空间复杂度 ：O ( n + k );
时间复杂度 ：最好最坏都为 O( n * k );