数据结构：排序（1）

 

排序是数据处理中经常使用的一种重要运算,在计算机及其应用系统中,花费在排序上的时间在系统运行时间中占有很大比重;并且排序本身对推动算法分析的发展也起很大作用。

一、排序的基本概念

1.排序或分类

所谓排序，就是要整理文件中的记录，使之按关键字递增(或递减)次序排列起来。其确切定义如下：

1）被排序对象--文件

• 被排序的对象--文件由一组记录组成。

• 记录则由若干个数据项(或域)组成。其中有一项可用来标识一个记录，称为关键字项。该数据项的值称为关键字(Key)。

  注意：
   　在不易产生混淆时，将关键字项简称为关键字。
  

2）排序运算的依据--关键字

• 用来作排序运算依据的关键字，可以是数字类型，也可以是字符类型。
• 关键字的选取应根据问题的要求而定。

2.排序的稳定性

在待排序的文件中，若存在多个关键字相同的记录，经过排序后这些具有相同关键字的记录之间的相对次序保持不变，该排序方法是稳定的；若具有相同关键字的记录之间的相对次序发生变化，则称这种排序方法是不稳定的。

3.排序方法的分类

1）按是否涉及数据的内、外存交换分

在排序过程中，若整个文件都是放在内存中处理，排序时不涉及数据的内、外存交换，则称之为内部排序(简称内排序)；反之，若排序过程中要进行数据的内、外存交换，则称之为外部排序。

