1、冒泡排序
原理：重復(fù)地走訪過(guò)要排序的元素列，依次比較兩個(gè)相鄰的元素，如果他們的順序（如從大到小、首字母從A到Z）錯(cuò)誤就把他們交換過(guò)來(lái)。走訪元素的工作是重復(fù)地進(jìn)行直到?jīng)]有相鄰元素需要交換，也就是說(shuō)該元素已經(jīng)排序完成。
#pragma mark - 冒泡降序排序
- (void)bubbleDescendingOrderSortWithArray:(NSMutableArray *)descendingArr
{
for (int i = 0; i < descendingArr.count; i++) {
for (int j = 0; j < descendingArr.count-1-i; j++) {
NSInteger left = [descendingArr[j] integerValue];
NSInteger right = [descendingArr[j+1] integerValue];
if (left<right) {
[descendingArr exchangeObjectAtIndex:j withObjectAtIndex:j+1];
}
}
}
NSLog(@"冒泡降序排序后結(jié)果：%@", descendingArr);
}
#pragma mark - 冒泡升序排序
- (void)bubbleAscendingOrderSortWithArray:(NSMutableArray *)ascendingArr
{
for (int i = 0; i < ascendingArr.count; i++) {
for (int j = 0; j < ascendingArr.count-1-i; j++) {
NSInteger left = [ascendingArr[j] integerValue];
NSInteger right = [ascendingArr[j+1] integerValue];
if (left > right) {
[ascendingArr exchangeObjectAtIndex:j withObjectAtIndex:j+1];
}
}
}
NSLog(@"冒泡升序排序后結(jié)果：%@", ascendingArr);
}
平均時(shí)間復(fù)雜度：O(n^2)
輔助空間：O(1)
算法穩(wěn)定性：相同元素的前后順序不會(huì)發(fā)生改變，所以冒泡排序是一種穩(wěn)定排序算法。
2、選擇排序
原理：它的工作原理是每一次從待排序的數(shù)據(jù)元素中選出最小（或最大）的一個(gè)元素，存放在序列的起始位置，然后，再?gòu)氖Ｓ辔磁判蛟刂欣^續(xù)尋找最小（大）元素，然后放到已排序序列的末尾。以此類推，直到全部待排序的數(shù)據(jù)元素排完。
#pragma mark - 選擇降序排序
- (void)selectionDescendingOrderSortWithArray:(NSMutableArray *)descendingArr
{
for (int i = 0; i < descendingArr.count; i++) {
for (int j = i+1; j < descendingArr.count; j++) {
if ([descendingArr[i] integerValue] < [descendingArr[j] integerValue]) {
[descendingArr exchangeObjectAtIndex:i withObjectAtIndex:j];
}
}
}
NSLog(@"選擇降序排序后結(jié)果：%@", descendingArr);
}
#pragma mark - 選擇升序排序
- (void)selectionAscendingOrderSortWithArray:(NSMutableArray *)ascendingArr
{
for (int i = 0; i < ascendingArr.count; i++) {
for (int j = i+1; j < ascendingArr.count; j++) {
if ([ascendingArr[i] integerValue] > [ascendingArr[j] integerValue]) {
[ascendingArr exchangeObjectAtIndex:i withObjectAtIndex:j];
}
}
}
NSLog(@"選擇升序排序后結(jié)果：%@", ascendingArr);
}
平均時(shí)間復(fù)雜度：O(n^2)
輔助空間：O(1)
算法穩(wěn)定性：穩(wěn)定算法。
3、快速排序
快速排序（Quicksort）是對(duì)冒泡排序的一種改進(jìn)。
通過(guò)一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個(gè)排序過(guò)程可以遞歸進(jìn)行，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列。
#pragma mark - 快速升序排序
- (void)quickAscendingOrderSort:(NSMutableArray *)arr leftIndex:(NSInteger)left rightIndex:(NSInteger)right
{
if (left < right) {
NSInteger temp = [self getMiddleIndex:arr leftIndex:left rightIndex:right];
/**** 遞歸排序 ***/
//排序基準(zhǔn)數(shù)左邊的
[self quickAscendingOrderSort:arr leftIndex:left rightIndex:temp-1];
//排序基準(zhǔn)數(shù)右邊的
[self quickAscendingOrderSort:arr leftIndex:temp+1 rightIndex:right];
}
NSLog(@"快速升序排序結(jié)果：%@", arr);
}
- (NSInteger)getMiddleIndex:(NSMutableArray *)arr leftIndex:(NSInteger)left rightIndex:(NSInteger)right
{
NSInteger tempValue = [arr[left] integerValue]; //記錄基準(zhǔn)數(shù)
while (left < right) {
/**** 首先從右邊right開(kāi)始查找比基準(zhǔn)數(shù)小的值 ***/
while (left < right && tempValue<= [arr[right] integerValue]) {//如果比基準(zhǔn)數(shù)大，繼續(xù)查找
right--;
}
if (left < right) {//如果比基準(zhǔn)數(shù)小，則將查找到的小值調(diào)換到left的位置
arr[left] = arr[right];
}
/**** 當(dāng)在右邊查找到一個(gè)比基準(zhǔn)數(shù)小的值時(shí)，就從left開(kāi)始往后找比基準(zhǔn)數(shù)大的值 ***/
while (left < right && [arr[left] integerValue] <= tempValue) {
left ++;
}
if (left < right) {//如果比基準(zhǔn)數(shù)大，則將查找到的大值調(diào)換到right的位置
arr[right] = arr[left];
}
}
arr[left] = [NSNumber numberWithInteger:tempValue];//將基準(zhǔn)數(shù)放到正確位置
return left;
}
//調(diào)用
NSMutableArray *arr = [NSMutableArray arrayWithObjects:@29,@21,@2,@34,@3,@10,@20,@22,@11,@9,@2,@28,@45,@64,@4, nil];
[self quickAscendingOrderSort:arr leftIndex:0 rightIndex:arr.count-1];
平均時(shí)間復(fù)雜度：O(nlogn)
輔助空間：O(logn)~O(n)
算法穩(wěn)定性：不穩(wěn)定排序算法。
4、插入排序
實(shí)現(xiàn)思路：
- 從第一個(gè)元素開(kāi)始，認(rèn)為該元素已經(jīng)是排好序的。
- 取下一個(gè)元素，在已經(jīng)排好序的元素序列中從后向前掃描。
- 如果已經(jīng)排好序的序列中元素大于新元素，則將該元素往右移動(dòng)一個(gè)位置。
- 重復(fù)步驟3，直到已排好序的元素小于或等于新元素。
- 在當(dāng)前位置插入新元素。
- 重復(fù)步驟2。
#pragma mark - 插入升序排序
- (void)insertionAscendingOrderSort:(NSMutableArray *)ascendingArr
{
for (int i = 1; i < ascendingArr.count; i++) {
NSInteger temp = [ascendingArr[i] integerValue];
for (int j = i-1; j >= 0 && temp < [ascendingArr[j] integerValue]; j--) {
ascendingArr[j+1] = ascendingArr[j];
ascendingArr[j] = [NSNumber numberWithInteger:temp];
}
}
NSLog(@"插入升序排序結(jié)果：%@",ascendingArr);
}
平均時(shí)間復(fù)雜度：O(n^2)
輔助空間：O(1)
算法穩(wěn)定性：穩(wěn)定。
5、堆排序
堆排序(Heap Sort) 就是利用堆(假設(shè)利用大堆頂)進(jìn)行排序的方法。它的基本思想是，將待排序的序列構(gòu)成一個(gè)大頂堆。此時(shí)，整個(gè)序列的最大值就是堆頂?shù)母?jié)點(diǎn)。將它移走(其實(shí)就是將其與堆數(shù)組的末尾元素交換，此時(shí)末尾元素就是最大值)，然后將剩余的n-1個(gè)序列重新構(gòu)造成一個(gè)堆，這樣就會(huì)得到n個(gè)元素中的次小值。如此反復(fù)執(zhí)行，便能得到一個(gè)有序序列了。
#pragma mark - 堆排序
- (void)heapSort:(NSMutableArray *)list
{
NSInteger i ,size;
size = list.count;
//找出最大的元素放到堆頂，構(gòu)建大頂堆
for (i= list.count/2-1; i>=0; i--) {
[self createBiggesHeap:list withSize:size beIndex:i];
}
while(size > 0){
[list exchangeObjectAtIndex:size-1 withObjectAtIndex:0]; //將根(最大) 與數(shù)組最末交換
size -- ;//樹(shù)大小減小
[self createBiggesHeap:list withSize:size beIndex:0];
}
NSLog(@"%@",list);
}
- (void)createBiggesHeap:(NSMutableArray *)list withSize:(NSInteger) size beIndex:(NSInteger)element
{
NSInteger lchild = element *2 + 1,rchild = lchild+1; //左右子樹(shù)
while (rchild < size) { //子樹(shù)均在范圍內(nèi)
if ([list[element] integerValue] >= [list[lchild] integerValue] && [list[element] integerValue] >= [list[rchild]integerValue]) return; //如果比左右子樹(shù)都大，完成整理
if ([list[lchild] integerValue] > [list[rchild] integerValue]) { //如果左邊最大
[list exchangeObjectAtIndex:element withObjectAtIndex:lchild]; //把左面的提到上面
element = lchild; //循環(huán)時(shí)整理子樹(shù)
}else{//否則右面最大
[list exchangeObjectAtIndex:element withObjectAtIndex:rchild];
element = rchild;
}
lchild = element * 2 +1;
rchild = lchild + 1; //重新計(jì)算子樹(shù)位置
}
//只有左子樹(shù)且子樹(shù)大于自己
if (lchild < size && [list[lchild] integerValue] > [list[element] integerValue]) {
[list exchangeObjectAtIndex:lchild withObjectAtIndex:element];
}
}
平均時(shí)間復(fù)雜度：O(nlogn)
輔助空間：O(1)
算法穩(wěn)定性：由于記錄的比較和交換是跳躍式進(jìn)行，因此堆排序也是一種不穩(wěn)定的排序方法。
6、歸并排序
歸并排序(Merging Sort) 就是利用歸并的思想實(shí)現(xiàn)的排序方法。它的原理是假設(shè)初始序列含有n個(gè)記錄，則可以看成是n個(gè)有序的子序列，每個(gè)子序列的長(zhǎng)度為1，然后兩兩歸并，得到n/2個(gè)長(zhǎng)度為2或者1的有序子序列；再兩兩歸并，......，如此反復(fù)，直到得到一個(gè)長(zhǎng)度為n的有序序列為止，這種排序方法稱為歸并排序。
#pragma mark - 歸并升序排序
- (void)megerSortAscendingOrderSort:(NSMutableArray *)ascendingArr
{
//tempArray數(shù)組里存放ascendingArr.count個(gè)數(shù)組，每個(gè)數(shù)組包含一個(gè)元素
NSMutableArray *tempArray = [NSMutableArray arrayWithCapacity:1];
for (NSNumber *num in ascendingArr) {
NSMutableArray *subArray = [NSMutableArray array];
[subArray addObject:num];
[tempArray addObject:subArray];
}
//開(kāi)始合并為一個(gè)數(shù)組
while (tempArray.count != 1) {
NSInteger i = 0;
while (i < tempArray.count - 1) {
tempArray[i] = [self mergeArrayFirstList:tempArray[i] secondList:tempArray[i + 1]];
[tempArray removeObjectAtIndex:i + 1];
I++;
}
}
NSLog(@"歸并升序排序結(jié)果：%@", tempArray[0]);
}
- (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;
}
平均時(shí)間復(fù)雜度：O(nlogn)
輔助空間：O(n)
算法穩(wěn)定性：因?yàn)槭莾蓛杀容^，不存在跳躍，因此是一種穩(wěn)定的排序算法。雖然占用內(nèi)存比較多，但卻是一種效率高的算法。
7、希爾排序
希爾排序在插入排序的基礎(chǔ)上增加一個(gè)叫增量的概念。那什么增量？插入排序只能與相鄰的元素進(jìn)行比較，而希爾排序則是進(jìn)行跳躍比較，而增量就是步長(zhǎng)。比如增量為3時(shí)，下標(biāo)為0的元素與下標(biāo)為3的元素比較，3再與6比較，1與4比較，4再與7比較……比較完后，再去減少增量，重復(fù)之前步驟，直到增量為1，此時(shí)只有一個(gè)分組了，再對(duì)這一個(gè)分組進(jìn)行插入排序，整個(gè)希爾排序就結(jié)束了。
#pragma mark - 希爾排序
-(void)shellSort:(NSMutableArray *)list{
int gap = (int)list.count / 2;//起始間隔值gap設(shè)置為總數(shù)的一半，直到gap==1結(jié)束
while (gap >= 1) {
for(int i = gap ; i < [list count]; i++){
NSInteger temp = [[list objectAtIndex:i] intValue];
int j = I;
while (j >= gap && temp < [[list objectAtIndex:(j - gap)] intValue]) {
[list replaceObjectAtIndex:j withObject:[list objectAtIndex:j-gap]];
j -= gap;
}
[list replaceObjectAtIndex:j withObject:[NSNumber numberWithInteger:temp]];
}
gap = gap / 2;
}
NSLog(@"希爾升序排序結(jié)果：%@", list);
}
平均時(shí)間復(fù)雜度：O(nlogn)~O(n^2)
輔助空間：O(1)
算法穩(wěn)定性：由于記錄是跳躍式的移動(dòng)，希爾排序并不是一種穩(wěn)定的排序算法。
8、基數(shù)排序
基數(shù)排序(Radix Sort)是根據(jù)關(guān)鍵字中各位的值，通過(guò)對(duì)排序的N個(gè)元素進(jìn)行若干趟“分配”與“收集”來(lái)實(shí)現(xiàn)排序的。
#pragma mark - 基數(shù)排序
- (void)radixSort:(NSMutableArray *)ascendingArr
{
/**
基于LSD方法的鏈?zhǔn)交鶖?shù)排序的基本思想
“多關(guān)鍵字排序”的思想實(shí)現(xiàn)“單關(guān)鍵字排序”。對(duì)數(shù)字型或字符型的單關(guān)鍵字，可以看作由多個(gè)數(shù)位或多個(gè)字符構(gòu)成的多關(guān)鍵字，此時(shí)可以采用“分配-收集”的方法進(jìn)行排序，這一過(guò)程稱作基數(shù)排序法，其中每個(gè)數(shù)字或字符可能的取值個(gè)數(shù)稱為基數(shù)。比如，撲克牌的花色基數(shù)為4，面值基數(shù)為13。在整理?yè)淇伺茣r(shí)，既可以先按花色整理，也可以先按面值整理。按花色整理時(shí)，先按紅、黑、方、花的順序分成4摞（分配），再按此順序再疊放在一起（收集），然后按面值的順序分成13摞（分配），再按此順序疊放在一起（收集），如此進(jìn)行二次分配和收集即可將撲克牌排列有序。
基數(shù)排序:
是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次類推，直到最高位。有時(shí)候有些屬性是有優(yōu)先級(jí)順序的，先按低優(yōu)先級(jí)排序，再按高優(yōu)先級(jí)排序。最后的次序就是高優(yōu)先級(jí)高的在前，高優(yōu)先級(jí)相同的低優(yōu)先級(jí)高的在前?；鶖?shù)排序基于分別排序，分別收集，所以是穩(wěn)定的。
*/
//創(chuàng)建空桶
NSMutableArray *buckt = [self createBucket];
//待排數(shù)組的最大數(shù)值
NSNumber *maxnumber = [self listMaxItem:ascendingArr];
//最大數(shù)值的數(shù)字位數(shù)
NSInteger maxLength = numberLength(maxnumber);
// 按照從低位到高位的順序執(zhí)行排序過(guò)程
for (int digit = 1; digit <= maxLength; digit++) {
// 入桶
for (NSNumber *item in ascendingArr) {
//確定item 歸屬哪個(gè)桶 以digit位數(shù)為基數(shù)
NSInteger baseNumber = [self fetchBaseNumber:item digit:digit];
NSMutableArray *mutArray = buckt[baseNumber];
//將數(shù)據(jù)放入空桶上
[mutArray addObject:item];
}
NSInteger index = 0;
//出桶
for (int i = 0; i < buckt.count; i++) {
NSMutableArray *array = buckt[i];
//將桶的數(shù)據(jù)放回待排數(shù)組中
while (array.count != 0) {
NSNumber *number = [array objectAtIndex:0];
ascendingArr[index] = number;
[array removeObjectAtIndex:0];
index++;
}
}
}
NSLog(@"基數(shù)升序排序結(jié)果：%@", ascendingArr);
}
//創(chuàng)建空桶，每個(gè)桶里都是數(shù)組
- (NSMutableArray *)createBucket {
NSMutableArray *bucket = [NSMutableArray array];
for (int index = 0; index < 10; index++) {//數(shù)字0~9
NSMutableArray *array = [NSMutableArray array];
[bucket addObject:array];
}
return bucket;
}
//數(shù)據(jù)最大值
- (NSNumber *)listMaxItem:(NSArray *)list {
NSNumber *maxNumber = list[0];
for (NSNumber *number in list) {
if ([maxNumber integerValue] < [number integerValue]) {
maxNumber = number;
}
}
return maxNumber;
}
//數(shù)字的位數(shù)
NSInteger numberLength(NSNumber *number) {
NSString *string = [NSString stringWithFormat:@"%ld", (long)[number integerValue]];
return string.length;
}
- (NSInteger)fetchBaseNumber:(NSNumber *)number digit:(NSInteger)digit {
//digit為基數(shù)位數(shù)
if (digit > 0 && digit <= numberLength(number)) {
NSMutableArray *numbersArray = [NSMutableArray array];
//number的位數(shù)確定
NSString *string = [NSString stringWithFormat:@"%ld", [number integerValue]];
for (int index = 0; index < numberLength(number); index++) {
[numbersArray addObject:[string substringWithRange:NSMakeRange(index, 1)]];
}
//number的位數(shù)是幾位數(shù)的
NSString *str = numbersArray[numbersArray.count - digit];
return [str integerValue];
}
return 0;
}
時(shí)間復(fù)雜度：假設(shè)在基數(shù)排序中，r為基數(shù)，d為位數(shù)。則基數(shù)排序的時(shí)間復(fù)雜度為O(d(n+r))。我們可以看出，基數(shù)排序的效率和初始序列是否有序沒(méi)有關(guān)聯(lián)。
空間復(fù)雜度：在基數(shù)排序過(guò)程中，對(duì)于任何位數(shù)上的基數(shù)進(jìn)行“裝桶”操作時(shí)，都需要n+r個(gè)臨時(shí)空間。
算法穩(wěn)定性：是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次類推，直到最高位。有時(shí)候有些屬性是有優(yōu)先級(jí)順序的，先按低優(yōu)先級(jí)排序，再按高優(yōu)先級(jí)排序。最后的次序就是高優(yōu)先級(jí)高的在前，高優(yōu)先級(jí)相同的低優(yōu)先級(jí)高的在前?；鶖?shù)排序基于分別排序，分別收集，所以是穩(wěn)定的。
參考：
http://www.itdecent.cn/p/97cdc7135773
https://www.cnblogs.com/ZachRobin/p/7094852.html
http://www.itdecent.cn/p/b59df9d0a169
http://www.itdecent.cn/p/fe271bc3e544
http://www.itdecent.cn/p/c74dd2954b8e
http://www.itdecent.cn/p/43de49cd23e6
