桶排序+冒泡+选择+快排之总结

r囧r小猫 2022-05-13 01:48 131阅读 0赞

一：

桶排序。

在2018年九月九号发现了这个神奇的算法，精神为之振奋！

这是一个最简单的桶排序，

例题：有五个学生的成绩，需要排序。

下列代码是桶排序的简化版，但是大致思想是相同的，不过这种排序对空间开销有点大：

#include<cstdio>
    #include<iostream>
    #include<cmath>
    #include<cstdlib>
    using namespace std;
    int a[101]={};
    int main()
    {
        int i=0,sore=0;
        for(;i<5;i++){
            cin>>sore;
            a[sore]++;
        }
        for(int i=0;i<101;i++)
            for(int j=0;j<a[i];j++)
            if(a[i])cout<<i<<endl;
        system("pause");
    }

冒泡：

老冒泡排序，自己分了一年也没有分清楚冒泡和选择排序的区别，希望自己这次记住吧！

#include<cstdio>
    #include<iostream>
    #include<cmath>
    #include<cstdlib>
    using namespace std;
    int a[5]={};
    int main()
    {
        int i=0,sore=0;
        for(;i<5;i++){
            cin>>sore;
            a[i]==sore;
        }
        for(int i=0;i<5-1;i++)//需要N-1次遍历 
            for(int j=0;j<5-1-i;j++)//每次将最大（小）的一个放在最后面 
                if(a[j]>a[i]){
                    int tem=a[i];
                    a[i]=a[j];
                    a[j]=tem;
                } 
        system("pause");
    }

接下来是选择排序：

这是鄙人闭着眼都能搞下来的排序！哈哈

#include<cstdio>
    #include<iostream>
    #include<cmath>
    #include<cstdlib>
    using namespace std;
    int a[5]={};
    int main()
    {
        int i=0,sore=0;
        for(;i<5;i++){
            cin>>sore;
            a[i]==sore;
        }
        for(int i=0;i<5-1;i++)//需要N-1次遍历 
            for(int j=i+1;j<5;j++)//每次将最大（小）的一个放在最后面 (这里和冒泡排序不一样)
                if(a[j]>a[i]){
                    int tem=a[i];
                    a[i]=a[j];
                    a[j]=tem;
                } 
        system("pause");
    }

还有快排，快速排序：

我在以前的博客：快速排序入门有图有真相的详细的介绍了快排，这里就再粗略提一下！

快排是一个具有二分思想的，最坏情况复杂度和冒泡一样的算法！

在最左（也可以是最右）设立一个哨兵，每次把大于哨兵的数放在哨兵右边，小于哨兵的数放在哨兵左边，递归至结束！

void quicksort(long left,long right)
    {
        if(left>right){return ;}
        long i=left,j=right;
        long long tem=ac[left];
        while(i!=j){
            while(i<j&&ac[j]>=tem)j--;
            if(i<j)ac[i++]=ac[j];    
            while(i<j&&ac[i]<=tem)i++;
            if(i<j)ac[j--]=ac[i];
        }
        ac[i]=tem;
        quicksort(left,i-1);
        quicksort(i+1,right);
    }
    
    
    void quicksort(long left,long right)
    {
        if(left>right)return ;
        long i=left,j=right;
        long long tem=ac[left]; 
        while(i<j){
            while(i<j){
                if(ac[j]>tem){j--;
                }else{
                    ac[i++]=ac[j];    
                    break;
                }
            }    
            
            while(i<j){
                if(ac[i]<tem){i++;
                }else {
                    ac[j--]=ac[i];    
                    break;
                }    
            }
        }
        ac[i]=tem;
        quicksort(left,i-1);
        quicksort(i+1,right);
    }
    
    
    void quicksort(int left,int right)
    {
        int i,j,base;
        i=left; j=right;//i为最左下标志 
        base=ac[(i+j)/2];//随机取值取个中间值 
        while (i<=j){
            while (ac[i]<base) i++;
            while (ac[j]>base) j--;
            if (i<=j){
                int t=ac[i]; ac[i]=ac[j];ac[j]=t;
                i++;
                j--;
            }
        }
        if (left<j) quicksort(left,j);
        if (i<right) quicksort(i,right);
    }

接下来会有合并等排序方法，日后补写！