归并排序与快速排序

快速排序

/*************当每次划分为 n-1 个元素和 0 个元素时，最坏情况发生*********/

 //方法一
 function quickSort(arr) {
    if (arr.length <= 1) {
     return arr
 }
 let mid = Math.floor(arr.length / 2)
 let leftArr = [];
 let rightArr = [];
 let midArr = arr.splice(mid, 1);

 for (let i = 0; i < arr.length; i++) {

     if (arr[i] < midArr[0]) {
         leftArr.push(arr[i])
     } else {
         rightArr.push(arr[i])
     }
  }

 leftArr = quickSort(leftArr)

 rightArr = quickSort(rightArr)

 return leftArr.concat(midArr, rightArr)
 }
// 方法二
var quickSort = function(arr) {
 if (arr.length <= 1) { return arr; }
 var pivotIndex = Math.floor(arr.length / 2);   //基准位置（理论上可任意选取）
 var pivot = arr.splice(pivotIndex, 1)[0];  //基准数   此处获得基准数并将基准数从数组中去掉
 var left = [];
 var right = [];
 for (var i = 0; i < arr.length; i++){
     if (arr[i] < pivot) {
         left.push(arr[i]);
     } else {
         right.push(arr[i]);
     }
 }
 return quickSort(left).concat([pivot], quickSort(right));  //链接左数组、基准数构成的数组、右数组
 }


 arr = quickSort(arr)

归并排序

 function merge(arr, p, q, r) {
 let leftArr = arr.slice(p, q + 1)
 let rightArr = arr.slice(q + 1, r + 1)

 leftArr.push(Number.POSITIVE_INFINITY)
 rightArr.push(Number.POSITIVE_INFINITY)
 let i = 0;
 let j = 0;
 for (let k = p; k <= r; k++) {

     if (leftArr[i] <= rightArr[j]) {
         arr[k] = leftArr[i]
         i++
     } else {
         arr[k] = rightArr[j]
         j++
     }
 }
 }
 // js 函数默认返回的是 undefined
 function mergeSort(arr, p, r) {
     if (p >= r) return;
     let q = Math.floor((p + r) / 2)
     mergeSort(arr, p, q)
     mergeSort(arr, q + 1, r)
     merge(arr, p, q, r)
 
 }
 mergeSort(arr, 0, arr.length - 1)

归并排序与快速排序都是分治策略的应用，二者的区别是：

1. 快速排序生成新的数组而归并排序是在原有数组上更改
2. 二者时间复杂度不相同，快速排序最坏情况是 O(n^2)
3. 二者区别的根本原因是快速排序的划分是不稳定的，有可能划分为 n-1 个元素的子数组和 0 个元素的子数组

平均情况下快速排序的时间复杂度是 Θ(nlgn)，最坏情况是 Θ(n2) :

1. 当划分产生的两个子问题分别包含 n-1 和 0 个元素时，最坏情况发生。
   划分操作的时间复杂度为 Θ(n)，T(0)=Θ(1)
   算法运行时间的递归式为 T(n)=T(n−1)+T(0)+Θ(n)=T(n−1)+Θ(n)
   解为 T(n)=Θ(n2)

2. 当划分产生的两个子问题分别包含 ⌊n/2⌋ 和 ⌈n/2⌉−1 个元素时，最好情况发生。
   算法运行时间递归式为 T(n)=2T(n/2)+Θ(n)
   解为 T(n)=Θ(nlgn)

3. 事实上只要划分是常数比例的，算法的运行时间总是O(nlgn)。 假设按照 9:1 划分，每层代价最多为 cn，递归深度为 log9n/10=Θ(lgn)，故排序的总代价为 O(nlgn)
   平均情况下，比如一次坏的划分接着一次好的划分，坏的划分那一项可以合并到好的划分里，统计上来讲平均情况下的时间复杂度仍然是Θ(nlgn)