iOS - 快速排序

Demo_github

图片源于网络

快速排序

快速排序（Quick Sort）是对冒泡排序的一种改进。通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

算法思想

• 从数列中挑出一个元素，称为 "基准"（pivot）

• 分割（partition）操作:重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分割之后，该基准是它的最后位置。

• 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

• 快速排序是基于分治模式处理的，对一个典型子数组A[p...r]排序的分治过程为三个步骤：

  • 分解:
    A[p..r]被划分为俩个（可能空）的子数组A[p ..q-1]和A[q+1 ..r]，使得
    　A[p ..q-1] <= A[q] <= A[q+1 ..r]

  • 解决:
    通过递归调用快速排序，对子数组A[p ..q-1]和A[q+1 ..r]排序。

  • 合并:
    将排序好的子数组A[p ..q-1]和A[q+1 ..r]合并

图-快速排序示例图

上图中，演示了快速排序的处理过程：

• 初始状态为一组无序的数组：{2,4,5,1,3}

• 经过以上操作步骤后，完成了第一次的排序，得到新的数组：{1,2,5,4,3}

• 新的数组中，以2为分割点，左边都是比2小的数，右边都是比2大的数。

• 因为2已经在数组中找到了合适的位置，所以不用再动。

• 2左边的数组只有一个元素1，所以显然不用再排序，位置也被确定。（注：这种情况时，left指针和right指针显然是重合的。因此在代码中，我们可以通过设置判定条件left必须小于right，如果不满足，则不用排序了）。

• 2右边的数组{5,4,3},设置left指向5，right指向3，开始继续重复图中的一、二、三、四步骤，对新的数组进行排序。

范例代码

#pragma mark --- 快速排序
/**
 快速排序
 
 @param array 需要排序的Array
 @param left 初始索引
 @param right 最后一位索引
 */
+ (void)quickSort:(NSMutableArray *)array left:(int)left right:(int)right
{
    
    if(array == nil || array.count == 0 || left >= right){
        NSLog(@"注意快速排序条件");
        return;
    }
    
    // 以最左边的数(left)为基准
    int base = left;
    NSNumber *prmt = array[base];
    //    //取中值
    //    int middle = left + (right - left)/2;
    //    NSNumber *prmt = array[middle];
    int i = left;
    int j = right;
    
    /**
     while是循环流程控制，使用的标准格式为
     while(表达式)
     {
     循环语句体；
     }
     说明：①while循环的表达式是循环进行的条件，用作循环条件的表达式中一般至少包括一个能够改变表达式的变量，这个变量称为循环变量
     ②当表达式的值为真（非零）时，执行循环体；为假（0）时，则循环结束
     ③当循环体不需要实现任何功能时，可以用空语句作为循环体
     ④对于循环变量的初始化应在while语句之前进行，可以通过适当方式给循环变量赋初值
     */
    //开始排序，使得left<prmt 同时right>prmt
    while (i < j) {
        //        while ([array[j] intValue] > [prmt intValue]) {
        //该行与下一行作用相同
        // j 从右至左移动(j--) 直到找到一个小于[prmt intValue]的数停下来
        while ([array[j] compare:prmt] == NSOrderedDescending) {
            j--;
        }
        //        while ([array[i] intValue] < [prmt intValue]) {
        //该行与下一行作用相同
        /**
         i 从左至右移动(i++) 直到找到一个大于[prmt intValue]的数停下来
         */
        while ([array[i] compare:prmt] == NSOrderedAscending) {
            i++;
        }
        
        //如果i与j未相遇 交换其数据
        if(i < j){
            [array exchangeObjectAtIndex:i withObjectAtIndex:j];
            //i 与j 各移动一位 进入下一循环
            i++;
            j--;
        }
        NSLog(@"快速排序排序中:%@",array);
    }
    
    //第一轮排序完成 将数组拆成 A[p ..q-1] <= A[q] <= A[q+1 ..r] 模式的两个数组 递归
    /**
     程序调用自身的编程技巧称为递归（ recursion）。递归做为一种算法在程序设计语言中广泛应用。递归有直接递归和间接递归
     •直接递归：函数在执行过程中调用本身。
     •间接递归：函数在执行过程中调用其它函数再经过这些函数调用本身。
     •递归算法有四个特性：
     （1）必须有可最终达到的终止条件，否则程序将陷入无穷循环；
     （2）子问题在规模上比原问题小，或更接近终止条件；
     （3）子问题可通过再次递归调用求解或因满足终止条件而直接求解；
     （4）子问题的解应能组合为整个问题的解。
     */
    
    // 对“基准标号“左侧的一组数值进行递归的切割，以至于将这些数值完整的排序
    if (left < j) {
        [self quickSort:array left:left right:j];
    }
    // 对“基准标号“右侧的一组数值进行递归的切割，以至于将这些数值完整的排序
    if (right > i) {
        [self quickSort:array left:i right:right];
    }
}

算法分析

• 快速排序的算法性能

快速排序的算法性能

• 时间复杂度

  • 快速排序涉及到递归调用。其递归算法的时间复杂度公式：T[n] = aT[n/b] + f(n)

  • 最优情况下时间复杂度

    快速排序最优的情况就是每一次取到的元素都刚好平分整个数组；

    此时的时间复杂度公式则为：T[n] = 2T[n/2] + f(n)；T[n/2]为平分后的子数组的时间复杂度，f[n] 为平分这个数组时所花的时间；

    快速排序最优的情况下时间复杂度为：O( N*log N )

  • 最差情况下时间复杂度

    最差的情况就是每一次取到的元素就是数组中最小/最大的，这种情况其实就是冒泡排序了(每一次都排好一个元素的顺序)

    这种情况时间复杂度就是冒泡排序的时间复杂度：T[n] = n * (n-1) = n^2 + n;

    快速排序最差的情况下时间复杂度为：O( N^2 )

  • 平均时间复杂度

    快速排序平均时间复杂度为：O( N*log N )

• 空间复杂度

  快速排序在每次分割的过程中，需要 1 个空间存储基准值。
  最优的情况下空间复杂度为：O(log N) ；每一次都平分数组的情况
  最差的情况下空间复杂度为：O( N ) ；退化为冒泡排序的情况

• 算法稳定性

  在快速排序中，相等元素可能会因为分区而交换顺序，如: 当待排序元素类似[6,1,3,7,3]且基准元素为6时，经过分区，形成[1,3,3,6,7],两个3的相对位置发生了改变，所是快速排序是一种不稳定排序。

参考

排序二 快速排序

坐在马桶上看算法：快速排序

图解快速排序

排序算法之 快速排序 及其时间复杂度和空间复杂度