- let arr = randomArr(10000, 100)
- console.time('quickSort')
- quickSort(arr)
- console.timeEnd('quickSort')
- function randomArr( arrLen = 100, maxValue = 1000 ) {
- let arr = []
- for(let i = 0; i <arrLen; i++) {
- arr[i] = Math.floor((maxValue+1)*Math.random())
- }
- return arr
- }
- function quickSort(arr) {
- function _quickSort(arr, start, end) {
- if(start>= end) return
- let key = arr[end]
- let left = start, right = end - 1
- while(left <right) {
- while(arr[left] < key && left < right) left++
- while(arr[right]>= key && left <right) right--
- [arr[left], arr[right]] = [arr[right], arr[left]]
- }
- if(arr[left]>= arr[end]) {
- [arr[left], arr[end]] = [arr[end], arr[left]]
- } else {
- // 如 [2, 1, 3, 4]
- left++
- }
- _quickSort(arr, start, left - 1)
- _quickSort(arr, left + 1, end)
- }
- _quickSort(arr, 0, arr.length - 1)
- return arr
- }
经浏览器测试, 对于长度为 10000 的数组, 排序约需要 2.67ms(100 次平均值), 对于长度为 100000 的数组, 排序约需要 94ms(100 次样本平均值).
来源: http://www.qdfuns.com/article/51116/328d5d58038e04096a9b14f0ffb71222.html