概述
方法1. 最浅显易懂的
http://www.ruanyifeng.com/blog/2011/04/quicksort_in_javascript.html
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));
};方法2
思路来自中国大学mooc的浙大的数据结构这门课里的。先贴代码：（出了bug。输出的是0,1,2,3,4,5,6,7,9,8）
function ArrayList(){
var array = [];
this.insert = function(item){
array.push(item);
};
this.toString= function(){
return array.join();
};
this.quickSort = function(){
quick(array, 0, array.length - 1);
};
var swapQuickStort = function(array, index1, index2){
var aux = array[index1];
array[index1] = array[index2];
array[index2] = aux;
};
var Median3 = function(array, left, right){
var center = Math.floor((left + right)/2);
if(array[left] > array[right]){
swapQuickStort(array, left, right);
}
if(array[left] > array[center]){
swapQuickStort(array, left, center);
}
if(array[center] > array[right]){
swapQuickStort(array, center, right);
}
/*此时array[left]<=array[center]<=array[right]*/
swapQuickStort(array, center, right-1);//将基准pivot藏到右边
/*只需要考虑array[left+1]...array[right-2]，因为array[left]在上面经过调整一定比基准小，array[right]一定比基准大，array[right-1]即基准，值就是基准对应的值*/
return array[right-1];
// 下面三行也可以表示array[right-1]
// var pivot = array.splice(right-1,1)[0];//这个splice是要删数组的，不能删啊！后面有影响的
// array.splice(right-1, 0, pivot);//所以上一行取完数之后要把数重新添加回去
// return pivot;
};
var quick = function(array, left, right){
var pivot, low, high;
if(left < right){
console.log(array);
pivot = Median3(array, left, right);
low = left; high = right-1;
while(1){/*将序列中的比基准小的移到基准左边，大的移到右边*/
while(array[++low] < pivot);//注意了，这两句while在js是不行的。不要用[++low]用另一种表达代替
while(array[--high] > pivot);
if(low < high) swapQuickStort(array, low, high);
else break;
}
swapQuickStort(array, low, right-1);
quick(array, left, low-1);
quick(array, low+1, right);
}
};
}
console.log('********** Quick Sort **********');
var array = new ArrayList();
array.insert(3);
array.insert(1);
array.insert(4);
array.insert(5);
array.insert(0);
array.insert(2);
array.insert(9);
array.insert(8);
array.insert(7);
array.insert(6);
console.log(array.toString());
array.quickSort();
console.log(array.toString());有些地方不明白？没关系！手动图解~还不懂的话先画图，再不懂的话可以留言~
10.10补充：仍未解决
//记得之前改过代码，也成功过的。但是现在找不到了，现在这个代码还是有些错误。
function swapQuickStort(array, index1, index2){
var aux = array[index1];
array[index1] = array[index2];
array[index2] = aux;
};
function Median3(array, left, right){
var center = Math.floor((left + right)/2);
if(array[left] > array[right]){
swapQuickStort(array, left, right);
}
if(array[left] > array[center]){
swapQuickStort(array, left, center);
}
if(array[center] > array[right]){
swapQuickStort(array, center, right);
}
/*此时array[left]<=array[center]<=array[right]*/
swapQuickStort(array, center, right-1);//将基准pivot藏到右边
/*只需要考虑array[left+1]...array[right-2]，因为array[left]在上面经过调整一定比基准小，array[right]一定比基准大，array[right-1]即基准，值就是基准对应的值*/
return array[right-1];
};
function quick(array, left, right){
var pivot, low, high;
console.log('left:'+left+' '+'right:'+right);
console.log(`array[${left}]`+':'+array[left]+' '+`array[${right}]`+':'+array[right]);
if(left < right){
pivot = Median3(array, left, right);
low = left+1; high = right-2;
console.log('pivot:'+pivot+' '+'low:'+low+' '+'high:'+high);
while(1){/*将序列中的比基准小的移到基准左边，大的移到右边*/
while(array[low] < pivot)low++;
while(array[high] > pivot)high--;
if(low < high) {
console.log('swap ' + array[low] + ' with ' + array[high]);
swapQuickStort(array, low, high);
}
else break;
}
//swapQuickStort(array, low, right-1);//①
if(low<=right-1){
swapQuickStort(array, low, right-1);
}
quick(array, left, low-1);
quick(array, low+1, right);
}
};
console.log('********** Quick Sort **********');
var array = [3,1,4,5,0,2,9,8,7,6];
console.log(array.toString());
quick(array, 0, array.length - 1);
console.log(array.toString());//输出0,1,2,3,4,5,6,7,9,8 <=怎么就9,8了...利用console.log查了一下快排顺序，原因出在while(1）后面的“swapQuickStort(array, low, right-1);”（即①
此时的low=left+1=8+19，right=9，right-1=8，8,9位置的值要对调。因此我直接在进行对调的地方前加一个if判断：
暂时解决了问题，不知道还会不会出新问题
方法3
源码来自学习Javascript数据结构与算法。找工作笔试面试啥的背这个吧
function ArrayList(){
var array = [];
this.insert = function(item){
array.push(item);
};
this.toString= function(){
return array.join();
};
this.quickSort = function(){
quick(array, 0, array.length - 1);
};
var swapQuickStort = function(array, index1, index2){
var aux = array[index1];
array[index1] = array[index2];
array[index2] = aux;
};
var partition = function(array, left, right) {
var pivot = array[Math.floor((right + left) / 2)],
i = left,
j = right;
// console.log('pivot is ' + pivot + '; left is ' + left + '; right is ' + right);
while (i <= j) {
while (array[i] < pivot) {
i++;
// console.log('i = ' + i);
}
while (array[j] > pivot) {
j--;
// console.log('j = ' + j);
}
if (i <= j) {
// console.log('swap ' + array[i] + ' with ' + array[j]);
swapQuickStort(array, i, j);
i++;
j--;
}
}
return i;//这是返回数组下标。注意i与方法二的low的意义不太一样。方法二的low就代表了正确的点
//这里正确的点是在i-1，所以quick里面才有"index-1"与"index"本身
};
var quick = function(array, left, right){
var 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);//将index塞进去，说明index不代表一趟快排之后正确的位置
//因为如果代表的话，它是不需要参与之后的排序的
}
}
return array;
};
}
console.log('********** Quick Sort **********');
var array = new ArrayList();
array.insert(3);
array.insert(5);
array.insert(1);
array.insert(6);
array.insert(4);
array.insert(7);
array.insert(2);
console.log(array.toString());
array.quickSort();
console.log(array.toString());整理之后可以背的：（改了一点点，将index变成了一趟快排之后的正确位置）
function swapQuickStort(array, index1, index2){
[array[index1],array[index2]] = [array[index2],array[index1]];
};
function partition(array, left, right) {
var pivot = array[Math.floor((right + left) / 2)],
i = left,
j = right;
while (1) {
while (array[i] < pivot) i++;
while (array[j] > pivot) j--;
if (i < j) {
swapQuickStort(array, i, j);
}else{
break;
}
}
return i;
};
function quick(array, left, right){
var index;
if (array.length > 1) {
index = partition(array, left, right);
if (left < index) {
quick(array, left, index-1);
}
if (index < right) {
quick(array, index+1, right);
}
}
return array;
};
console.log('********** Quick Sort **********');
var array = [3,5,1,6,4,7,2];
console.log(array.toString());
quick(array, 0, array.length - 1);
console.log(array.toString());
最后
以上就是酷炫服饰为你收集整理的javascript快排三种解法的全部内容，希望文章能够帮你解决javascript快排三种解法所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复