冒泡排序（及排序总结）

题：写出你所知道的3种常用的排序方法，并用其中一种方法设计出程序为数组a[100]排序。

这是网上找的一道面试题，晚上拿出数据结构书看看，印象中就记得一个冒泡排序，但具体实现算法忘了。面试肯定会用得着，现在趁早复习一下。

冒泡排序具体算法：
void BubbleSort(SeqList R)
   { //R（l..n)是待排序的文件，采用自下向上扫描，对R做冒泡排序
     int i，j；
     Boolean exchange； //交换标志
     for(i=1;i<n;i++){ //最多做n-1趟排序
       exchange=FALSE； //本趟排序开始前，交换标志应为假
       for(j=n-1;j>=i；j--) //对当前无序区R[i..n]自下向上扫描
        if(R[j+1].key<R[j].key){//交换记录
          R[0]=R[j+1]； //R[0]不是哨兵，仅做暂存单元
          R[j+1]=R[j]；
          R[j]=R[0]；
          exchange=TRUE； //发生了交换，故将交换标志置为真
         }
       if(!exchange) //本趟排序未发生交换，提前终止算法
             return；
     } //endfor(外循环)
    } //BubbleSort

在这里也对［排序］做一下总结，当然内容大多还是抄网上或者书目上的原话。

排序概念：将一个数据元素（或记录）的任意序列，按关键字递增或递减次序重新排列成一个序列。

排序方法分类：1）内部排序－－待排序记录存放在计算机内存中，排序时在内存中进行；2）外部排序－－待排序记录数量很大，排序过程需要进行数据的内存和外存的交换。

内部排序方法：
1）插入排序　　直接插入排序；希尔排序；其它还折半插入排序，2－路插入排序等。

2）选择排序　　简单选择排序；树形选择排序；堆排序。

3）交换排序　　冒泡排序；快速排序。

4）归并排序

5）基数排序

各排序实现的具体算法在这个网页上：http://student.zjzk.cn/course_ware/data_structure/web/paixu/paixu8.1.1.1.htm