排序算法

这篇文章主要介绍了啊哈算法的排序问题，包括桶排序、快速排序、冒泡排序

桶排序

算法描述

这个算法好比有11个桶，编号从0~10。每出现一个数，就在对应编号的桶里放一个小旗子。最后只要数数每个桶中有几个小旗子就可以了。例如2号桶中有2个旗子，表示数字2出现了2次。

问题描述

班上有5个同学，输入5个同学的分数（满分是10分），按从大到小输出5个同学的分数

输入数据

5 3 5 2 8

输出数据

8 5 5 3 2

代码

#include<stdio.h>
#include<iostream>
using namespace std;
int main(){
    int a[11]={0},t;//将数组元素初始化为0
    //int a[11]={1};第一个元素为1，其他元素为0
    for(int i=0;i<5;i++){//循环输入5个数
        cin>>t;
        a[t]++;
    }
    for(int i=0;i<10;i++){
        for(int j=0;j<a[i];j++){
            cout<<i<<"  ";
        }
    }
    getchar();getchar();
    return 0;
}

快速排序

算法描述

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

代码

#include<stdio.h>
#include<iostream>
using namespace std;
int n,a[101];
void quicksort(int left,int right){
    int temp,i ,j ,t;//temp存基数
    if(left>right){
        return;
    }
    temp=a[left];
    i=left;
    j=right;
    while(i!=j){
        //顺序很重要，要先从右往左查找
        while(a[j]>=temp && i<j){
            j--;
        }
        //然后从左往右找
        while(a[i]<=temp&&i<j){
            i++;
        }
        //交换两个数的位置
        if(i<j){//当哨兵没有相遇时
            t=a[i];
            a[i]=a[j];
            a[j]=t;
        }
    }
    //最终基数归位
    a[left]=a[i];
    a[i]=temp;
    quicksort(left,i-1);
    quicksort(i+1,right);
}
int main(){
    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;
}