本文主要介绍归并排序和快速排序，并用swift语言实现，以及一个LeetCode练习题。
归并排序快速排序.数组中的第K个最大元素归并排序
利用分治思想将输入序列分成两部分，分别排序然后再组合成有序序列。具体步骤如下：
把长度为n的输入序列分成两个长度为n/2的子序列；对这两个子序列分别采用归并排序；将两个排序好的子序列合并成一个最终的排序序列。其中第一步是一个递归过程，将序列分成只含一个元素的子序列。
特点：
复杂度稳定为O(nlogn)稳定排序需要额外空间swift语言实现
publicfuncmergeSort()-[Element]{guardself.count1else{returnself}//1先分治letmid=self.count/2letright:[Element]=Array(self.suffix(from:mid)).mergeSort()letleft:[Element]=Array(self.prefix(upTo:mid)).mergeSort()//2然后合并varmerged=ArrayElement.init()vari=0,j=0whileiright.countjleft.count{ifright[i]left[j]{merged.append(left[j])j+=1}else{merged.append(right[i])i+=1}}ifiright.count{merged.append(contentsOf:right.suffix(from:i))}ifjleft.count{merged.append(contentsOf:left.suffix(from:j))}returnmerged}
性能分析：观察程序中的步骤1和步骤2可以得出下面的复杂度公式
T(n)=2*T(n/2)+n=2*(2*T(n/4)+n/2)+n=4*T(n/4)+2n...=2^k*T(n/2^k)+k*nn/2^K=1=2^k=n=k=lognT(n)=Cn+n*logn=O(nlogn)快速排序
快速排序是选定一个标识位通过一趟遍历将序列分为两部分，一部分比标志位大另一部分标志位小。具体步骤如下
从数列中挑出一个元素，称为“基准”（pivot）；重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）递归地把小于基准值元素的子数列和大于基准值元素的子数列排序特点：
复杂度为O(nlogn),在极其特殊情况下为O(n)不稳定排序原地排序，不需要额外空间为数组添加快排扩展
extensionArraywhereElement:Comparable{funcquickSort()-[Element]{vararray=selfprint(self)quickSort_c(array,0,array.count-1)returnarray;}funcquickSort_c(_array:inout[Element],_start:Int,_end:Int){//1.结束条件guardendstartelse{return}//2.随机选取元素letpvoit=Int.random(in:start...end)array.swapAt(start,pvoit)//3.分区lettemp=array[start]vark=start+1foriink...end{ifarray[i]temp{array.swapAt(k,i)k+=1}}k-=1array.swapAt(start,k)//4.递归快排子分区quickSort_c(array,k+1,end)quickSort_c(array,start,k-1)}}
性能分析：利用归并排序复杂度的分析方法，快排的复杂度为O(nlogn)，但快排的复杂度是不稳定的，只有两个分区元素个数相同时复杂度为O(nlogn)，一种特殊情况就是数据有序的或者接近有序的，每次分区点都选择最后一个数据，那快速排序算法就会变得非常糟糕，时间复杂度就会退化为O(n2)。这也是代码中第二步随机选取元素存在的意义
.数组中的第K个最大元素LeetCode题
在未排序的数组中找到第k个最大的元素。请注意，你需要找的是数组排序后的第k个最大的元素，而不是第k个不同的元素。
示例输入:[3,2,1,5,6,4]和k=2输出:5输入:[3,2,3,1,2,4,5,5,6]和k=4输出:4
该题可以利用快排思想解答，每一趟快排可以确定标志位元素的位置，当元素位置等于K是结束递归。下面是具体代码
classSolution2{funcfindKthLargest(_nums:[Int],_k:Int)-Int{vararr=numsifarr.countk{return-1}returnpartition(arr,k,0,arr.count-1)}//分区递归privatefuncpartition(_nums:inout[Int],_k:Int,_start:Int,_end:Int)-Int{letpivot=Int.random(in:start...end);nums.swapAt(pivot,end)//分区：比pivot大的在左侧，小于pivot的元素在右侧vari=start;forjini..end{ifnums[j]nums[end]{nums.swapAt(i,j);i+=1;}}nums.swapAt(i,end)ifi+1==k{//pivot正好为第k大元素返回pivot元素returnnums[i];}elseifi+1k{//左侧元素个数k,递归在右侧寻找returnpartition(nums,k,i+1,end);}else{//左侧元素个数k,递归在左侧寻找returnpartition(nums,k,start,i-1);}}}
复杂度分析
递归的复杂度公式为T(n)=T(n/2)+n做如下变换可得复杂度为O(n)
T(n)=T(n/2)+n=T(n/4)+n/2+n=T(n/8)+n/4+n/2+n...=T(1)+...+n/4+n/2+n=n+n/2+n/4+...+1(等比数列求和)=2n-1=O(n)
欢迎同学们白癜风吃什么药好得快白癜风是怎么样的