|
14天阅读挑战赛
努力是为了不平庸~
算法学习有些时候是枯燥的，这一次，让我们先人一步，趣学算法！欢迎记录下你的那些努力时刻（算法学习知识点/算法题解/遇到的算法bug/等等），在分享的同时加深对于算法的理解，同时吸收他人的奇思妙想，一起见证技术er的成长~
学习加油
算法知识点
分治法求解排序问题思想：按某种方式将序列分成两个或多个子序列，分别进行排序，再将已排序的子序列合并成一个有序序列。合并排序和快速排序是两种典型的符合分治策略的排序算法。
合并排序：把两个或多个有序序列合并成一个有序序列。最基本的合并排序算法——两路合并排序。两路合并排序：把两个有序序列合并成一个有序序列。
算法题目来源
排序问题
算法题目描述
各种排序
做题思路
提示：两路合并排序。使用分治法的两路合并排序算法：
将待排序的元素序列一分为二，得到长度基本相等的两个子序列，分别排序。如果子序列较长，还可继续细分，直到子序列的长度不超过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)个元素下降一层。
每筛下一层要进行两次比较（先左右两子节点相比，然后此元素与其中较大者比）。
|