我的编程学习日志(8)--排序(冒泡,选择,快速以及sort函数)

分类: C/C++ , algorithm

2014-09-21

|

669

|

评论:1

分享:

关于排序最先学的就是后一个与前一个比较并交换的冒泡排序,记录下标的选择排序,这里就不多介绍了,只把它的代码贴出来,重点说一下快速排序。

一、冒泡,选择:

   //冒泡
         for(i=0;i<8;i++)
                   for(j=0;j<8-i-1;j++)
                   {
                            if(a[j]>a[j+1])
                            {
                                     t=a[j];
                                     a[j]=a[j+1];
                                     a[j+1]=t;
                            }
                   }
         //选择
         for(i=0;i<8;i++)
                   for(j=i;j<8-1;j++)
                   {
                            if(a[j]>a[j+1])
                            {
                                     t=a[j];
                                     a[j]=a[j+1];
                                     a[j+1]=t;
                            }
                   }

      

二、快速排序

(用c++的同学如果实在看不懂就不要看了,直接看 三。用纯c的话,你必须看懂)

既然叫快速排序,说明他是速度最快的。


快速排序首先选一个数组中的值作为参照,比他小的放在他的左边,大的放在右边。

然后对左半部分,同样选一个参照,比他小的放在他的左边,大的放在右边。

若此时左半部分的左边只有一个数,就对左半部分的右边做同样的操作。否则再对其(左半部分的左边)左边做同样操作。

左半部分完成后,对右半部分做和左半部分一样的操作。


具体过程如下:

一般选a[0]作为参照,假设数组为a[5],从小到大排

key=a[o];n=0;m=4;

①  然后把a[m]和key比较,如果a[m]<key就a[n]=a[m],

如果a[m]>=key,就m--,一直循环到a[m]<key或者m<n时结束循环。

(当然,若到循环结束也没找到一个a[m]大于key就说明数组是已经排好序的了。)

②  接下来把a[n]和key比较,如果a[n]>key就a[m]=a[n],如果a[n]<=key,就n++,一直循环到a[n]>key或者m<n时结束循环。

③  接着把key放到a[n],此时a[n]左边一定比他小,右边比他大。

④  然后对a[n]左边重复1,2,3步。

⑤  然后对a[n]右边重复1,2,3步。

实现时,4,5步用一个递归就行。

 

代码如下:

void quick(int*a,int i,int j)
{
         int n,m,key;
         key=a[i];
         n=i;
         m=j;
         while(n<m)
         {
                   while(a[m]>key&&m>n)
                   {m--;}
                   a[n]=a[m];
                   while(a[n]<key&&n<m)
                   {n++;}
                   a[m]=a[n];

         }
         a[n]=key;
         if(n>i) quick(a,i,n-1);
         if(n<j) quick(a,n+1,j);
}
int main()
{
         int a[5]={7,6,10,5,67};
         quick(a,0,5-1);
         return 0;
}


三、sort()函数

sort()函数在c++的头文件algorithm中

用法是sort(begin,end,排序规则)

sort()函数是用快速法排序,在不写排序规则的情况下,默认从小到大排序

 

代码如下:

#include<stdio.h>
#include<iostream>
#include<algorithm>
usingnamespace std;
intmain()
{
         int a[5]={7,6,10,5,67};
         sort(a,a+5);
         for(int i=0;i<5;i++)
                   printf("%d  ",a[i]);
         return 0;
}

(如果写成sort(a+1,a+4),表示对a[1]-a[3]排序)


那么,从大到小该如何做呢?

#include<stdio.h>
#include<iostream>
#include<algorithm>
usingnamespace std;
boolcompare(int a,int b)
{returna>b;}
intmain()
{
         int a[5]={7,6,10,5,67};
         sort(a,a+5,compare);
         for(int i=0;i<5;i++)
                   printf("%d  ",a[i]);
         return 0;
}


 

我们还可以用头文件functional里提供的函数

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<functional>
usingnamespace std;
intmain()
{
         int a[5]={7,6,10,5,67};
         sort(a,a+5,greater<int>());//从大到小
         sort(a,a+5,less<int>());//从小到大
         return 0;
}




标签: 快排 排序
本文共 1 个回复

n37r06u3
发布于:2018年7月17日 15:41
😑


发表评论 (对文章评论)

captcha