iOS中常用的排序方法有（冒泡装悲、選擇昏鹃、快速、插入诀诊、希爾洞渤、歸并、基數(shù)）
接下來就依次介紹一下畏梆，直接上代碼
1结借、冒泡排序：
冒泡算法是一種基礎(chǔ)的排序算法纷妆，這種算法會重復(fù)的比較數(shù)組中相鄰的兩個元素浪汪。如果一個元素比另一個元素大（胁诼蟆）滥玷，那么就交換這兩個元素的位置议谷。重復(fù)這一比較直至最后一個元素巫玻。這一比較會重復(fù)n-1趟榜配，每一趟比較n-j次极祸，j是已經(jīng)排序好的元素個數(shù)慈格。每一趟比較都能找出未排序元素中最大或者最小的那個數(shù)字。這就如同水泡從水底逐個飄到水面一樣遥金。冒泡排序是一種時間復(fù)雜度較高浴捆，效率較低的排序方法。其空間復(fù)雜度是O(n)稿械。
實(shí)現(xiàn)思路
1选泻，每一趟比較都比較數(shù)組中兩個相鄰元素的大小
2，如果i元素小于i-1元素，就調(diào)換兩個元素的位置
3页眯，重復(fù)n-1趟的比較
C 語言寫法：
```
//*********** 冒泡降序排序 **********//
int array[10] = {24,17,85,13,9,54,76,45,5,63};
int num =sizeof(array)/sizeof(int);
for(int i =0; i < num-1; i++) {
? ? for(int j =0; j < num -1- i; j++) {
? ? ? ? if(array[j] < array[j+1]) {
? ? ? ? ? ? int tmp = array[j];
? ? ? ? ? ? array[j] = array[j+1];
? ? ? ? ? ? array[j+1] = tmp;
? ? ? ? }
? ? }
}
for(int i =0; i < num; i++) {
? ? printf("%d\t", array[i]);
}
Objective-C 寫法：
#pragmamark - 冒泡降序排序
- (void)bubbleDescendingOrderSortWithArray:(NSMutableArray *)descendingArr
{
? ? for(int i =0; i < descendingArr.count; i++) {
? ? ? ? for(intj =0; j < descendingArr.count -1- i; j++) {
? ? ? ? ? ? if([descendingArr[j] ?intValue] < [descendingArr[j +1] ?intValue]) {
? ? ? ? ? ? ? ? int tmp = [descendingArr[j] intValue];
? ? ? ? ? ? ? ? descendingArr[j] = descendingArr[j +1];
? ? ? ? ? ? ? ? descendingArr[j +1] = [NSNumber numberWithInt:tmp];
? ? ? ? ? ? }
? ? ? ? }
? ? }
? ? NSLog(@"冒泡降序排序后結(jié)果：%@", descendingArr);
}
#pragmamark - 冒泡升序排序
- (void)bubbleAscendingOrderSortWithArray:(NSMutableArray *)ascendingArr
{
? ? for(int i =0; i < ascendingArr.count; i++) {
? ? ? ? for(int j =0; j < ascendingArr.count -1- i;j++) {
? ? ? ? ? ? if([ascendingArr[j+1] intValue] < [ascendingArr[j] intValue]) {
? ? ? ? ? ? ? ? inttemp = [ascendingArr[j] intValue];
? ? ? ? ? ? ? ? ascendingArr[j] = ascendingArr[j +1];
? ? ? ? ? ? ? ? ascendingArr[j +1] = [NSNumber numberWithInt:temp];
? ? ? ? ? ? }
? ? ? ? }
? ? }
? ? NSLog(@"冒泡升序排序后結(jié)果：%@", ascendingArr);
}
2梯捕、選擇排序：
實(shí)現(xiàn)思路：
?1.?設(shè)數(shù)組內(nèi)存放了n個待排數(shù)字，數(shù)組下標(biāo)從1開始窝撵，到n結(jié)束傀顾。
?2.?i=1
?3.?從數(shù)組的第i個元素開始到第n個元素，尋找最小的元素碌奉。（具體過程為:先設(shè)arr[i]為最小短曾，逐一比較，若遇到比之小的則交換）
?4.?將上一步找到的最小元素和第i位元素交換赐劣。
?5.?如果i=n－1算法結(jié)束错英，否則回到第3步
?復(fù)雜度：
平均時間復(fù)雜度：O(n^2)
平均空間復(fù)雜度：O(1)
#pragmamark - 選擇升序排序
- (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]) {
? ? ? ? ? ? ? ? int temp = [ascendingArr[i] intValue];
? ? ? ? ? ? ? ? ascendingArr[i] = ascendingArr[j];
? ? ? ? ? ? ? ? ascendingArr[j] = [NSNumber numberWithInt:temp];
? ? ? ? ? ? }
? ? ? ? }
? ? }
? ? NSLog(@"選擇升序排序后結(jié)果：%@", ascendingArr);
}
#pragmamark - 選擇降序排序
- (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]) {
? ? ? ? ? ? ? ? int temp = [descendingArr[i] ?intValue];
? ? ? ? ? ? ? ? descendingArr[i] = descendingArr[j];
? ? ? ? ? ? ? ? descendingArr[j] = [NSNumber numberWithInt:temp];
? ? ? ? ? ? }
? ? ? ? }
? ? }
? ? NSLog(@"選擇降序排序后結(jié)果：%@", descendingArr);
}
3、快速排序：
實(shí)現(xiàn)思路：
1.?從數(shù)列中挑出一個元素隆豹，稱為?"基準(zhǔn)"（pivot）椭岩，
2.?重新排序數(shù)列，所有元素比基準(zhǔn)值小的擺放在基準(zhǔn)前面璃赡，所有元素比基準(zhǔn)值大的擺在基準(zhǔn)的后面（相同的數(shù)可以到任一邊）判哥。在這個分割之后，該基準(zhǔn)是它的最后位置碉考。這個稱為分割（partition）操作塌计。
3.?遞歸地（recursive）把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序。?
快速排序是基于分治模式處理的侯谁，對一個典型子數(shù)組A[p...r]排序的分治過程為三個步驟：
1.分解：
A[p..r]被劃分為倆個（可能空）的子數(shù)組A[p ..q-1]和A[q+1 ..r]锌仅，使得
A[p ..q-1] <= A[q] <= A[q+1 ..r]
2.解決：通過遞歸調(diào)用快速排序，對子數(shù)組A[p ..q-1]和A[q+1 ..r]排序墙贱。
3.合并热芹。
遞回的最底部情形，是數(shù)列的大小是零或一惨撇，也就是永遠(yuǎn)都已經(jīng)被排序好了伊脓。雖然一直遞回下去，但是這個算法總會結(jié)束魁衙，因?yàn)樵诿看蔚牡╥teration）中报腔，它至少會把一個元素擺到它最后的位置去。
復(fù)雜度：
平均時間復(fù)雜度：O(n^2)
平均空間復(fù)雜度：O(nlogn)???????O(nlogn)~O(n^2)
偽代碼：
QUICK_SORT(A,p,r)
? ? if(p<r)
? ? ? ? then q <—— PARTITION(A,p,r)
? ? ? ? ? ? QUICK_SORT(A,p,q-1)
? ? ? ? ? ? QUICK_SORT(A,q+1,r)
//核心函數(shù)剖淀，對數(shù)組A[p,r]進(jìn)行就地重排纯蛾，將小于A[r]的數(shù)移到數(shù)組前半部分，將大于A[r]的數(shù)移到數(shù)組后半部分纵隔。
PARTITION(A,p,r)
? ? pivot <—— A[r]
? ? i <—— p-1
for j <—— p to r-1
do ifA[j] < pivot
? ? ? ? ? ? i <—— i+1?
?? ? ? ? ? exchange A[i]<——>A[j]
? ? exchange A[i+1]<——>A[r]
return i+1
C 語言實(shí)現(xiàn)：
#include <stdio.h>
int partition(int *arr,intl ow,int high)
{
? ? int pivot = arr[high];
? ? int i = low -1;
? ? int j, tmp;
? ? for(j = low; j< high; ++j)
? ? ? ? if(arr[j] < pivot) {
? ? ? ? ? ? tmp = arr[++i];
? ? ? ? ? ? arr[i] = arr[j];
? ? ? ? ? ? arr[j] = tmp;
? ? ? ? }
? ? tmp = arr[i+1];
? ? arr[i+1] = arr[high];
? ? arr[high] = tmp;
? ? return i+1;
}
void quick_sort(int *arr,int low,int high)
{
? ? if(low < high){
? ? ? ? int mid = partition(arr, low, high);
? ? ? ? quick_sort(arr, low, mid-1);
? ? ? ? quick_sort(arr, mid+1, high);
? ? }
}
//test
int main()
{
? ? intarr[10]={1,4,6,2,5,8,7,6,9,12};
? ? quick_sort(arr,0,9);
? ? int i;
? ? for(i=0;i<10;++i)
? ? ? ? printf("%d ",arr[i]);
}
Objective-C 實(shí)現(xiàn)：
#pragmamark - 快速升序排序
- (void)quickAscendingOrderSort:(NSMutableArray *)arr leftIndex:(NSInteger)left rightIndex:(NSInteger)right
{
? ? if(left < right) {
? ? ? ? NSInteger temp = [self getMiddleIndex:arr leftIndex:left rightIndex:right];
? ? ? ? [self quickAscendingOrderSort:arr leftIndex:left rightIndex:temp -1];
? ? ? ? [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];
? ? while(left < right) {
? ? ? ? while(left < right && tempValue <= [arr[right] ?integerValue]) {
? ? ? ? ? ? right --;
? ? ? ? }
? ? ? ? if(left < right) {
? ? ? ? ? ? arr[left] = arr[right];
? ? ? ? }
? ? ? ? while(left < right && [arr[left] integerValue] <= tempValue) {
? ? ? ? ? ? left ++;
? ? ? ? }
? ? ? ? if(left < right) {
? ? ? ? ? ? arr[right] = arr[left];
? ? ? ? }
? ? }
? ? arr[left] = [NSNumber numberWithInteger:tempValue];
? ? return left;
}
4翻诉、插入排序：
實(shí)現(xiàn)思路：
1.?從第一個元素開始帆卓，認(rèn)為該元素已經(jīng)是排好序的。
2.?取下一個元素米丘，在已經(jīng)排好序的元素序列中從后向前掃描剑令。
3.?如果已經(jīng)排好序的序列中元素大于新元素，則將該元素往右移動一個位置拄查。
4.?重復(fù)步驟3吁津，直到已排好序的元素小于或等于新元素。
5.?在當(dāng)前位置插入新元素堕扶。
6.?重復(fù)步驟2碍脏。
復(fù)雜度：
平均時間復(fù)雜度：O(n^2)
平均空間復(fù)雜度：O(1)
#pragmamark - 插入升序排序
- (void)insertionAscendingOrderSort:(NSMutableArray *)ascendingArr
{
? ? for(NSInteger ?i =1; i < ascendingArr.count; i ++) {
? ? ? ? NSInteger temp = [ascendingArr[i] ?integerValue];
? ? ? ? for(NSInteger ?j = i -1; j >=0&& temp < [ascendingArr[j] ?integerValue]; j --) {
? ? ? ? ? ? ascendingArr[j +1] = ascendingArr[j];
? ? ? ? ? ? ascendingArr[j] = [NSNumber numberWithInteger:temp];
? ? ? ? }
? ? }
? ? NSLog(@"插入升序排序結(jié)果：%@",ascendingArr);
}
五、堆排序：?
#pragmamark - 堆排序
- (void)heapsortAsendingOrderSort:(NSMutableArray *)ascendingArr
{
? ? NSInteger endIndex = ascendingArr.count -1;
? ? ascendingArr = [self heapCreate:ascendingArr];
? ? while(endIndex >=0) {
//? ? ? ? NSLog(@"將list[0]:\%@與list[\(endIndex)]:\%@交換", ascendingArr[0], ascendingArr[endIndex]);
????NSNumber *temp = ascendingArr[0];
? ? ? ? ascendingArr[0] = ascendingArr[endIndex];
? ? ? ? ascendingArr[endIndex] = temp;
? ? ? ? endIndex -=1;
? ? ? ? ascendingArr = [self heapAdjast:ascendingArr withStartIndex:0withEndIndex:endIndex +1];
? ? }
? ? NSLog(@"堆排序結(jié)果：%@", ascendingArr);
}
- (NSMutableArray *)heapCreate:(NSMutableArray *)array
{
? ? NSInteger i = array.count;
? ? while(i >0) {
? ? ? ? array = [self heapAdjast:array withStartIndex:i -1 withEndIndex:array.count];
? ? ? ? i -=1;
? ? }
? ? return array;
}
- (NSMutableArray *)heapAdjast:(NSMutableArray *)items withStartIndex:(NSInteger)startIndex withEndIndex:(NSInteger)endIndex
{
? ? NSNumber *temp = items[startIndex];
? ? NSInteger fatherIndex = startIndex +1;
? ? NSInteger maxChildIndex =2* fatherIndex;
? ? while(maxChildIndex <= endIndex) {
? ? ? ? if(maxChildIndex < endIndex && [items[maxChildIndex -1] floatValue] < [items[maxChildIndex] floatValue]) {
? ? ? ? ? ? maxChildIndex++;
? ? ? ? }
? ? ? ? if([temp floatValue] < [items[maxChildIndex -1] floatValue]) {
? ? ? ? ? ? items[fatherIndex -1] = items[maxChildIndex -1];
? ? ? ? } else {
? ? ? ? ? ? break;
? ? ? ? }
? ? ? ? fatherIndex = maxChildIndex;
? ? ? ? maxChildIndex = fatherIndex *2;
? ? }
? ? items[fatherIndex -1] = temp;
? ? return items;
}
六稍算、歸并排序：
把序列分成元素盡可能相等的兩半典尾。
把兩半元素分別進(jìn)行排序。
把兩個有序表合并成一個糊探。
#pragmamark - 歸并升序排序
- (void)megerSortAscendingOrderSort:(NSMutableArray *)ascendingArr
{
? ? NSMutableArray *tempArray = [NSMutableArray arrayWithCapacity:1];
? ? for(NSNumber *num in ascendingArr) {
? ? ? ? NSMutableArray *subArray = [NSMutableArray array];
? ? ? ? [subArray addObject:num];
? ? ? ? [tempArray addObject:subArray];
? ? }
? ? 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é)果：%@", ascendingArr);
}
- (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;
}
七钾埂、希爾排序：
#pragmamark - 希爾排序
- (void)shellAscendingOrderSort:(NSMutableArray *)ascendingArr
{
? ? NSMutableArray *buckt = [self createBucket];
? ? NSNumber *maxnumber = [self listMaxItem:ascendingArr];
? ? NSInteger maxLength = numberLength(maxnumber);
? ? for(int digit =1; digit <= maxLength; digit++) {
? ? ? ? // 入桶
????for(NSNumber *itemin ascendingArr) {
? ? ? ? ? ? NSInteger baseNumber = [self fetchBaseNumber:item digit:digit];
? ? ? ? ? ? NSMutableArray *mutArray = buckt[baseNumber];
? ? ? ? ? ? [mutArray addObject:item];
? ? ? ? }
? ? ? ? NSInteger index =0;
? ? ? ? for(inti =0; i < buckt.count; i++) {
? ? ? ? ? ? NSMutableArray *array = buckt[i];
? ? ? ? ? ? while(array.count !=0) {
? ? ? ? ? ? ? ? NSNumber *number = [array objectAtIndex:0];
? ? ? ? ? ? ? ? ascendingArr[index] = number;
? ? ? ? ? ? ? ? [array removeObjectAtIndex:0];
? ? ? ? ? ? ? ? index++;
? ? ? ? ? ? }
? ? ? ? }
? ? }
? ? NSLog(@"希爾升序排序結(jié)果：%@", ascendingArr);
}
- (NSMutableArray *)createBucket {
? ? NSMutableArray *bucket = [NSMutableArray array];
? ? for(intindex =0; index <10; index++) {
? ? ? ? NSMutableArray *array = [NSMutableArray array];
? ? ? ? [bucket addObject:array];
? ? }
? ? return bucket;
}
- (NSNumber *)listMaxItem:(NSArray *)list {
? ? NSNumber *maxNumber = list[0];
? ? for(NSNumber *numberin list) {
? ? ? ? if([maxNumber integerValue] < [number integerValue]) {
? ? ? ? ? ? maxNumber = number;
? ? ? ? }
? ? }
? ? return maxNumber;
}
NSInteger numberLength(NSNumber *number) {
? ? NSString *string= [NSString stringWithFormat:@"%ld", (long)[number integerValue]];
? ? returnstring.length;
}
- (NSInteger)fetchBaseNumber:(NSNumber *)number digit:(NSInteger)digit {
? ? if(digit >0&& digit <= numberLength(number)) {
? ? ? ? NSMutableArray *numbersArray = [NSMutableArray array];
? ? ? ? NSString *string= [NSString stringWithFormat:@"%ld", [number integerValue]];
? ? ? ? for(int index =0; index < numberLength(number); index++) {
? ? ? ? ? ? [numbersArray addObject:[stringsubstringWithRange:NSMakeRange(index,1)]];
? ? ? ? }
? ? ? ? NSString *str = numbersArray[numbersArray.count - digit];
? ? ? ? return [str integerValue];
? ? }
? ? return 0;
}
8、基數(shù)排序：
#pragmamark - 基數(shù)排序
- (void)radixAscendingOrderSort:(NSMutableArray *)ascendingArr
{
? ? NSMutableArray *buckt = [self createBucket];
? ? NSNumber *maxnumber = [self listMaxItem:ascendingArr];
? ? NSInteger maxLength = numberLength(maxnumber);
? ? for(int digit =1; digit <= maxLength; digit++) {
? ? ? ? // 入桶
????for(NSNumber *itemin ascendingArr) {
? ? ? ? ? ? NSInteger ?baseNumber = [self fetchBaseNumber:item digit:digit];
? ? ? ? ? ? NSMutableArray *mutArray = buckt[baseNumber];
? ? ? ? ? ? [mutArray addObject:item];
? ? ? ? }
? ? ? ? NSInteger index =0;
? ? ? ? for(int i =0; i < buckt.count; i++) {
? ? ? ? ? ? NSMutableArray *array = buckt[i];
? ? ? ? ? ? while(array.count !=0) {
? ? ? ? ? ? ? ? NSNumber *number = [array objectAtIndex:0];
? ? ? ? ? ? ? ? ascendingArr[index] = number;
? ? ? ? ? ? ? ? [array removeObjectAtIndex:0];
? ? ? ? ? ? ? ? index++;
? ? ? ? ? ? }
? ? ? ? }
? ? }
? ? NSLog(@"基數(shù)升序排序結(jié)果：%@", ascendingArr);
}
