常用排序算法 - Objective-C

常用排序

1.冒泡排序
2.選擇排序
3.快速排序
4.插入排序
5.希爾排序
6.歸并排序
7.堆排序
8.桶排序

1.冒泡排序

思想

依次比較相鄰的元素，如果前一個比后一個大(小)，就交換位置，把最大(小)的移動到數(shù)組待排序的最前(后)位置，循環(huán)比較直到所有元素有序。

動圖效果

冒泡.gif

代碼

-(void)sortBuddleArray:(NSMutableArray *)array{
    for (int i = 0; i< array.count - 1; i++) {
        for (int j = 0; j< array.count - i -1; j++) {
            NSNumber *a = array[j];
            NSNumber *b = array[j+1];
            if (a.intValue > b.intValue) {
                [array exchangeObjectAtIndex:j withObjectAtIndex:j+1];
            }
        }
    }
}

2.選擇排序

思想

依次查找數(shù)組中最大(小)的元素，把最大(小)的元素移動到數(shù)組的待排序的最前(后)位置，循環(huán)比較移動直到所有元素有序。

動圖效果

選擇.gif

代碼

-(void)sortSelectArray:(NSMutableArray *)array{
    for (int i = 0; i< array.count; i++) {
        int maxIndex = i;
        for (int j = i+1; j< array.count; j++) {
            NSNumber *maxValue = array[maxIndex];
            NSNumber *b = array[j];
            if (maxValue.longValue < b.longValue) {
                maxIndex = j;
            }
        }
        [array exchangeObjectAtIndex:i withObjectAtIndex:maxIndex];
    }
}

3.快速排序

思想

快速排序的思路是把數(shù)組元素分為以基準(zhǔn)元素為界限的兩部分，左右兩邊分別為大于和小于基準(zhǔn)元素的元素，再遞歸分別對左右兩部分未排序的元素進行排序。直到數(shù)組中所有元素都有序。

動圖效果

快速.gif

代碼

- (void)quickSortArray:(NSMutableArray *)array fromIndex:(NSInteger)fromIndex toIndex:(NSInteger)toIndex
{
    if (fromIndex >= toIndex) {//數(shù)組個數(shù)<= 1 直接返回
        return ;
    }
    NSInteger i = fromIndex;//起止點
    NSInteger j = toIndex;//終止點
    //比較基準(zhǔn)數(shù)
    NSInteger target = [array[i] integerValue];
    while (i < j) {
        // 首先從右邊j開始查找比基準(zhǔn)數(shù)小的值
        while (i < j && [array[j] integerValue] >= target) {//如果比基準(zhǔn)數(shù)大，繼續(xù)查找
            j--;
        }
        //如果比基準(zhǔn)數(shù)小，則將查找到的小值調(diào)換到i的位置
        array[i] = array[j];
        // 當(dāng)在右邊查找到一個比基準(zhǔn)數(shù)小的值時，就從i開始往后找比基準(zhǔn)數(shù)大的值
        while (i < j && [array[i] integerValue] <= target) {//如果比基準(zhǔn)數(shù)小，繼續(xù)查找
            i++;
        }
        //如果比基準(zhǔn)數(shù)大，則將查找到的大值調(diào)換到j(luò)的位置
        array[j] = array[i];
    }
    //將基準(zhǔn)數(shù)放到正確位置
    array[i] = @(target);
    // 按基準(zhǔn)數(shù)分左右兩部分，然后左右兩邊分別遞歸再排序
    //排序基準(zhǔn)數(shù)左邊的
    [self quickSortArray:array fromIndex:fromIndex toIndex:i - 1];
    //排序基準(zhǔn)數(shù)右邊的
    [self quickSortArray:array fromIndex:i + 1 toIndex:toIndex];
}

4.插入排序

思想

插入排序的思想就是把待排序元素依次插入到已排序元素中對應(yīng)位置，直到所有元素都有序。

動圖效果

插入.gif

代碼

-(void)insertSortArray:(NSMutableArray *)array{
    for (long i = 0; i< array.count; i++) {
        long j = i-1;
        long target = i;
        while (j >= 0 && [array[j] longValue] > [array[target] longValue]) {
            [array exchangeObjectAtIndex:target withObjectAtIndex:j];
            target = j;
            j--;
        }
    }
}

5.希爾排序

思想

希爾排序是對插入排序的優(yōu)化，看4.插入排序的動圖，能夠很直觀的看到，如果元素位置和排序位置相反，則需要比較和移動的次數(shù)較多，希爾排序先進行幾次 大步調(diào)的插入排序，從而讓整個數(shù)組大致有序，整體順序接近最終順序，然后再最后進行一次插入排序，這樣能大幅降低比較和移動的次數(shù)。提升排序效率

動圖效果

希爾.gif

代碼

-(void)shellSortArray:(NSMutableArray *)array{
    long d = (array.count-1)/2;
    while (d>0) {
        for (long m = 0;m < d;m++) {
            for (long i = m; i < array.count; i = i+d) {
                long j = i-d;
                long target = i;
                while (j >= 0 && [array[j] longValue] > [array[target] longValue]) {
                        [array exchangeObjectAtIndex:target withObjectAtIndex:j];
                        target = j;
                    j = j - d;
                }
            }
        }
        d = d/2;
    }
}

6.歸并排序

思想

歸并排序思想就是遞歸調(diào)用，將兩個已經(jīng)有序的數(shù)組合并起來，如果數(shù)組無序，繼續(xù)拆分，直到只剩一個元素。

動圖效果

歸并.gif

代碼

-(NSArray *)mergeSortTotalArray:(NSArray *)array{
    long d = array.count/2;
    if (d > 0) {
        NSArray *array1 = [array subarrayWithRange:NSMakeRange(0, d)];
        NSArray *array2 = [array subarrayWithRange:NSMakeRange(d, array.count - d)];
        return [self mergeSortArray1:array1 array2:array2];
    }
    return array;
}
//歸并排序
-(NSMutableArray *)mergeSortArray1:(NSArray *)array1 array2:(NSArray *)array2{
    NSArray *arr1 = [self mergeSortTotalArray:array1];
    NSArray *arr2 = [self mergeSortTotalArray:array2];
    NSMutableArray *newArray = [[NSMutableArray alloc] init];
    long i = 0;
    long j = 0;
    while (i< arr1.count && j < arr2.count) {
        if ([arr1[i] longValue] <= [arr2[j] longValue]) {
            [newArray addObject:arr1[i]];
            i++;
        }else{
            [newArray addObject:arr2[j]];
            j++;
        }
    }
    for (long m = i; m < arr1.count; m++) {
        [newArray addObject:arr1[m]];
    }
    for (long m = j; m < arr2.count; m++) {
        [newArray addObject:arr2[m]];
    }
    return newArray;
}

7.堆排序

思想

堆排序 和選擇排序類似，都是依次把待排序最大(小)元素放到最后面，選擇排序是遍歷查找最大(小)值，而堆排序是通過 構(gòu)造大(小)頂堆 來查找最值。

動圖效果

堆排序.gif

代碼

/*
 * 堆排序
 */
-(void)heapSortArray:(NSMutableArray *)array{
    for (long i = 0; i< array.count; i++) {
        [self makeMaxHeap:array toIndex:array.count-i -1];
        [array exchangeObjectAtIndex:0 withObjectAtIndex:array.count-i -1];
    }
}

/*
* 構(gòu)造大頂堆
*/
-(void)makeMaxHeap:(NSMutableArray *)array toIndex:(long)index{
    for (long i = (index-1)/2; i>= 0 ; i--) {
        if (2*i+1 <= index && [array[2*i+1] longValue] > [array[i] longValue] ) {
            [array exchangeObjectAtIndex:2*i+1 withObjectAtIndex:i];
        }
        if (2*i+2 <= index && [array[2*i+2] longValue] > [array[i] longValue] ) {
            [array exchangeObjectAtIndex:2*i+2 withObjectAtIndex:i];
        }
    }
}

8.桶排序

思想

桶排序的思想是，先按照最大-最小值的差定義一批桶（數(shù)組），按照值域把待排序元素放入對應(yīng)的桶中，桶中元素各自排序，然后依次取出桶中的元素即可。

動圖效果

桶排序.gif

代碼

-(void)bucketSortArray:(NSMutableArray *)array{
    long max = [array[0] longValue];
    long min = [array[0] longValue];
    for (long i = 0; i< array.count ; i++) {
        max = [array[i] longValue] > max ? [array[i] longValue] : max;
        min = [array[i] longValue] < min ? [array[i] longValue] : min;
    }
//構(gòu)造桶，d為桶的大小 值范圍大小
    long dm = (max - min)%4 > 0 ? 1 : 0;
    long d = (max - min)/4 + dm;
    NSMutableArray *bucketArray = [NSMutableArray new];
    for (long i = 0; i < 5; i++) {
        NSMutableArray *arr = [NSMutableArray new];
        [bucketArray addObject:arr];
    }
//遍歷待排序數(shù)組，把元素放到對應(yīng)的桶中
    for (long i = 0; i < array.count; i++) {
        long arrIndex = ([array[i] longValue] - min)/d;
        NSMutableArray *arr = bucketArray[arrIndex];
        [arr addObject:array[i]];
    }
//合并取出所有桶中元素，放回元素組
    long index = 0;
    for (long i = 0; i < 5; i++) {
        NSMutableArray *arr = bucketArray[i];
        [self sortPaoArray:arr];
        for (long j = 0; j < arr.count; j++) {
            array[index] = arr[j];
            index++;
        }
    }
}

/*
 * 冒泡排序（桶中元素排序的方式隨意選擇都可）
 */
-(void)sortPaoArray:(NSMutableArray *)array{
    if (array.count <= 1) {
        return;
    }
    for (int i = 0; i< array.count - 1; i++) {
        for (int j = 0; j< array.count - i -1; j++) {
            NSNumber *a = array[j];
            NSNumber *b = array[j+1];
            if (a.intValue > b.intValue) {
                [array exchangeObjectAtIndex:j withObjectAtIndex:j+1];
            }
        }
    }
}
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

友情鏈接更多精彩內(nèi)容