Last active
January 15, 2020 20:17
-
-
Save xiaomuzhu/9091f1634c90339cdf66c3b9a9f4f81f to your computer and use it in GitHub Desktop.
快速排序与冒泡排序在数据规模不同情况下的执行时间差异
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| function bubbleSort(arr) { | |
| for (var j = 0; j < arr.length - 1; j++) { | |
| // 这里要根据外层for循环的 j，逐渐减少内层 for循环的次数 | |
| for (var i = 0; i < arr.length - 1 - j; i++) { | |
| if (arr[i] > arr[i + 1]) { | |
| var temp = arr[i] | |
| arr[i] = arr[i + 1] | |
| arr[i + 1] = temp | |
| } | |
| } | |
| } | |
| return arr | |
| } | |
| const quickSort = (function() { | |
| // 默认状态下的比较函数 | |
| function compare(a, b) { | |
| if (a === b) { | |
| return 0 | |
| } | |
| return a < b ? -1 : 1 | |
| } | |
| function swap(array, a, b) { | |
| ;[array[a], array[b]] = [array[b], array[a]] | |
| } | |
| // 分治函数 | |
| function partition(array, left, right) { | |
| // 用index取中间值而非splice | |
| const pivot = array[Math.floor((right + left) / 2)] | |
| let i = left | |
| let j = right | |
| while (i <= j) { | |
| while (compare(array[i], pivot) === -1) { | |
| i++ | |
| } | |
| while (compare(array[j], pivot) === 1) { | |
| j-- | |
| } | |
| if (i <= j) { | |
| swap(array, i, j) | |
| i++ | |
| j-- | |
| } | |
| } | |
| return i | |
| } | |
| // 快排函数 | |
| function quick(array, left, right) { | |
| let index | |
| if (array.length > 1) { | |
| index = partition(array, left, right) | |
| if (left < index - 1) { | |
| quick(array, left, index - 1) | |
| } | |
| if (index < right) { | |
| quick(array, index, right) | |
| } | |
| } | |
| return array | |
| } | |
| return function quickSort(array) { | |
| return quick(array, 0, array.length - 1) | |
| } | |
| })() | |
| function random(min, max) { | |
| return Math.round(Math.random() * (max - min)) + min | |
| } | |
| function faker(count) { | |
| const arr = [] | |
| for (let i = 0; i < count; i++) { | |
| const num = random(0, count) | |
| arr.push(num) | |
| } | |
| return arr | |
| } | |
| const arr1 = faker(50) | |
| const arr2 = faker(50000) | |
| console.time("bubbleSort time") | |
| bubbleSort(arr1) | |
| console.timeEnd("bubbleSort time") | |
| console.time("quickSort time") | |
| quickSort(arr1) | |
| console.timeEnd("quickSort time") |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment