[工学]数据结构_内部排序.ppt

各种排序方法的比较 各种排序方法的选择 选择合适的排序方法应考虑的因素： ①待排序的记录数目n； ②记录的大小（规模）； ③关键字的结构及其初始状态； ④对稳定性的要求； ⑤语言工具的条件； ⑥存储结构； ⑦时间和辅助空间复杂度等。 各种排序方法的选择 ①就平均时间性能而言，快速排序最佳，其所需时间最省，但快速排序在最坏情况下的时间性能不如堆排序和归并排序。当n较大时，归并排序较堆排序省，但归并排序所需的辅助空间最大。 ②简单排序方法中，直接插入排序最简单，当待排序的结点已按键值“基本有序”且n较小时，则应采用直接插入排序或冒泡排序，直接插入排序比冒泡排序更快些，因此经常将直接插入排序和其他的排序方法结合在一起使用。 ③当n很大且键值位数较小时，采用基数排序较好；而当键值的最高位分布较均匀时，可先按其最高位将待排序结点分成若干子表，而后对各子表进行直接插入排序。 ④从方法的稳定性来比较，直接插入排序、冒泡排序、归并排序和基数排序是稳定的排序方法；而直接选择排序、希尔排序、堆排序和快速排序都是不稳定的排序方法。 实验 输入10个数，从插入排序、快速排序、选择排序三类算法中各选一种编程实现。 一、起泡排序 　　假设在排序过程中，记录序列R[1..n]的状态为： 第 i 趟起泡排序 无序序列R[1..n-i+1] 有序序列 R[n-i+2..n] n-i+1 无序序列R[1..n-i] 有序序列 R[n-i+1..n] 比较相邻记录，将关键字最大的记录交换到 n-i+1 的位置上 void BubbleSort(Elem R[ ], int n) { while (i 1) { } // while } // BubbleSort i = n; i = lastExchangeIndex; // 本趟进行过交换的 // 最后一个记录的位置 if (R[j+1].key R[j].key) { Swap(R[j], R[j+1]); lastExchangeIndex = j; //记下进行交换的记录位置 } //if for (j = 1; j i; j++) lastExchangeIndex = 1; 注意: 2. 一般情况下，每经过一趟“起泡”，“i 减一”，但并不是每趟都如此。 例如: 2 5 5 3 1 5 7 9 8 9 i=7 i=6 for (j = 1; j i; j++) if (R[j+1].key R[j].key) … 1 3 i=2 1. 起泡排序的结束条件为， 最后一趟没有进行“交换记录”。 二、一趟快速排序（一次划分） 　目标：找一个记录，以它的关键字作为“枢轴”，凡其关键字小于枢轴的记录均移动至该记录之前，反之，凡关键字大于枢轴的记录均移动至该记录之后。 致使一趟排序之后，记录的无序序列R[s..t]将分割成两部分：R[s..i-1]和R[i+1..t]，且 R[j].key≤ R[i].key ≤ R[j].key (s≤j≤i-1) 枢轴 (i+1≤j≤t)。 s t low high 设 R[s]=52 为枢轴 将 R[high].key 和 枢轴的关键字进行比较，要求R[high].key ≥ 枢轴的关键字 将 R[low].key 和 枢轴的关键字进行比较，要求R[low].key ≤ 枢轴的关键字 high 23 low 80 high 14 low 52 例如 R[0] 52 low high high high low 可见，经过“一次划分” ，将关键字序列 52, 49, 80, 36, 14, 58, 61, 97, 23, 75 调整为: 23, 49, 14, 36, (52) 58, 61, 97, 80, 75 在调整过程中，设立了两个指针： low 和high，它们的初值分别为： s 和 t， 之后逐渐减小 high，增加 low，并保证 R[high].key≥52，和 R[low].key≤52,否则进行记录的“交换”。 int Partition (RedType R[], int low, int high) { pivotkey = R[low].key; while (lowhigh) { while (lowhigh R[high].k