基于分治策略的排序算法实现

实验1-分治策略（2017） 本实验的主要目的是让学生理解分治法的算法思想，并通过实践来加深对分治法的算法原理及实现过程的理解。实验内容包括使用分治法实现两路合并排序和快速排序，采用基于“五元中值组取中值分割法”的线性时间选择算法，找出N个元素集合S中的第k个最小的元素。 在排序问题中，分治法是一种常用的策略。它的思路是将序列分成两个或多个子序列，然后分别对每个子序列进行排序，最后将已排序的子序列合并成一个有序序列。两路合并排序和快速排序是两种典型的符合分治策略的排序算法。 在两路合并排序算法中，将待排序元素平分成大小大致相同的两个子序列，然后对每个子序列分别使用递归的方法进行两路合并排序，直到子序列长度变为1，最后利用合并算法将得到的已排序好的两个子序列合并成一个有序的序列。两路合并排序算法的核心部分是将子问题的解组合成原问题解得合并操作。 快速排序算法也是一种基于分治策略的排序算法。它的基本思想是选择一个ivot元素，然后将待排序序列分成两个部分，一部分元素小于ivot，另一部分元素大于ivot。然后，对这两个部分分别进行快速排序，直到整个序列排序完成。 在实现排序算法时，需要定义一个可排序表类SortableList，其中包括输入函数Input和输出函数Output。Input函数用于向可排序表中输入待排序序列，而Output函数用于输出已经排序好的序列。 在实验中，学生需要使用C++语言实现两路合并排序和快速排序算法，并将其应用于实际问题中。通过实验，学生将加深对分治法的算法原理及实现过程的理解，并掌握排序算法的实现技术。 实验步骤： 一、两路合并排序和快速排序 1. 排序是数据处理中常用的重要手段，是指将一个元素序列调整为按指定关键字值的递增（或递减）次序排列的有序序列。 2. 用分治法求解排序问题的思路是，按某种方式将序列分成两个或多个子序列，分别进行排序，再将已排序的子序列合并成一个有序序列。 3. 如果采用顺序存储的可排序表作为算法实现的数据结构，则需要定义一个可排序表类SortableList，两路合并算法和快速排序算法均由定义在该类上的函数实现。 二、基于“五元中值组取中值分割法”的线性时间选择算法 1. 找出N个元素集合S中的第k个最小的元素，使其在线性时间内解决。 2. 采用基于“五元中值组取中值分割法”的线性时间选择算法，找出N个元素集合S中的第k个最小的元素。 通过本实验，学生将掌握排序算法的实现技术，理解分治法的算法思想，并加深对算法原理及实现过程的理解。