算法导论复习常见算法思想PPT2-1：1. 堆排序（选择类排序，不稳定）（1）初始化操作：将R1.n构造为初始堆；（2）每一趟排序的基本操作：将当前无序区的堆顶记录R1和该区间的最后一个记录交换，然后将新的无序区调整为堆（亦称重建堆）。时间复杂度是：O（nlgn）2. 归并排序 归并排序采用分治法思想的稳定的排序。算法思想是先使每个子序列有序，再使子序列段间有序。第一步：申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列第二步：设定两个指针，最初位置分别为两个已经排序序列的起始位置第三步：比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置重复步骤3直到某一指针超出序列尾，将另一序列剩下的所有元素直接复制到合并序列尾。时间复杂度是：O（nlgn）3. 快速排序（交换类排序，不稳定）（1）通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小；（2）然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递
