第八章 排序技术——数据结构

1.排序的基本概念

排序：给定一组记录的集合{r1, r2, ……, rn}，其相应的关键码分别为{k1, k2, ……, kn}，排序是将这些记录排列成顺序为{rs1, rs2, ……, rsn}的一个序列，使得相应的关键码满足ks1≤ks2≤……≤ksn（称为升序）或ks1≥ks2≥……≥ksn（称为降序）。

正序：待排序序列中的记录已按关键码排好序。

逆序（反序）：待排序序列中记录的排列顺序与排好序的顺序正好相反。

趟：在排序过程中，将待排序的记录序列扫描一遍称为一趟。

        通常，一次排序过程需要进行多趟扫描才能完成

排序算法的稳定性：

假定在待排序的记录集中，存在多个具有相同键值的记录，

若经过排序，这些记录的相对次序仍然保持不变，

即在原序列中，ki=kj且ri在rj之前，而在排序后的序列中，ri仍在rj之前，则称这种排序算法是稳定的；否则称为不稳定的。

排序的分类-根据排序数据在内存中还是在外存中：

2. 外排序：由于待排序的记录个数太多，不能同时放置在内存，而需要将一部分记录放置在内存，另一部分记录放置在外存上，整个排序过程需要在内外存之间多次交换数据才能得到排序的结果。

基于比较的内排序

1. 插入排序

2. 交换排序

3. 选择排序

4. 归并排序

排序算法的性能

内排序在排序过程中的基本操作：

⑴比较：关键码之间的比较；

⑵移动：记录从一个位置移动到另一个位置。

2.空间复杂性： 辅助存储空间。

辅助存储空间是指在数据规模一定的条件下，除了存放待排序记录占用的存储空间之外，执行算法所需要的其他存储空间。

2.插入类排序     

   1.直接插入排序 

基本思想：在插入第 i（i＞1）个记录时，前面的 i-1个记录已经排好序。

算法描述：for (i=2; i<=n; i++)          {    插入第i个记录，即第i趟直接插入排序；}

 void  insertSort (int  r[ ], int n){ 

   for (i=2; i<=n; i++)   {

       r[0]=r[i]; j=i-1;

       while (r[0]<r[j])     

  {     r[j+1]=r[j]; 

        j=j-1;              }

       r[j+1]=r[0]; 

    }

}

    2.希尔排序

基本思想：

将整个待排序记录分割成若干个子序列，

在子序列内分别进行直接插入排序，

待整个序列中的记录基本有序时，对全体记录进行直接插入排序。

算法描述：for (d=n/2; d>=1; d=d/2) {     以d为增量，进行组内直接插入排序；  }

void Shellsort(int r[],int n){

  for (d=n/2; d>=1; d=d/2){

     for (i=d+1; i<=n; i++) {

       r[0]=r[i];          

       j=i-d;               

       while (j>0 && r[0]<r[j])

       {    r[j+d]=r[j];

            j=j-d;           }

        r[j+d]=r[0];

  }

  }

}

3.交换类排序

     1.冒泡排序

基本思想：两两比较相邻记录的关键码，如果反序则交换，直到没有反序的记录为止。

算法描述：while (exchange) {    执行一趟起泡排序；  }

void BubbleSort(int r[ ], int n)

{ 

    exchange=n;  

    while (exchange)

    {

        bound=exchange;

        exchange=0； 

        for (j=1; j<bound; j++)

            if (r[j]>r[j+1]) {

                r[j]←→r[j+1]；

        exchange=j；

            }

     }

 }///

///void BubbleSort(int r[ ], int n)

{ 

    change=true; bound=n;

    while (change)

    {

        change=false;

         

        for (j=1; j<bound; j++)

            if (r[j]>r[j+1]) {

                r[j]←→r[j+1]；

        bound=j；

        change=true

            }

     }

 }

2.快速排序

快速排序的基本思想

首先选一个轴值（即比较的基准），

通过一趟排序将待排序记录分割成独立的两部分，

前一部分记录的关键码均小于或等于轴值，

后一部分记录的关键码均大于或等于轴值，

然后分别对这两部分重复上述方法，直到整个序列有序。

选择轴值的方法：

1.使用第一个记录的关键码；

2.选取序列中间记录的关键码；

3.比较序列中第一个记录、最后一个记录和中间记录的关键码，取关键码居中的作为轴值并调换到第一个记录的位置；

4.随机选取轴值。

选取不同轴值的后果：

决定两个子序列的长度，子序列的长度最好相等。

4.选择排序

      1.简单选择排序 

基本思想：第i 趟在n-i+1（i=1,2,…,n-1）个记录中选取关键码最小的记录作为有序序列中的第i个记录。

void  selectSort ( int  r[ ], int n)

{  

    for ( i=1; i<n; i++)

    { 

        index=i;  

        for (j=i+1; j<=n; j++)

           if  (r[j]<r[index])  index=j;

        if (index!=i)   r[i]<==>r[index];    

    }

}

     2.堆排序

堆是具有下列性质的完全二叉树：每个结点的值都小于或等于其左右孩子结点的值（称为小根堆），或每个结点的值都大于或等于其左右孩子结点的值（称为大根堆）。

基本思想：

首先将待排序的记录序列构造成一个堆(大顶堆)，

此时，选出了堆中所有记录的最大者，然后将它从堆中移走，

并将剩余的记录再调整成堆，

这样又找出了次大的记录，以此类推，直到堆中只有一个记录。

堆调整：在一棵完全二叉树中，根结点的左右子树均是堆，如何调整根结点，使整个完全二叉树成为一个堆？

堆调整——算法描述：

void sift ( int r[ ], int k, int m )

{//要筛选结点的编号为k，堆中最后一个结点的编号为m

    i=k;  j=2*i;  temp=r[i];  //将筛选记录暂存

    while (j<=m )           //筛选还没有进行到叶子

    {

        if (j<m && r[j]<r[j+1]) j++;  //左右孩子中取较大者

        if (temp>r[j]) break;

        else {

             r[i]=r[j];   i=j;   j=2*i;

        }

     }

     r[i]=temp;   //将筛选记录移到正确位置

}

5.归并排序

归并：将两个或两个以上的有序序列合并成一个有序序列的过程。

二路归并排序

基本思想：

将一个具有n个待排序记录的序列看成是n个长度为1的有序序列，

然后进行两两归并，

得到n/2个长度为2的有序序列，

再进行两两归并，得到n/4个长度为4的有序序列，

……，

直至得到一个长度为n的有序序列为止。

 

6.分配排序

基于分配和收集

基本思想

先将数据分配到不同的桶中

再将桶中的数据收集到一起

两种方法

桶式排序(单关键字排序)

链式基数排序（多关键字排序）

特点

排序过程无须比较关键字，而是通过“分配”和“收集”过程来实现排序

           它们的时间复杂度可达到线性阶：O(n)。

7.

 

 

 

 

 

 

3.

4.

5.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

8-1-1    排序的基本概念8-1-8-1-1    排序的基本概念8-1-1    排序的基本概念    排序的基本概念8-1-1    排序的基本概念8-1-1    排序的8-1-1    排序的基本概念基本概念