数据结构-排序(2)

3. 怎样进行整个序列的堆排序？ *基于初始堆进行堆排序的算法步骤：

堆的第一个对象a[0]具有最大的关键码，将a[0]与a[n-1]对调，把具有最大关键码的对象交换到最后;

再对前面的n-1个对象，使用堆的调整算法，重新建立堆（调整根结点使之满足最大堆的定义）。结再对调a[0]和a[n-2]，然后对前n-2个对象重新调整，…如此反复，最后得到全部排序好的对象序列。 果具有次最大关键码的对象又上浮到堆顶，即a[0]位置; 例5：对刚才建好的最大堆进行排序： public static void heapSort(int[] a){ }

4、堆排序算法分析：

? ? ?

时间效率：O(nlog2n)。 空间效率：O(1)。 稳定性： 不稳定。 int temp; int n = a.Length; initCreateHeap(a); for(int i = n - 1; i > 0; i --){ }

temp = a[0]; a[0] = a[i]; a[i] = temp;

createHeap(a,i, 0); //调整根结点满足最大堆

//初始化创建最大堆 //当前最大堆个数每次递减1

//把堆顶a[0]元素和当前最大堆的最后一个元素交换

练习1：以下序列是堆的是（ ）

A. {75,65,30,15,25,45,20,10} B. {75,65,45,10,30,25,20,15} C. {75,45,65,30,15,25,20,10} D. {75,45,65,10,25,30,20,15} 练习2：有一组数据{15,9,7,8,20,1,7*,4}，建成的最小堆为（ ）。 A.{1,4,8,9,20,7,15,7*} B.{1,7,15,7*,4,8,20,9} C.{1,4,7,8,20,15,7*,9} D.以上都不对

练习3：已知序列{503，87，512，61，908，170，897，275，653，462}，写出采用堆排序对该序列作非递减排列时的排序过程。

排序好的序列为：61，87，170，275，462，503，512，653，897，908 8.4 交换排序

交换排序的基本思想是：利用交换数据元素的位置进行排序的方法。 交换排序的主要算法有： 1) 冒泡排序 2) 快速排序 8.4.1 冒泡排序

1、基本思路：每趟不断将记录两两比较，并按“前小后大”（或“前大后小”）规则交换。

2、优点：每趟结束时，不仅能挤出一个最大值到最后面位置，还能同时部分理顺其他元素；一旦下趟没有交换发生，还可以提前结束排序。

例：关键字序列 T=(21，25，49，25*，16，08），请按从小到大的顺序，写出冒泡排序的具体实现过程。 初态：21，25，49， 25*，16， 08 第1趟21，25，25*，16， 08 ， 49

第2趟21，25， 16， 08 ，25*，49 第3趟21，16， 08 ，25， 25*，49 第4趟16，08 ，21， 25， 25*，49 第5趟08，16， 21， 25， 25*，49 3、冒泡排序算法

public static void bubbleSort(int[] a){ }

4、冒泡排序的算法分析

时间效率：O（n) —因为要考虑最坏情况（数据元素全部逆序），当然最好情况是数据元素已全部排好序，此时循环n-1次，时间复杂度为O（n)

空间效率：O（1） —只在交换时用到一个缓冲单元 稳 定 性： 稳定 —25和25在排序前后的次序未改变

