十大经典排序c++笔记

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

---

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

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

---

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

---

一.冒泡排序

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

代码如下：

#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;
}