排序算法
2021-05-20 本文已影响0人
Silence_xl
#import <Foundation/Foundation.h>
NS_ASSUME_NONNULL_BEGIN
@interface NSArray (Sort)
/**
* 插入排序
*
* 是否基于比较：是
* 是否稳定排序：是
* 是否原地操作：是
* 时间复杂度为O(n2)，比较高，适合小规模数据的排序。
* 适合排序数据类型：NSString,NSNumber,CGFloat,NSInteger,long
**/
- (void)insertionSortArray:(NSMutableArray *)array;
/**
* 选择排序
*
* 是否基于比较：是
* 是否稳定排序：否
* 是否原地操作：是
* 时间复杂度为O(n2)，比较高，适合小规模数据的排序。
* 适合排序数据类型：NSString,NSNumber,CGFloat,NSInteger,long
**/
- (void)selectSortArray:(NSMutableArray *)array;
/**
* 冒泡排序
*
* 是否基于比较：是
* 是否稳定排序：是
* 是否原地操作：是
* 时间复杂度为O(n2)，比较高，适合小规模数据的排序。
* 适合排序数据类型：NSString,NSNumber,CGFloat,NSInteger,long
**/
- (void)bubbleSortArray:(NSMutableArray *)array;
/**
* 快速排序
*
* 是否基于比较：是
* 是否稳定排序：否
* 是否原地操作：是
* 时间复杂度为O(nlogn)，因此大规模表现良好。
* 适合排序数据类型：NSString,NSNumber,CGFloat,NSInteger,long
**/
- (void)quickSortArray:(NSMutableArray *)array withLeftIndex:(NSInteger)leftIndex andRightIndex:(NSInteger)rightIndex;
/**
* 希尔排序
*
* 是否基于比较：是
* 是否稳定排序：是
* 是否原地操作：是
* 时间复杂度为O(n(1.3—2))，因此中等大小规模表现良好。
* 适合排序数据类型：NSString,NSNumber,CGFloat,NSInteger,long
**/
- (void)shellSortArray:(NSMutableArray *)array;
//堆排序
- (void)heapSortArray:(NSMutableArray *)array;
/**
* 归并排序
*
* 是否基于比较：是
* 是否稳定排序：是
* 是否原地操作：否
* 时间复杂度为O(nlogn)，因此大规模表现良好。
* 适合排序数据类型：NSString,NSNumber,CGFloat,NSInteger,long
**/
- (void)megerSortAscendingOrderSort:(NSMutableArray *)ascendingArray;
/**
* 基数排序
*
* 是否基于比较：否（线性排序）
* 是否稳定排序：是
* 是否原地操作：否
* 时间复杂度为更低的O(n)，但是对要排序的数据要求很苛刻，基数排序要求数据可以划分成高低位，位之间有递进关系。比较两个数，我们只需要比较高位，高位相同的再比较低位。而且每一-位的数据范围不能太大。
* 适合排序数据类型：NSString,NSNumber,NSInteger,long
**/
- (void)radixSortArray:(NSMutableArray *)array;
/**
* 二分查找（循环）
**/
- (NSInteger)binarySearch:(NSArray *)source target:(NSInteger)target;
@end
NS_ASSUME_NONNULL_END
#import "NSArray+Sort.h"
@implementation NSArray (Sort)
#pragma mark 插入排序
/**
* 插入排序
*
* 是否基于比较：是
* 是否稳定排序：是
* 是否原地操作：是
* 时间复杂度为O(n2)，比较高，适合小规模数据的排序。
* 适合排序数据类型：NSString,NSNumber,CGFloat,NSInteger,long
**/
- (void)insertionSortArray:(NSMutableArray *)array {
for (int i = 1; i < array.count; i++) {
int j = i; /* j是一个坑， 确定坑的位置，再把数从坑里取出来，注意顺序*/
id temp = array[i]; /* temp 是从坑里取数*/
if ([array[i] intValue] < [array[i-1] intValue]) { /* j > 0 防止越界。写&&前面效率更高*/
while (j > 0 && [temp intValue] < [array[j-1] intValue]) {
array[j] = array[j-1];
j--;
}
array[j] = temp;
}
}
NSLog(@"%@",array);
}
#pragma mark 选择排序 --每次把最大的选出来 放到前面，然后依次类推
/**
* 选择排序
*
* 是否基于比较：是
* 是否稳定排序：否
* 是否原地操作：是
* 时间复杂度为O(n2)，比较高，适合小规模数据的排序。
* 适合排序数据类型：NSString,NSNumber,CGFloat,NSInteger,long
**/
- (void)selectSortArray:(NSMutableArray *)array {
int index = 0;//记录找到的关键字下标
for (int i = 0; i < array.count - 1; i++) {
index = i;
for (int j = i + 1; j < array.count; j++) {
if ([array[index] integerValue] < [array[j]integerValue]) {
//如果有比当前index值大的值,则记录次下标
index = j;//记录最大值(最小值)的下标
}
}
if (i != index) { //若index不等于i，说明找到最大值，交换
[array exchangeObjectAtIndex:i withObjectAtIndex:index];
}
}
NSLog(@"%@",array);
}
#pragma mark 冒泡排序
/**
* 冒泡排序
*
* 是否基于比较：是
* 是否稳定排序：是
* 是否原地操作：是
* 时间复杂度为O(n2)，比较高，适合小规模数据的排序。
* 适合排序数据类型：NSString,NSNumber,CGFloat,NSInteger,long
**/
- (void)bubbleSortArray:(NSMutableArray *)array {
for (NSInteger i = 0; i < array.count-1; i++) {
for (NSInteger j = 0; j < array.count-1-i; j++) {
NSInteger left = [array[j] integerValue];
NSInteger right = [array[j+1] integerValue];
if (left > right) {
[array exchangeObjectAtIndex:j withObjectAtIndex:j+1];
}
}
}
NSLog(@"%@",array);
}
#pragma mark 快速排序
//1. 算法思想
//快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
//2. 实现原理
//2.1、设置两个变量 low、high，排序开始时：low=0，high=size-1。
//2.2、整个数组找基准正确位置，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面
//默认数组的第一个数为基准数据，赋值给key，即key=array[low]。
//因为默认数组的第一个数为基准，所以从后面开始向前搜索（high–），找到第一个小于key的array[high]，就将 array[high] 赋给 array[low]，即 array[low] = array[high]。（循环条件是 array[high] >= key；结束时 array[high] < key）
//此时从前面开始向后搜索（low++），找到第一个大于key的array[low]，就将 array[low] 赋给 array[high]，即 array[high] = array[low]。（循环条件是 array[low] <= key；结束时 array[low] > key）
//循环 2-3 步骤，直到 low=high，该位置就是基准位置。
//把基准数据赋给当前位置。
//2.3、第一趟找到的基准位置，作为下一趟的分界点。
//2.4、递归调用（recursive）分界点前和分界点后的子数组排序，重复2.2、2.3、2.4的步骤。
//2.5、最终就会得到排序好的数组。
/**
* 快速排序
*
* 是否基于比较：是
* 是否稳定排序：否
* 是否原地操作：是
* 时间复杂度为O(nlogn)，因此大规模表现良好。
* 适合排序数据类型：NSString,NSNumber,CGFloat,NSInteger,long
**/
- (void)quickSortArray:(NSMutableArray *)array withLeftIndex:(NSInteger)leftIndex andRightIndex:(NSInteger)rightIndex {
if (leftIndex >= rightIndex) {//如果数组长度为0或1时返回
return ;
}
NSInteger i = leftIndex;
NSInteger j = rightIndex;
//记录比较基准数
NSInteger key = [array[i] integerValue];
while (i < j) {
/**** 首先从右边j开始查找比基准数小的值 ***/
while (i < j && [array[j] integerValue] >= key) {//如果比基准数大，继续查找
j--;
}
//如果比基准数小，则将查找到的小值调换到i的位置
array[i] = array[j];
/**** 当在右边查找到一个比基准数小的值时，就从i开始往后找比基准数大的值 ***/
while (i < j && [array[i] integerValue] <= key) {//如果比基准数小，继续查找
i++;
}
//如果比基准数大，则将查找到的大值调换到j的位置
array[j] = array[i];
}
//将基准数放到正确位置
array[i] = @(key);
/**** 递归排序 ***/
//排序基准数左边的
[self quickSortArray:array withLeftIndex:leftIndex andRightIndex:i - 1];
//排序基准数右边的
[self quickSortArray:array withLeftIndex:i + 1 andRightIndex:rightIndex];
NSLog(@"快速排序 %@",array);
}
#pragma mark 希尔排序
/**
* 希尔排序
*
* 是否基于比较：是
* 是否稳定排序：是
* 是否原地操作：是
* 时间复杂度为O(n(1.3—2))，因此中等大小规模表现良好。
* 适合排序数据类型：NSString,NSNumber,CGFloat,NSInteger,long
**/
- (void)shellSortArray:(NSMutableArray *)array {//起始间隔值gap设置为总数的一半，直到gap==1结束
int gap = (int)array.count / 2;
while (gap >= 1) {
for(int i = gap; i < [array count]; i++){
NSInteger temp = [[array objectAtIndex:i] intValue];
int j = i;
while (j >= gap && temp < [[array objectAtIndex:(j - gap)] intValue]) {
[array replaceObjectAtIndex:j withObject:[array objectAtIndex:j-gap]];
j -= gap;
}
[array replaceObjectAtIndex:j withObject:[NSNumber numberWithInteger:temp]];
}
gap = gap / 2;
}
NSLog(@"希尔排序 %@",array);
}
//==========================堆排序============================
//堆排序
- (void)heapSortArray:(NSMutableArray *)array {
NSInteger i,size;
size = array.count;
//找出最大的元素放到堆顶
for (i = array.count/2-1; i >= 0; i--) {
[self createBiggesHeap:array withSize:size beIndex:i];
}
while(size > 0){
[array exchangeObjectAtIndex:size-1 withObjectAtIndex:0]; //将根(最大) 与数组最末交换
size -- ;//树大小减小
[self createBiggesHeap:array withSize:size beIndex:0];
}
NSLog(@"%@",array);
}
- (void)createBiggesHeap:(NSMutableArray *)array withSize:(NSInteger) size beIndex:(NSInteger)element {
NSInteger lchild = element *2 + 1,rchild = lchild+1; //左右子树
while (rchild < size) { //子树均在范围内
if ([array[element] integerValue] >= [array[lchild] integerValue] && [array[element] integerValue] >= [array[rchild]integerValue]) return; //如果比左右子树都大，完成整理
if ([array[lchild] integerValue] > [array[rchild] integerValue]) { //如果左边最大
[array exchangeObjectAtIndex:element withObjectAtIndex:lchild]; //把左面的提到上面
element = lchild; //循环时整理子树
}else{//否则右面最大
[array exchangeObjectAtIndex:element withObjectAtIndex:rchild];
element = rchild;
}
lchild = element * 2 +1;
rchild = lchild + 1; //重新计算子树位置
}
//只有左子树且子树大于自己
if (lchild < size && [array[lchild] integerValue] > [array[element] integerValue]) {
[array exchangeObjectAtIndex:lchild withObjectAtIndex:element];
}
}
//==========================堆排序============================
//==========================归并排序============================
#pragma mark 归并排序
//时间复杂度为O(nlogn)
//（1）“分解”——将序列每次折半划分
//（2）“合并”——将划分后的序列段两两合并后排序
/**
* 归并排序
*
* 是否基于比较：是
* 是否稳定排序：是
* 是否原地操作：否
* 时间复杂度为O(nlogn)，因此大规模表现良好。
* 适合排序数据类型：NSString,NSNumber,CGFloat,NSInteger,long
**/
- (void)megerSortAscendingOrderSort:(NSMutableArray *)ascendingArray {
// 排序数组
NSMutableArray *tempArray = [NSMutableArray arrayWithCapacity:1];
// 第一趟排序是的子数组个数为ascendingArr.count
for (NSNumber *num in ascendingArray) {
NSMutableArray *subArray = [NSMutableArray array];
[subArray addObject:num];
[tempArray addObject:subArray];
}
/**
分解操作 每一次归并操作
当数组个数为偶数时tempArray.count/2; 当数组个数为奇数时tempArray.count/2+1; 当tempArray.count == 1时，归并排序完成
*/
while (tempArray.count != 1) {
NSInteger i = 0;
// 当数组个数为偶数时 进行合并操作， 当数组个数为奇数时，最后一位轮空
while (i < tempArray.count - 1) {
// 将i 与i+1 进行合并操作 将合并结果放入i位置上 将i+1位置上的元素删除
tempArray[i] = [self mergeArrayFirstList:tempArray[i] secondList:tempArray[i + 1]];
[tempArray removeObjectAtIndex:i + 1];
// i++ 继续下一循环的合并操作
i++;
}
}
NSLog(@"归并升序排序结果：%@", tempArray[0]);
}
// 合并
- (NSArray *)mergeArrayFirstList:(NSArray *)array1 secondList:(NSArray *)array2 {
// 合并序列数组
NSMutableArray *resultArray = [NSMutableArray array];
// firstIndex是第一段序列的下标 secondIndex是第二段序列的下标
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;
}
//==========================归并排序============================
//==========================基数排序============================
#pragma mark --- 基数排序
/**
* 基数排序
*
* 是否基于比较：否（线性排序）
* 是否稳定排序：是
* 是否原地操作：否
* 时间复杂度为更低的O(n)，但是对要排序的数据要求很苛刻，基数排序要求数据可以划分成高低位，位之间有递进关系。比较两个数，我们只需要比较高位，高位相同的再比较低位。而且每一-位的数据范围不能太大。
* 适合排序数据类型：NSString,NSNumber,NSInteger,long
**/
- (void)radixSortArray:(NSMutableArray *)array {
NSMutableArray *bucket = [self createBucket];
double maxNumber = [self listMaxItem:array];
NSInteger maxLength = [self numberLength:maxNumber];
for (NSInteger digit = 1; digit <= maxLength; digit++) {
//入桶
for (NSNumber *number in array) {
NSInteger baseNumber = [self fetchBaseNumber:number.doubleValue digit:digit];
NSMutableArray *subArray = bucket[baseNumber];
[subArray addObject:number];
}
//出桶
NSInteger index = 0;
for (NSInteger i = 0; i < bucket.count; i++) {
NSMutableArray *subArray = bucket[i];
while (subArray.count > 0) {
NSNumber *item = subArray[0];
[array replaceObjectAtIndex:index withObject:item];
[subArray removeObjectAtIndex:0];
index++;
}
}
}
NSLog(@"基数排序 %@",array);
}
//创建10个空桶
- (NSMutableArray *)createBucket {
NSMutableArray *bucketArray = [NSMutableArray array];
for (NSInteger i = 0; i < 10; i++) {
[bucketArray addObject:[NSMutableArray array]];
}
return bucketArray;
}
//计算无序序列中最大的数值
- (double)listMaxItem:(NSArray *)array {
double maxNumber = [array[0] doubleValue];
for (NSNumber *number in array) {
if (maxNumber < number.doubleValue) {
maxNumber = number.doubleValue;
}
}
return maxNumber;
}
//获取数字的长度
- (NSInteger)numberLength:(double)number {
NSString *numberStr = [NSString stringWithFormat:@"%f",number];
return numberStr.length;
}
//获取数值中特定位数的值
- (NSInteger)fetchBaseNumber:(double)number digit:(NSInteger)digit {
if (digit > 0 && digit <= [self numberLength:number]) {
NSMutableArray *numbersArray = [NSMutableArray array];
NSString *numberStr = [NSString stringWithFormat:@"%f",number];
for (NSInteger i = 0; i < numberStr.length; i++) {
NSString *subStr = [numberStr substringWithRange:NSMakeRange(i, 1)];
[numbersArray addObject:[NSNumber numberWithInteger:subStr.doubleValue]];
}
return [numbersArray[numbersArray.count - digit] integerValue];
}
return 0;
}
//==========================基数排序============================
/**
* 二分查找（循环）
**/
- (NSInteger)binarySearch:(NSArray *)source target:(NSInteger)target {
if (source.count == 0) {
return -1;
}
NSInteger start = 0;
NSInteger end = source.count - 1;
NSInteger mid = 0;
while (start + 1 < end) {
mid = start + (end - start) / 2;
if ([source[mid] integerValue] == target) { // 相邻就退出
return mid;
} else if ([source[mid] integerValue] < target) {
start = mid;
} else {
end = mid;
}
}
if ([source[start] integerValue] == target) {
return start;
}
if ([source[end] integerValue] == target) {
return end;
}
return -1;
}
@end
