排序算法学习

术语说明

• 稳定： 如果a原本在b前面，a=b,排序后a仍然在b的前面
• 不稳定: 如果a原本在b前面，a=b,排序后a可能会出现在b的后面
• 内排序： 所有排序操作在内存完成
• 外排序：由于数据太大，数据存在磁盘中，排序通过磁盘和内存的数据传输才能进行

稳定性排序

• 稳定: 冒泡、插入、归并、计数、桶排序、基数排序
• 不稳定：选择排序、希尔排序、快排、堆排序

各类排序算法介绍

冒泡排序

• 最佳情况：T(n) = O(n)
• 最差情况：T(n) = O(n²)
• 平均情况：T(n) = O(n²)

1. 比较相邻的元素，如果第一个比第二个大，交换
2. 对每一对相邻元素做同样的工作，每轮结束后，最大的数位于元素最后
3. 重复以上步骤，除了每轮最后一个，直到排序完成

Swift
func bubbleSort<T: Comparable>(_ numbers: inout [T]) {
    for i in 0 ..< numbers.count {
        for j in 0 ..< numbers.count - i-1  {
            if numbers[j] > numbers[j+1] {
                (numbers[j], numbers[j+1]) = (numbers[j+1], numbers[j])
            }
            
        }
        print("第\(i)趟: \(numbers)")
    }
}

var array = [100, 50, 30, 10, 200, 0, -11, 44.5, -20, 120.3]
print("冒泡排序前:\(array)")
bubbleSort(&array)
print("冒泡排序后:\(array)")

OC
- (void)bubbleSort:(NSMutableArray<NSNumber*>*)numbers{
    for(int i = 0; i < numbers.count;i++){
        BOOL isExchange = NO;
        for(int j = 0; j < numbers.count-i-1; j++){
            if (numbers[j].floatValue > numbers[j+1].floatValue) {
                isExchange = YES;
                [numbers exchangeObjectAtIndex:j withObjectAtIndex:j+1];
            }
        }
        if (!isExchange) {  //一次排序未发生任何交换，证明已排序完毕，结束。 增加此代码，原总共需排序10躺将变为排序8躺
            break;
        }
        NSLog(@"第%d躺：%@", i, [numbers mj_JSONString]);
    }
}
NSMutableArray *array = [NSMutableArray arrayWithArray:@[@100, @50, @30, @10, @200, @0, @-11, @44.5, @-20, @120.3]];
    NSLog(@"冒泡排序前:%@",[array mj_JSONString]);
    [self bubbleSort:array];
    NSLog(@"冒泡排序后:%@", [array mj_JSONString]);

冒泡排序前:[100.0, 50.0, 30.0, 10.0, 200.0, 0.0, -11.0, 44.5, -20.0, 120.3]
第0趟: [50.0, 30.0, 10.0, 100.0, 0.0, -11.0, 44.5, -20.0, 120.3, 200.0]
第1趟: [30.0, 10.0, 50.0, 0.0, -11.0, 44.5, -20.0, 100.0, 120.3, 200.0]
第2趟: [10.0, 30.0, 0.0, -11.0, 44.5, -20.0, 50.0, 100.0, 120.3, 200.0]
第3趟: [10.0, 0.0, -11.0, 30.0, -20.0, 44.5, 50.0, 100.0, 120.3, 200.0]
第4趟: [0.0, -11.0, 10.0, -20.0, 30.0, 44.5, 50.0, 100.0, 120.3, 200.0]
第5趟: [-11.0, 0.0, -20.0, 10.0, 30.0, 44.5, 50.0, 100.0, 120.3, 200.0]
第6趟: [-11.0, -20.0, 0.0, 10.0, 30.0, 44.5, 50.0, 100.0, 120.3, 200.0]
第7趟: [-20.0, -11.0, 0.0, 10.0, 30.0, 44.5, 50.0, 100.0, 120.3, 200.0]
第8趟: [-20.0, -11.0, 0.0, 10.0, 30.0, 44.5, 50.0, 100.0, 120.3, 200.0]
第9趟: [-20.0, -11.0, 0.0, 10.0, 30.0, 44.5, 50.0, 100.0, 120.3, 200.0]
冒泡排序后:[-20.0, -11.0, 0.0, 10.0, 30.0, 44.5, 50.0, 100.0, 120.3, 200.0]

