数据结构-排序

目录排序排序的概念常见的排序算法常见排序算法的实现插入排序直接插入排序希尔排序( 缩小增量排序 )选择排序直接选择排序:堆排序交换排序冒泡排序快速排序快速排序优化1. 三数取中法选 key基准2. 递归到小的子区间时可以考虑使用插入排序快速排序非递归归并排序非比较排序排序算法复杂度及稳定性分析​编辑选择题排序排序的概念排序所谓排序就是使一串记录按照其中的某个或某些关键字的大小递增或递减的排列起来的操作。稳定性假定在待排序的记录序列中存在多个具有相同的关键字的记录若经过排序这些记录的相对次 序保持不变即在原序列中r[i]r[j]且r[i]在r[j]之前而在排序后的序列中r[i]仍在r[j]之前则称这种排 序算法是稳定的否则称为不稳定的。内部排序数据元素全部放在内存中的排序。外部排序数据元素太多不能同时放在内存中根据排序过程的要求不能在内外存之间移动数据的排序。常见的排序算法常见排序算法的实现插入排序直接插入排序直接插入排序是一种简单的插入排序法其基本思想是把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中直到所有的记录插入完为 止得到一个新的有序序列 。直接插入排序当插入第i(i1)个元素时前面的array[0],array[1],…,array[i-1]已经排好序此时用array[i]的排序码与 array[i-1],array[i-2],…的排序码顺序进行比较找到插入位置将array[i]插入原来位置上的元素顺序后移简单来说就是把数组分成两部分左边是已排序好的右边是待插入的。每次从右边拿一个数插入到左边正确的位置。直接插入排序的特性总结1. 元素集合越接近有序直接插入排序算法的时间效率越高2. 时间复杂度O(N^2)3. 空间复杂度O(1)它是一种稳定的排序算法4. 稳定性稳定希尔排序( 缩小增量排序 )希尔排序法又称缩小增量法。希尔排序法的基本思想是先介绍一下增量gap指的是下标之间的距离不是两个数字的差值。先选定一个整数称为增量 gap把待排序文件中所有记录分成gap 个组所有距离为gap的记录分在同一组内并对每一组内的记录进行直接插入排序。然后取下一个更小的 gap例如按照 Knuth 提出的方式gap gap/3 1或初始gap n/2并逐步折半重复上述分组和排序的工作。当gap 1时所有记录在统一组内排好序此时整个文件成为有序序列。实际上希尔排序就是直接插入排序的改进版直接插入排序每次只移动相邻元素增量1效率低。希尔排序先按大间隔分组对每组做直接插入排序让数组宏观上基本有序最后再用直接插入排序gap1收尾这样整体速度大大提升。初始数组下标和值下标: 0 1 2 3 4 5 6 7 8 9值: 9 1 2 5 7 4 8 6 3 5第一趟gap 5。分组根据下标差5组0下标0,5 → 值 [9, 4]组1下标1,6 → 值 [1, 8]组2下标2,7 → 值 [2, 6]组3下标3,8 → 值 [5, 3]组4下标4,9 → 值 [7, 5]每组内部排序每组只有两个元素直接比较交换就行组04 比 9 小 → 交换位置 → 下标0变成4下标5变成9组11 比 8 小不动 → [1, 8] 保持组22 比 6 小不动组33 比 5 小 → 交换 → 下标3变成3下标8变成5组45 比 7 小 → 交换 → 下标4变成5下标9变成7结果第一趟排序后下标: 0 1 2 3 4 5 6 7 8 9值: 4 1 2 3 5 9 8 6 5 7第二趟gap 2基于上面结果4 1 2 3 5 9 8 6 5 7分组下标差2组0下标0,2,4,6,8 → 值 [4, 2, 5, 8, 5]组1下标1,3,5,7,9 → 值 [1, 3, 9, 6, 7]组0内部排序直接插入排序初始 [4, 2, 5, 8, 5]插入 22 比 4 小 → [2, 4, 5, 8, 5]插入 5比 4 大不动 → [2, 4, 5, 8, 5]插入 8不动插入 5比 8 小比 5 小比较5比5相等不动不应该插入到 5 和 8 之间 → [2, 4, 5, 5, 8]所以组0最终 [2, 4, 5, 5, 8]对应回下标 (0,2,4,6,8)下标02, 下标24, 下标45, 下标65, 下标88组1内部排序初始 [1, 3, 9, 6, 7]已有序前两个1,3插入 9不动插入 6比 9 小比 3 大 → [1, 3, 6, 9, 7]插入 7比 9 小比 6 大 → [1, 3, 6, 7, 9]组1最终 [1, 3, 6, 7, 9]对应下标 (1,3,5,7,9)下标11, 下标33, 下标56, 下标77, 下标99合并后结果第二趟排序后下标: 0 1 2 3 4 5 6 7 8 9值: 2 1 4 3 5 6 5 7 8 9第三趟gap 1这就是一次普通的直接插入排序对整个数组排序最终得到1 2 3 4 5 5 6 7 8 9规则分组按“下标差为 gap”分成多个子序列。排序每个子序列内部独立进行直接插入排序不是整体交换。不断缩小 gap最后 gap1 就是全局插入排序。希尔排序的特性总结1. 希尔排序是对直接插入排序的优化。2. 当gap 1时都是预排序目的是让数组更接近于有序。当gap 1时数组已经接近有序的了这样就 会很快。这样整体而言可以达到优化的效果。我们实现后可以进行性能测试的对比。3. 希尔排序的时间复杂度不好计算因为gap的取值方法很多导致很难去计算希尔排序的时间复杂度都不固定4. 稳定性不稳定关于时间复杂度每个教材都给出了相关解释比如《数据结构(C语言版)》--- 严蔚敏《数据结构-用面相对象方法与C描述》--- 殷人昆选择排序基本思想 每一次从待排序的数据元素中选出最小或最大的一个元素存放在序列的起始位置直到全部待排序的 数据元素排完 。即每次从待排序的区间中选出最小或最大的元素放到区间的起始位置或末尾位置然后缩小待排序区间重复这个过程。直接选择排序:在元素集合array[i]--array[n-1]中选择关键码最大(小)的数据元素若它不是这组元素中的最后一个(第一个)元素则将它与这组元素中的最后一个第一个元素交换在剩余的array[i]--array[n-2]array[i1]--array[n-1]集合中重复上述步骤直到集合剩余1个元素特性1. 直接选择排序思考非常好理解但是效率不是很好。实际中很少使用2. 时间复杂度O(N^2)3. 空间复杂度O(1)4. 稳定性不稳定堆排序堆排序(Heapsort)是指利用堆积树堆这种数据结构所设计的一种排序算法它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆排降序建小堆。特性1. 堆排序使用堆来选数效率就高了很多。2. 时间复杂度O(N*logN)3. 空间复杂度O(1)4. 稳定性不稳定交换排序基本思想所谓交换就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置交换排 序的特点是将键值较大的记录向序列的尾部移动键值较小的记录向序列的前部移动。冒泡排序特性1. 冒泡排序是一种非常容易理解的排序2. 时间复杂度O(N^2)3. 空间复杂度O(1)4. 稳定性稳定快速排序快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法其基本思想为任取待排序元素序列中 的某元素作为基准值按照该排序码将待排序集合分割成两子序列左子序列中所有元素均小于基准值右 子序列中所有元素均大于基准值然后最左右子序列重复该过程直到所有元素都排列在相应位置上为止。// 假设按照升序对array数组中[left, right)区间中的元素进行排序 void QuickSort(int array[], int left, int right) { if(right - left 1) return; // 按照基准值对array数组的 [left, right)区间中的元素进行划分 int div partion(array, left, right); // 划分成功后以div为边界形成了左右两部分 [left, div) 和 [div1, right) // 递归排[left, div) QuickSort(array, left, div); // 递归排[div1, right) QuickSort(array, div1, right); }上述为快速排序递归实现的主框架发现与二叉树前序遍历规则非常像在写递归框架时可想想二叉 树前序遍历规则即可快速写出来后序只需分析如何按照基准值来对区间中数据进行划分的方式即可。 将区间按照基准值划分为左右两半部分的常见方式有hoare,挖坑法前后指针这三种这三种都是快速排序中实现分区partition的不同方法。它们的目标一样选一个基准值pivot把数组分成左边 ≤ pivot、右边 ≥ pivot 的两部分并返回基准的最终位置。下面用数组[6, 1, 2, 7, 9, 3, 4, 5, 10, 8]为例假设选第一个元素6作为基准。1. Hoare 版本原始版本由快速排序发明者 Hoare 提出使用左右指针向中间扫描交换逆序对。左指针 L 从左边找大于等于pivot 的元素右指针 R 从右边找小于等于pivot 的元素交换 L 和 R 指向的元素继续直到 L ≥ R最后将 pivot 与 R 指向的元素交换特点效率高交换次数少基准最终位置不一定是分界点分界点在左右指针相遇处边界条件容易错2. 挖坑法用坑位的概念代替交换更直观。保存 pivot 值原位置成为“坑”右指针找比 pivot 小的数填入左边坑位右指针处变新坑左指针找比 pivot 大的数填入右边坑位左指针处变新坑交替进行直到左右指针相遇最后把 pivot 填入最后的坑位特点逻辑清晰不需要交换元素只是搬运容易理解和实现相对于 Hoare多了一次赋值操作过程示意pivot6[6, 1, 2, 7, 9, 3, 4, 5, 10, 8]坑位0右找小5 → 填入坑位0 → [5, 1, 2, 7, 9, 3, 4, _, 10, 8] 坑位7左找大7 → 填入坑位7 → [5, 1, 2, _, 9, 3, 4, 7, 10, 8] 坑位3右找小4 → 填入坑位3 → [5, 1, 2, 4, 9, 3, _, 7, 10, 8] 坑位6左找大9 → 填入坑位6 → [5, 1, 2, 4, _, 3, 9, 7, 10, 8] 坑位4右找小3 → 填入坑位4 → [5, 1, 2, 4, 3, _, 9, 7, 10, 8] 坑位5左右相遇填入 pivot 6 → [5, 1, 2, 4, 3, 6, 9, 7, 10, 8]3. 前后指针版本使用两个指针前指针 i后指针 j同向移动维护一个“小于等于 pivot 的区域”。选择 pivot通常最右或最左指针 i 指向分区边界左侧指针 j 遍历数组遇到 ≤ pivot 的元素就与 i1 交换然后 i 前进最后将 pivot 与 i1 交换特点代码最简洁不容易出错单次遍历只需一个循环交换次数较多但现代计算机上性能差异不大过程示意pivot6基准选最右或最左稍有不同若选最左为 pivot则从第二个元素开始用 j 扫描小于 6 的依次交换到前面。遍历后得到[1, 2, 3, 4, 5, 6, 9, 7, 10, 8]这样的效果。理解原理推荐挖坑法或前后指针逻辑直观追求极致性能可以考虑Hoare版交换次数更少实际写代码时前后指针最简洁、最不容易写错快速排序优化三数取中→ 让分区更平衡避免最坏情况。小数组插入排序→ 降低递归深度提升小规模数据排序速度。两者结合后快速排序的实际性能接近最优被广泛应用于标准库如 C 的qsort、C 的std::sort的内省排序中也包含类似思想。1. 三数取中法选 key基准问题背景普通快排通常选第一个或最后一个元素作为基准key。如果数组已经有序或接近有序每次选到的 key 都是最小或最大值导致分区极度不平衡。结果递归深度 n时间复杂度退化为O(n²)。优化思想不固定选端点而是从当前子数组的左端、中间、右端三个位置取元素选择它们中大小居中的那个作为 key。具体做法以选左端为 key 的场景为例计算中间位置mid left (right - left) / 2。比较arr[left]、arr[mid]、arr[right]。将三个值中中间大小的元素与arr[left]交换使其成为新的 key。之后正常执行分区算法挖坑/Hoare/前后指针。举例子数组[8, 3, 6, 1, 9]left8, mid6, right9排序三个数[6,8,9]中值是8所以还是选 8 作为 key如果原数组是[1,2,3,4,5]则左1,中3,右5 → 选 3 作为 key比选 1 更平衡效果极大降低最坏情况发生的概率。对于基本有序的数据性能接近 O(n log n)。额外代价仅增加常数次比较和一次交换。2. 递归到小的子区间时可以考虑使用插入排序问题背景快速排序是分治算法会一直递归直到子数组长度为 1。当子数组长度很小比如 10时递归调用的函数开销压栈、调用已经大于排序本身的工作量。插入排序在小规模数据上常数因子小、对缓存友好实际速度比快排更快。优化思想在递归函数中增加一个判断如果当前子数组长度 ≤ 某个阈值通常取 10~20则不再继续递归而是直接调用插入排序对该子数组排序。具体做法伪代码void quickSort(arr, left, right) { if (left right) return; // 小数组优化 if (right - left 1 10) { insertionSort(arr, left, right); return; } // 否则正常分区 递归左右子数组 int p partition(arr, left, right); quickSort(arr, left, p-1); quickSort(arr, p1, right); }插入排序实现void insertionSort(int arr[], int left, int right) { for (int i left1; i right; i) { int key arr[i]; int j i-1; while (j left arr[j] key) { arr[j1] arr[j]; j--; } arr[j1] key; } }阈值选择通常取10 ~ 20具体可通过测试调整。太大会削弱快排优势太小优化不明显。效果减少递归调用次数递归树底部的许多小节点被剪枝。利用插入排序在小数组上的高效和稳定性。快速排序非递归快速排序通常用递归实现但递归太深可能导致栈溢出。非递归版本用自己管理的栈保存待排序的区间避免了系统调用栈的开销。执行流程初始将整个区间入栈循环弹出区间进行分区再将得到的左右子区间入栈直到栈空。非递归快排的核心思想递归快排的工作流程quickSort(arr, left, right): if (left right) return pivot partition(arr, left, right) // 分区得到基准下标 quickSort(arr, left, pivot-1) // 递归处理左半区 quickSort(arr, pivot1, right) // 递归处理右半区非递归模拟我们用栈来保存“每一次递归调用需要处理的区间边界”。初始将[left, right]压栈。循环弹出栈顶区间[L, R]如果区间有效L R则进行分区得到基准位置div。然后将左子区间[L, div-1]和右子区间[div1, R]分别压栈。重复直到栈空。栈的LIFO特性决定了处理顺序先压入右区间再压入左区间则左区间会先被处理类似递归中的先左后右。void QuickSortNonR(int* a, int left, int right) { Stack st; StackInit(st); // 初始将整个区间 [left, right] 压栈先压左边界后压右边界 //注意顺序先左后右 → 弹栈时会先得到右边界。 StackPush(st, left); StackPush(st, right); while (StackEmpty(st) ! 0) // 栈非空则继续处理 { // 因为压栈顺序是先左后右所以先弹出的是右边界 right StackTop(st); StackPop(st); left StackTop(st); StackPop(st); // 区间内元素个数 2 则不需要排序注意这里是 left right if (left right) continue; // 分区返回基准元素的最终下标基准已经归位 int div PartSort1(a, left, right); // 将右子区间 [div1, right] 压栈 StackPush(st, div 1); StackPush(st, right); // 将左子区间 [left, div-1] 压栈 StackPush(st, left); StackPush(st, div - 1); } StackDestroy(st); }例子初始数组[6, 1, 2, 7, 9, 3, 4, 5, 10, 8]下标 0~9。假设分区函数PartSort1返回基准最终位置例如挖坑法pivot6 最后放到下标 5。栈初始[0, 9]先左后右第一轮循环弹出left0, right9→ 分区得div5右子区间[6,9]压栈StackPush(6); StackPush(9);左子区间[0,4]压栈StackPush(0); StackPush(4);此时栈内容从底到顶[6,9] , [0,4]栈顶是 [0,4]第二轮循环弹出栈顶[0,4]弹出left0, right4→ 分区得div3假设压右区间[4,4]→ 压左区间[0,2]栈内容[6,9] , [4,4] , [0,2]第三轮循环弹出[0,2]分区得div1压右区间[2,2]→ 压左区间[0,0]栈内容[6,9] , [4,4] , [2,2] , [0,0]第四轮循环弹出[0,0]left0, right0→left right跳过栈内容[6,9] , [4,4] , [2,2]第五轮循环弹出[2,2]跳过栈内容[6,9] , [4,4]第六轮循环弹出[4,4]跳过栈内容[6,9]第七轮循环弹出[6,9]继续分区以此类推直到栈空。最终数组排序完成。特性总结1. 快速排序整体的综合性能和使用场景都是比较好的所以才敢叫快速排序2. 时间复杂度O(N*logN)3. 空间复杂度O(logN)4. 稳定性不稳定归并排序基本思想归并排序MERGE-SORT是建立在归并操作上的一种有效的排序算法,该算法是采用分治法Divide and Conquer的一个非常典型的应用。将已有序的子序列合并得到完全有序的序列即先使每个子序列有 序再使子序列段间有序。若将两个有序表合并成一个有序表称为二路归并。 归并排序核心步骤第一阶段分解 (Divide)分解的过程就像是一棵树的生长过程自顶向下不断地将数组从中间劈成两半直到每一个节点只剩下两个元素或一个元素。第一层分解◦ 将 {10, 6, 7, 1, 3, 9, 4, 2} 分成左半部分 {10, 6, 7, 1} 和右半部分 {3, 9, 4, 2}。第二层分解◦ 左半部分继续分变成 {10, 6} 和 {7, 1}。◦ 右半部分继续分变成 {3, 9} 和 {4, 2}。第三层分解叶子节点◦ 直到每个子数组只有两个元素图中绿色底线部分{10, 6}, {7, 1}, {3, 9}, {4, 2}。◦ (注在计算机实现中通常会继续分解到单个元素因为单个元素默认是有序的)。第二阶段合并 (Merge)这是算法真正干活的地方自底向上。我们需要从下往上看将两个已经有序的子数组合并成一个更大的有序数组。合并的基本规则双指针法比较两个数组当前的第一个元素谁小就把谁拿出来放到新数组里然后移动那个数组的指针。第一层合并两两合并◦ 合并 {10, 6}▪ 比较 10 和 66 小先放 6。▪ 剩下 10放 10。▪ 结果{6, 10} 变成了有序的蓝框。◦ 合并 {7, 1}▪ 比较 7 和 11 小先放 1。▪ 剩下 7放 7。▪ 结果{1, 7}。◦ 右侧同理 合并得到 {3, 9} 和 {2, 4}。第二层合并四个四个合并◦ 合并左边 {6, 10} 和 {1, 7}▪ 新数组空比较 6 和 1 - 取出 1。▪ 比较 6 和 7 - 取出 6。▪ 比较 10 和 7 - 取出 7。▪ 取出剩下的 10。▪ 最终结果{1, 6, 7, 10}。◦ 合并右边 {3, 9} 和 {2, 4}▪ 比较 3 和 2 - 取出 2。▪ 比较 3 和 4 - 取出 3。▪ 比较 9 和 4 - 取出 4。▪ 取出剩下的 9。▪ 最终结果{2, 3, 4, 9}。第三层合并终极合并◦ 现在有两个大数组{1, 6, 7, 10} 和 {2, 3, 4, 9}。◦ 这是一个典型的“两个有序链表/数组合并”问题▪ 1 2取 1▪ 6 2取 2▪ 6 3取 3▪ 6 4取 4▪ 6 9取 6▪ 7 9取 7▪ 10 9取 9▪ 剩下 10取 10◦ 最终结果{1, 2, 3, 4, 6, 7, 9, 10}。总结与特性性质稳定性 归并排序是稳定的排序算法。这意味着在排序过程中相等元素的相对位置不会改变时间复杂度 O(n log n)。◦ log n 来自于“分”的过程树的高度。◦ n 来自于“合”的过程每一层合并都需要遍历所有元素。◦ 这是所有比较排序算法中能达到的最优平均时间复杂度。空间复杂度 O(n)。◦ 归并排序在合并的过程中需要借助额外的辅助数组来存放临时数据因此它不是原地排序算法。适用场景◦ 数据量较大时。◦ 对稳定性有要求时。◦ 链表排序不需要连续内存空间只需改变指针指向。非比较排序计数排序Counting Sort是一种非常巧妙的非比较排序算法。与我们之前学的归并排序或快速排序不同它不通过比较元素的大小来确定顺序而是利用数据的范围来进行排序。它特别适合处理数据范围集中且数据量大的整数数组。核心思想鸽巢原理与哈希定址计数排序的基本思想是如果我们知道每个数值在数组中出现了多少次我们只需要按顺序把这些数值“填”回去就能得到一个有序的数组。这其实就是哈希表的直接定址法的一个变形用数组下标代表数值用数组的值代表该数值出现的次数。操作步骤1. 统计相同元素出现次数2. 根据统计的结果将序列回收到原来的序列中详细解释第一步找出最大值和最小值确定数据范围遍历 A找到 Min 0Max 5。范围 K Max - Min 1 6。所以我们建立计数数组 C[0..5]初值为全 0。第二步统计相同元素出现的频率对应图 a遍历原数组 A 的每个元素C[A[i]]A[0]2 → C[2] → C[2]1A[1]5 → C[5] → C[5]1A[2]3 → C[3] → C[3]1A[3]0 → C[0] → C[0]1A[4]2 → C[2] → C[2]2A[5]3 → C[3] → C[3]2A[6]0 → C[0] → C[0]2A[7]3 → C[3] → C[3]3统计完之后图 a 中 C 的状态是C [2, 0, 2, 3, 0, 1]含义0 出现 2 次1 出现 0 次2 出现 2 次3 出现 3 次4 出现 0 次5 出现 1 次。第三步对计数数组求前缀和对应图 b这一步是计数排序的精髓所在。我们把 C 从前往后累加C[0] 2C[1] 2 0 2C[2] 2 2 4C[3] 4 3 7C[4] 7 0 7C[5] 7 1 8图 b 中 C 变成了C [2, 2, 4, 7, 7, 8]现在 C[i] 的含义变了——它不再表示i 出现的次数而是表示≤ i 的元素一共有多少个。换句话说数值 i 在最终有序数组中的最后一个合法位置是 C[i]这里图里位置编号是从 1 开始的即 B 的下标 1~8。这样做的目的有两个一是让我们知道每个值该放哪里二是为接下来的逆向回填保证稳定性打基础。第四步根据统计结果将序列回收到原来的序列中对应图 c → 图 d这是最关键的一步。从原数组 A 的末尾向前遍历逆向对每一个元素 A[i]查 C[A[i]]得到这个值应该放的新位置 pos C[A[i]]把 A[i] 放到结果数组 B 的第 pos 个位置下标 pos-1C[A[i]]--跟着图 c 走一遍A {2, 5, 3, 0, 2, 3, 0, 3}。最终 B 如图 d 所示B {0, 0, 2, 2, 3, 3, 3, 5}再把 B 抄回原数组 A排序完成。注意为什么从后往前​ 图中两个 3A[2] 和 A[7]A[7] 在原数组中靠后它先被处理占住了位置 7A[2] 靠前后被处理占住了位置 6。所以输出后两个 3 的相对顺序还是原来的前 3 还在前原来的后 3 还在后——这就是稳定性的保证。计数排序的特性总结1. 高效但受限于场景计数排序的致命短版是它需要开的额外数组大小由值域范围决定。如果数据是 {1, 999999}范围接近百万但只有两个数C 数组就得开百万级——纯属浪费。所以计数排序只适合数据范围集中且较小的整数场景比如成绩排序 0~100、年龄排序 0~150 等。2. 时间复杂度O(N K)N 是数组长度K 是值域范围Max - Min 1。遍历 A 统计频次花 O(N)前缀和遍历 C 花 O(K)逆向回填再花 O(N)合起来就是 O(N K)。图上 K6、N8整个过程确实是线性时间远快于任何基于比较的 O(N log N) 排序——但前提是 K 不能太大。3. 空间复杂度O(K)需要额外开一个大小为 K 的计数数组 C以及通常还需要一个大小为 N 的结果数组 B有些写法可以优化成一个 B 然后拷回 A所以额外空间 O(K N)但主导项就是 O(K)。4. 稳定性稳定关键在于第三步的前缀和变换 第四步的从后往前逆向回填。正着填会破坏相等元素的先后顺序逆着填就能保住。图 c 的箭头方向从下往上扫描 A直观地体现了这一点。排序算法复杂度及稳定性分析选择题1. 快速排序算法是基于 的一个排序算法。A分治法B贪心法C递归法D动态规划法2.对记录54,38,96,23,15,72,60,45,83进行从小到大的直接插入排序时当把第8个记录45插入到有序表时为找到插入位置需比较 次采用从后往前比较A 3B 4C 5D 63.以下排序方式中占用On辅助存储空间的是A 简单排序B 快速排序C 堆排序D 归并排序4.下列排序算法中稳定且时间复杂度为O(n2)的是 A 快速排序B 冒泡排序C 直接选择排序D 归并排序5.关于排序下面说法不正确的是A 快排时间复杂度为O(N*logN)空间复杂度为O(logN)B 归并排序是一种稳定的排序,堆排序和快排均不稳定C 序列基本有序时快排退化成冒泡排序直接插入排序最快D 归并排序空间复杂度为O(N), 堆排序空间复杂度的为O(logN)6.下列排序法中最坏情况下时间复杂度最小的是 A 堆排序B 快速排序C 希尔排序D 冒泡排序7.设一组初始记录关键字序列为(65,56,72,99,86,25,34,66)则以第一个关键字65为基准而得到的一趟快速排序结果是A 3456256586997266B 2534566599867266C 3456256566998672D 3456256599867266答案 1.A 2.C 3.D 4.B 5.D 6.A 7.A