<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd"> <html><head><meta http-equiv="Cont-阿里云开发者社区

开发者社区> 开发与运维> 正文

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd"> <html><head><meta http-equiv="Cont

简介: 冒泡排序解决了桶排序浪费 空间的问题,但在算法的执行效率上却牺牲了很多,它的时间复杂度达到了 O(N2)。假如我 们的计算机每秒钟可以运行 10亿次,那么对 1亿个数进行排序,桶排序只需要 0.1秒,而冒 泡排序则需要 1千万秒,达到 115 天之久。
  • 冒泡排序解决了桶排序浪费 空间的问题,但在算法的执行效率上却牺牲了很多,它的时间复杂度达到了 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。
  • 如图解所示:
  • 代码:
 #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;
}

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
开发与运维
使用钉钉扫一扫加入圈子
+ 订阅

集结各类场景实战经验,助你开发运维畅行无忧

其他文章