1、冒泡排序
原理：重复地走访过要排序的元素列，依次比较两个相邻的元素，如果他们的顺序（如从大到小、首字母从A到Z）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素已经排序完成。
#pragma mark - 冒泡降序排序
- (void)bubbleDescendingOrderSortWithArray:(NSMutableArray *)descendingArr
{
for (int i = 0; i < descendingArr.count; i++) {
for (int j = 0; j < descendingArr.count-1-i; j++) {
NSInteger left = [descendingArr[j] integerValue];
NSInteger right = [descendingArr[j+1] integerValue];
if (left<right) {
[descendingArr exchangeObjectAtIndex:j withObjectAtIndex:j+1];
}
}
}
NSLog(@"冒泡降序排序后结果：%@", descendingArr);
}
#pragma mark - 冒泡升序排序
- (void)bubbleAscendingOrderSortWithArray:(NSMutableArray *)ascendingArr
{
for (int i = 0; i < ascendingArr.count; i++) {
for (int j = 0; j < ascendingArr.count-1-i; j++) {
NSInteger left = [ascendingArr[j] integerValue];
NSInteger right = [ascendingArr[j+1] integerValue];
if (left > right) {
[ascendingArr exchangeObjectAtIndex:j withObjectAtIndex:j+1];
}
}
}
NSLog(@"冒泡升序排序后结果：%@", ascendingArr);
}
平均时间复杂度：O(n^2)
辅助空间：O(1)
算法稳定性：相同元素的前后顺序不会发生改变，所以冒泡排序是一种稳定排序算法。
2、选择排序
原理：它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到全部待排序的数据元素排完。
#pragma mark - 选择降序排序
- (void)selectionDescendingOrderSortWithArray:(NSMutableArray *)descendingArr
{
for (int i = 0; i < descendingArr.count; i++) {
for (int j = i+1; j < descendingArr.count; j++) {
if ([descendingArr[i] integerValue] < [descendingArr[j] integerValue]) {
[descendingArr exchangeObjectAtIndex:i withObjectAtIndex:j];
}
}
}
NSLog(@"选择降序排序后结果：%@", descendingArr);
}
#pragma mark - 选择升序排序
- (void)selectionAscendingOrderSortWithArray:(NSMutableArray *)ascendingArr
{
for (int i = 0; i < ascendingArr.count; i++) {
for (int j = i+1; j < ascendingArr.count; j++) {
if ([ascendingArr[i] integerValue] > [ascendingArr[j] integerValue]) {
[ascendingArr exchangeObjectAtIndex:i withObjectAtIndex:j];
}
}
}
NSLog(@"选择升序排序后结果：%@", ascendingArr);
}
平均时间复杂度：O(n^2)
辅助空间：O(1)
算法稳定性：稳定算法。
3、快速排序
快速排序（Quicksort）是对冒泡排序的一种改进。
通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
#pragma mark - 快速升序排序
- (void)quickAscendingOrderSort:(NSMutableArray *)arr leftIndex:(NSInteger)left rightIndex:(NSInteger)right
{
if (left < right) {
NSInteger temp = [self getMiddleIndex:arr leftIndex:left rightIndex:right];
/**** 递归排序 ***/
//排序基准数左边的
[self quickAscendingOrderSort:arr leftIndex:left rightIndex:temp-1];
//排序基准数右边的
[self quickAscendingOrderSort:arr leftIndex:temp+1 rightIndex:right];
}
NSLog(@"快速升序排序结果：%@", arr);
}
- (NSInteger)getMiddleIndex:(NSMutableArray *)arr leftIndex:(NSInteger)left rightIndex:(NSInteger)right
{
NSInteger tempValue = [arr[left] integerValue]; //记录基准数
while (left < right) {
/**** 首先从右边right开始查找比基准数小的值 ***/
while (left < right && tempValue<= [arr[right] integerValue]) {//如果比基准数大，继续查找
right--;
}
if (left < right) {//如果比基准数小，则将查找到的小值调换到left的位置
arr[left] = arr[right];
}
/**** 当在右边查找到一个比基准数小的值时，就从left开始往后找比基准数大的值 ***/
while (left < right && [arr[left] integerValue] <= tempValue) {
left ++;
}
if (left < right) {//如果比基准数大，则将查找到的大值调换到right的位置
arr[right] = arr[left];
}
}
arr[left] = [NSNumber numberWithInteger:tempValue];//将基准数放到正确位置
return left;
}
//调用
NSMutableArray *arr = [NSMutableArray arrayWithObjects:@29,@21,@2,@34,@3,@10,@20,@22,@11,@9,@2,@28,@45,@64,@4, nil];
[self quickAscendingOrderSort:arr leftIndex:0 rightIndex:arr.count-1];
平均时间复杂度：O(nlogn)
辅助空间：O(logn)~O(n)
算法稳定性：不稳定排序算法。
4、插入排序
实现思路：
- 从第一个元素开始，认为该元素已经是排好序的。
- 取下一个元素，在已经排好序的元素序列中从后向前扫描。
- 如果已经排好序的序列中元素大于新元素，则将该元素往右移动一个位置。
- 重复步骤3，直到已排好序的元素小于或等于新元素。
- 在当前位置插入新元素。
- 重复步骤2。
#pragma mark - 插入升序排序
- (void)insertionAscendingOrderSort:(NSMutableArray *)ascendingArr
{
for (int i = 1; i < ascendingArr.count; i++) {
NSInteger temp = [ascendingArr[i] integerValue];
for (int j = i-1; j >= 0 && temp < [ascendingArr[j] integerValue]; j--) {
ascendingArr[j+1] = ascendingArr[j];
ascendingArr[j] = [NSNumber numberWithInteger:temp];
}
}
NSLog(@"插入升序排序结果：%@",ascendingArr);
}
平均时间复杂度：O(n^2)
辅助空间：O(1)
算法稳定性：稳定。
5、堆排序
堆排序(Heap Sort) 就是利用堆(假设利用大堆顶)进行排序的方法。它的基本思想是，将待排序的序列构成一个大顶堆。此时，整个序列的最大值就是堆顶的根节点。将它移走(其实就是将其与堆数组的末尾元素交换，此时末尾元素就是最大值)，然后将剩余的n-1个序列重新构造成一个堆，这样就会得到n个元素中的次小值。如此反复执行，便能得到一个有序序列了。
#pragma mark - 堆排序
- (void)heapSort:(NSMutableArray *)list
{
NSInteger i ,size;
size = list.count;
//找出最大的元素放到堆顶，构建大顶堆
for (i= list.count/2-1; i>=0; i--) {
[self createBiggesHeap:list withSize:size beIndex:i];
}
while(size > 0){
[list exchangeObjectAtIndex:size-1 withObjectAtIndex:0]; //将根(最大) 与数组最末交换
size -- ;//树大小减小
[self createBiggesHeap:list withSize:size beIndex:0];
}
NSLog(@"%@",list);
}
- (void)createBiggesHeap:(NSMutableArray *)list withSize:(NSInteger) size beIndex:(NSInteger)element
{
NSInteger lchild = element *2 + 1,rchild = lchild+1; //左右子树
while (rchild < size) { //子树均在范围内
if ([list[element] integerValue] >= [list[lchild] integerValue] && [list[element] integerValue] >= [list[rchild]integerValue]) return; //如果比左右子树都大，完成整理
if ([list[lchild] integerValue] > [list[rchild] integerValue]) { //如果左边最大
[list exchangeObjectAtIndex:element withObjectAtIndex:lchild]; //把左面的提到上面
element = lchild; //循环时整理子树
}else{//否则右面最大
[list exchangeObjectAtIndex:element withObjectAtIndex:rchild];
element = rchild;
}
lchild = element * 2 +1;
rchild = lchild + 1; //重新计算子树位置
}
//只有左子树且子树大于自己
if (lchild < size && [list[lchild] integerValue] > [list[element] integerValue]) {
[list exchangeObjectAtIndex:lchild withObjectAtIndex:element];
}
}
平均时间复杂度：O(nlogn)
辅助空间：O(1)
算法稳定性：由于记录的比较和交换是跳跃式进行，因此堆排序也是一种不稳定的排序方法。
6、归并排序
归并排序(Merging Sort) 就是利用归并的思想实现的排序方法。它的原理是假设初始序列含有n个记录，则可以看成是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到n/2个长度为2或者1的有序子序列；再两两归并，......，如此反复，直到得到一个长度为n的有序序列为止，这种排序方法称为归并排序。
#pragma mark - 归并升序排序
- (void)megerSortAscendingOrderSort:(NSMutableArray *)ascendingArr
{
//tempArray数组里存放ascendingArr.count个数组，每个数组包含一个元素
NSMutableArray *tempArray = [NSMutableArray arrayWithCapacity:1];
for (NSNumber *num in ascendingArr) {
NSMutableArray *subArray = [NSMutableArray array];
[subArray addObject:num];
[tempArray addObject:subArray];
}
//开始合并为一个数组
while (tempArray.count != 1) {
NSInteger i = 0;
while (i < tempArray.count - 1) {
tempArray[i] = [self mergeArrayFirstList:tempArray[i] secondList:tempArray[i + 1]];
[tempArray removeObjectAtIndex:i + 1];
I++;
}
}
NSLog(@"归并升序排序结果：%@", tempArray[0]);
}
- (NSArray *)mergeArrayFirstList:(NSArray *)array1 secondList:(NSArray *)array2 {
NSMutableArray *resultArray = [NSMutableArray array];
NSInteger firstIndex = 0, secondIndex = 0;
while (firstIndex < array1.count && secondIndex < array2.count) {
if ([array1[firstIndex] floatValue] < [array2[secondIndex] floatValue]) {
[resultArray addObject:array1[firstIndex]];
firstIndex++;
} else {
[resultArray addObject:array2[secondIndex]];
secondIndex++;
}
}
while (firstIndex < array1.count) {
[resultArray addObject:array1[firstIndex]];
firstIndex++;
}
while (secondIndex < array2.count) {
[resultArray addObject:array2[secondIndex]];
secondIndex++;
}
return resultArray.copy;
}
平均时间复杂度：O(nlogn)
辅助空间：O(n)
算法稳定性：因为是两两比较，不存在跳跃，因此是一种稳定的排序算法。虽然占用内存比较多，但却是一种效率高的算法。
7、希尔排序
希尔排序在插入排序的基础上增加一个叫增量的概念。那什么增量？插入排序只能与相邻的元素进行比较，而希尔排序则是进行跳跃比较，而增量就是步长。比如增量为3时，下标为0的元素与下标为3的元素比较，3再与6比较，1与4比较，4再与7比较……比较完后，再去减少增量，重复之前步骤，直到增量为1，此时只有一个分组了，再对这一个分组进行插入排序，整个希尔排序就结束了。
#pragma mark - 希尔排序
-(void)shellSort:(NSMutableArray *)list{
int gap = (int)list.count / 2;//起始间隔值gap设置为总数的一半，直到gap==1结束
while (gap >= 1) {
for(int i = gap ; i < [list count]; i++){
NSInteger temp = [[list objectAtIndex:i] intValue];
int j = I;
while (j >= gap && temp < [[list objectAtIndex:(j - gap)] intValue]) {
[list replaceObjectAtIndex:j withObject:[list objectAtIndex:j-gap]];
j -= gap;
}
[list replaceObjectAtIndex:j withObject:[NSNumber numberWithInteger:temp]];
}
gap = gap / 2;
}
NSLog(@"希尔升序排序结果：%@", list);
}
平均时间复杂度：O(nlogn)~O(n^2)
辅助空间：O(1)
算法稳定性：由于记录是跳跃式的移动，希尔排序并不是一种稳定的排序算法。
8、基数排序
基数排序(Radix Sort)是根据关键字中各位的值，通过对排序的N个元素进行若干趟“分配”与“收集”来实现排序的。
#pragma mark - 基数排序
- (void)radixSort:(NSMutableArray *)ascendingArr
{
/**
基于LSD方法的链式基数排序的基本思想
“多关键字排序”的思想实现“单关键字排序”。对数字型或字符型的单关键字，可以看作由多个数位或多个字符构成的多关键字，此时可以采用“分配-收集”的方法进行排序，这一过程称作基数排序法，其中每个数字或字符可能的取值个数称为基数。比如，扑克牌的花色基数为4，面值基数为13。在整理扑克牌时，既可以先按花色整理，也可以先按面值整理。按花色整理时，先按红、黑、方、花的顺序分成4摞（分配），再按此顺序再叠放在一起（收集），然后按面值的顺序分成13摞（分配），再按此顺序叠放在一起（收集），如此进行二次分配和收集即可将扑克牌排列有序。
基数排序:
是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。基数排序基于分别排序，分别收集，所以是稳定的。
*/
//创建空桶
NSMutableArray *buckt = [self createBucket];
//待排数组的最大数值
NSNumber *maxnumber = [self listMaxItem:ascendingArr];
//最大数值的数字位数
NSInteger maxLength = numberLength(maxnumber);
// 按照从低位到高位的顺序执行排序过程
for (int digit = 1; digit <= maxLength; digit++) {
// 入桶
for (NSNumber *item in ascendingArr) {
//确定item 归属哪个桶 以digit位数为基数
NSInteger baseNumber = [self fetchBaseNumber:item digit:digit];
NSMutableArray *mutArray = buckt[baseNumber];
//将数据放入空桶上
[mutArray addObject:item];
}
NSInteger index = 0;
//出桶
for (int i = 0; i < buckt.count; i++) {
NSMutableArray *array = buckt[i];
//将桶的数据放回待排数组中
while (array.count != 0) {
NSNumber *number = [array objectAtIndex:0];
ascendingArr[index] = number;
[array removeObjectAtIndex:0];
index++;
}
}
}
NSLog(@"基数升序排序结果：%@", ascendingArr);
}
//创建空桶，每个桶里都是数组
- (NSMutableArray *)createBucket {
NSMutableArray *bucket = [NSMutableArray array];
for (int index = 0; index < 10; index++) {//数字0~9
NSMutableArray *array = [NSMutableArray array];
[bucket addObject:array];
}
return bucket;
}
//数据最大值
- (NSNumber *)listMaxItem:(NSArray *)list {
NSNumber *maxNumber = list[0];
for (NSNumber *number in list) {
if ([maxNumber integerValue] < [number integerValue]) {
maxNumber = number;
}
}
return maxNumber;
}
//数字的位数
NSInteger numberLength(NSNumber *number) {
NSString *string = [NSString stringWithFormat:@"%ld", (long)[number integerValue]];
return string.length;
}
- (NSInteger)fetchBaseNumber:(NSNumber *)number digit:(NSInteger)digit {
//digit为基数位数
if (digit > 0 && digit <= numberLength(number)) {
NSMutableArray *numbersArray = [NSMutableArray array];
//number的位数确定
NSString *string = [NSString stringWithFormat:@"%ld", [number integerValue]];
for (int index = 0; index < numberLength(number); index++) {
[numbersArray addObject:[string substringWithRange:NSMakeRange(index, 1)]];
}
//number的位数是几位数的
NSString *str = numbersArray[numbersArray.count - digit];
return [str integerValue];
}
return 0;
}
时间复杂度：假设在基数排序中，r为基数，d为位数。则基数排序的时间复杂度为O(d(n+r))。我们可以看出，基数排序的效率和初始序列是否有序没有关联。
空间复杂度：在基数排序过程中，对于任何位数上的基数进行“装桶”操作时，都需要n+r个临时空间。
算法稳定性：是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。基数排序基于分别排序，分别收集，所以是稳定的。
参考：
https://www.jianshu.com/p/97cdc7135773
https://www.cnblogs.com/ZachRobin/p/7094852.html
https://www.jianshu.com/p/b59df9d0a169
https://www.jianshu.com/p/fe271bc3e544
https://www.jianshu.com/p/c74dd2954b8e
https://www.jianshu.com/p/43de49cd23e6
