美文网首页程序员
十大经典排序c++笔记

十大经典排序c++笔记

作者: 优劣在于己 | 来源:发表于2020-10-11 14:41 被阅读0次

    最近翻了一下大一整理的一些代码,做个小笔记


    十大排序是排序里面最经典的了,掌握它其实也不难,只要理解就好了,看不懂就带数演练就好

    以下文字解释来自于我的理解,图片来自于网络,如有冒犯,请与我联系删除


    小目录:
    一.冒泡排序
    二.选择排序
    三.插入排序
    四.希尔排序
    五.快速排序
    六.桶排序
    七.基数排序
    八.计数排序
    九.归并排序
    十.堆排序


    一.冒泡排序

    算法原理:(小->大)
    比较相邻两个数的大小,前一个大于后一个就交换,第一次得到最后一个最大,之后最后一个就不参与比较,直至只剩最后一个元素为止

    代码如下:

    #include<iostream>
    using namespace std;
    int main(){
        int n,t,a[100];
        cin>>n;
        for(int i=0;i<n;i++)cin>>a[i];
        for(int i=0;i<n;i++){
            for(int j=0;j<n-i-1;j++){
                if(a[j]>a[j+1]){
                    t=a[j];
                    a[j]=a[j+1];
                    a[j+1]=t;
                }
            }
        }
        for(int i=0;i<n;i++) cout<<a[i]<<" ";
        return 0;
    }
    
    

    二、选择排序

    算法原理:(小->大)
    第一次先把里面最大的值的下标记录下来,然后放入最后一位,之后最后一位当作不存在,接着比较剩下的,以此类推

    代码如下:

    #include<iostream>
    using namespace std;
    int main(){
        int a[10],i,j;
        for(i=0;i<10;i++)cin>>a[i];
        for(i=0;i<10;i++){
            int k=i;//记录下标
            for(j=i;j<10;j++)
                if(a[k]<a[j])
                    k=j;
            if(k!=i){//符合条件交换
                int t=a[i];
                a[i]=a[k];
                a[k]=t;
            }
        }
        for(i=0;i<10;i++)cout<<a[i]<<" ";
        return 0;
    }
    
    

    三、插入排序

    算法原理:(小->大)
    这个举例子吧
    【50,40,70,20,60】从第二个位置开始

    第一次:比较50与40,小,往前走,最后结果【40,50,70,20,60】
    第二次:70与前一位比较,大,直接结束,放置当前位,最后结果【40,50,70,20,60】
    第三次:20与70比较,小,交换得【40,50,20,70,60】,接着再与50比较,换得【40,20,50,70,60】,再与40比较最终得【20,40,50,70,60】
    第四次:60与70比较,小,换【20,40,50,60,70】,与50比较,大,停止
    结束最终得【20,40,50,60,70】

    代码如下:

    #include<iostream>
    using namespace std;
    int n,a[10];
    int main(){
        cin>>n;
        for(int i=0;i<n;i++)cin>>a[i];
        for(int i=1;i<n;i++){
            for(int j=i;j>0;j--){
                if(a[j]<a[j-1]){
                    int t=a[j];
                    a[j]=a[j-1];
                    a[j-1]=t;
                }
                else break;
            }
        }
        for(int i=0;i<n;i++)cout<<a[i]<<" ";
        return 0;
    }
    
    

    四、希尔排序

    算法原理:(小->大)

    代码如下:

    # include<iostream>
    using namespace std;
    void shellsort(int a[], int size){
        int i, j, gap;
        for (gap = size / 2; gap > 0; gap /= 2){ // 每次的增量,递减趋势
            for (i = gap; i < size; i++) //每次增量下,进行几组插入排序,如第一步就是(从12,9,73,26,37)5次
                for (j = i ; j -gap >= 0 && a[j-gap] > a[j]; j -= gap)// 每个元素组中进行直接插入排序
                    swap(a[j-gap], a[j]); //交换函数
            for(int k=0; k<size; k++) // 输出每轮排序结果
                cout<<a[k]<<",";
            cout<<endl;
            }
    }
    int main(){
        int array [10] = {8,9,1,7,2,3,5,4,6,0};
        int len = 10;
        cout<<"输入的原始序列:  ";
        for(int i=0; i<len; i++)cout<<array[i]<<","; // 输出原序列
        cout<<endl<<endl;
        cout<<"  ----希尔排序开始---- " << endl;
        shellsort(array,len); // 调用排序函数
        return 0;
    }
    
    

    五.快速排序

    算法原理:(小->大)
    1、从数列中取出一个数作为基准数(x)。
    2、将数组进行划分,将比基准数大的元素都移至枢轴右边,将小于等于基准数的元素都移至枢轴左边。
    3、再对左右的子区间重复第二步的划分操作,直至每个子区间只有一个元素。

    代码如下:

    #include<iostream>
    using namespace std;
    int ssort(int a[],int l,int r){
        int i=l,x=a[l];//x为基准数
        for(int j=l+1;j<=r;j++){
            if(a[j]<=x){
                i++;//i的位置前面都是小于等于基准数的
                swap(a[i],a[j]);//交换函数,比它小,放左边
            }
        }
        swap(a[i],a[l]);//最终i的位置为基准数的最终位置
        return i;
    }
    void ksort(int a[],int l,int r){
        if(l<r){
            int i=ssort(a,l,r);
            ssort(a,l,i-1);//左右两边继续递归
            ssort(a,i+1,r);
        }
    }
    int main(){
        int a[100],n;
        cin>>n;
        for(int i=0;i<n;i++)cin>>a[i];
        ksort(a,0,n-1);
        for(int i=0;i<n;i++)cout<<a[i]<<" ";
        return 0;
    }
    
    

    六.桶排序

    简单桶排序

    算法原理:(小->大)
    1、建立好对应的桶
    2、把要排序的数组分别放入对应的桶中
    3、统计元素在桶中出现的次数
    4、按照桶的顺序输出同理的元素

    代码如下:

    #include <iostream>
    #include<cstring>
    using namespace std;
    int max1=8;//数组中的最大值
    int Score[5]={5,3,5,2,8};
    void TongSort(int *score,int num){
        int a[max1+1];
        memset(a,0,sizeof a);//桶的初始化
        for(int i=0;i<num;i++){
            int temp=score[i];
            a[temp]++;
        }
        for(int i=0;i<max1+1;i++){
            for(int j=1;j<=a[i];j++)
               cout<<i<<" ";
        }
    }
    
    int main(){
        int num=5;
        TongSort(Score,num);
        return 0;
    }
    
    
    基本桶排序

    算法原理:(小->大)
    设置一个定量的数组当作空桶;
    遍历输入数据,并且把数据一个一个放到对应的桶里去;
    对每个不是空的桶进行排序;
    从不是空的桶里把排好序的数据拼接起来。

    代码如下:

    #include <iostream>
    #include <vector>
    #include <algorithm> 
    using namespace std; 
    void bksort(float A[],int l,int h){
        int size = h-l+1;
        vector<float> b[size];//有size个数据,就分配size个桶
        for(int i=l;i<=h;i++){
            int bi = size*A[i];//元素A[i]的桶编号
            b[bi].push_back(A[i]);//将元素A[i]压入桶中
        }
        for(int i=0;i<size;i++)
            sort(b[i].begin(),b[i].end());//桶内排序
        int idx = l;//指向数组A的下标
        for(int i=0;i<size;i++){//遍历桶
            for(int j=0;j<b[i].size();j++){//遍历桶内元素
                A[idx++] = b[i][j];
            }
        }
    }
     
    int main(){
        float A[] = {0.78,0.17,0.39,0.26,0.72,0.94,0.21,0.12,0.23,0.68};
        bksort(A,0,9);
        for(int i=0;i<10;i++)
            cout<<A[i]<<" ";
    }
    

    七.基数排序

    算法原理:(小->大)
    从低位开始排,之后再往前一位,直至最后

    代码如下:

    #include<iostream>
    using namespace std;
    void kkk(int a[],int n){
        for(int i=1;i<=100;i*=10){
            int tmp[20][10]={0};//临时存放的位数地址数组
            for(int j=0;j<n;j++){
                int t=(a[j]/i)%10;
                tmp[j][t]=a[j];//存放在与当前位数相同的数的位置
            }
            int k=0;
            for(int p=0;p<10;p++){
                for(int q=0;q<n;q++){
                    if(tmp[q][p]!=0)
                        a[k++]=tmp[q][p];//更新数组
                }
            }
        }
    }
    int  main(){
        int a[100]={11,99,25,31,51,12,85,123};
        int n=8;
        kkk(a,n);
        for(int i=0;i<n;i++)
            cout<<a[i]<<" ";
        cout<<endl;
    }
    
    

    八.计数排序

    算法原理:(小->大)
    记录比当前位小的数的个数n,然后放入另一个数组的第n位储存,如果已经储存了之前相同的数,那就往后挪一位
    代码如下:

    #include<iostream>
    using namespace std;
    void kkk(int a[],int len,int b[]){
        if(len<1)
            return ;
        for(int i=0;i<len;i++){
            int cc=0;//对第i个数计数,记录比它小的数的个数
            for(int j=0;j<len;j++){
                if(a[i]>a[j])
                    cc++;
            }
            while(b[cc]==a[i])
                cc++;//如果有多个相同的往后移位
            b[cc]=a[i];
        }
    }
    int main(){
        int a[10]={45,12,100,14,12,85,12,45,85,65};
        int b[10]={0};
        int n=10;
        cout<<"before:";
        for(int i=0;i<n;i++)cout<<a[i]<<" ";
        kkk(a,n,b);
        cout<<endl<<"after:";
        for(int i=0;i<n;i++)cout<<b[i]<<" ";
        return 0;
    }
    
    

    九.归并排序

    算法原理:(小->大)
    采用分治法,划分最小块,然后相邻比较,之后又跟相邻的比较,看动图就理解了

    代码如下:

    #include<iostream>
    #include <cstdlib>
    using namespace std;
    void Merge(int A[],int B[], int L, int mid, int R){
        int i = L, j=mid+1, k = L;
        while(i!=mid+1 && j!=R+1){
            if(A[i] > A[j])
                B[k++] = A[j++];
            else
                B[k++] = A[i++];
        }
        while(i != mid+1)
            B[k++] = A[i++];
        while(j != R+1)
            B[k++] = A[j++];
        for(i=L; i<=R; i++)
            A[i] = B[i];
    }
    //内部使用递归
    void vvv(int A[], int B[], int l, int r){
        int mid;
        if(l < r)    {
            mid= l + (r-l) / 2;//避免溢出int
            vvv(A, B, l, mid);
            vvv(A, B, mid+1, r);
            Merge(A, B, l, mid, r);
        }
    }
    int main(){
        int a[8] = {50, 10, 20, 30, 70, 40, 80, 60};
        int i, b[8];
        vvv(a, b, 0, 7);
        for(i=0; i<8; i++)cout<<a[i]<<" ";
        return 0;
    }
    
    

    十.堆排序

    算法原理:(小->大)
    先组成一个大顶堆,之后每次输出a[0],从而完成排序

    动图演示

    代码如下:

    #include<bits/stdc++.h>
    using namespace std;
    void paixu(int a[],int star,int end1){
        int dad=star;
        int son=dad*2+1;
        while(son<=end1){
            if(son+1<=end1&&a[son]<a[son+1])//这个判断是否有右孩子,以及左右孩子的大小
                son++;//记录较大孩子
            if(a[son]<a[dad])
                return ;
            else{
                int t=a[son];
                a[son]=a[dad];
                a[dad]=t;
                dad=son;
                son=dad*2+1;
            }
        }
    }
    void duipai(int a[],int n){
        for(int i=n/2-1;i>=0;i--)//即有孩子的父亲开始,完成大顶堆
            paixu(a,i,n-1);
        for(int i=n-1;i>0;i--){//将每a[0]放置最后一位代表输出了
            int t=a[i];
            a[i]=a[0];
            a[0]=t;
            paixu(a,0,i-1);
        }
    }
    int main(){
        int a[10]={10,80,50,20,60,30,90,40,70,100};
        int n=10;
        duipai(a,n);
        for(int i=0;i<n;i++)cout<<a[i]<<" ";
        cout<<endl;
        return 0;
    }
    

    相关文章

      网友评论

        本文标题:十大经典排序c++笔记

        本文链接:https://www.haomeiwen.com/subject/vfrlpktx.html