数据结构－第10章 节 －排序.pptVIP

10.3.2 快速排序 (Quick Sort) 快速排序方法的基本思想：是任取待排序对象序列中的某个对象 (例如取第一个对象) 作为枢轴，按照枢轴的关键字大小，将整个对象序列划分为左右两个子序列： 左侧子序列中所有对象的关键字都小于或等于枢 轴的关键字 右侧子序列中所有对象的关键字都大于枢轴的关 键字 10.3.2 快速排序 (Quick Sort) 枢轴则排在这两个子序列中间（这也是该对 象最终应安放的位置)。 然后分别对这两个子序列重复施行上述方法，直到所有的对象都排在相应位置上为止。 10.3.2 快速排序——具体做法 一趟快速排序的具体做法是：附设两个指针low和high，它们的初值分别为low和high，设枢轴记录的关键字为pivotkey，则首先从high所指位置起向前有哪些信誉好的足球投注网站找到第一个关键字小于pivotkey的记录和pivot枢轴记录互相交换，然后从low所指位置起向后有哪些信誉好的足球投注网站，找到第一个关键字大于pivotkey的记录和枢轴记录互相交换，重复这两步直至low＝high为止。 e.g: 将序列 49、38、65、97、76、13、27、49 用快速排序的方法进行排序。 0 1 2 3 4 5 6 7 8 49 38 65 97 76 13 27 49 10.3.2 快速排序——示例1 38 65 97 76 13 27 49 high low 49 界点 pivot 10.3.2 快速排序——示例1 38 65 97 76 13 27 49 high low 49 界点 pivot 38 65 97 76 13 27 49 high low 49 界点 pivot 10.3.2 快速排序——示例1 38 65 97 76 13 27 49 high low 49 界点 pivot pivot 38 65 97 76 13 27 49 high low 49 界点 10.3.2 快速排序——示例1 38 65 97 76 13 27 49 high low 49 界点 pivot pivot 38 65 97 76 13 27 49 high low 49 界点 10.3.2 快速排序——示例1 38 65 97 76 13 27 49 high low 49 界点 pivot 38 65 97 76 13 27 49 high low 49 界点 pivot 0 1 2 36 24 10 6 3 4 5 36 24 12 i 10 6 12 12 10.2.1 直接插入排序——例2 例: 36、24、10、6、12存放在 r 数组的下标为 1 至 5 的元素之中，用直接插入法将其排序。结果仍保存在下标为 1 至 5 的元素之中。 j i=5; r[0]=r[i]=12; j=i-1=4; r[j]r[0]; 0 1 2 36 24 10 6 3 4 5 36 24 12 i 10 6 12 10.2.1 直接插入排序——例2 例: 36、24、10、6、12存放在 r 数组的下标为 1 至 5 的元素之中，用直接插入法将其排序。结果仍保存在下标为 1 至 5 的元素之中。 j r[j+1]=r[j]; j - -; 0 1 2 36 24 10 6 3 4 5 36 24 12 i 10 6 12 10.2.1 直接插入排序——例2 例: 36、24、10、6、12存放在 r 数组的下标为 1 至 5 的元素之中，用直接插入法将其排序。结果仍保存在下标为 1 至 5 的元素之中。 j r[j+1]=r[j]; j - -; 0 1 2 36 24 10 6 3 4 5 36 24 12 i 10 6 12 12 10.2.1 直接插入排序——例2 例: 36、24、10、6、12存放在 r 数组的下标为 1 至 5 的元素之中，用直接插入法将其排序。结果仍保存在下标为 1 至 5 的元素之中。 j r[j+1]=r[0]; 10.2.1 直接插入排序——算法1 //监视哨设在低下标端的插入排序算法（算法10.2） void InsertSort ( SqList L ) //对顺序表L作直接插入排序 { for ( i = 2; i = L.length ; ++i ) if ( LT( L.r[i].key, L.r[i-1].key ) ) // ““，需将L.r[i]插入有序子表 { L.r[0].key = L.r[i].key