快速排序--最常用的排序

你的名字 2022-06-02 06:11 198阅读 0赞

*  冒泡排序解决了桶排序浪费 空间的问题，但在算法的执行效率上却牺牲了很多，它的时间复杂度达到了 O(N2)。假如我 们的计算机每秒钟可以运行 10亿次，那么对 1亿个数进行排序，桶排序只需要 0.1秒，而冒 泡排序则需要 1千万秒，达到 115 天之久。所以这里介绍下一个—快速排序
 *  其实快速排序是基于一 种叫做“二分”的思想。它的平均时间复杂度为 O(NlogN)。
 *  假设我们现在对“6 1 2 7 9 3 4 5 10 8”这 10个数进行排序。首先在这个序列中随 便找一个数作为**基准数**。为了方便，就让第一个数 6 作为基准数吧。接下来，需要将这个序列中 所有比基准数大的数放在 6的右边，比基准数小的数放在 6的左边，类似下面这种排列。  
    3 1 2 5 4 6 9 7 10 8
 *  先从 右往左找一个小于 6的数，再从左往右找一个大于 6的数，然后交换它们。这里可以用两个 变量 i和 j，分别指向序列左边和右边。我们为这两个变量起个好听的名字“哨兵 i”和 “哨兵 j”。刚开始的时候让哨兵 i指向序列的左边（即 i=1），指向数字 6。让哨兵 j指向序 列的右边（即 j=10），指向数字 8。
 *  如图解所示：  
    ![5036250.jpg][]
 *  代码：

#include<iostream>
    using namespace std;
     int a[101],n;
    void quicksort(int left,int last){
         if(left>last){
            return ;
         }
         int key=a[left];
         int i=left;
         int j=last;
         int t;
         while(i!=j){
            while(a[j]>=key&&i<j){
                j--;
            }
            while(a[i]<=key&&i<j){
                i++;
            }
            if(i<j){
    
                t=a[i];
                a[i]=a[j];
                a[j]=t;
            }
         }
         a[left]=a[i];
         a[i]=key;
         quicksort(left,i-1);
         quicksort(j+1,last);
    
    }
    int main(){
       int n;
       cin>>n;
       for(int i=0;i<n;i++){
        cin>>a[i];
       }
       quicksort(0,n-1);
        for(int i=0;i<n;i++){
            cout<<a[i]<<" ";
        }
      return 0;
    }

[5036250.jpg]: http://oz3ijy2k5.bkt.clouddn.com/18-1-5/5036250.jpg