当前位置： 首页 >> 数据结构与算法 >> 中级排序

---

中级排序

2020-07-04 18:25:13 星期六  阅读：2001

---

前面讲的三种排序算法，都适合小规模数据排序。因为时间复杂度是O(n^2)，如果要对大规模数据排序，则需要使用归并排序和快速排序。归并排序和快速排序都用到了分治的思想。 ####归并排序 如果要排序一个数组，我们先把数组从中间分成前后两部分，然后对前后两部分分别排序，再将排好序的两部分合并在一起，这样整个数组就都有序了。分治的思想其实就是分而治之，将一个大的问题分解成小的子问题来解决。 #####算法性能分析 递归排序是稳定的算法 不管是最好、最坏还是平均情况下，时间复杂度都是O(nlogn) 空间复杂度是O(n) 将两个有序的数组合并 ``` # 需要合并的两个有序arr def merge(a, b): ai = 0 # 数组a的游标 bi = 0 # 数组b的游标 tmp = [] # 最终合并后的数组 while (ai < len(a) or bi < len(a)): # 判断游标是否超过任何一个数组的最大下标 if a[ai] < b[bi]: # 如果某个数值比较小，则对应的下标加1，同时把最小值append到tmp里 tmp.append(a[ai]) ai += 1 else: tmp.append(b[bi]) bi += 1 # 如果某个数组比较短，另外一个很长，当短的数组遍历完后， # 长的数组里剩下的所有元素都不需要比较了。肯定都是大于该数组的 # 把未比较的数据直接搬移到tmp尾部即可 if ai >= len(a): tmp = tmp + b[bi:] break # 一定要退出循环，否则数组下标越界 if bi >= len(b): tmp = tmp + a[ai:] break return tmp # 示例， 故意设置了一些重复值且两个数组长度不相等 a = [3, 5, 9, 10, 12, 19] b = [5, 6, 8, 10, 11, 12, 15, 16, 20, 21, 23, 25, 29, 30] ret = merge(a, b) print(ret) # 输出如下 [3, 5, 5, 6, 8, 9, 10, 10, 11, 12, 12, 15, 16, 19, 20, 21, 23, 25, 29, 30] ``` ####快速排序 快排也是利用分治的思想，看起来有点像归并排序。但其实完全不一样。快排的思想是：如果要排序数组中下标从p到r之间的一组数据，我们选择p到r之间的任意一个数据作为pivot（分区点）。我们遍历 p 到 r 之间的数据，将小于 pivot 的放到左边，将大于 pivot 的放到右边，将 pivot 放到中间。经过这一步骤之后，数组 p 到 r 之间的数据就被分成了三个部分，前面 p 到 q-1 之间都是小于 pivot 的，中间是 pivot，后面的 q+1 到 r 之间是大于 pivot 的。 快排和归并的原理如下：归并是从下到上，而快排是从上到下。 #####性能分析 时间复杂度是O(nlogn) #####代码实现 ``` def quick_sort(arr): if len(arr) <= 1: # 递归终止条件 数组中只有一个元素 return arr x = arr[-1] # 获取分区节点，我这里直接取最后一个 arr.pop(-1) # 记得要把分区节点的数据删除，不参与遍历 left, right = [], [] for i in arr: # 大于分区节点的数据放到右边的数组里 ,小于或等于分区节点的数据放到左边的数组里 left.append(i) if i <= x else right.append(i) return quick_sort(left) + [x] + quick_sort(right) # 再递归对左右两边的数据进行拆分 ``` ####思考题 现在你有 10 个接口访问日志文件，每个日志文件大小约 300MB，每个文件里的日志都是按照时间戳从小到大排序的。你希望将这 10 个较小的日志文件，合并为 1 个日志文件，合并之后的日志仍然按照时间戳从小到大排列。如果处理上述排序任务的机器内存只有 1GB，你有什么好的解决思路，能“快速”地将这 10 个日志文件合并吗？ 答案： 先构建十条io流，分别指向十个文件，每条io流读取对应文件的第一条数据，然后比较时间戳，选择出时间戳最小的那条数据，将其写入一个新的文件，然后指向该时间戳的io流读取下一行数据，然后继续刚才的操作，比较选出最小的时间戳数据，写入新文件，io流读取下一行数据，以此类推，完成文件的合并， 这种处理方式，日志文件有n个数据就要比较n次，每次比较选出一条数据来写入，时间复杂度是O（n），空间复杂度是O（1）,几乎不占用内存。