1.插入排序
/**
插入排序
解释：默认数组第一个元素为有序序列，将后面一个元素插入前面的有序序列中，从而得到一个新的序列
eg.
【初始数组】 48。 65。 33。 46
i = 1 (48) 65 33 46
i = 2 (48 65) 33 46
i = 3 (33 48 65) 46
i = 4 (33 46 48 65)
*/
+ (NSMutableArray *)insert_sortWithArray:(NSArray *)sortArray {
#if 0 //新建 数组 插入
NSMutableArray *newArray = [NSMutableArray array];
for (int i = 0; i < sortArray.count; i++) {
if (i == 0) {
[newArray addObject:sortArray[i]];
}else {
int index = -1;
for (int j = 0; j < newArray.count; j++) {
if ([sortArray[i] integerValue] < [newArray[j] integerValue]) {
index = j;
break;
}
}
if (index == -1) {
[newArray addObject:sortArray[i]];
}else {
[newArray insertObject:sortArray[i] atIndex:index];
}
}
}
return newArray;
#endif
#if 1 // 原数组替换
NSMutableArray *newArray = [NSMutableArray arrayWithArray:sortArray];
for (int i = 0; i < newArray.count; i++) {
for (int j = 0; j < i; j++) {
if ([newArray[i] integerValue] < [newArray[j] integerValue]) {
NSString *indexStr = newArray[i];
// 直接进行数据删除插入 可能会引起 数据改变
[newArray removeObjectAtIndex:i];
[newArray insertObject:indexStr atIndex:j];
}
}
}
return newArray;
#endif
}
2.希尔排序
/**
希尔排序
增量排序，增量设置为总数的 2/3 或一半
从增量位置开始，依次与差一个增量的值进行比较，小的移动到前面，比较完后起始位置+1继续比较。
比较到最后，增量减半，并以此为起始点，重复上一步骤，知道间隔为1为止结束
*/
+ (NSMutableArray *)shell_sortWithArray:(NSArray *)sortArray {
NSMutableArray *newArray = [NSMutableArray arrayWithArray:sortArray];
int shell = (int)newArray.count / 2;
while (shell >= 1) {
// 通过半值以后向前对比
for(int i = shell; i < [newArray count]; i++){
NSInteger temp = [[newArray objectAtIndex:i] intValue];
int j = i;
while (j >= shell && temp < [[newArray objectAtIndex:(j - shell)] intValue]) {
[newArray replaceObjectAtIndex:j withObject:[newArray objectAtIndex:j - shell]];
j -= shell;
}
[newArray replaceObjectAtIndex:j withObject:[NSNumber numberWithInteger:temp]];
}
shell = shell / 2;
}
return newArray;
}
3.简单选择排序
/**
简单选择排序
选择最小的 放在第一个位置
通过选择剩下的最小的放在第二个位置，以此类推
最后一个就是最大的
*/
+ (NSMutableArray *)simpleSelect_sortWithArray:(NSArray *)sortArray {
NSMutableArray *newArray = [NSMutableArray arrayWithArray:sortArray];
for (int i = 0; i < newArray.count; i++) {
NSInteger temp = [newArray[i] integerValue];
int tag = i;
for (int j = i; j < newArray.count; j++) {
if ([newArray[j] integerValue] < temp) {
temp = [newArray[j] integerValue];
tag = j;
}
}
[newArray replaceObjectAtIndex:tag withObject:newArray[i]];
[newArray replaceObjectAtIndex:i withObject:[NSString stringWithFormat:@"%ld", temp]];
}
return newArray;
}
4.堆排序
/**
堆排序
设当前元素在数组中 R [ i ] 表示，那么
它的左孩子结点是：R [ 2 * i + 1 ];
它的右孩子结点是：R [ 2 * i + 2 ];
它的父节点是：R [ ( i - 1 ) / 2 ];
从小到大排序需要满足
R [ i ] <= R [ 2 * i + 1 ] && R [ i ] <= R [ 2 * I + 2 ];
*/
+ (NSMutableArray *)heap_sortWithArray:(NSArray *)sortArray {
#if 0 // 别人写的
NSMutableArray *newArray = [NSMutableArray arrayWithArray:sortArray];
//最后一个元素的索引
NSInteger endIndex = newArray.count - 1;
//构建初始堆
newArray = [self heapCreate:newArray];
// 进行n-1次循环，完成排序
while (endIndex > 0) {
// NSLog(@"将list[0]:\%@与list[\(endIndex)]:\%@交换", ascendingArr[0], ascendingArr[endIndex]);
// 最后一个元素和第一元素进行交换
NSNumber *temp = newArray[0];
newArray[0] = newArray[endIndex];
newArray[endIndex] = temp;
//堆调整
newArray = [self heapAdjast:newArray withFatherIndex:0 withEndIndex:endIndex];
// 下一次循环
endIndex -= 1;
}
#endif
#if 1 // 自己写的
// 初始化堆序列
NSMutableArray *newArray = [self heap_create:[NSMutableArray arrayWithArray:sortArray] endIndex:sortArray.count];
// 堆排序
//将堆第一个和最后一个做调整后排序
NSInteger tag = newArray.count - 1;
while (tag > 0) {
NSString *lastObj = newArray[tag];
[newArray replaceObjectAtIndex:tag withObject:newArray[0]];
[newArray replaceObjectAtIndex:0 withObject:lastObj];
tag -= 1;
[self heap_create:newArray endIndex:tag];
}
#endif
return newArray;
}
+ (NSMutableArray *)heap_create:(NSMutableArray *)array endIndex:(NSInteger)endIndex{
// 首先建立初始的堆排序，即 最大值在最上面
// 从后往前推
// 最后一个元素的 父节点为
NSInteger fatherIndex = array.count / 2 - 1;
while (fatherIndex > -1) {
[self heap_sortLoopFatherIndex:fatherIndex endIndex:endIndex array:array];
fatherIndex -= 1;
}
return array;
}
// 循环堆排序，判断父节点是否存在子节点
+ (NSMutableArray *)heap_sortLoopFatherIndex:(NSInteger)fatherIndex endIndex:(NSInteger)endIndex array:(NSMutableArray *)array {
//初始默认最大值是父节点
NSInteger tempIndex = fatherIndex;
// 判断 父节点是否有两个子节点,并比较大小
if (fatherIndex * 2 + 1 > endIndex) {
return array;
}
if (fatherIndex * 2 + 1 <= array.count - 1 && fatherIndex * 2 + 2 <= array.count - 1) {
NSInteger child1 = [array[fatherIndex * 2 + 1] integerValue];
NSInteger child2 = fatherIndex * 2 + 2 > endIndex ? child1 - 1 : [array[fatherIndex * 2 + 2] integerValue];
//判断两个子节点哪个大则初始是哪个， 优先右边
NSInteger temp = child2 >= child1 ? child2 : child1;
tempIndex = child2 >= child1 ? fatherIndex * 2 + 2 : fatherIndex * 2 + 1;
// 判断 子节点和父节点哪个大
tempIndex = [array[fatherIndex] integerValue] >= temp ? fatherIndex : tempIndex;
}else {
//如果只存在一个节点
NSInteger child1 = [array[fatherIndex * 2 + 1] integerValue];
// 判断子节点和父节点哪个大
tempIndex = [array[fatherIndex] integerValue] >= child1 ? fatherIndex : fatherIndex * 2 + 1;
}
// 判断 最大的是否是 父节点
if (tempIndex != fatherIndex) {
// 如果不是父节点
NSString *str = array[tempIndex];
[array replaceObjectAtIndex:tempIndex withObject:array[fatherIndex]];
[array replaceObjectAtIndex:fatherIndex withObject:str];
// 替换完 再判断被替换的是否还有子节点
if (tempIndex * 2 + 1 < array.count) {
array = [self heap_sortLoopFatherIndex:tempIndex endIndex:endIndex array:array];
}
}
return array;
}
//循环建立初始堆
+ (NSMutableArray *)heapCreate:(NSMutableArray *)array
{
NSInteger i = array.count/2;
while (i >= 0) {
array = [self heapAdjast:array withFatherIndex:i withEndIndex:array.count];
i -= 1;
}
return array;
}
//排序
+ (NSMutableArray *)heapAdjast:(NSMutableArray *)items withFatherIndex:(NSInteger)fatherIndex withEndIndex:(NSInteger)endIndex
{
//开始元素
NSNumber *temp = items[fatherIndex];
//先获得左子索引
NSInteger childIndex = 2 * fatherIndex+1;
while (childIndex < endIndex) {
// 如果有右孩子结点，并且右孩子结点的值大于左孩子结点，则选取右孩子结点
if (childIndex+1 < endIndex && [items[childIndex] floatValue] < [items[childIndex+1] floatValue]) {
childIndex++;
}
// 如果父结点的值已经大于孩子结点的值，则直接结束
if ([temp floatValue] >= [items[childIndex] floatValue]) {
break;
}
// 把孩子结点的值赋给父结点
items[fatherIndex] = items[childIndex];
fatherIndex = childIndex;
childIndex = 2 * fatherIndex +1;
}
items[fatherIndex] = temp;
return items;
}
5.冒泡排序
/**
冒泡排序
两两对比排序
数组有n个元素， 原则上对比 n-1次
*/
+ (NSMutableArray *)bubble_sortWithArray:(NSArray *)sortArray {
NSMutableArray *newArray = [NSMutableArray arrayWithArray:sortArray];
for (int i = 0; i < newArray.count; i++) {
for (int j = i + 1; j < newArray.count; j++) {
NSString *indexStr = newArray[i];
if ([indexStr integerValue] > [newArray[j] integerValue]) {
[newArray replaceObjectAtIndex:i withObject:newArray[j]];
[newArray replaceObjectAtIndex:j withObject:indexStr];
}
}
}
return newArray;
}
6.快速排序
/**
快速排序
i = 0 j = array.cont - 1
key = array [ 0 ]
key从右到左选第一个最小，替换
key 从左到右选第一个最小，替换
先排序基数 key左边的
再排序基数 key右边的序列
*/
+ (NSMutableArray *)fast_sortWithArray:(NSArray *)sortArray {
NSMutableArray *newArray = [NSMutableArray arrayWithArray:sortArray];
[self quickSortArr:newArray withLeftIndex:0 andRightIndex:newArray.count - 1];
return newArray;
}
+ (void)quickSortArr:(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 && key <= [array[j] integerValue]) {
// 当未查找到则继续查找
j --;
}
// 如果比基数小， 替换
array[i] = array[j];
// 开始从左往右查找比基数大的数
while (i < j && key >= [array[i] integerValue]) {
// 如果比基数小 则继续查找
i ++;
}
//如果比基数大则替换
array[j] = array[i];
}
// 将基数放在正确的位置
array[i] = @(key);
//前面排序
[self quickSortArr:array withLeftIndex:leftIndex andRightIndex:i -1];
//后面排序
[self quickSortArr:array withLeftIndex:i + 1 andRightIndex:rightIndex];
}
7.归并排序
/**
归并排序
分成2 个或者 2 个以上的表
然后排序成有序表
合并成一个新的有序表，然后整合成一个整体的有序表
*/
+ (NSMutableArray *)meger_sortWithArray:(NSArray *)sortArray {
NSMutableArray *newArray = [NSMutableArray arrayWithCapacity:1];
for (NSString *num in sortArray) {
NSMutableArray *subArray = [NSMutableArray array];
[subArray addObject:num];
[newArray addObject:subArray];
}
while (newArray.count != 1) {
NSInteger i = 0;
while (i < newArray.count - 1) {
newArray[i] = [self mergeArrayFirstList:newArray[i] secondList:newArray[i + 1]];
[newArray removeObjectAtIndex:i + 1];
i++;
}
}
return newArray;
}
+ (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;
}
