iOS算法总结-快速排序

末蓝、 2023-10-17 16:38 35阅读 0赞

快速排序 
    
      
      
       
    
       
       
        快速排序(Quick Sort) 的基本思想是：通过一趟排序将待排序的记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序的目的。 
    
      
      
       
    
      
      
       动效图如下： 
      
      
       
    
      
      
       
    
    
       
       
        
         
        
        快速排序动效图
       
       
        
    
      
      
       
    
      
      
       排序思路： 
    
      
      
       
    
       
       
        数组选第一个数，把比数小的放到数的左边，比数大的放到右边，结束后对左右两边的数组作重复处理即可。 
    
      
      
       
    
      
      
       排序演示： 
    
      
      
       假设数组为 [3，6，1，4，7，2，5] 
    
      
      
       
        
         
          下标 
          0 
          1 
          2 
          3 
          4 
          5 
          6 
         
        
        
         
          排序 
          3 
          6 
          1 
          4 
          7 
          2 
          5 
         
        
       
    
      
      
       以第一个元素3为基数，从最后一个元素开始查找比3小的数字，发现2，交换位置： 
    
      
      
       
        
         
          下标 
          0 
          1 
          2 
          3 
          4 
          5 
          6 
         
        
        
         
          排序 
          2 
          6 
          1 
          4 
          7 
          3 
          5 
         
        
       
    
      
      
       从2的右面开始与基数3比找比3大的数字，找到6，交换位置： 
    
      
      
       
        
         
          下标 
          0 
          1 
          2 
          3 
          4 
          5 
          6 
         
        
        
         
          排序 
          2 
          3 
          1 
          4 
          7 
          6 
          5 
         
        
       
    
      
      
       从6的左边面开始与基数3比，找比3小的数字，找到1，交换位置： 
    
      
      
       
        
         
          下标 
          0 
          1 
          2 
          3 
          4 
          5 
          6 
         
        
        
         
          排序 
          2 
          1 
          3 
          4 
          7 
          6 
          5 
         
        
       
    
      
      
       结束第一次排序，分别开始对3的左右两边的数据作循环对比，左边：2与1对比更改位置： 
    
      
      
       
        
         
          下标 
          0 
          1 
          2 
          3 
          4 
          5 
          6 
         
        
        
         
          排序 
          1 
          2 
          3 
          4 
          7 
          6 
          5 
         
        
       
    
      
      
       左边结束。右边：4为基数，从右边开始找比4小的数，找不到，循环结束，因为4的左边已经完毕，从4的右边开始，也就是从7开始作基数对比，找比7小得数放到7的左面，找到5，交换位置： 
    
      
      
       
        
         
          下标 
          0 
          1 
          2 
          3 
          4 
          5 
          6 
         
        
        
         
          排序 
          1 
          2 
          3 
          4 
          5 
          6 
          7 
         
        
       
    
      
      
       从5的右边查找发现已经有序，循环结束。 
    
      
      
       快速排序代码： 
    
      
      
       - (void)quickSortArray:(NSMutableArray *)array withLeftIndex:(NSInteger)leftIndex andRightIndex:(NSInteger)rightIndex
    {
        if (leftIndex >= rightIndex) {//如果数组长度为0或1时返回
            return ;
        }
        
        NSInteger i = leftIndex;
        NSInteger j = rightIndex;
        //记录比较基准数
        NSInteger key = [array[i] integerValue];
        
        while (i < j) {
            /**** 首先从右边j开始查找比基准数小的值 ***/
            while (i < j && [array[j] integerValue] >= key) {//如果比基准数大，继续查找
                j--;
            }
            //如果比基准数小，则将查找到的小值调换到i的位置
            array[i] = array[j];
            
            /**** 当在右边查找到一个比基准数小的值时，就从i开始往后找比基准数大的值 ***/
            while (i < j && [array[i] integerValue] <= key) {//如果比基准数小，继续查找
                i++;
            }
            //如果比基准数大，则将查找到的大值调换到j的位置
            array[j] = array[i];
            
        }
        
        //将基准数放到正确位置
        array[i] = @(key);
        
        /**** 递归排序 ***/
        //排序基准数左边的
        [self quickSortArray:array withLeftIndex:leftIndex andRightIndex:i - 1];
        //排序基准数右边的
        [self quickSortArray:array withLeftIndex:i + 1 andRightIndex:rightIndex];
    }
    
        NSMutableArray * arr = @[@16,@1,@2,@9,@7,@12,@5,@3,@8,@13,@10].mutableCopy;
        [self quickSortArray:arr withLeftIndex:0 andRightIndex:arr.count-1];
    
     
      
      
       打印结果为： 
      
      
       
       
       
        1,    2,    3,    5,    7,    8,    9,    10,    12,    13,    16 
      
      
       
      
      
       快速排序复杂度分析： 
      
      
       最优的情况下，时间复杂度为O(nlogn),最坏的情况下为O(n²)。平实的情况为O(nlogn)。 
      
      
       对于空间复杂度来说，主要是递归造成的栈空间的使用，最好情况，递归树的深度为log₂n,其空间复杂度也就是O(longn),最坏情况，需要进行n-1次递归调用，空间复杂度为O(n),平均情况，空间复杂度为O(logn) 
      
      
       可惜的是，由于关键字的比较和交换是跳跃进行的，因此，快速排序是一种不稳定的排序方法。 
      
      
       
     
     
      
    
    作者：方圆一里
    链接：http://www.jianshu.com/p/65b5d66e5c72
    來源：简书
    著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。