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

下面说一下交换排序，交换排序主要有：冒泡排序和快速排序，快速排序（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 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 {
while(high>low&&R.r[high].key>Key)
high--;
if(low {
R.r[low]=R.r[high];
low++;
}
while(low ++low;
if(low {
R.r[high]=R.r[low];
high--;
}
}
R.r[low]=R.r[0];
QuickSort(R,s,low-1);
QuickSort(R,low+1,t);
}
　　好了，就先说到这里了。

作者“flute的专栏”