c/c++开发分享C日记——基本的排序算法

语法是语言的特色，而算法却是灵魂

算法不分语言

入门的算法要数排序算法

今天的算法讲解将以为例子将以下几个排序算法

1. 桶排序

2. 插入排序

3. 冒泡排序

4. 快速排序

首先给大家介绍一个最简单粗暴的排序算法

桶排序

桶排序要先知道要排序的数的范围

然后要这么多的桶去装这些可能出现数的次数

 

 

//这里的范围是0~999

int b[1000];

这个数组就是用来装出现次数的

然后输入数字，然后这个相应的桶的次数就加1

输出时遍历全部桶，然后桶的数字是几就输出几次这个数字

代码如下

#include

int main(){

int num;

//弄一个大桶装所有可能出现的数，用来记录每个数字出现的次数，桶的个数是可能出现的最大值

  int b[1000]={0};    int i,j;    for(i=0;i<10;i++){    scanf("%d",&num);    //该数字出现次数+1    b[num]++;    }    for(i=0;i<1000;i++){    //桶有装有几个数就输出几次    for(j=0;

这方法够简单够粗暴吧

其实这方法还可以优化一下

我们虽然是知道范围，但输入的数的范围可能要比给出的范围少得多，这样的话遍历全部桶就很浪费时间了

所以我们可以找到输入数字的最大值和最小值，只需遍历最大值和最小值之间的桶就行了，因为其他桶都是0，不用输出所以代码就可以改为
#include

int main(){

int num;

//弄一个大桶装所有可能出现的数，用来记录每个数字出现的次数，桶的个数是可能出现的最大值

  int b[1000]={0};    int max=0;    int min=1000;    int i,j;    for(i=0;i<10;i++){    scanf("%d",&num);    //该数字出现次数+1    b[num]++;    / 到最大值，后面输出可以节省时间，最大值后面的桶都是0，也可以再找最小值，最小值前面的桶都是0    if(num>max){    max=num;    }    if(num

桶的编码对应的是它记录的数字然后有人就问如果有负数怎么办负数的话，把全部桶平移一下就好，输出时把桶的编码再减去平移值

比如范围是-10~9

可以开个数组int b[20];

输入的话就是b[num+10]++

输出的话printf(“%d “,i-10);

这个算法大概就是这样了，虽然说是简单，但是我们通常情况下是不知道确切的范围的，如果以最大范围去开辟桶就会很浪费空间然后接下来讲第二种算法插入排序插入排序的基本思想是，从第二个数开始，插入到前面有序序列的位置

 

比如说3个数，分别是5,4,2

 

然后从第二个数开始

4比5小，应该插到5的前面

然后5后退一位

现在的序列4，5，2然后到第三个数2

2应该插到4前面

所以4和5都要后退一位

现在就变成2,4,5的有序序列了具体代码是这样#include

int main(){

int a[1000];

int b;

int i;

for(i=0;i<10;i++){

scanf("%d",&a[i]);

//还可以在输入的时候就排序了

}

for(i=1;i<10;i++){

int temp=a[i];

int n=i-1;

//跟前面的比较，小的话就向前，并且该位向后移动一位

while(n>-1&&temp第二个for循环i=1就是从第二个数开始可能需要大家一点抽象思维去想象比如排队

是按号排队的

他迟到了

然后他就拿这号从最后一位一直向前问

后面的都比他大，终于找到一个比他小的

他不可能排他前面，所以只能排他后面

然后他就插队进去了

他后面的人都被他挤后了一位接下来介绍另一种排序算法冒泡排序冒泡排序的思想是，每次把最小的数冒到左边

就像气泡一样越接近水面的泡泡越大

 

继续是以刚刚的数列5,4,2为例

 

从第一个数开始

5比4大，然后就交换

4比2大然后就交换

然后现在的序列是2，5，4

然后到第二个数开始

5比4大，交换位置

然后这个序列就排好了具体代码如下#include

int main(){

int a[1000];

int i,j,temp;

for(i=0;i<10;i++){

scanf("%d",&a[i]);

}

for(i=0;i<9;i++){

//跟后面的所有数进行比较，大的就交换

for(j=i+1;j<10;j++){

//交换

if(a[i]>a[j]){

temp=a[i];

a[i]=a[j];

a[j]=temp;

}

}

}

for(i=0;i<10;i++){

printf("%d ",a[i]);

}

return 0;

} 这种排序方法是初学者必须掌握的一种排序方法最后讲一种高级一点的算法快速排序掌握这种方法可以说是初学者的分水岭这种排序方法包含了递归和分治的思想递归我们最熟悉的就是吃桃最后一天剩一个，每天吃总数的一半，吃了五天，然后问你最开始有多少个桃子然后就是从最后一天开始算，一直算到第一天分治就是，讲一个问题分开处理但分开处理是没有影响的就比如扫地可以扫地分为扫客厅和扫房间快速排序的思想是从给一个数组，然后在数组中找一个基准值两边派一个士兵去帮我找数要从右边的士兵开始右边的士兵要找一个比基准值小的数找到后停下来等左边的士兵左边的士兵要找一个比基准值大的数找到后就停下来，交换这两个数的位置交换后继续找，直到他们相遇相遇时这个数一定比基准值小大家直到为啥吗我们有一个很关键的一步从右边开始右边停下的位置一定是小于基准值的相遇后相遇的数和基准值交换，我们这里取最左边的数为基准值交换之后，基准值的左边都是比基准值小的，基准值右边都是比基准值大的然后就按相同的规则排基准值的左边和右边排序时不仅要传入数组，还要传入范围一旦排到左边界等于右边了就不用排了，就可以return返回了代码如下#include

int main(){

int a[1000];

int i;

for(i=0;i<10;i++){

scanf("%d",&a[i]);

}

quicksort(a,0,9);

for(i=0;i<10;i++){

printf("%d ",a[i]);

}

return 0;

}

void quicksort(int a[],int left,int right){

if(left>=right){

return;

}

int low=left;

int high=right;

//这个基准值可以随便取，只要在left和right范围内就好

int key=a[left];

while(low!=high){

//顺序很重要，要先从右边开始找

//因为最后交换时左边的要都比基准小

//右边大于基准值就跳过

while(low=key){

high–;

}

//左边小于基准值就跳过

while(low如果大家理解了这种算法，对c语言的造诣就会深一层

这篇关于快速排序博客有配图更加形象这里讲的都是从小到大的排序，大家可以思考一下用这几种算法如何从大到小排序