优秀算法系列--排序算法（一）

排序算法是我们常用算法之一，也是计算机程序设计中的一种重要操作，它的功能是将一个数据元素（或记录）的任意序列，重新排列成一个关键字有序的序列。排序过程中涉及的存储器不同，可将排序方法分为两大类：一类是内排序，指的是待排序记录存放在计算机随机存储器中进行的排序过程，内排序有：插入排序、希尔排序、交换排序、快速排序、选择排序等；另一类是外排序，指的是待排序记录的数量很大，以致内存一次不能容纳全部记录，在排序过程中尚需对外存进行访问的排序过程。

下面说一下交换排序，交换排序主要有：冒泡排序和快速排序，快速排序（Quicksort）其实是对冒泡排序的一种改进。

为了方便描述，使用顺序表类型定义如下：

#define MAXSIZE 1000
typedef int KeyType;
typedef struct {
KeyType key;
InfoType otherinfo;
}RecType;

typedef struct {
RecType r[MAXSIZE+1];
int length;
}SqList;
　　

冒泡排序
基本概念是：依次比较相邻的两个数，将小数放在前面，大数放在后面。整个排序过程最多执行n-1趟，它是一种稳定的算法。

　　C Code：

void BubbleSort(SqList &q)
{
int j,h,p=q.length-1,temp;
for(h=1;h<=p;)
for(j=0;j<p-1;j++)
    if(q.r[j].Key>q.r[j+1].key)
     {
      temp=q.r[j];
      q.r[j]=q.r[j+1];
      q.r[j+1]=temp;
      p=j
     }
}
　　冒泡排序法存在这不足,当排序的数据比较多时排序的时间会明显延长。具体做法：任意选取某一记录（通常取第一个记录），比较其关键字与所有记录的关键字，并将关键字比它小的记录全部放在它的前面，将比它大的记录均存放在它的后面，这样，经过一次排序之后，可将所有记录以该记录所在的分界点分为两部分，然后分别对这两部分进行快速排序，直至排序完 ,这就是改进的方法：快速排序。

快速排序
　设要排序的数组是a[0]……a[n-1]，

一趟快速排序的算法是：

　　1）设置两个变量low、high，排序开始的时候：low=0，low=n-1；

　　2）以第一个数组元素作为关键数据，赋值给key，即 key=a[0]；

　　3）从J开始向前搜索，即由后开始向前搜索（high=high-1），找到第一个小于key的值a[high]，并与a[low]交换；

　　4）从I开始向后搜索，即由前开始向后搜索（low=low+1），找到第一个大于key的a[low]，与a[high]交换；

　　5）重复第3、4、5步，直到 low=high；

示意图：

C Code:

void QuickSort(SqList &R ,int s,int t)
{
   int low, high,Key;
   low=s;
   high=t;
   Key=R.r[s].key;
   R.r[0]=R.r[s];
   while(low<high)
    {
        while(high>low&&R.r[high].key>Key)
          high--;
        if(low<high)
        {
         R.r[low]=R.r[high];
         low++;
         }
        while(low<high&&R.r[high].key<=Key)
         ++low;
        if(low<high)
        {
         R.r[high]=R.r[low];
         high--;
         }
    }
    R.r[low]=R.r[0];
    QuickSort(R,s,low-1);
    QuickSort(R,low+1,t);
}
　　好了，就先说到这里了。

作者“flute的专栏”

补充：软件开发 , C语言 ,