1、冒泡排序
原理：重復地走訪過要排序的元素列，依次比較兩個相鄰的元素，如果他們的順序（如從大到小、首字母從A到Z）錯誤就把他們交換過來。走訪元素的工作是重復地進行直到?jīng)]有相鄰元素需要交換，也就是說該元素已經(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(@"冒泡降序排序后結果：%@", 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(@"冒泡升序排序后結果：%@", ascendingArr);
}
平均時間復雜度：O(n^2)
輔助空間：O(1)
算法穩(wěn)定性：相同元素的前后順序不會發(fā)生改變，所以冒泡排序是一種穩(wěn)定排序算法。
2、選擇排序
原理：它的工作原理是每一次從待排序的數(shù)據(jù)元素中選出最?。ɑ蜃畲螅┑囊粋€元素，存放在序列的起始位置，然后，再從剩余未排序元素中繼續(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(@"選擇降序排序后結果：%@", 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(@"選擇升序排序后結果：%@", ascendingArr);
}
平均時間復雜度：O(n^2)
輔助空間：O(1)
算法穩(wěn)定性：穩(wěn)定算法。
3、快速排序
快速排序（Quicksort）是對冒泡排序的一種改進。
通過一趟排序將要排序的數(shù)據(jù)分割成獨立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對這兩部分數(shù)據(jù)分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數(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];
/**** 遞歸排序 ***/
//排序基準數(shù)左邊的
[self quickAscendingOrderSort:arr leftIndex:left rightIndex:temp-1];
//排序基準數(shù)右邊的
[self quickAscendingOrderSort:arr leftIndex:temp+1 rightIndex:right];
}
NSLog(@"快速升序排序結果：%@", arr);
}
- (NSInteger)getMiddleIndex:(NSMutableArray *)arr leftIndex:(NSInteger)left rightIndex:(NSInteger)right
{
NSInteger tempValue = [arr[left] integerValue]; //記錄基準數(shù)
while (left < right) {
/**** 首先從右邊right開始查找比基準數(shù)小的值 ***/
while (left < right && tempValue<= [arr[right] integerValue]) {//如果比基準數(shù)大，繼續(xù)查找
right--;
}
if (left < right) {//如果比基準數(shù)小，則將查找到的小值調(diào)換到left的位置
arr[left] = arr[right];
}
/**** 當在右邊查找到一個比基準數(shù)小的值時，就從left開始往后找比基準數(shù)大的值 ***/
while (left < right && [arr[left] integerValue] <= tempValue) {
left ++;
}
if (left < right) {//如果比基準數(shù)大，則將查找到的大值調(diào)換到right的位置
arr[right] = arr[left];
}
}
arr[left] = [NSNumber numberWithInteger:tempValue];//將基準數(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];
平均時間復雜度：O(nlogn)
輔助空間：O(logn)~O(n)
算法穩(wěn)定性：不穩(wěn)定排序算法。
4、插入排序
實現(xiàn)思路：
- 從第一個元素開始，認為該元素已經(jīng)是排好序的。
- 取下一個元素，在已經(jīng)排好序的元素序列中從后向前掃描。
- 如果已經(jīng)排好序的序列中元素大于新元素，則將該元素往右移動一個位置。
- 重復步驟3，直到已排好序的元素小于或等于新元素。
- 在當前位置插入新元素。
- 重復步驟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(@"插入升序排序結果：%@",ascendingArr);
}
平均時間復雜度：O(n^2)
輔助空間：O(1)
算法穩(wěn)定性：穩(wěn)定。
5、堆排序
堆排序(Heap Sort) 就是利用堆(假設利用大堆頂)進行排序的方法。它的基本思想是，將待排序的序列構成一個大頂堆。此時，整個序列的最大值就是堆頂?shù)母?jié)點。將它移走(其實就是將其與堆數(shù)組的末尾元素交換，此時末尾元素就是最大值)，然后將剩余的n-1個序列重新構造成一個堆，這樣就會得到n個元素中的次小值。如此反復執(zhí)行，便能得到一個有序序列了。
#pragma mark - 堆排序
- (void)heapSort:(NSMutableArray *)list
{
NSInteger i ,size;
size = list.count;
//找出最大的元素放到堆頂，構建大頂堆
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 -- ;//樹大小減小
[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; //左右子樹
while (rchild < size) { //子樹均在范圍內(nèi)
if ([list[element] integerValue] >= [list[lchild] integerValue] && [list[element] integerValue] >= [list[rchild]integerValue]) return; //如果比左右子樹都大，完成整理
if ([list[lchild] integerValue] > [list[rchild] integerValue]) { //如果左邊最大
[list exchangeObjectAtIndex:element withObjectAtIndex:lchild]; //把左面的提到上面
element = lchild; //循環(huán)時整理子樹
}else{//否則右面最大
[list exchangeObjectAtIndex:element withObjectAtIndex:rchild];
element = rchild;
}
lchild = element * 2 +1;
rchild = lchild + 1; //重新計算子樹位置
}
//只有左子樹且子樹大于自己
if (lchild < size && [list[lchild] integerValue] > [list[element] integerValue]) {
[list exchangeObjectAtIndex:lchild withObjectAtIndex:element];
}
}
平均時間復雜度：O(nlogn)
輔助空間：O(1)
算法穩(wěn)定性：由于記錄的比較和交換是跳躍式進行，因此堆排序也是一種不穩(wěn)定的排序方法。
6、歸并排序
歸并排序(Merging Sort) 就是利用歸并的思想實現(xiàn)的排序方法。它的原理是假設初始序列含有n個記錄，則可以看成是n個有序的子序列，每個子序列的長度為1，然后兩兩歸并，得到n/2個長度為2或者1的有序子序列；再兩兩歸并，......，如此反復，直到得到一個長度為n的有序序列為止，這種排序方法稱為歸并排序。
#pragma mark - 歸并升序排序
- (void)megerSortAscendingOrderSort:(NSMutableArray *)ascendingArr
{
//tempArray數(shù)組里存放ascendingArr.count個數(shù)組，每個數(shù)組包含一個元素
NSMutableArray *tempArray = [NSMutableArray arrayWithCapacity:1];
for (NSNumber *num in ascendingArr) {
NSMutableArray *subArray = [NSMutableArray array];
[subArray addObject:num];
[tempArray addObject:subArray];
}
//開始合并為一個數(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(@"歸并升序排序結果：%@", 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;
}
平均時間復雜度：O(nlogn)
輔助空間：O(n)
算法穩(wěn)定性：因為是兩兩比較，不存在跳躍，因此是一種穩(wěn)定的排序算法。雖然占用內(nèi)存比較多，但卻是一種效率高的算法。
7、希爾排序
希爾排序在插入排序的基礎上增加一個叫增量的概念。那什么增量？插入排序只能與相鄰的元素進行比較，而希爾排序則是進行跳躍比較，而增量就是步長。比如增量為3時，下標為0的元素與下標為3的元素比較，3再與6比較，1與4比較，4再與7比較……比較完后，再去減少增量，重復之前步驟，直到增量為1，此時只有一個分組了，再對這一個分組進行插入排序，整個希爾排序就結束了。
#pragma mark - 希爾排序
-(void)shellSort:(NSMutableArray *)list{
int gap = (int)list.count / 2;//起始間隔值gap設置為總數(shù)的一半，直到gap==1結束
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(@"希爾升序排序結果：%@", list);
}
平均時間復雜度：O(nlogn)~O(n^2)
輔助空間：O(1)
算法穩(wěn)定性：由于記錄是跳躍式的移動，希爾排序并不是一種穩(wěn)定的排序算法。
8、基數(shù)排序
基數(shù)排序(Radix Sort)是根據(jù)關鍵字中各位的值，通過對排序的N個元素進行若干趟“分配”與“收集”來實現(xiàn)排序的。
#pragma mark - 基數(shù)排序
- (void)radixSort:(NSMutableArray *)ascendingArr
{
/**
基于LSD方法的鏈式基數(shù)排序的基本思想
“多關鍵字排序”的思想實現(xiàn)“單關鍵字排序”。對數(shù)字型或字符型的單關鍵字，可以看作由多個數(shù)位或多個字符構成的多關鍵字，此時可以采用“分配-收集”的方法進行排序，這一過程稱作基數(shù)排序法，其中每個數(shù)字或字符可能的取值個數(shù)稱為基數(shù)。比如，撲克牌的花色基數(shù)為4，面值基數(shù)為13。在整理撲克牌時，既可以先按花色整理，也可以先按面值整理。按花色整理時，先按紅、黑、方、花的順序分成4摞（分配），再按此順序再疊放在一起（收集），然后按面值的順序分成13摞（分配），再按此順序疊放在一起（收集），如此進行二次分配和收集即可將撲克牌排列有序。
基數(shù)排序:
是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次類推，直到最高位。有時候有些屬性是有優(yōu)先級順序的，先按低優(yōu)先級排序，再按高優(yōu)先級排序。最后的次序就是高優(yōu)先級高的在前，高優(yōu)先級相同的低優(yōu)先級高的在前。基數(shù)排序基于分別排序，分別收集，所以是穩(wěn)定的。
*/
//創(chuàng)建空桶
NSMutableArray *buckt = [self createBucket];
//待排數(shù)組的最大數(shù)值
NSNumber *maxnumber = [self listMaxItem:ascendingArr];
//最大數(shù)值的數(shù)字位數(shù)
NSInteger maxLength = numberLength(maxnumber);
// 按照從低位到高位的順序執(zhí)行排序過程
for (int digit = 1; digit <= maxLength; digit++) {
// 入桶
for (NSNumber *item in ascendingArr) {
//確定item 歸屬哪個桶 以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ù)升序排序結果：%@", ascendingArr);
}
//創(chuàng)建空桶，每個桶里都是數(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ù)排序中，r為基數(shù)，d為位數(shù)。則基數(shù)排序的時間復雜度為O(d(n+r))。我們可以看出，基數(shù)排序的效率和初始序列是否有序沒有關聯(lián)。
空間復雜度：在基數(shù)排序過程中，對于任何位數(shù)上的基數(shù)進行“裝桶”操作時，都需要n+r個臨時空間。
算法穩(wěn)定性：是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次類推，直到最高位。有時候有些屬性是有優(yōu)先級順序的，先按低優(yōu)先級排序，再按高優(yōu)先級排序。最后的次序就是高優(yōu)先級高的在前，高優(yōu)先級相同的低優(yōu)先級高的在前?；鶖?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