选择排序

• 最佳情况：T(n) = O(n²)
• 最差情况：T(n) = O(n²)
• 平均情况：T(n) = O(n²)

1. 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
2. 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾
3. 重复1、2，直到所有元素均排序完毕

Swift
func selectionSort<T: Comparable>(_ numbers: inout [T]) {  //选择
    for i in 0 ..< numbers.count {
        var minIdx = i
        //数组中找出一个最小数
        for j in i ..< numbers.count   {
            if numbers[j] < numbers[minIdx] {
                minIdx = j
            }
        }
        //将数组中最小数与待排位置交换
        (numbers[i], numbers[minIdx]) = (numbers[minIdx], numbers[i])
        print("第\(i)趟: \(numbers)")
    }
}
var array = [100, 50, 30, 10, 200, 0, -11, 44.5, -20, 120.3]
print("选择排序前:\(array)")
selectionSort(&array)
print("选择排序后:\(array)")

OC
- (void)selectionSort:(NSMutableArray<NSNumber*> *)numbers{
    for(int i = 0; i < numbers.count; i++){
        int minIdx = i;
        for(int j = i; j < numbers.count; j++){
            if ([numbers objectAtIndex:j].floatValue < numbers[minIdx].floatValue) {
                minIdx = j;
            }
        }
        [numbers exchangeObjectAtIndex:i withObjectAtIndex:minIdx];
    }
}
NSMutableArray *array = [NSMutableArray arrayWithArray:@[@100, @50, @30, @10, @200, @0, @-11, @44.5, @-20, @120.3]];
NSLog(@"选择排序前:%@",[array mj_JSONString]);
    [self selectionSort:array];
NSLog(@"选择排序后:%@", [array mj_JSONString]);

选择排序前:[100.0, 50.0, 30.0, 10.0, 200.0, 0.0, -11.0, 44.5, -20.0, 120.3]
第0趟: [-20.0, 50.0, 30.0, 10.0, 200.0, 0.0, -11.0, 44.5, 100.0, 120.3]
第1趟: [-20.0, -11.0, 30.0, 10.0, 200.0, 0.0, 50.0, 44.5, 100.0, 120.3]
第2趟: [-20.0, -11.0, 0.0, 10.0, 200.0, 30.0, 50.0, 44.5, 100.0, 120.3]
第3趟: [-20.0, -11.0, 0.0, 10.0, 200.0, 30.0, 50.0, 44.5, 100.0, 120.3]
第4趟: [-20.0, -11.0, 0.0, 10.0, 30.0, 200.0, 50.0, 44.5, 100.0, 120.3]
第5趟: [-20.0, -11.0, 0.0, 10.0, 30.0, 44.5, 50.0, 200.0, 100.0, 120.3]
第6趟: [-20.0, -11.0, 0.0, 10.0, 30.0, 44.5, 50.0, 200.0, 100.0, 120.3]
第7趟: [-20.0, -11.0, 0.0, 10.0, 30.0, 44.5, 50.0, 100.0, 200.0, 120.3]
第8趟: [-20.0, -11.0, 0.0, 10.0, 30.0, 44.5, 50.0, 100.0, 120.3, 200.0]
第9趟: [-20.0, -11.0, 0.0, 10.0, 30.0, 44.5, 50.0, 100.0, 120.3, 200.0]
选择排序后:[-20.0, -11.0, 0.0, 10.0, 30.0, 44.5, 50.0, 100.0, 120.3, 200.0]

插入排序

• 最佳情况：T(n) = O(n)
• 最差情况：T(n) = O(n²)
• 平均情况：T(n) = O(n²)

1. 第一个元素当着已排序序列，取下一个元素，在已排序序列中从后往前扫描
2. 如果已排序元素大于新数，将该元素往后移动一位
3. 重复2，直到出现已排序元素小于或等于新元素。将新元素插入到该位置后
4. 重复2、3

