如果你交給某人一個(gè)程序，你將“折磨”他一整天；如果你教某人如何編寫(xiě)程序钞诡，你將“折磨”他一輩子。——《大話數(shù)據(jù)結(jié)構(gòu)》
這陣子抽空看了一些算法與數(shù)據(jù)結(jié)構(gòu)相關(guān)的東西臭增，不得不說(shuō)算法數(shù)據(jù)結(jié)構(gòu)這些思想真的是博大精深，作為 iOS 開(kāi)發(fā)人員竹习，為什么要學(xué)習(xí)算法誊抛？說(shuō)實(shí)話很多開(kāi)發(fā)人員可能不會(huì)算法，但照樣能做 App整陌，有位大家都熟悉的大神在幾個(gè)月前寫(xiě)了篇文章拗窃，我也是無(wú)意間讀到的，搞 iOS 的學(xué)算法有意義嗎泌辫？随夸，大家有興趣的話可以去讀讀。
這兩天看了八大排序算法震放，并試著用 OC 語(yǔ)言寫(xiě)了幾種宾毒，給大家分享下！
算法一：冒泡排序
個(gè)人覺(jué)得冒泡排序是最簡(jiǎn)單的排序了
#pragma mark - 冒泡排序
+ (void)bubbleSort:(NSMutableArray *)mutableArray {
if(mutableArray == nil || mutableArray.count == 0)
return;
NSLog(@"冒泡排序之前: %@", mutableArray);
for (NSInteger i = 0; i < mutableArray.count; i++) {
for (NSInteger j = 0; j < mutableArray.count - i - 1; j++) {
if ([mutableArray[j + 1] floatValue] < [mutableArray[j] floatValue]) {
CGFloat tempFloat = [mutableArray[j] floatValue];
mutableArray[j] = mutableArray[j + 1];
mutableArray[j + 1] = [NSNumber numberWithFloat:tempFloat];
}
}
}
NSLog(@"冒泡排序之后: %@", mutableArray);
}
- 算法步驟：
1）比較相鄰的元素殿遂。如果第一個(gè)比第二個(gè)大诈铛，就交換他們兩個(gè)。
2）對(duì)每一對(duì)相鄰元素作同樣的工作墨礁，從開(kāi)始第一對(duì)到結(jié)尾的最后一對(duì)幢竹。這步做完后，最后的元素會(huì)是最大的數(shù)恩静。
3）針對(duì)所有的元素重復(fù)以上的步驟焕毫，除了最后一個(gè)。
4）持續(xù)每次對(duì)越來(lái)越少的元素重復(fù)上面的步驟驶乾，直到?jīng)]有任何一對(duì)數(shù)字需要比較邑飒。
算法二：直接插入排序
#pragma mark - 直接插入排序
+ (void)insertSort:(NSMutableArray *)mutableArray {
if(mutableArray == nil || mutableArray.count == 0)
return;
NSLog(@"直接插入排序之前: %@", mutableArray);
for (NSInteger i = 0; i < mutableArray.count; i++) {
CGFloat tempFloat = [mutableArray[i] floatValue];
for (NSInteger j = i - 1; j >= 0 && tempFloat < [mutableArray[j] floatValue]; j--) {
mutableArray[j + 1] = mutableArray[j];
mutableArray[j] = [NSNumber numberWithFloat:tempFloat];
}
}
NSLog(@"直接插入排序之后: %@", mutableArray);
}
- 算法步驟：
1）將第一待排序序列第一個(gè)元素看做一個(gè)有序序列，把第二個(gè)元素到最后一個(gè)元素當(dāng)成是未排序序列级乐。
2）從頭到尾依次掃描未排序序列幸乒，將掃描到的每個(gè)元素插入有序序列的適當(dāng)位置。（如果待插入的元素與有序序列中的某個(gè)元素相等唇牧，則將待插入元素插入到相等元素的后面罕扎。）
算法三：選擇排序
#pragma mark - 選擇排序
+ (void)chooseSort:(NSMutableArray *)mutableArray {
if(mutableArray == nil || mutableArray.count == 0)
return;
NSLog(@"選擇排序之前: %@", mutableArray);
for (NSInteger i = 0; i < mutableArray.count; i++) {
for (NSInteger j = i + 1; j < mutableArray.count; j++) {
if ([mutableArray[i] floatValue] > [mutableArray[j] floatValue]) {
CGFloat tempFloat = [mutableArray[i] floatValue];
mutableArray[i] = mutableArray[j];
mutableArray[j] = [NSNumber numberWithFloat:tempFloat];
}
}
}
NSLog(@"選擇排序之后: %@", mutableArray);
}
- 算法步驟：
1）首先在未排序序列中找到最小（大）元素丐重，存放到排序序列的起始位置
2）再?gòu)氖Ｓ辔磁判蛟刂欣^續(xù)尋找最星徽佟（大）元素，然后放到已排序序列的末尾扮惦。
3）重復(fù)第二步臀蛛，直到所有元素均排序完畢憎夷。
算法四：折半插入排序
#pragma mark - 折半插入排序
+ (void)binaryInsertSort:(NSMutableArray *)mutableArray {
if(mutableArray == nil || mutableArray.count == 0)
return;
NSLog(@"折半插入排序之前: %@", mutableArray);
for(NSInteger i = 1 ; i < mutableArray.count ; i++) {
CGFloat tempFloat = [[mutableArray objectAtIndex:i] floatValue];
NSInteger left = 0;
NSInteger right = i - 1;
while (left <= right) {
CGFloat middle = (left + right) / 2;
if(tempFloat < [[mutableArray objectAtIndex:middle] floatValue]){
right = middle - 1;
} else {
left = middle + 1;
}
}
for(NSInteger j = i ; j > left; j--) {
[mutableArray replaceObjectAtIndex:j withObject:[mutableArray objectAtIndex:j - 1]];
}
[mutableArray replaceObjectAtIndex:left withObject:[NSNumber numberWithFloat:tempFloat]];
}
NSLog(@"折半插入排序之后: %@", mutableArray);
}
- 折半插入排序是對(duì)插入排序算法的一種改進(jìn)别瞭，排序算法過(guò)程，就是不斷的依次將元素插入前面已排好序的序列中。
算法五：希爾排序
#pragma mark - 希爾排序
+ (void)shellSort:(NSMutableArray *)mutableArray {
if(mutableArray == nil || mutableArray.count == 0)
return;
NSLog(@"希爾排序之前: %@", mutableArray);
NSInteger shellValue = mutableArray.count / 2;
while (shellValue >= 1) {
for(NSInteger i = shellValue; i < mutableArray.count; i++) {
CGFloat tempFloat = [[mutableArray objectAtIndex:i] floatValue];
NSInteger j = i;
while (j >= shellValue && tempFloat < [[mutableArray objectAtIndex:(j - shellValue)] floatValue]) {
[mutableArray replaceObjectAtIndex:j withObject:[mutableArray objectAtIndex:j - shellValue]];
j -= shellValue;
}
[mutableArray replaceObjectAtIndex:j withObject:[NSNumber numberWithFloat:tempFloat]];
}
shellValue = shellValue / 2;
}
NSLog(@"希爾排序之后: %@", mutableArray);
}
- 算法步驟：
1）選擇一個(gè)增量序列t1饮焦，t2，…遍膜，tk爵赵，其中ti>tj，tk=1洲劣；
2）按增量序列個(gè)數(shù)k备蚓，對(duì)序列進(jìn)行k 趟排序；
3）每趟排序囱稽，根據(jù)對(duì)應(yīng)的增量ti郊尝，將待排序列分割成若干長(zhǎng)度為m 的子序列，分別對(duì)各子表進(jìn)行直接插入排序战惊。僅增量因子為1 時(shí)流昏，整個(gè)序列作為一個(gè)表來(lái)處理，表長(zhǎng)度即為整個(gè)序列的長(zhǎng)度吞获。
排序算法就先總結(jié)到這里横缔，需要看代碼打印效果的童鞋可以到這里下載代碼：代碼傳送門(mén)
另外分享一篇很不錯(cuò)的博文，八大排序算法衫哥，下面是各種排序算法的時(shí)間復(fù)雜度空間復(fù)雜度以及穩(wěn)定性的展示圖表：
圖片來(lái)自博文八大排序算法
