算法思想之排序问题

算法知识点

分治法求解排序问题思想：按某种方式将序列分成两个或多个子序列，分别进行排序，再将已排序的子序列合并成一个有序序列。合并排序和快速排序是两种典型的符合分治策略的排序算法。

合并排序：把两个或多个有序序列合并成一个有序序列。最基本的合并排序算法——两路合并排序。两路合并排序：把两个有序序列合并成一个有序序列。

算法题目来源

排序问题

算法题目描述

各种排序

做题思路

提示：两路合并排序。使用分治法的两路合并排序算法：

将待排序的元素序列一分为二，得到长度基本相等的两个子序列，分别排序。如果子序列较长，还可继续细分，直到子序列的长度不超过1为止。当分解所得的子序列已排列有序时，将两个有序子序列合并成一个有序子序列，得到原问题的解。

合并方法：

比较两序列中的最小值，输出其中较小者，然后重复此过程，直到其中一个队列为空时，如果另一个队列还有元素没有输出，则将剩余元素依次输出。

模板代码

两路合并排序算法

void MergeSort(int left,int right)

{

if (left<right) {//序列长度大于1时，进一步划分

int mid=(left+right)/2;//一分为二

MergeSort(left,mid);//对左子序列元素排序

MergeSort(mid+1,right);//对右子序列元素排序

Merge(left,mid,right);

//将已排好序的左、右子序列合并成一个有序序列

}

做题过程中遇到的bug及解决方案

void Merge (int left,int mid,int right)

{ T* temp=new T[right-left+1];

int k=0; //k为数组temp中当前位置

int i=left,j=mid+1;//i为左子序列当前位置；j为右子序列当前位置

while ((i<=mid) && (j<=right))

if (l[i]<=l[j])temp[k++]=l[i++];

else temp[k++]=l[j++];

while (i<=mid) temp[k++]=l[i++];

while (j<=right) temp[k++]=l[j++];

for (i=0,k=left;k<=right;) l[k++]=temp[i++];

//从temp中重新写回序列l中

}

相关算法题型题目总结

两路合并算法时间复杂度分析

Merge函数将长度之和为n的两个有序子序列合并成一个有序序列，执行过程中最多需进行n-1次关键字值间的比较，其时间复杂度为O(n)。

请写出合并排序递归算法MergeSort的时间复杂度递归函数？

两路合并算法时间复杂度分析

Merge函数将长度之和为n的两个有序子序列合并成一个有序序列，执行过程中最多需进行n-1次关键字值间的比较，其时间复杂度为O(n)。

由此可得到合并排序递归算法MergeSort的时间复杂度递归函数：

由定理5-1，或通过迭代计算，均可得到两路合并排序的时间复杂度为T(n)=O(nlogn)。

两路合并算法空间复杂度分析

两路合并排序一般需要一个与原序列相同长度的辅助数组temp，因此它所需的额外空间为O(n)。

两路合并排序

快速排序

快速排序（又称分划交换排序）：在待排序的序列（k0,k1,…,kn-1）中选择一个元素作为分划元素，也称为主元。以主元为轴心，对原序列重新排列，分成左右两个子序列，使主元左侧子序列中所有元素都不大于主元，主元右侧子序列中所有元素都不小于主元，这样的分解过程称为一趟分划。原序列被分成三部分：主元和左、右两个子序列(Kp(0),Kp(1),…Kp(j-1))Kp(j)(Kp(j+1),Kp(j+2),Kp(n-1))

通过分划操作，原序列的排序问题被分解成了两个性质相同、相互独立的子问题，分别对两个子序列进行排序。

快速排序算法

void QuickSort(int left,int right)

{if (left<right){ //当序列长度>1时，用Partition函数分割

int j=Partition(left,right);//对序列进行分划操作

QuickSort(left,j-1);//对左子序列进行快速排序

QuickSort(j+1,right);//对右子序列进行快速排序

}

}

拓展

快速排序算法空间复杂度分析

最坏情况下，程序所需的系统栈调用深度，最大为O(n)。

如果希望减少使用的栈空间，可以每次分划后在栈中保存较大子序列的上、下界，而对较小的子序列先进行排序。这样可使所需的栈空间大小降为O(logn)。

堆排序是利用二叉树的一种排序方法。

堆(Heap)也译为堆或堆垒,是与二叉排序树不同的一种二叉树，它的定义为：一个完全二叉树(完全二叉树：各层都是满的，只是最下面一层从右边起连续缺几个结点)，它的每个结点对应于原始数据的一个元素，且规定：如果一个结点有子结点，此结点数据必须大于或等于其子结点的数据。

由此可见，堆是完全二叉树，且规定了父结点和子结点数据之间必须满足的条件。阵排序分为建立堆阵和利用堆阵排序两大步骤。设堆阵有r个满层，元素个数n=2r-1。

最坏的情况假设每个元素都需要从原来位置“筛”到堆阵的最底层，仅原来在最底层的不必筛，这样一来最上层的一个元素要下降r-1层；第二层的两个元素要下降r-2层；……；中间第i层2(i-1)个元素要下降r-i层；……；下面倒数第二层，也即第r-1层的2(r-2)个元素下降一层。

每筛下一层要进行两次比较（先左右两子节点相比，然后此元素与其中较大者比）。