Swift
func insertionSort<T: Comparable>(_ numbers: inout [T]) {  //插入
    for i in 0 ..< numbers.count-1 {
        var preIdx = i  //已排序好的序列
        let current = numbers[i+1]  //待排序数
        //已排序数组中，移动数据，直到新元素大于已排序数
        while preIdx >= 0 && current < numbers[preIdx] {
            numbers[preIdx+1] = numbers[preIdx]
            preIdx -= 1
        }
        numbers[preIdx+1] = current
        print("第\(i)趟: \(numbers),待排数\(current)")
    }
}
var array = [100, 50, 30, 10, 200, 0, -11, 44.5, -20, 120.3]
print("排序前:\(array)")
insertionSort(&array)
print("排序后:\(array)")

OC
- (void)insertionSort:(NSMutableArray<NSNumber*>*)numbers{
    for(int i = 0; i < numbers.count-1;i++){
        double current = [numbers[i+1] doubleValue];
        int preIdx = i;
        while (preIdx >= 0 && current < numbers[preIdx].doubleValue) {
            [numbers exchangeObjectAtIndex:preIdx withObjectAtIndex:preIdx+1];
            preIdx--;
        }
        numbers[preIdx+1] = @(current);
        NSLog(@"第%d躺：%@", i, [numbers mj_JSONString]);
    }
}
NSMutableArray *array = [NSMutableArray arrayWithArray:@[@100, @50, @30, @10, @200, @0, @-11, @44.5, @-20, @120.3]];
NSLog(@"排序前:%@",[array mj_JSONString]);
[self insertionSort:array];
NSLog(@"排序后:%@", [array mj_JSONString]);

排序前:[100.0, 50.0, 30.0, 10.0, 200.0, 0.0, -11.0, 44.5, -20.0, 120.3]
第0趟: [50.0, 100.0, 30.0, 10.0, 200.0, 0.0, -11.0, 44.5, -20.0, 120.3],待排数50.0
第1趟: [30.0, 50.0, 100.0, 10.0, 200.0, 0.0, -11.0, 44.5, -20.0, 120.3],待排数30.0
第2趟: [10.0, 30.0, 50.0, 100.0, 200.0, 0.0, -11.0, 44.5, -20.0, 120.3],待排数10.0
第3趟: [10.0, 30.0, 50.0, 100.0, 200.0, 0.0, -11.0, 44.5, -20.0, 120.3],待排数200.0
第4趟: [0.0, 10.0, 30.0, 50.0, 100.0, 200.0, -11.0, 44.5, -20.0, 120.3],待排数0.0
第5趟: [-11.0, 0.0, 10.0, 30.0, 50.0, 100.0, 200.0, 44.5, -20.0, 120.3],待排数-11.0
第6趟: [-11.0, 0.0, 10.0, 30.0, 44.5, 50.0, 100.0, 200.0, -20.0, 120.3],待排数44.5
第7趟: [-20.0, -11.0, 0.0, 10.0, 30.0, 44.5, 50.0, 100.0, 200.0, 120.3],待排数-20.0
第8趟: [-20.0, -11.0, 0.0, 10.0, 30.0, 44.5, 50.0, 100.0, 120.3, 200.0],待排数120.3
排序后:[-20.0, -11.0, 0.0, 10.0, 30.0, 44.5, 50.0, 100.0, 120.3, 200.0]

快速排序

• 最佳情况：T(n) = O(nlogn)
• 最差情况：T(n) = O(n²)
• 平均情况：T(n) = O(nlogn)

通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序
设置两个变量 low、high，排序开始时：low=0，high=size-1。

• 整个数组找基准正确位置，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面

• 默认数组的第一个数为基准数据，赋值给key，即key=array[low]。
  因为默认数组的第一个数为基准，所以从后面开始向前搜索（high–），找到第一个小于key的array[high]，就将 array[high] 赋给 array[low]，即 array[low] = array[high]。（循环条件是 array[high] >= key；结束时 array[high] < key）
  此时从前面开始向后搜索（low++），找到第一个大于key的array[low]，就将 array[low] 赋给 array[high]，即 array[high] = array[low]。（循环条件是 array[low] <= key；结束时 array[low] > key）

• 循环，直到 low=high，该位置就是基准位置。

• 第一趟找到的基准位置，作为下一趟的分界点。

