我的编程学习日志（8）--排序（冒泡，选择，快速以及sort函数）

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

一、冒泡，选择：

   //冒泡
         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;
}

那么，从大到小该如何做呢？

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