1.插入排序
/**
插入排序
解釋：默認(rèn)數(shù)組第一個(gè)元素為有序序列目溉，將后面一個(gè)元素插入前面的有序序列中，從而得到一個(gè)新的序列
eg.
【初始數(shù)組】 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 //新建 數(shù)組 插入
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 // 原數(shù)組替換
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];
// 直接進(jìn)行數(shù)據(jù)刪除插入 可能會(huì)引起 數(shù)據(jù)改變
[newArray removeObjectAtIndex:i];
[newArray insertObject:indexStr atIndex:j];
}
}
}
return newArray;
#endif
}
2.希爾排序
/**
希爾排序
增量排序妻献，增量設(shè)置為總數(shù)的 2/3 或一半
從增量位置開始，依次與差一個(gè)增量的值進(jìn)行比較周霉，小的移動(dòng)到前面姚炕，比較完后起始位置+1繼續(xù)比較摊欠。
比較到最后，增量減半柱宦，并以此為起始點(diǎn)些椒，重復(fù)上一步驟，知道間隔為1為止結(jié)束
*/
+ (NSMutableArray *)shell_sortWithArray:(NSArray *)sortArray {
NSMutableArray *newArray = [NSMutableArray arrayWithArray:sortArray];
int shell = (int)newArray.count / 2;
while (shell >= 1) {
// 通過半值以后向前對(duì)比
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.簡(jiǎn)單選擇排序
/**
簡(jiǎn)單選擇排序
選擇最小的 放在第一個(gè)位置
通過選擇剩下的最小的放在第二個(gè)位置掸刊，以此類推
最后一個(gè)就是最大的
*/
+ (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.堆排序
/**
堆排序
設(shè)當(dāng)前元素在數(shù)組中 R [ i ] 表示免糕，那么
它的左孩子結(jié)點(diǎn)是：R [ 2 * i + 1 ];
它的右孩子結(jié)點(diǎn)是：R [ 2 * i + 2 ];
它的父節(jié)點(diǎn)是：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];
//最后一個(gè)元素的索引
NSInteger endIndex = newArray.count - 1;
//構(gòu)建初始堆
newArray = [self heapCreate:newArray];
// 進(jìn)行n-1次循環(huán)，完成排序
while (endIndex > 0) {
// NSLog(@"將list[0]:\%@與list[\(endIndex)]:\%@交換", ascendingArr[0], ascendingArr[endIndex]);
// 最后一個(gè)元素和第一元素進(jìn)行交換
NSNumber *temp = newArray[0];
newArray[0] = newArray[endIndex];
newArray[endIndex] = temp;
//堆調(diào)整
newArray = [self heapAdjast:newArray withFatherIndex:0 withEndIndex:endIndex];
// 下一次循環(huán)
endIndex -= 1;
}
#endif
#if 1 // 自己寫的
// 初始化堆序列
NSMutableArray *newArray = [self heap_create:[NSMutableArray arrayWithArray:sortArray] endIndex:sortArray.count];
// 堆排序
//將堆第一個(gè)和最后一個(gè)做調(diào)整后排序
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{
// 首先建立初始的堆排序忧侧，即 最大值在最上面
// 從后往前推
// 最后一個(gè)元素的 父節(jié)點(diǎn)為
NSInteger fatherIndex = array.count / 2 - 1;
while (fatherIndex > -1) {
[self heap_sortLoopFatherIndex:fatherIndex endIndex:endIndex array:array];
fatherIndex -= 1;
}
return array;
}
// 循環(huán)堆排序石窑，判斷父節(jié)點(diǎn)是否存在子節(jié)點(diǎn)
+ (NSMutableArray *)heap_sortLoopFatherIndex:(NSInteger)fatherIndex endIndex:(NSInteger)endIndex array:(NSMutableArray *)array {
//初始默認(rèn)最大值是父節(jié)點(diǎn)
NSInteger tempIndex = fatherIndex;
// 判斷 父節(jié)點(diǎn)是否有兩個(gè)子節(jié)點(diǎn),并比較大小
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];
//判斷兩個(gè)子節(jié)點(diǎn)哪個(gè)大則初始是哪個(gè)， 優(yōu)先右邊
NSInteger temp = child2 >= child1 ? child2 : child1;
tempIndex = child2 >= child1 ? fatherIndex * 2 + 2 : fatherIndex * 2 + 1;
// 判斷 子節(jié)點(diǎn)和父節(jié)點(diǎn)哪個(gè)大
tempIndex = [array[fatherIndex] integerValue] >= temp ? fatherIndex : tempIndex;
}else {
//如果只存在一個(gè)節(jié)點(diǎn)
NSInteger child1 = [array[fatherIndex * 2 + 1] integerValue];
// 判斷子節(jié)點(diǎn)和父節(jié)點(diǎn)哪個(gè)大
tempIndex = [array[fatherIndex] integerValue] >= child1 ? fatherIndex : fatherIndex * 2 + 1;
}
// 判斷 最大的是否是 父節(jié)點(diǎn)
if (tempIndex != fatherIndex) {
// 如果不是父節(jié)點(diǎn)
NSString *str = array[tempIndex];
[array replaceObjectAtIndex:tempIndex withObject:array[fatherIndex]];
[array replaceObjectAtIndex:fatherIndex withObject:str];
// 替換完 再判斷被替換的是否還有子節(jié)點(diǎn)
if (tempIndex * 2 + 1 < array.count) {
array = [self heap_sortLoopFatherIndex:tempIndex endIndex:endIndex array:array];
}
}
return array;
}
//循環(huán)建立初始堆
+ (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) {
// 如果有右孩子結(jié)點(diǎn)蚓炬，并且右孩子結(jié)點(diǎn)的值大于左孩子結(jié)點(diǎn)松逊，則選取右孩子結(jié)點(diǎn)
if (childIndex+1 < endIndex && [items[childIndex] floatValue] < [items[childIndex+1] floatValue]) {
childIndex++;
}
// 如果父結(jié)點(diǎn)的值已經(jīng)大于孩子結(jié)點(diǎn)的值，則直接結(jié)束
if ([temp floatValue] >= [items[childIndex] floatValue]) {
break;
}
// 把孩子結(jié)點(diǎn)的值賦給父結(jié)點(diǎn)
items[fatherIndex] = items[childIndex];
fatherIndex = childIndex;
childIndex = 2 * fatherIndex +1;
}
items[fatherIndex] = temp;
return items;
}
5.冒泡排序
/**
冒泡排序
兩兩對(duì)比排序
數(shù)組有n個(gè)元素肯夏， 原則上對(duì)比 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從右到左選第一個(gè)最小经宏，替換
key 從左到右選第一個(gè)最小，替換
先排序基數(shù) key左邊的
再排序基數(shù) 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) {
// 判斷數(shù)組長(zhǎng)度為 0 或者1 時(shí) 跳出循環(huán)
return;
}
NSInteger i = leftIndex;
NSInteger j = rightIndex;
// 記錄基數(shù)
NSInteger key = [array[i]integerValue];
while (i < j) {
// 從右j 開始查找比基數(shù)小的數(shù)
while (i < j && key <= [array[j] integerValue]) {
// 當(dāng)未查找到則繼續(xù)查找
j --;
}
// 如果比基數(shù)小驯击， 替換
array[i] = array[j];
// 開始從左往右查找比基數(shù)大的數(shù)
while (i < j && key >= [array[i] integerValue]) {
// 如果比基數(shù)小 則繼續(xù)查找
i ++;
}
//如果比基數(shù)大則替換
array[j] = array[i];
}
// 將基數(shù)放在正確的位置
array[i] = @(key);
//前面排序
[self quickSortArr:array withLeftIndex:leftIndex andRightIndex:i -1];
//后面排序
[self quickSortArr:array withLeftIndex:i + 1 andRightIndex:rightIndex];
}
7.歸并排序
/**
歸并排序
分成2 個(gè)或者 2 個(gè)以上的表
然后排序成有序表
合并成一個(gè)新的有序表烛恤，然后整合成一個(gè)整體的有序表
*/
+ (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;
}
