前言
在開(kāi)發(fā)中耕陷，也許算法很少用到掂名，但是面試的時(shí)候被面試官問(wèn)到算法方面的知識(shí)，就一臉懵逼了哟沫！這里整理了一些排序算法：冒泡排序饺蔑，冒泡排序(倒序)，快速排序嗜诀，直接插入排序膀钠，二分排序，希爾排序裹虫，堆排序肿嘲，選擇排序，歸并排序筑公。希望能幫到一些人雳窟，大牛就可以忽略了，有什么不足的地方匣屡，還請(qǐng)大牛們多多指教封救！
冒泡排序
對(duì)數(shù)組中每個(gè)位置的數(shù)據(jù)，從后往前推捣作，依次比較相鄰的兩個(gè)數(shù)誉结，如果后面的數(shù)較小，則交換兩者位置券躁，如果一次遍歷沒(méi)有發(fā)生任何數(shù)據(jù)交換惩坑，則排序直接完成。
+ (void)bubbleSort:(NSMutableArray *)list {
if (!list.count) {
return;
}
BOOL bFinish = YES;//是否發(fā)生數(shù)據(jù)交換
for (int i = 1; i <= list.count && bFinish; i ++) {
bFinish = NO;//每次遍歷時(shí)也拜，重置標(biāo)志
//從最后一位開(kāi)始以舒，依次跟前一位相比，如果較小慢哈，則交換位置
//當(dāng)一次遍歷沒(méi)有任何數(shù)據(jù)交換時(shí)蔓钟，則說(shuō)明已經(jīng)排序完成(bFinish=YES)，則不再進(jìn)行循環(huán)
for (int y = (int)list.count - 1; y >= i; y --) {
if ([[list objectAtIndex:y] intValue] < [[list objectAtIndex:y-1] intValue]) {
//交換位置
NSLog(@"%d<->%d",[[list objectAtIndex:y - 1] intValue],[[list objectAtIndex:y] intValue]);
[list exchangeObjectAtIndex:y - 1 withObjectAtIndex:y];
bFinish = YES;//發(fā)生數(shù)據(jù)交換卵贱，則繼續(xù)進(jìn)行下一次遍歷滥沫，直到未發(fā)生數(shù)據(jù)交換或者循環(huán)完成為止
NSLog(@"sortList == %@",[list componentsJoinedByString:@" "]);
}
}
}
NSLog(@"冒泡排序 == %@",list);
}
冒泡排序(倒序)
對(duì)數(shù)組中每個(gè)位置的數(shù)據(jù)侣集，從后往前推，依次比較相鄰的兩個(gè)數(shù)兰绣，如果后面的數(shù)較大肚吏，則交換兩者位置，如果一次遍歷沒(méi)有發(fā)生任何數(shù)據(jù)交換狭魂，則排序直接完成罚攀。
+ (void)bubbleSortDesc:(NSMutableArray *)list {
if (!list.count) {
return;
}
BOOL bFinish = YES;//是否發(fā)生數(shù)據(jù)交換
for (int i = 1; i <= list.count && bFinish; i ++) {
bFinish = NO;//每次遍歷時(shí)，重置標(biāo)志
//從最后一位開(kāi)始雌澄，依次跟前一位相比斋泄，如果較大，則交換位置
//當(dāng)一次遍歷沒(méi)有任何數(shù)據(jù)交換時(shí)镐牺，則說(shuō)明已經(jīng)排序完成(bFinish=YES)炫掐，則不再進(jìn)行循環(huán)
for (int y = (int)list.count - 1; y >= i; y --) {
if ([[list objectAtIndex:y] intValue] > [[list objectAtIndex:y-1] intValue]) {
//交換位置
NSLog(@"%d<->%d",[[list objectAtIndex:y - 1] intValue],[[list objectAtIndex:y] intValue]);
[list exchangeObjectAtIndex:y - 1 withObjectAtIndex:y];
bFinish = YES;//發(fā)生數(shù)據(jù)交換，則繼續(xù)進(jìn)行下一次遍歷睬涧，直到未發(fā)生數(shù)據(jù)交換或者循環(huán)完成為止
NSLog(@"sortList == %@",[list componentsJoinedByString:@" "]);
}
}
}
NSLog(@"冒泡排序(倒序) == %@",list);
}
快速排序
任意選取一個(gè)數(shù)據(jù)（通常選用數(shù)組的第一個(gè)數(shù)）作為關(guān)鍵數(shù)據(jù)募胃，然后將所有比它小的數(shù)都放到它前面，所有比它大的數(shù)都放到它后面畦浓，再分別對(duì)兩邊的數(shù)據(jù)進(jìn)行快速排序痹束。
+ (void)quickSort:(NSMutableArray *)list {
if (!list.count) {
return;
}
[self quickSort:list startIndex:0 endIndex:list.count - 1];
NSLog(@"快速排序 == %@",list);
}
+ (void)quickSort:(NSMutableArray *)list startIndex:(NSInteger)start endIndex:(NSInteger)end {
if (start > end) {
return;//低位大于高位，排序結(jié)束
}
NSInteger low = start;
NSInteger high = end;
NSInteger key = [[list objectAtIndex:start] integerValue];//取第一個(gè)數(shù)作為關(guān)鍵數(shù)據(jù)
while (low < high) {
//從后往前推讶请，直到找到第一個(gè)比關(guān)鍵數(shù)據(jù)小的值
while ([[list objectAtIndex:high] integerValue] >= key && low < high) {
high --;
}
//將這個(gè)值與關(guān)鍵數(shù)據(jù)對(duì)調(diào)（關(guān)鍵數(shù)據(jù)處于low位置）祷嘶，對(duì)調(diào)完關(guān)鍵數(shù)據(jù)處于high位置
[list exchangeObjectAtIndex:low withObjectAtIndex:high];
//從前往后推，直到找到第一個(gè)比關(guān)鍵數(shù)據(jù)大的值
while ([[list objectAtIndex:low] integerValue] <= key && low < high) {
low ++;
}
//將這個(gè)值與關(guān)鍵數(shù)據(jù)（關(guān)鍵數(shù)據(jù)已經(jīng)處于high位置）對(duì)調(diào)夺溢，對(duì)調(diào)完關(guān)鍵數(shù)據(jù)處于low位置
[list exchangeObjectAtIndex:high withObjectAtIndex:low];
}
//對(duì)關(guān)鍵數(shù)據(jù)前面的數(shù)據(jù)進(jìn)行快速排序
[self quickSort:list startIndex:start endIndex:low - 1];
//對(duì)關(guān)鍵數(shù)據(jù)后面的數(shù)據(jù)進(jìn)行快速排序
[self quickSort:list startIndex:low + 1 endIndex:end];
}
直接插入排序
把待排序的紀(jì)錄按其關(guān)鍵碼值的大小逐個(gè)插入到一個(gè)已經(jīng)排好序的有序序列中论巍，直到所有的紀(jì)錄插入完為止。
+ (void)insertionSort:(NSMutableArray *)list {
if (!list.count) {
return;
}
//從第1位開(kāi)始风响，依次將數(shù)組分成2部分：前一部分可以視為已經(jīng)排好序的嘉汰，后一部分是未排序的
//對(duì)后一部分的數(shù)據(jù)依次遍歷，插入到前一部分中的合適位置
for (int i = 0; i < list.count; i ++) {
int j = i;
//待排序的數(shù)（是未排序部分的第1個(gè)數(shù)状勤，它的上一位數(shù)就是已經(jīng)排序的部分的最后一位數(shù)）
NSInteger temp = [[list objectAtIndex:i] integerValue];
//從已排序部分的最后一位開(kāi)始依次往前推鞋怀，如果比待排序的數(shù)大，則將其位置往后移一位
while (j > 0 && [[list objectAtIndex:j -1] integerValue] > temp) {
[list replaceObjectAtIndex:j withObject:[list objectAtIndex:j - 1]];
j --;
}
//循環(huán)結(jié)束后的j即為待排序的數(shù)需要插入的位置
[list replaceObjectAtIndex:j withObject:@(temp)];
}
NSLog(@"直接插入排序 == %@",list);
}
二分排序
從第1位開(kāi)始荧降，依次將數(shù)組分成2部分：前一部分可以視為已經(jīng)排好序的接箫，后一部分是未排序的,對(duì)后一部分的數(shù)據(jù)依次遍歷攒读，插入到前一部分中的合適位置朵诫。
+ (void)binaryInsertionSort:(NSMutableArray *)list {
if (!list.count) {
return;
}
for (int i = 0; i < list.count; i ++) {
int left = 0;
int right = i - 1;
int middle;
//待排序的數(shù)（是未排序部分的第1個(gè)數(shù)，它的上一位數(shù)就是已經(jīng)排序的部分的最后一位數(shù)）
NSInteger temp = [[list objectAtIndex:i] integerValue];
while (left <= right) {
//每次從已經(jīng)排序的部分中取中間位置的數(shù)進(jìn)行比較
middle = (left+right)/2;
//如果跟待排序數(shù)相等薄扁，則直接插入到此位置即可
if ([[list objectAtIndex:middle] integerValue] == temp) {
left = middle;
break;
}
//如果比待排序數(shù)大剪返，則從中間位置左邊范圍內(nèi)再次取中間數(shù)查找（下一循環(huán)）
else if ([[list objectAtIndex:middle] integerValue] > temp) {
right = middle - 1;
}
//如果比待排序數(shù)小废累，則從中間位置右邊范圍再次取中間數(shù)查找（下一循環(huán)）
else {
left = middle + 1;
}
}
//循環(huán)結(jié)束，找到待插入位置left
//依次將left右邊（比left位置數(shù)據(jù)都大）的數(shù)據(jù)向右移動(dòng)一位
for (int j = i; j > left; j --) {
[list replaceObjectAtIndex:j withObject:[list objectAtIndex:j - 1]];
}
//在left位置插入待排序數(shù)
[list replaceObjectAtIndex:left withObject:@(temp)];
}
NSLog(@"二分排序 == %@",list);
}
希爾排序
先取一個(gè)正整數(shù)d1<n脱盲，把所有序號(hào)相隔d1的數(shù)組元素放一組邑滨，組內(nèi)進(jìn)行直接插入排序；然后取d2<d1钱反，重復(fù)上述分組和排序操作掖看；直至di=1，即所有記錄放進(jìn)一個(gè)組中排序?yàn)橹埂?/p>
+ (void)shellInsertionSort:(NSMutableArray *)list {
if (!list.count) {
return;
}
NSInteger delt = list.count / 2;//增量：取數(shù)組長(zhǎng)度一半面哥，以后每次減半哎壳，直到增量為1
NSInteger i;
while (delt > 1) {
//對(duì)位置距離=增量的組分別進(jìn)行直接插入排序
for (i = delt; i < list.count; i ++) {
NSInteger j = i;
//待排序的數(shù)
NSInteger temp = [[list objectAtIndex:i] integerValue];
//從已排序部分的最后一位開(kāi)始依次往前推(間隔=增量)，如果比待排序的數(shù)大尚卫，則將其位置往后移“增量”位
while (j > delt && [[list objectAtIndex:j-delt] integerValue] > temp) {
[list replaceObjectAtIndex:j withObject:[list objectAtIndex:j-delt]];
j -= delt;//按增量遞推
}
//循環(huán)結(jié)束后的j即為待排序的數(shù)需要插入的位置
[list replaceObjectAtIndex:j withObject:@(temp)];
}
delt = delt/2;//增量：每次減半
}
NSLog(@"希爾排序 == %@",list);
}
堆排序
利用堆的特性（堆頂肯定是最大或者最小值）归榕，將堆頂數(shù)據(jù)與堆尾數(shù)據(jù)交換（相當(dāng)于刪除堆頂數(shù)據(jù)并保存到堆尾），再重新構(gòu)造堆吱涉，直到堆中只剩下1個(gè)數(shù)據(jù)刹泄。
+ (void)heapSort:(NSMutableArray *)list {
if (!list.count) {
return;
}
NSInteger i;
//初始化堆，取父節(jié)點(diǎn)和左右子節(jié)點(diǎn)中最大（或者最性蹙簟）值作為堆頂
//因?yàn)槎压?jié)點(diǎn)i的葉子節(jié)點(diǎn)是2*i+1特石，因此初始化是從length/2-1處開(kāi)始整理堆即可
for (i = list.count/2 - 1; i >= 0; i --) {
[self heapAdjust:list withIndex:i andLength:list.count];
}
NSLog(@"構(gòu)造堆== %@",[list componentsJoinedByString:@" "]);
//整理完堆后，第0位數(shù)肯定是最大（或者最斜盍础）值县匠，將它跟第n-1位交換，相當(dāng)于從堆中刪除第0位撒轮，再對(duì)剩下的數(shù)據(jù)重新整理堆
//依次執(zhí)行上述交換操作乞旦，直到只剩下1個(gè)數(shù)
for (i = list.count - 1; i > 0; i --) {
[list exchangeObjectAtIndex:0 withObjectAtIndex:i];
[self heapAdjust:list withIndex:0 andLength:i];
NSLog(@"構(gòu)造堆== %@",[list componentsJoinedByString:@" "]);
}
NSLog(@"堆排序 == %@",list);
}
/**
* 構(gòu)造堆（最大堆）
*
*
* @param list 待整理的數(shù)組
* @param index 待整理的位置
* @param length 待整理的數(shù)組的長(zhǎng)度（這里因?yàn)榇判虻臄?shù)據(jù)和已排序的數(shù)據(jù)共用了一個(gè)數(shù)組）
*/
+ (void)heapAdjust:(NSMutableArray *)list withIndex:(NSInteger)index andLength:(NSInteger)length {
//左子節(jié)點(diǎn)，右子節(jié)點(diǎn)為rChild+1
NSInteger rChild = index*2 + 1;
while (rChild < length) {
//判斷是否有右子節(jié)點(diǎn)题山，如果有則判斷右子節(jié)點(diǎn)是否比左節(jié)點(diǎn)大兰粉，如果比左節(jié)點(diǎn)大則用右子節(jié)點(diǎn)于父節(jié)點(diǎn)進(jìn)行比較
if (rChild + 1 < length && [[list objectAtIndex:rChild + 1] integerValue] > [[list objectAtIndex:rChild] integerValue]) {
rChild ++;//++表示將左節(jié)點(diǎn)位置移到右節(jié)點(diǎn)位置,為的是下面跟父節(jié)點(diǎn)進(jìn)行比較
}
//如果父節(jié)點(diǎn)比子節(jié)點(diǎn)小，則說(shuō)明本身就是一個(gè)堆顶瞳，無(wú)需再整理
if ([[list objectAtIndex:rChild] integerValue] < [[list objectAtIndex:index] integerValue]) {
break;
}
//交換父節(jié)點(diǎn)和子節(jié)點(diǎn)的值（將父節(jié)點(diǎn)下沉）
[list exchangeObjectAtIndex:index withObjectAtIndex:rChild];
//父節(jié)點(diǎn)位置下沉到子節(jié)點(diǎn)的位置玖姑，再繼續(xù)整理下面的堆
index = rChild;
rChild = index*2 + 1;
}
}
選擇排序
每一次從待排序的數(shù)據(jù)元素中選出最小（或最大）的一個(gè)元素慨菱，存放在序列的起始位置焰络，直到全部待排序的數(shù)據(jù)元素排完。
+ (void)selectSort:(NSMutableArray *)list {
if (!list.count) {
return;
}
//從第0位開(kāi)始排序符喝，直到最后一位（最后一位無(wú)需再排序）
for (NSInteger i = 0; i < list.count; i ++) {
NSInteger j = i;//記錄當(dāng)前位置闪彼，作為對(duì)比的關(guān)鍵元素
//依次遍歷后面的元素
for (NSInteger k = i + 1; k < list.count; k ++) {
//如果元素比關(guān)鍵元素小，則將關(guān)鍵元素位置指向此位置，再繼續(xù)遍歷
if ([[list objectAtIndex:k] integerValue] < [[list objectAtIndex:j] integerValue]) {
j = k;
}
}
//遍歷結(jié)束后畏腕，得到最小元素位置j缴川，如果不是初始位置，則交換2個(gè)位置的值
if (i != j) {
[list exchangeObjectAtIndex:i withObjectAtIndex:j];
}
}
NSLog(@"選擇排序 == %@",list);
}
歸并排序
將數(shù)組分割成2部分描馅，使左右2部分都有序把夸，再合并成一個(gè)，為了使左右2部分都有序铭污，可通過(guò)遞歸的方式恋日，再對(duì)其進(jìn)行分割，直至分割后只剩1個(gè)元素嘹狞，可以視其為已經(jīng)有序的谚鄙，再將左右2部分進(jìn)行合并，合并時(shí)刁绒，分別從2部分中取第0個(gè)數(shù)進(jìn)行比較闷营，將較小（或者較大）的數(shù)保存到臨時(shí)數(shù)組里知市，再用下一個(gè)數(shù)和上次比較中較大者進(jìn)行比較傻盟，直到某一邊沒(méi)有數(shù)據(jù)，再將另外一邊中剩余的數(shù)復(fù)制到臨時(shí)數(shù)組里嫂丙，最后生成的臨時(shí)數(shù)組就是已經(jīng)排好序的結(jié)果娘赴。
+ (void)mergeSort:(NSMutableArray *)list {
if (!list.count) {
return;
}
[self mergeSort:list startIndex:0 endIndex:list.count - 1];
NSLog(@"歸并排序 == %@",list);
}
+ (void)mergeSort:(NSMutableArray *)list startIndex:(NSInteger)startIndex endIndex:(NSInteger)endIndex {
if (startIndex < endIndex) {
//取中間位置，將左右兩邊分別遞歸進(jìn)行歸并跟啤，直至左右兩邊只剩1個(gè)元素
NSInteger middle = (startIndex + endIndex)/2;
[self mergeSort:list startIndex:startIndex endIndex:middle];
[self mergeSort:list startIndex:middle + 1 endIndex:endIndex];
//對(duì)左右2邊的數(shù)據(jù)進(jìn)行合并
NSInteger i = startIndex;//左邊數(shù)據(jù)的起始位置
NSInteger j = middle + 1;//右邊數(shù)據(jù)的起始位置
NSMutableArray *temp = [NSMutableArray array];//臨時(shí)數(shù)組
while (i <= middle && j <= endIndex) {
//如果左邊數(shù)據(jù)較小诽表，則將其放到臨時(shí)數(shù)組里，并將左邊位置向后移一位
if ([[list objectAtIndex:i] integerValue] < [[list objectAtIndex:j] integerValue]) {
[temp addObject:[list objectAtIndex:i]];
i ++;
}
//否則將右邊數(shù)據(jù)放到臨時(shí)數(shù)組里隅肥，并將右邊位置向后移一位
else {
[temp addObject:[list objectAtIndex:j]];
j ++;
}
}
//如果左邊還有數(shù)據(jù)竿奏，則將剩余的部分全都復(fù)制到臨時(shí)數(shù)組里
while (i <= middle) {
[temp addObject:[list objectAtIndex:i]];
i ++;
}
//如果右邊還有數(shù)據(jù)（左右兩邊只可能存在一邊有剩余數(shù)據(jù)的情況），則將剩余的部分全都復(fù)制到臨時(shí)數(shù)組里
while (j <= endIndex) {
[temp addObject:[list objectAtIndex:j]];
j ++;
}
//再將臨時(shí)數(shù)組里的數(shù)據(jù)（已經(jīng)排好序了）保存到原始數(shù)據(jù)中腥放，以達(dá)到對(duì)原始數(shù)據(jù)的排序
for (i = 0; i < temp.count; i ++) {
//注意：需要從startIndex位置開(kāi)始泛啸，因?yàn)檫@里是遞歸調(diào)用的
[list replaceObjectAtIndex:startIndex withObject:[temp objectAtIndex:i]];
startIndex ++;
}
}
}
后序
下面來(lái)看一下結(jié)果，當(dāng)然秃症，這個(gè)大家都知道"+"方法如何調(diào)用(忽略我類(lèi)名寫(xiě)的搓)候址。
打印結(jié)果：
