快速排序算法的深入分析

项目被搁置了, 看文档看的瞌睡了, 来研究一下算法, 第一次(可能之前学习过,忘掉了)看到这种算法, 觉得挺有意思, 遂来深入分析一下:

第一步分为两段快速排序, 首先用数学公式退到一下遍历的次数(此处假设认为其他操作不耗时, 只有遍历操作耗时).

那么普通排序的遍历次数是n * n-1, 分成两段的遍历次数是n + m * (m - 1) + (n - m - 1) * (n - m - 2) [1 < m < n],

解释一下后面这个公式, 前面的n是进行分组, 后面的是分两段进行普通排序, m代表第一段的长度.

(n * n-1) - (n + m * (m - 1) + (n - m - 1) * (n - m - 2) [1 < m < n]) = m * m - 2 *(n - 1) * (m + 2)

看上去这个公式恒小于零, 推导证明就不做了, 绕啊绕的苦涩难懂, 而且这里忽略了其他操作的耗时, 所以还是直接用代码说话吧:

import now from 'performance-now';

// Generate Array to Sort
const originArray = [];
const max = 10;
for (let k = 0; k < max; k++) {
  originArray[k] = Math.floor(Math.random() * max) + 1;
}
console.log("Origin       Array", JSON.stringify(originArray));
console.log();

const len = originArray.length;
let normalSort = [], quickSort = [], normalTimes = 0, quickTimes = 0;

var t0 = now();
//Normal Sort Method
normalSort = Array.from(originArray);
for (let i = 0; i < len; i++) {
  for (let j = i + 1; j < len; j++) {
    normalTimes++;
    if (normalSort[i] < normalSort[j]) {
      let temp = normalSort[i];
      normalSort[i] = normalSort[j];
      normalSort[j] = temp;
    }
  }
}

var t1 = now();

//Quick Sort Method
const half = Math.floor(len / 2);
let rightPart = [];
for (let i = 0; i < len; i++) {
  if (originArray[i] > originArray[half]) {
    quickSort.push(originArray[i]);
  } else {
    rightPart.push(originArray[i]);
  }
}
const splitLen = quickSort.length;
quickSort = quickSort.concat(rightPart);
for (let i = 0; i < splitLen; i++) {
  for (let j = i + 1; j < splitLen; j++) {
    quickTimes++;
    if (quickSort[i] < quickSort[j]) {
      let temp = quickSort[i];
      quickSort[i] = quickSort[j];
      quickSort[j] = temp;
    }
  }
}
for (let i = splitLen; i < len; i++) {
  for (let j = i + 1; j < len; j++) {
    quickTimes++;
    if (quickSort[i] < quickSort[j]) {
      let temp = quickSort[i];
      quickSort[i] = quickSort[j];
      quickSort[j] = temp;
    }
  }
}
var t2 = now();

console.log("Normal Sort Result", JSON.stringify(normalSort));
console.log("Quick Sort  Result", JSON.stringify(quickSort));
console.log();

console.log("NormalSort took " + (t1 - t0) + " milliseconds. loop times" + normalTimes);
console.log("QuickSort  took " + (t2 - t1) + " milliseconds. loop times" + quickTimes);

下面分别是数组长度对应10、100、1000...的执行时间:

可以看出, 除了1000次的时候, 慢一点, 其他的时候, 速度优势是很明显的.

刚好最近在学Python, 于是翻译成python, 重新跑了一遍:

import random
import timeit
import copy
import math
import json

# Generate Array to Sort
originArray = []
maxN = 10
for i in range(0, maxN):
    originArray.append(random.randint(1, maxN))

lenN = len(originArray);
normalSort = []
quickSort = []
normalTimes = 0
quickTimes = 0

t0 = timeit.default_timer()
# Normal Sort Method
normalSort = copy.copy(originArray)
for i in range(0, lenN):
    for j in range(i + 1, lenN):
        normalTimes = normalTimes + 1
        if normalSort[i] < normalSort[j]:
            temp = normalSort[i]
            normalSort[i] = normalSort[j]
            normalSort[j] = temp

t1 = timeit.default_timer()

# Quick Sort Method
half = math.floor(lenN / 2)
rightPart = []
for i in range(0, maxN):
    if originArray[i] > originArray[half]:
        quickSort.append(originArray[i])
    else:
        rightPart.append(originArray[i])

splitLen = len(quickSort)
quickSort = quickSort + rightPart
for i in range(0, splitLen):
    for j in range(i + 1, splitLen):
        quickTimes = quickTimes + 1
        if quickSort[i] < quickSort[j]:
            temp = quickSort[i]
            quickSort[i] = quickSort[j]
            quickSort[j] = temp

for i in range(splitLen, lenN):
    for j in range(i + 1, lenN):
        quickTimes = quickTimes + 1
        if quickSort[i] < quickSort[j]:
            temp = quickSort[i]
            quickSort[i] = quickSort[j]
            quickSort[j] = temp
t2 = timeit.default_timer()

# print("Normal Sort Result", json.dumps(normalSort));
# print("Quick Sort  Result", json.dumps(quickSort));
# console.log();

print("NormalSort took {} milliseconds. loop times {}".format((t1 - t0) * 1000, normalTimes))
print("QuickSort  took {} milliseconds. loop times {}".format((t2 - t1) * 1000, quickTimes))

下面分别是数组长度对应10、100、1000...的执行时间:

不继续了,总之快速排序是要快的.

Python性能有点低啊. 哈哈

快速排序算法的深入分析

推荐阅读