Skip to content

Instantly share code, notes, and snippets.

@ideawu

ideawu/quicksort

Last active June 29, 2021 08:29
Show Gist options
  • Save ideawu/a114679bb8f0a94452d462ae14b7c977 to your computer and use it in GitHub Desktop.
Save ideawu/a114679bb8f0a94452d462ae14b7c977 to your computer and use it in GitHub Desktop.
Download ZIP
快速排序QuickSort算法JavaScript实现, 包括 Hoare 和 Lomuto 版本的实现，以及网友实现版本的对比
Raw
quicksort
<html>
<body>
<script>
// @author: ideawu
// @link: http://www.ideawu.net/blog/archives/1021.html
var swap_count = 0;
var cmp_count = 0;
// https://gist.github.com/wintercn/c30464ed3732ee839c3eeed316d73253
function wintercn_qsort(arr, start, end){
var midValue = arr[start];
var p1 = start, p2 = end;
while(p1 < p2) {
swap(arr, p1, p1 + 1);
while(compare(arr[p1], midValue) >= 0 && p1 < p2) {
swap(arr, p1, p2--);
}
p1 ++;
}
if(start < p1 - 1)
wintercn_qsort(arr, start, p1 - 1);
if(p1 < end)
wintercn_qsort(arr, p1, end);
}
// http://www.ruanyifeng.com/blog/2011/04/quicksort_in_javascript.html
var ruanyifeng_qsort = function(arr) {
if (arr.length <= 1) { return arr; }
var pivotIndex = Math.floor(arr.length / 2);
var pivot = arr.splice(pivotIndex, 1)[0];
swap_count++;
var left = [];
var right = [];
for (var i = 0; i < arr.length; i++){
if (compare(arr[i], pivot) < 0) {
swap_count++;
left.push(arr[i]);
} else {
swap_count++;
right.push(arr[i]);
}
}
swap_count++;
return ruanyifeng_qsort(left).concat([pivot], ruanyifeng_qsort(right));
}
function compare(a, b){
cmp_count ++;
return a-b;
}
function swap(arr, s, e){
swap_count ++;
var tmp = arr[s];
arr[s] = arr[e];
arr[e] = tmp;
}
function partition_hoare(arr, start, end){
var pivot = arr[start];
var s = start;
var e = end;
while(1){
while(compare(arr[s], pivot) < 0){
s ++;
}
while(compare(arr[e], pivot) > 0){
e --;
}
if(s == e){
return s;
}else if(s > e){
return s-1;
}
swap(arr, s, e);
s++;
e--;
}
}
function qsort_hoare(arr, start, end){
if(start >= end){
return;
}
var p = partition_hoare(arr, start, end);
qsort_hoare(arr, start, p);
qsort_hoare(arr, p+1, end);
}
function partition_lomuto(arr, start, end){
var pivot = arr[end];
var s = start;
for(var g = start; g < end; g++){
if(compare(arr[g], pivot) < 0){
if(s != g){
swap(arr, s, g);
}
s ++;
}
}
if(s == end){
return s-1;
}else{
swap(arr, s, end);
return s;
}
}
function qsort_lomuto(arr, start, end){
if(start >= end){
return;
}
// console.log('in', arr, start, end);
var p = partition_lomuto(arr, start, end);
// console.log(JSON.stringify(arr.slice(start, p+1)), JSON.stringify(arr.slice(p+1, end+1)));
qsort_lomuto(arr, start, p);
qsort_lomuto(arr, p+1, end);
}
function bubble_sort(arr, start, end){
for(var i=start; i<=end; i++){
for(var j=start; j<=end-i-1; j++){
if(compare(arr[j], arr[j+1]) > 0){
swap(arr, j, j+1);
}
}
}
}
function check_result(a){
var pass = true;
var v = a[0];
for(var j=0; j<a.length; j++){
var n = a[j];
if(n < v){
pass = false;
break;
}
v = a[j];
}
return pass;
}
function run_test(func, name){
document.write('<b>run test: ', name, '</b><br/>');
swap_count = 0;
cmp_count = 0;
var nlogn = 0;
var stime = (new Date()).getTime();
for(var i=1; i<=arr.length; i++){
var a = arr.slice(0, i);
var b = func(a, 0, a.length - 1);
if(func == ruanyifeng_qsort){
a = b;
}
if(!check_result(a)){
console.log(i, 'fail');
console.log(a);
}
nlogn += Math.floor(i*Math.log(i));
// console.log('n:', i, 'swaps:', swap_count, 'compares:', cmp_count, 'nlogn:', Math.floor(i*Math.log(i)), JSON.stringify(a));
}
var etime = (new Date()).getTime();
document.write('time: ', etime-stime, ' ms', '<br/>');
document.write('compare: ', cmp_count, ' swap: ', swap_count, ' nlogn: ', nlogn, '<br/>');
document.write('<br/>');
}
var count = 2000;
var arr = [];
for(var i=0; i<count; i++){
arr.push(Math.floor(Math.random() * count));
}
console.log('datasource:', JSON.stringify(arr));
document.write('Running...');
setTimeout(function(){
document.write('<pre>');
run_test(wintercn_qsort, 'wintercn_qsort');
run_test(ruanyifeng_qsort, 'ruanyifeng_qsort');
run_test(qsort_hoare, 'qsort_hoare');
run_test(qsort_lomuto, 'qsort_lomuto');
document.write('</pre>');
// document.write('Running bubble_sort...');
// setTimeout(function(){
// document.write('<pre>');
// run_test(bubble_sort, 'bubble_sort');
// document.write('</pre>');
// }, 0);
}, 0);
</script>
</body>
</html>
@ideawu
Copy link
Author

ideawu commented May 11, 2018

一次典型的结果对比：

run test: wintercn_qsort
time: 256 ms
compare: 30123003 swap: 30123003 nlogn: 14208385

run test: ruanyifeng_qsort
time: 748 ms
compare: 22853877 swap: 25524713 nlogn: 14208385

run test: qsort_hoare
time: 208 ms
compare: 33571306 swap: 4960909 nlogn: 14208385

run test: qsort_lomuto
time: 208 ms
compare: 33104842 swap: 10504357 nlogn: 14208385

@ZTGeng
Copy link

ZTGeng commented May 11, 2018 •
edited
Loading

hoare改进版。compare和swap数量更低。

function qsort_recr(arr, start, end){
    var midValue = arr[start];

    var h = start + 1;
    var t = end;

    while (h <= t) {
        while (h <= t && compare(arr[h], midValue) <= 0) {
            h++;
        }
        if (h > t) {
            break;
        }
        while (t >= h && compare(midValue, arr[t]) <= 0) {
            t--;
        }
        if (t < h) {
            break;
        }
        swap(arr, h, t);
        h++;
        t--;
    }

    swap(arr, start, t);

    if (t - 1 > start) {
        qsort_recr(arr, start, t - 1);
    }
    if (h < end) {
        qsort_recr(arr, h, end);
    } 
}

@wintercn
Copy link

wintercn commented May 11, 2018 •
edited
Loading

讲真，首先我认为在时间复杂度不变的前提下，这种优化非常无聊
其次，你非要比这个憋说我欺负你：

function wintercn_qsort(arr, start, end){
    //start = start | 0;
    //end = end | 0 ;

    var midValue = arr[start];
    var p1 = start + 1, p2 = end;
    while(p1 < p2) {
        while(compare(arr[p1], midValue) >= 0 && p1 < p2) {
            swap(arr, p1, p2--);
        }
        p1 ++;
    }
    var mid = arr[p2] <= midValue ? p2 : p2 -1;
    swap(arr, start, mid);
    if(start < mid - 1) 
        wintercn_qsort(arr, start, mid - 1);
    if(mid < end) 
        wintercn_qsort(arr, mid + 1, end);
}

结果：

time: 223 ms
compare: 22042901 swap: 13008246 nlogn: 14208385

run test: ruanyifeng_qsort
time: 962 ms
compare: 22773479 swap: 25452695 nlogn: 14208385

run test: qsort_hoare
time: 243 ms
compare: 32123353 swap: 4989996 nlogn: 14208385

run test: qsort_lomuto
time: 251 ms
compare: 33021494 swap: 10394010 nlogn: 14208385

@wintercn
Copy link

wintercn commented May 11, 2018 •
edited
Loading

看到我注释掉那两行没？ 这种语言特定的优化我都懒得用。

@ideawu
Copy link
Author

ideawu commented May 11, 2018

@ZTGeng 赞！目前是你的版本最快。compare明显减少，swap减少不明显。

@tidyoux
Copy link

tidyoux commented May 11, 2018

贴个基础版：

function qsort_base(arr, start, end) {
    if (start >= end) {
        return
    }

    var m = start;
    for (var i = start + 1; i <= end; i++) {
        if (compare(arr[i], arr[start]) < 0) {
            m++;
            if (m != i) {
                swap(arr, m, i);
            }
        }
    }
    swap(arr, start, m);

    qsort_base(arr, start, m - 1);
    qsort_base(arr, m + 1, end);
}

@ZTGeng
Copy link

ZTGeng commented May 11, 2018

再来个非递归版，和递归版其实是一样的，compare和swap数量应该与递归版完全相同（因为计算过程完全一致），耗时也许能少一丢丢？

function qsort_loop(arr, start, end) {
    var _start = start;
    var _end = end;
    var stack = [];

    while (1) {
        var midValue = arr[_start];

        var h = _start + 1;
        var t = _end;

        while (h <= t) {
            while (h <= t && compare(arr[h], midValue) <= 0) {
                h++;
            }
            if (h > t) {
                break;
            }
            while (t >= h && compare(midValue, arr[t]) <= 0) {
                t--;
            }
            if (t < h) {
                break;
            }
            swap(arr, h, t);
            h++;
            t--;
        }

        swap(arr, _start, t);

        if (h < _end) {
            stack.push(h);
            stack.push(_end);
        } 
        if (t - 1 > _start) {
            _end = t - 1;
        } else if (stack.length > 0) {
            _end = stack.pop();
            _start = stack.pop();
        } else {
            break;
        }
    }
}

@shiye515
Copy link

shiye515 commented May 12, 2018 •
edited
Loading

耗时排名稳定在第一或者第二的位置，weibo：光挣钱不说话

function shiye515Sort(arr, start, end) {
  let divider = end;
  let dividerValue = arr[divider]
  let blank = divider
  let pickStart = start
  let pickEnd = end - 1
  let isAsc = true
  while (pickStart <= pickEnd) {
    if (isAsc) {
      if (compare(arr[pickStart], dividerValue) > 0) {
        swap(arr, blank, pickStart);
        blank = pickStart
        isAsc = false
      }
      pickStart++
    } else {
      if (compare(arr[pickEnd], dividerValue) < 0) {
        swap(arr, blank, pickEnd);
        blank = pickEnd
        isAsc = true
      }
      pickEnd--
    }
  }
  let mid = isAsc ? (pickEnd + 1) : (pickStart - 1)
  if (start < mid - 1) {
    shiye515Sort(arr, start, mid - 1)
  }
  if (mid + 1 < end) {
    shiye515Sort(arr, mid + 1, end)
  }
}

@yyssjj33
Copy link

为啥没人提到要先shuffle下？quicksort最坏复杂度不是O^2吗？

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment