几种常见的排序算法

一 快速排序

快速排序是我们平常最常使用的一种排序算法,因为它速度快,效率高,是最优秀的一种排序算法.

它的平均时间复杂度为:O(nlgn)

原理:

快速排序采用的是一种分治的思想,它先找一个基准数,然后将比这个基准数小的数字都放到它的左边,然后再递归调用,分别对左右两边快速排序,直到每一边只有一个数字.整个排序就完成了.

OC实现:

-(void)quickSort:(NSMutableArray *)list startIndex:(NSInteger )startIndex endIndex:(NSInteger)endIndex
{
    if (list==nil||startIndex>=endIndex) {
        return;
    }
    
    NSInteger tempIndex=startIndex;
    NSNumber *tempNumber=list[startIndex];
    
    for (NSInteger i=startIndex+1; i<=endIndex; i++) {
        
        if ([tempNumber integerValue]>[list[i] integerValue]) {
            tempIndex++;
            [list exchangeObjectAtIndex:tempIndex withObjectAtIndex:i];
        }
        
    }
    
    [list exchangeObjectAtIndex:startIndex withObjectAtIndex:tempIndex];
    
    [self quickSort:list startIndex:startIndex endIndex:tempIndex-1];
    [self quickSort:list startIndex:tempIndex+1 endIndex:endIndex];
    
}

二 冒泡排序

冒泡排序在我们实际开发中,使用的还是比较少的.它更加适合数据规模比较少的时候,因为它的效率是比较低的,但是优点是逻辑简单,容易让我们记得.

原理:

冒泡排序其实就是逐一比较交换,进行里外两次循环,外层循环为遍历所有数字,逐个确定每个位置,里层循环为确定了位置后,遍历所有后面没有确定位置的数字,与该位置的数字进行比较,只要比该位置的数字小,就和该位置的数字进行交换.

OC实现:

-(void)bubbleSort:(NSMutableArray *)list
{
    for (int i=0; i<list.count; i++) {
        
        for (int j=i+1; j<list.count; j++) {
            if ([list[i] integerValue]>[list[j] integerValue]) {
                
                [list exchangeObjectAtIndex:i withObjectAtIndex:j];
            }
        }
        
    }
}

三 直接插入排序

直接插入排序的平均时间复杂度是:O(n^2)

原理:

直接插入排序是将从第二个数字开始,逐个拿出来,插入到之前排好序的数列里.
如图:

直接插入排序

OC实现:

-(void)insertSort:(NSMutableArray *)list
{
    for (int i=1; i<list.count; i++) {
        
        NSInteger value=[list[i] integerValue];
        
        NSInteger j=i-1;
        
        while (j>=0&&value<[list[j] integerValue]) {
            j--;

        }
        
        [list removeObjectAtIndex:i];
        [list insertObject:@(value) atIndex:j+1];
        
        
    }
    
}

四 直接选择排序

直接选择排序的平均时间复杂度是:O(n^2),和冒泡排序一样,逻辑简单,但是效率不高,适合少量的数据排序

原理:

直接选择排序是从第一个位置开始遍历位置,找到剩余未排序的数据里最小的,找到最小的后,再做交换

OC实现:

-(void)selectSort:(NSMutableArray *)list
{
    for (int i=0; i<list.count; i++) {
        
        int k=i;
        for (int j=i+1; j<list.count; j++) {
            
            if ([list[j] integerValue]<[list[k] integerValue]) {
                k = j;
            }
            
        }
        
        [list exchangeObjectAtIndex:i withObjectAtIndex:k];
    }
}

与冒泡排序的区别:

冒泡排序法是两两依次比较，并做交换，交换的次数多。
选择排序法是每次循环找出最值，循环结束后将最值调整到合适位置，交换的次数少。

剩余常见排序算法:

归并排序,希尔排序,堆排序,基数排序,桶排序.