排序算法学习

我们要学习的排序算法有: 冒泡排序,归并排序,快速排序,使用C++的sort.

冒泡排序

冒泡排序是很简单的算法,这里我们看一下它的原是就可以了

通过的上面的图片我们可以等到下面的信息:

每一趟排序都是把最值排序在后面
对于有n个数的数组来说,要排序n-1趟
- n个数字只n-1个数字就可以了,最后一个数字自动就在第一位
对第1趟排序的范围是a[1]-->a[n-1]
对第2趟排序的范围是a[1]-->a[n-2]
对第i趟排序的范围是a[1]-->a[n-i]

一句话算法：第一趟循环len-1次,第二趟循环len-2次,第i趟循环len-i次

bubble_sort代码核心代码

void bubble_sort(int a[],int len){
    int i=len,j;
    for(i=1;i<=len-1;i++)
        for(j=1;j<=len-i;j++){
            if(a[j] > a[j+1]){
                tmp =a[j];
                a[j] =a[j+1]
                a[j+1]=tmp;
            }
        }
}

归并排序

原理如下:

我们发现归并排序原理就是:对原来已经有序的两个数组就合并操作(取两个头部比较)后还是有序.

简单的说归并排序就是:从两个有序数组的头部开始取,谁小就取谁

那我们的代码如下:

#include <cstdio>

int a[] = {1,3,7};
int b[] = {2,5,6};
int tmp[100];

int merge(){
    int i=0,j=0;//i,j分别指向a,b的头部
    int k=0;//k是tmp数的下标
    int len_a = sizeof(a)/sizeof(a[0]); //a的长度
    int len_b = sizeof(b)/sizeof(b[0]);//b的长度

    while(i< len_a && j< len_b){
        if(a[i] < b[j]){
            tmp[k]=a[i];i++;k++;
        } else{
            tmp[k]=b[j];j++;k++;
        }
    }
    while(i<len_a) {tmp[k++] = a[i];i++;}; //复制a数组的剩余
    while(j<len_b) {tmp[k++] = b[j];j++;}; //复制b数组的剩余
}

int main(){

    merge();

    int i;
    int len_a = sizeof(a)/sizeof(a[0]); //a的长度
    int len_b = sizeof(b)/sizeof(b[0]);//b的长度
    for(i=0;i<len_a+len_b;i++)
        printf("%d ",tmp[i]);
    return 0;
}

这里有一个问题:如果我们的数组只有一个,如何使用归并排序?

很简单,我们只要把数组tmp里的值再赋值给原数组就可以了!

完整的代码

/* 
 *  算法思想:
 *      分治
 * */

#include <cstdio>

int a[] ={1,7,3,6,5,2};
int tmp[100]; //临时存储的中间数组

void merge_sort(int s,int t){
        //s =start t=T
    int mid,i,j,k;

    if(s==t) return ; //如果区间只有一个数,就返回

    mid = (s+t)>>1; //取中间的点
    merge_sort(s,mid);
    merge_sort(mid+1,t);

    i=s;
    j=mid+1;
    k=s;

    while(i<=mid && j<=t){
        if( a[i] <=a[j]){
            tmp[k]=a[i];k++;i++;
        } else {
            tmp[k]=a[j];j++;k++;
        }
    }

    while(i<=mid) { tmp[k]=a[i];k++;i++;};
    while(j<=t)   { tmp[k]=a[j];k++;j++;};

    for(i=s;i<=t;i++)
        a[i]=tmp[i];
}

int main()
{
    merge_sort(0,sizeof(a)/sizeof(a[0])-1);
    int i;
    for(i=0;i<sizeof(a)/sizeof(a[0]);i++)
        printf("%d ",a[i]);
    return 0;
}

快速排序

快速排序的基本思想: 通过一趟排序将数组分成两个部分,其中一个部分都比关键字小,另一个部分都比关键字大,然后再分别对这两部分进行这种操作,最后就可以达到全部有序.通常我们取待排序部分的第一个值为关键字.

我们能不能把步骤想的更具体一点,怎么样做才能把数分成这样的两个部分?

上面的图片解释了一趟快速排序的原理,如果你有足够的想想象力,可以把红色,蓝色下标想象成两个机器人,它们不停的移动去判断值,一但符合条件,就把箱子里的值仍给另一个机器人,自己停止,另一个机器人又开始工作,这样的不停往返的下去,就可以把数分成两个部分了.

快速排序代码

/* 
 *   快速排序本质:
 *      用key值,把数据分成两个部分,一部分比较key小,一部分比key大
 * */

#include <cstdio>

int a[]={6,2,7,3,8,9};

void quicksort(int l,int r){
    int s=l,t=r;
    int key =a[l]; // 取第一个值为key

    while(s < t){
        while( s <t && a[t] >= key) --t;// 如果a[t] >= key,t下标不停变小,直到a[t] < key
        if(s < t) a[s++] = a[t];        //停下来的时候,看一看,是不是到中点,如果不是 交换值
        while(s<t && a[s] <= key) ++s;  //如果a[s] <= key  s的下标不停变大,直到a[s] > key
        if(s<t ) a[t--] = a[s];         //停下来的时候,看一看,是不是到了中点,如果不是,交换值
    }
    a[s] = key;  //上面while停止的时候,一定是s ==t
    quicksort(l,s-1);
    quicksort(s+1,r);
}

int main(){
    int len_a = sizeof(a)/sizeof(a[0]);
    quicksort(0,len_a-1);
    return 0;
}

C++内部函数 sort

下面的我们来使用C++本身给我们提供的排序函数.

sort(a+m,a+n);      //[a+m,a+n) 范围内的元素进行排序
sort(a+m,a+n,cmp); //cmp 是函数

样例代码

#include <cstdio>
#include <algorithm>
using namespace std;

int a[100];
int main(){
    int i;
    for (i=0;i<10;i++){ //输入10个数
        scanf("%d",&a[i]);
    }

    sort(a+0,a+10); //数组名+数字的本质是指针操作
    for(i=0;i<10;i++)
        printf("%d ",a[i]);

    return 0;
}

如果我们想让从大到小排序怎么办?

#include <cstdio>
#include <algorithm>
using namespace std;

int a[100];

/* 原是是为真的时候,第一个数字放前面 */
int mycmp(int &a,int &b){ 
    if(a > b)
        return 1;
    return 0;
}

int main(){
    int i;
    for (i=0;i<10;i++){ //输入10个数
        scanf("%d",&a[i]);
    }

    sort(a+0,a+10,mycmp); //数组名+数字的本质是指针操作
    for(i=0;i<10;i++)
        printf("%d ",a[i]);

    return 0;
}

冒泡排序

bubble_sort代码核心代码

归并排序

快速排序

C++内部函数 sort

题目