相对于上一节介绍的三种排序算法,本节的排序算法在实际中应用更加广泛,赶快学习起来吧。
归并排序
分治是归并排序算法的主要思想。在算法中的直接体现就是先将数组通过多次切割划分成极短的数据,当数据长度被划分成一时,不用排序对于一个数据本身来说就是有序的,这个划分的过程被称为归。 当数据长度被划分成一时,我们就要通过并操作来一边将之前划分的数据合并到一起一边排序。因为之前划分的每一个数组片段都是有序的,因此归操作逻辑就很简单了。
function seprate(array,start,end){
let l = end-start + 1
let mid
if(l>1){
if(l%2===0){//偶数个
mid = (start+end-1)/2
} else {//奇数个
mid = (start+end)/2
}
seprate(array, start,mid)
seprate(array, mid+1,end)
}
}
这是归操作的代码,当seprate调用栈到底的时候,start,end就会指向同一个元素,并且mid是undefined,最后再递归调用并函数。
function seprate(array,start,end){
let l = end-start + 1
let mid
if(l>1){
if(l%2===0){//偶数个
mid = (start+end-1)/2
} else {//奇数个
mid = (start+end)/2
}
seprate(array, start,mid)
seprate(array, mid+1,end)
}
mix(array, start, end, mid)
}
function mix (array, start, end, mid){
let length = end - start +1
if(mid){
let arrayA = []
let arrayB = []
//将左右两边的内容分别复制到两个数组里
for(let i = 0,l = mid-start+1;i<l;i++){
arrayA[i] = array[start+i]
}
for(let i = 0,l = end-mid;i<l;i++){
arrayB[i] = array[mid+i+1]
}
let arrayAindex = 0
let arrayBindex = 0
let arrayindex = start
//对比两个数组开头的内容,因为两个数组本身是有序的,去替换原数组的内容,
//直到两个数组的内容都被遍历完毕
while(arrayAindex + arrayBindex <length){
let arrayAItem = arrayA[arrayAindex]
let arrayBItem = arrayB[arrayBindex]
if(arrayAItem && arrayBItem){
if(arrayAItem<=arrayBItem){
array[arrayindex] = arrayAItem
arrayindex ++
arrayAindex++
}else {
array[arrayindex] = arrayBItem
arrayindex ++
arrayBindex++
}
} else if(arrayAItem) {
array[arrayindex] = arrayAItem
arrayindex ++
arrayAindex++
} else if(arrayBItem){
array[arrayindex] = arrayBItem
arrayindex ++
arrayBindex++
}
}
} else {
return //没有mid说明只剩下了一个元素
}
}
并操作每次是将两个有序的数组片段合并成一个有序的数组,因为两个数组片段本身就有序了。因此我们可以将两个数组片段复制下来,然后每次取两个数组中最小的,放到元素组的开头,以此类推,直到两个数组片段的数据被遍历完毕
算法分析
1.空间复杂度分析
在归的过程中,我们并没有使用线性的内存空间,而在并的过程中,我们每次都要复制一次原数组,因此空间复杂度为O(n)
2.时间复杂度分析
归并排序的时间复杂度分析很复杂,就不证明了,直接说出答案吧O(nlogn),可以看出来这个时间复杂度还是很优秀的,关键是归并排序的时间复杂度极其稳定,跟要排列的数据的有序度没有关系。
3.是否是稳定排序算法
当在并的过程中,如果两个数组的开头相同了,我们可以把位于前侧的数组内的数据优先放入目标数组中,这样就不会破坏原有数据的顺序了,因此是稳定排序算法。
快速排序
快速排序跟归并排序有相似之处,也是依靠分治的思想,但是在对数组片段的排序方式上又跟归并排序不太相同。如果说归并是从下往上排序的话,那么快排就是从上往下排序。归并排序在对数组片段进行排序时,会先从数组片段中随机找出一个元素,这个元素暂且称之为基数,然后再在数组片段的两头各布置一个哨兵,如果左侧的哨兵发现有大于基数的元素,那么把左侧的元素移到右侧,右边的哨兵也是一样。最后两个哨兵相遇,将基数的位置与哨兵相遇的位置互换,数组片段排序完成,再将数组片段分成两段,分别再操作左右两边两个数组片段,直到数组片段是1,结束递归。
function quicksort(array, left, right){
let i,j,target
if(left > right){ //说明已经没有数据可以再分了
return ;
}
//将左右两侧哨兵记录
i = left;
j = right;
//记录基数
target = array[right]
//左右哨兵相遇为终止条件
while(i!=j){
//左侧找到比基数大的节点停下
while(array[i]<=target && i<j){
i++
}
//右侧找到比基数小的节点停下
while(array[j]>=target && i<j){
j--
}
//哨兵没有相遇说明左侧找到了比基数大的,右侧找到了比基数小的,交换
if(i<j){
let item = array[i]
array[i] = array[j]
array[j] = item
}
}
//哨兵相遇,相遇的点就是基数应该位于的中间,与基数交换
array[right] = array[i]
array[i] = target
//继续排序左右两侧
quicksort(array, left, i-1)
quicksort(array, i+1, right)
}
注释已经把思路写的很清楚了,就不赘述了,直接算法分析
算法分析
1.空间复杂度分析
我们在算法过程中只使用了常数级的额外内存空间,因此空间复杂度是O(1),是一个原地排序算法。
2.时间复杂度分析
绝大多数情况下的时间复杂度为O(nlogn),在极端情况下会退化为O(n²)
3.是否是原地排序算法
由于我们在最后将基数和哨兵所指向的位置交换时,可能会破坏数组原有数据的顺序,因此不是一个原地排序算法