数据结构（第2版）（C语言实现）课件：排序.pptx

排序;8.1基本概念;8.1基本概念;8.1基本概念;8.1基本概念;8.1基本概念;8.2插入排序;8.2插入排序;8.2插入排序;8.2插入排序;8.2插入排序;8.2插入排序;8.2插入排序;8.2插入排序;8.2插入排序;8.2插入排序;8.2插入排序;8.2插入排序;8.3.1简单选择排序

简单选择排序是一种简单的选择类排序算法，它是通过依次找到待排序元素序列中最小的数据元素，并将其放在序列的最前面，从而使待排序元素序列变为有序序列。它的基本算法思想描述如下：

假设待排序的元素序列有n个，在第一趟排序过程中，从n个元素序列中选择最小的元素，并将其放在元素序列的最前面即第一个位置。在第二趟排序过程中，从剩余的n-1个元素中，选择最小的元素，将其放在第二个位置。依次类推，直到没有待比较的元素，简单选择排序算法结束。;简单选择排序的算法描述如下。

voidSelectSort(SqList*L,intn)

/*简单选择排序*/

{

inti,j,k;

DataTypet;

/*将第i个元素的关键字与后面[i+1...n]个元素的关键字比较，将关键字最小的的元素放在第i个位置*/

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

{

j=i;

for(k=i+1;k=n;k++) /*关键字最小的元素的序号为j*/

if(L-data[k].keyL-data[j].key)

j=k;

if(j!=i) /*如果序号i不等于j，则需要将序号i和序号j的元素交换*/

{

t=L-data[i];

L-data[i]=L-data[j];

L-data[j]=t;

}

}

};8.3选择排序;8.3.2堆排序

1．什么是堆和堆排序

堆排序(heapsort)是利用了二叉树的树形结构进行排序。所谓堆，排序的算法思想：堆排序主要是利用了二叉树的树形结构，按照完全二叉树的编号次序，将元素序列的关键字依次存放在相应的结点。然后从叶子结点开始，从互为兄弟的两个结点中（没有兄弟结点除外），选择一个较大（或较小）者与其双亲结点比较，如果该结点大于（或小于）双亲结点，则将两者进行交换，使较大（或较小）者成为双亲结点。将所有的结点都做类似操作，直到根结点为止。这时，根结点的元素值的关键字最大（或最小）。;堆中的每一个结点都大于（或小于）其孩子结点。堆的数学形式定义为：假???存在n个元素，其关键字序列为(k1,k2,…,ki,…,kn)，如果有：

如果将这些元素的关键字存放在一维数组中，将此一维数组中的元素与完全二叉树一一对应起来，则完全二叉树中的每个非叶子结点的值都不小于（或不大于）孩子结点的值。;在堆中，堆的根结点元素值一定是所有结点元素值的最大值或最小值。例如，序列(87,64,53,51,23,21,48,32)和(12,35,27,46,41,39,48,55,89,76)都是堆，相应的完全二叉树表示如图8.11所示。

;如果将堆中的根结点（堆顶）输出之后，然后将剩余的n-1个结点的元素值重新建立一个堆，则新堆的堆顶元素值是次大（或次小）值，将该堆顶元素输出。然后将剩余的n-2个结点的元素值重新建立一个堆，反复执行以上操作，直到堆中没有结点，就构成了一个有序序列，这样的重复建堆并输出堆顶元素的过程称为堆排序。;2．建堆

堆排序的过程就是建立堆和不断调整使剩余结点构成新堆的过程。假设将待排序的元素的关键字存放在数组a中，第1个元素的关键字a[1]表示二叉树的根结点，剩下的元素的关键字aa[2…n]分别与二叉树中的结点按照层次从左到右一一对应。例如，a[1]的左孩子结点存放在a[2]中，右孩子结点存放在a[3]中，a[i]的左孩子结点存放在a[2*i]中，右孩子结点存放在a[2*i+1]中。;例如，给定一组元素，其关键字序列为(21,47,39,58,39,57,48,62)，建立大顶堆的过程如图8.12所示。结点的旁边为对应的序号。建立后的大顶堆，其非叶子结点的元素值均不小于左、右子树结点的元素值。

;建立大顶堆的算法描述如下所示。

voidCreateHeap(SqList*H,intn)

/*建立大顶堆*/

{

inti;

for(i=n/2;i=1;i--) /*从序号n/2开始建立大顶堆*/

AdjustHeap(H,i,n);

};voidAdjustHeap(SqList*H,