分治算法之快速排序

1、快速排序

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序

2、思路

( 1 )分解:先从数列中取出一个元素作为基准元素。以基准元素为标准,将问题分解为两个子序列,使小于或等于基准元素的子序列在左侧,使大于基准元素的子序列在右侧。

        假设当前待排序的序列为 R[low:high] ,其中 low ≤ high 。
        步骤 1 :首先取数组的第一个元素作为基准元素 pivot=R[low] 。 i=low , j=high 。
        步骤 2 :从右向左扫描,找小于等于 pivot 的数,如果找到, R[i] 和 R[j] 交换, i++ 。
        步骤 3 :从左向右扫描,找大于 pivot 的数,如果找到, R[i] 和 R[j] 交换, j−− 。
        步骤 4 :重复步骤 2 ~步骤 3 ,直到 i 和 j 指针重合,返回该位置 mid=i ,该位置的数正好是 pivot 元素。

( 2 )治理:对两个子序列进行快速排序。

( 3 )合并:将排好序的两个子序列合并在一起,得到原问题的解。

3、代码实现

  

   

    

     

    
    

     

      #include <iostream>
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      using namespace std;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      #define length 100
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      //让小于某个值的所以数排在它前面，所有大于它的数据排后面
     
    
   

    

     

    
    

     

      void swap(int *a, int
     
    
  
 

文章来源: chenyu.blog.csdn.net，作者：chen.yu，版权归原作者所有，如需转载，请联系作者。

原文链接：chenyu.blog.csdn.net/article/details/79596976