101概述

101概述内容摘要：

9 10 11 1 2 3 4 5 6 7 8 9 10 11 1 2 3 4 5 6 7 8 9 10 11 1 2 3 4 5 6 7 8 9 10 11 void ShellInsert ( SqList amp。 L, int dk ) { for ( i=dk+1。 i=n。 ++i ) if ( [i].key [idk].key) { [0] = [i]。 // 暂存在 R[0] for (j=idk。 j0amp。 amp。 ([0].key[j].key)。 j=dk) [j+dk] = [j]。 // 记录后移，查找插入位置 [j+dk] = [0]。 // 插入 } // if } // ShellInsert void ShellSort (SqList amp。 L, int dlta[], int t) { // 增量为 dlta[]的希尔排序 for (k=0。 kt。 ++t) ShellInsert(L, dlta[k])。 //一趟增量为 dlta[k]的插入排序 } // ShellSort 快 速 排 序 一、起泡排序 二、一趟快速排序 三、快速排序 四、快速排序的时间分析 一、起泡排序 假设在排序过程中，记录序列 R[1..n]的状态为： 第 i 趟起泡排序 无序序列 R[1..ni+1] 有序序列 R[ni+2..n] ni+1 无序序列 R[1..ni] 有序序列 R[ni+1..n] 比较相邻记录，将 关键字最大的记录 交换到 ni+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。 时间分析 : 最好的情况（关键字在记录序列中顺序有序）： 只需进行一趟起泡 “比较”的次数： 最坏的情况（关键字在记录序列中逆序有序）： 需进行 n1趟起泡 “比较”的次数： 0 “移动”的次数： “移动”的次数： n1 2)1()1(2 nnini 2)1(3)1(3 2 nnini二、一趟快速排序（一次划分） 目标： 找一个记录， 以它的关键字作为“枢轴” ， 凡其 关键字小于枢轴 的记录均移动至该记录之前 ， 反之，凡 关键字大于枢轴 的记录均 移动至该记录之后。 致使 一趟排序 之后，记录的无序序列 R[s..t]将 分割成两部分 ： R[s..i1]和 R[i+1..t]， 且 R[j].key≤ R[i].key ≤ R[j].key (s≤j≤i1) 枢轴 (i+1≤j≤t)。 52 49 80 36 14 58 61 97 23 75s 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 hig 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) { }// Partition R[0] = R[low]。 pivotkey = R[low].key。 // 枢轴 while (lowhigh) { } while(lowhighamp。 amp。 R[high].key=pivotkey) high。 // 从右向左搜索 R[low] = R[high]。 while (lowhigh amp。 amp。 R[low].key=pivotkey) ++ low。 // 从左向右搜索 R[high] = R[low]。 R[low] = R[0]。 return low。 三、快速排序 首先对无序的记录序列进行“ 一次划分 ”，之后 分别 对分割所得两个子序列“ 递归 ”进行快速排序。 无 序 的 记 录 序 列 无序记录子序列 (1) 无序子序列 (2) 枢轴 一次划分 分别进行快速排序 void QSort (RedType amp。 R[], int s, int t ) { // 对记录序列 R[s..t]进行快速排序 if (s t) { // 长度大于 1 } } // QSort pivotloc = Partition(R, s, t)。 // 对 R[s..t] 进行 一次划分 QSort(R, s, pivotloc1)。 // 对低子序列递归排序， pivotloc是枢轴位置 QSort(R, pivotloc+1, t)。 // 对高子序列递归排序 void QuickSort( SqList amp。 L) { // 对顺序表进行快速排序 QSort(, 1, )。 } // QuickSort 第一次调用函数 Qsort 时，待排序记录序列的上、下界分别为 1 和。 四、快速排序的时间分析 假设 一次划分所得枢轴位置 i=k，则对n 个记录进行快排所需时间： 其中 Tpass(n)为对 n 个记录进行一次划分所需时间。 若待排序列中记录的关键字是随机分布的，则 k 取 1 至 n 中任意一值的可能性相同。 T(n) = Tpass(n) + T(k1) + T(nk)  nkav gav gav g knTkTnCnnT1)()1(1)(设 Tavg(1)≤ b 则可得结果： )1l n ()1)(22()(  nncbnT av g结论 : 快速排序的时间复杂度为 O(nlogn) 由此可得快速排序所需时间的平均值为： 若待排记录的初始状态为按关键字有序时，快速排序将蜕化为起泡排序 ，其时间复杂度为 O(n2)。 为避免出现这种情况， 需在进行一次划分之前，进行“ 予处理 ”， 即： 先对 R(s).key, R(t).key 和 R[(s+t)/2].key，进行相互比较，然后 取 关键字为 “三者之中” 的记录 为枢轴 记录。 堆 排 序 简 单 选 择 排 序 堆 排 序 一、简单选择排序 假设排序过程中，待排记录序列的状态为： 有序序列 R[1..i1] 无序序列 R[i..n] 第 i 趟 简单选择排序 从中选出 关键字最小的记录 有序序列 R[1..i] 无序序列 R[i+1..n] 简单选择排序 的算法描述如下： void SelectSort (Elem R[], int n ) { // 对记录序列 R[1..n]作简单选择排序。 for (i=1。 in。 ++i) { // 选择第 i 小的记录，并交换到位 } } // SelectSort j = SelectMinKey(R, i)。 // 在 R[i..n] 中选择关键字最小的记录 if (i!=j) R[i]←→ R[j]。 // 与第 i 个记录交换 时间性能分析 对 n 个记录进行简单选择排序，所需进行的 关键字间的比较次数 总计为： 移动记录的次数 ， 最小值为 0, 最大值。