文章目录
  1. 1. 快速排序
  2. 2. 归并排序

快速排序

/*当每次划分为 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++
    }
}
}

function mergeSort(arr, p, r) {
if (p < r) {
    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)

文章目录
  1. 1. 快速排序
  2. 2. 归并排序