• 递归调用（recursive）分界点前和分界点后的子数组排序。

Swift
func partitionSort<T: Comparable>(_ numbers: inout [T], tupe: (low: Int, high: Int)) {
    guard tupe.low < tupe.high && tupe.1 < numbers.count else {
        print("快排start\(tupe.low)必须小于end\(tupe.high)");
        return
    }
    //快排
    let key = numbers[tupe.0]  //默认数组左边第一个数为基准数，排序后，key左边的值小于key,右边的值大于key
    var i = tupe.0 //首
    var j = tupe.1 //尾
    while i < j {
        while i < j && numbers[j] >= key { //数组尾部查找到第一个比基准数小的数,
            j -= 1
        }
        numbers[i] = numbers[j]  //找到比基准数小的数，将该数调整到数组前部
        while i < j && numbers[i] <= key { //找到前部比基准大的数据
            i += 1
        }
        numbers[j] = numbers[i]  //将前部比基准小的数放置在末尾
    }
    //i=j,此位置为基准位置
    numbers[i] = key
    print("快排中:\(numbers)")
    partitionSort(&numbers, tupe: (tupe.low, i-1)) //递归排列左边元素
    partitionSort(&numbers, tupe: (i+1, tupe.high)) //递归排列右边元素
}
var array = [100, 50, 30, 10, 200, 0, -11, 44.5, -20, 120.3]
print("排序前:\(array)")
partitionSort(&array, tupe: (0, array.count-1))
print("排序后:\(array)")

OC
- (void)partitionSort:(NSMutableArray<NSNumber*>*)numbers low:(int)l high:(int)h{
    if (l >= h || h <= 0 ) {
        return;
    }
    NSNumber* key = numbers[l] ;
    int i = l;
    int j = h;
    while (i < j) {
        while (numbers[j].doubleValue >= key.doubleValue && i < j) { //数组尾部查找到第一个小于基准数
            j--;
        }
        numbers[i] = numbers[j];
        while (numbers[i].doubleValue <= key.doubleValue && i < j) {
            i++;
        }
        numbers[j] = numbers[i];
    }
    numbers[i] = key;
    NSLog(@"快排中%@", numbers.mj_JSONString);
    
    [self partitionSort:numbers low:l high:i-1];
    [self partitionSort:numbers low:i+1 high:h];
}
NSMutableArray *array = [NSMutableArray arrayWithArray:@[@100, @50, @30, @10, @200, @0, @-11, @44.5, @-20, @120.3]];
    NSLog(@"排序前:%@",[array mj_JSONString]);
    [self partitionSort:array low:0 high:array.count-1];
    NSLog(@"排序后:%@", [array mj_JSONString]);

排序前:[100.0, 50.0, 30.0, 10.0, 200.0, 0.0, -11.0, 44.5, -20.0, 120.3]
快排中:[-20.0, 50.0, 30.0, 10.0, 44.5, 0.0, -11.0, 100.0, 200.0, 120.3]
快排中:[-20.0, 50.0, 30.0, 10.0, 44.5, 0.0, -11.0, 100.0, 200.0, 120.3]
快排start0必须小于end-1
快排中:[-20.0, -11.0, 30.0, 10.0, 44.5, 0.0, 50.0, 100.0, 200.0, 120.3]
快排中:[-20.0, -11.0, 30.0, 10.0, 44.5, 0.0, 50.0, 100.0, 200.0, 120.3]
快排start1必须小于end0
快排中:[-20.0, -11.0, 0.0, 10.0, 30.0, 44.5, 50.0, 100.0, 200.0, 120.3]
快排中:[-20.0, -11.0, 0.0, 10.0, 30.0, 44.5, 50.0, 100.0, 200.0, 120.3]
快排start2必须小于end1
快排start3必须小于end3
快排start5必须小于end5
快排start7必须小于end6
快排中:[-20.0, -11.0, 0.0, 10.0, 30.0, 44.5, 50.0, 100.0, 120.3, 200.0]
快排start8必须小于end8
快排start10必须小于end9
排序后:[-20.0, -11.0, 0.0, 10.0, 30.0, 44.5, 50.0, 100.0, 120.3, 200.0]

超详细排序算法总结