注意： ① 内排序适用于记录个数不很多的小文件
      ② 外排序则适用于记录个数太多，不能一次将其全部记录放人内存的大文件。`

2）按策略划分内部排序方法 　

可以分为五类：插入排序、选择排序、交换排序、归并排序和分配排序。

3.排序算法分析

1）排序算法的基本操作

　 大多数排序算法都有两个基本的操作：

• 比较两个关键字的大小；
• 改变指向记录的指针或移动记录本身。

2）待排文件的常用存储方式

• 以顺序表(或直接用向量)作为存储结构

  排序过程：对记录本身进行物理重排（即通过关键字之间的比较判定，将记录移到合适的位置）

• 以链表作为存储结构 　　排序过程：无须移动记录，仅需修改指针。通常将这类排序称为链表(或链式)排序；

• 用顺序的方式存储待排序的记录，但同时建立一个辅助表(如包括关键字和指向记录位置的指针组成的索引表)

  排序过程：只需对辅助表的表目进行物理重排（即只移动辅助表的表目，而不移动记录本身）。适用于难于在链表上实现，仍需避免排序过程中移动记录的排序方法。

3）排序算法性能比较

评价排序算法好坏的标准主要有两条：

① 执行时间和所需的辅助空间　

② 算法本身的复杂程度

二、插入排序

1.直接插入排序

• 基本思想：把n个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，将它插入到有序表中的适当位置，使之成为新的有序表，重复n-1次可完成排序过程。
• 算法描述：动画演示过程

2.希尔排序

• 基本思想：先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。

• 算法描述：动画演示过程

三、交换排序

1.冒泡排序

• 基本思想：设待排序n个元素存放在数组a[n]中,无序区范围初始为(a(0),a(1),a(2),...,a[n-1]),冒泡排序方法是在当前无序区内,从最上面的元素a[0]开始,对每两个相邻的元素a[i+1]和ai进行比较,且使值较小的元素换至值较大的元素之上(若a[i]>a[i+1],则a[i]和a[i+1]的值互换),这样经过一趟冒泡排序后,假设最后下移的元素为a[k],则无序区中值较大的几个元素到达下端并从小到大依次存放在a[k+1],a[k+2],...a[n-1]中,这样无序区范围变为(a[0],a[1],a[2],...,a[k])。在当前无序区内进行下一趟冒泡排序。这个过程一直到某一趟排序中不出现元素交换的动作，排序结束。整个排序过程最多执行n-1遍。这种排序方法是通过相邻元素之间的比较与交换，使值较小的元素逐渐从后部移向前部（从下标较大的单元移向下标较小的单元），就象水底下的气泡一样逐渐向上冒。故称为冒泡排序法。
• 算法描述：动画演示过程

2.快速排序

• 基本思想：　①分解：在R[low..high]中任选一个记录作为基准(Pivot)，以此基准将当前无序区划分为左、右两个较小的子区间R[low..pivotpos-1)和R[pivotpos+1..high]，并使左边子区间中所有记录的关键字均小于等于基准记录(不妨记为pivot)的关键字pivot.key，右边的子区间中所有记录的关键字均大于等于pivot.key，而基准记录pivot则位于正确的位置(pivotpos)上，它无须参加后续的排序。 ②求解：通过递归调用快速排序对左、右子区间R[low..pivotpos-1]和R[pivotpos+1..high]快速排序。③组合：因为当"求解"步骤中的两个递归调用结束时，其左、右两个子区间已有序。对快速排序而言，"组合"步骤无须做什么，可看作是空操作。
• 算法描述：动画演示过程

三、选择排序

1.直接选择排序

• 基本思想：①初始状态：无序区为R[1..n]，有序区为空。②第1趟排序：在无序区R[1..n]中选出关键字最小的记录R[k]，将它与无序区的第1个记录R[1]交换，使R[1..1]和R[2..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。　……③第i趟排序：第i趟排序开始时，当前有序区和无序区分别为R[1..i-1]和Ri..n。该趟排序从当前无序区中选出关键字最小的记录R[k]，将它与无序区的第1个记录R[i]交换，使R[1..i]和R[i+1..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。
• 算法描述：动画演示过程

2.堆排序

• 基本思想：堆排序(HeapSort)是一树形选择排序。堆化数组后，第一次将A[0]与A[n - 1]交换，再对A[0…n-2]重新恢复堆。第二次将A[0]与A[n – 2]交换，再对A[0…n - 3]重新恢复堆，重复这样的操作直到A[0]与A[1]交换。由于每次都是将最小的数据并入到后面的有序区间，故操作完成后整个数组就有序了。

• 算法描述：动画演示过程

///Name:Tree
///Author:JA
///Date:2015-3-11



///对顺序表L作直接插入排序
void InsertSort(SqList *L){
    for (i = 2; i <= L.length;++i)
    if (LT(L.r[i].key, L.[r - 1].key)){        //将L.r[i]插入有序集表
        L.r[0] = L.r[i];
        L.r[i] = L.r[i - 1];
        for (j = i - 2; LT(L.r[0].key, L.r[j].key); --j)
            L.r[j + 1] = L.r[j];             //记录后移
        L.r[j + 1] = L.r[j];                 //插入到正确位置
    }
}//InsertSort

//希尔排序
void ShellPass(SeqList R，int d)
{//希尔排序中的一趟排序，d为当前增量
    for (i = d + 1; i <= n; i++) //将R[d+1．．n]分别插入各组当前的有序区
    if (R[i].key<R[i - d].key){
        R[0] = R[i]; j = i - d； //R[0]只是暂存单元，不是哨兵
        do {//查找R[i]的插入位置
            R[j + d]; = R[j]; //后移记录
            j = j - d; //查找前一记录
        } while (j>0 && R[0].key < R[j].key);
        R[j + d] = R[0]; //插入R[i]到正确的位置上
    } //endif
} //ShellPass
void  ShellSort(SeqList R)
{
    int increment = n; //增量初值，不妨设n>0
    do {
        increment = increment / 3 + 1; //求下一增量
        ShellPass(R,increment);  //一趟增量为increment的Shell插入排序
    } while (increment>1)
} //ShellSort

//冒泡排序
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

//快速排序
void QuickSort(SeqList R，,int low,int high)
{ //对R[low..high]快速排序
    int pivotpos; //划分后的基准记录的位置
    if (low<high){//仅当区间长度大于1时才须排序
        pivotpos = Partition(R，low，high); //对R[low..high]做划分
        QuickSort(R,low，pivotpos - 1); //对左区间递归排序
        QuickSort(R,pivotpos + 1,high); //对右区间递归排序
    }
} //QuickSort
int Partition(SeqList R,int i,int j)
{//调用Partition(R，low，high)时，对R[low..high]做划分，
    //并返回基准记录的位置
    ReceType pivot = R[i]; //用区间的第1个记录作为基准 '
    while (i<j){ //从区间两端交替向中间扫描，直至i=j为止
        while (i < j&&R[j].key >= pivot.key) //pivot相当于在位置i上
            j--; //从右向左扫描，查找第1个关键字小于pivot.key的记录R[j]
        if (i < j) //表示找到的R[j]的关键字<pivot.key
            R[i++] = R[j]; //相当于交换R[i]和R[j]，交换后i指针加1
        while (i < j&&R[i].key <= pivot.key) //pivot相当于在位置j上
            i++; //从左向右扫描，查找第1个关键字大于pivot.key的记录R[i]
        if (i<j) //表示找到了R[i]，使R[i].key>pivot.key
            R[j--] = R[i]; //相当于交换R[i]和R[j]，交换后j指针减1
    } //endwhile
    R[i] = pivot; //基准记录已被最后定位
    return i;
} //partition

//直接选择排序
void SelectSort(SeqList R)
{
    int i,j,k;
    for (i = 1; i<n; i++){//做第i趟排序(1≤i≤n-1)
        k = i;
        for (j = i + 1; j <= n; j++) //在当前无序区R[i..n]中选key最小的记录R[k]
        if (R[j].key<R[k].key)
            k = j; //k记下目前找到的最小关键字所在的位置
        if (k != i){ //交换R[i]和R[k]
            R[0] = R[i]; R[i] = R[k]; R[k] = R[0]; //R[0]作暂存单元
        } //endif
    } //endfor
} //SeleetSort

//堆排序
void HeapSort(SeqIAst R)
{ //对R[1..n]进行堆排序，不妨用R[0]做暂存单元
    int i;
    BuildHeap(R); //将R[1-n]建成初始堆
    for (i = n; i > 1; i--){ //对当前无序区R[1..i]进行堆排序，共做n-1趟。
        R[0] = R[1]; R[1] = R[i]; R[i] = R[0]; //将堆顶和堆中最后一个记录交换
            Heapify(R,1,i - 1); //将R[1..i-1]重新调整为堆，仅有R[1]可能违反堆性质
    } //endfor
} //HeapSort

---

3/13/2015 2:35:47 PM