练习：关键字序列 T=(31，15，9，25，16，28），请按从小到大的顺序，写出冒泡排序的具体实现过程。 初态：31，15，9， 25，16， 28 第1趟15，9，25，16， 28， 31 第2趟9，15， 16， 25，28，31 第3趟9，15， 16，25， 28，31

1、基本思想：设数组a中存放了n个数据元素，low为数组的低端下标，high为数组的高端下标，从数组a中任取一个元素（通常取a[low]）做为标准元素，以该标准元素调整数组a中其他各个元素的位置，使排在标准元素前面的元素均小于标准元素，排在标准元素后面的均大于或等于标准元素。这样一次排序过程结束后，一方面将标准元素放在了未来排好序的数组中该标准元素应位于的位置上，另一方面将数组中的元素以标准元素为中心分成了两个子数组，位于标准元素左边子数组中的元素均小于标准元素，位于标准元素右边子数组中的元素均大于等于或标准元素。对这两个子数组中的元素分别再进行方法类同的递归快速排序。算法的递归出口条件是low≥high。

例、关键字序列 T=(60，55，48，37，10，90，84，36），请按从小到大的顺序，写出快速排序的具体实现过程。

快速排序算法各次快速排序过程 3、快速排序算法

public static void quickSort(int[] a, int low, int high){

int i, j;

*

2

int i, j, flag=1; int temp; int n = a.Length;

for(i = 1; i < n && flag == 1; i++){ }

flag = 0;

for(j = 0; j < n-i; j++){ }

if(a[j] > a[j+1]){ }

flag = 1; temp = a[j]; a[j] = a[j+1]; a[j+1] = temp;

int temp; i = low; j = high;

temp = a[low]; //取第一个元素为标准数据元素 while(i < j){

while(i < j && temp <= a[j]) j--; if(i < j){ }

a[i] = a[j]; i++;

//在数组的右端扫描

//在数组的左端扫描 while(i < j && a[i] < temp) i++;

if(i < j){ }

a[j] = a[i]; j--;

} a[i] = temp;

if(low < i) quickSort(a, low, i-1); }

4、快速排序算法分析：

时间效率：一般情况下时间复杂度为O(nlog2n)，最坏情况是数据元素已全部正序或反序有序，此时每次标准元素都把当前数组分成一个大小比当前数组小1的子数组，此时时间复杂度为O(n) 空间效率：O（log2n）—因为递归要用栈 稳 定 性： 不 稳 定 —因为有跳跃式交换。

练习：已知序列{503,87,512,61,908,170,897,275,653,462}，给出采用快速排序对该序列作非递减排序时每趟的结果。

第一趟：【462 87 275 61 170】 503 【 897 908 653 512】 第二趟：【170 87 275 61 】 462 503 【512 653】 897 【908】 第三趟：【61 87】 170 【275】 462 503 512 【653】 897 908 第四趟：61 【 87】 170 275 462 503 512 653 897 908 最后排序结果：61 87 170 275 462 503 512 653 897 908 1.插入排序是稳定的，选择排序是不稳定的。

2.堆排序所需要附加空间数与待排序的记录个数无关。

3.对有n个记录的集合进行快速排序，所需时间确定于初始记录的排列情况，在初始记录无序的情况下最好。

4.直接插入排序在最好情况下的时间复杂度为（ A ） A.O(n) B.O(nlog2n) C. O(log2n) D.O(n)

5.数据序列{8,9,10,4,5,6,20,1,2}只能是（ C ）算法的两趟排序后的结果。 A.直接选择排序 B.冒泡排序 C.直接插入排序 D.堆排序

6.用直接插入排序对下面4个序列进行递增排序，元素比较次数最少的是（C ） A.94,32,40,90,80,46,21,69 B.32,40,21,46,69,94,90,80

2

2

//对左端子集合递归

if(i < high) quickSort(a, j+1, high); //对右端子集合递归

C.21,32,46,40,80,69,90,94 D.90,69,80,46,21,32,94,40

7. .以下排序算法中，（B ）不能保证每趟排序至少能将一个元素放到其最终位置上。 A. 快速排序 B.希尔排序 C.堆排序 D.冒泡排序

8.对关键字{28,16,32,12,60,2,5,72}序列进行快速排序，第一趟从小到大一次划分结果为（B ） A.(2,5,12,16)26(60,32,72) B.(5,16,2,12)28(60,32,72) C.(2,16,12,5)28(60,32,72) D.(5,16,2,12)28(32,60,72)

9.若用冒泡排序对关键字序列{18，16，14，12，10，8}进行从小到大的排序，所需进行的关键字比较总次数是（ B ）。

A.10 B.15 C.21 D.34 10. 一组记录的关键字为{45，80，55，40，42，85}，则利用堆排序的方法建立的初始堆为（ B ）。 A.{85，80，45，40，42，55} B.{85，80，55，40，42，45} C.{85，80，55，45，42，40} D.{85，55，80，42，45，40}

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库数据结构-排序(2)在线全文阅读。