快速排序时最常用的排序算法，和归并排序一样也是采用分治方法，但没有把数组分割开，也是将原数组分成较小的数组。
1、从数组的中间选择一项作为主元。
2、创建两个指针，left 指向数组的第一个元素，right指向数组的最后一个元素，移动left指针直到找到第一个比主元大的数，接着再移动right指针，找到比主元小的数，交换他们，重复这个过程，直到左右指针相遇。这个过程执行完主元左边都是比主元小的数，主元的右边都是比主元大的数。划分
3、接着对划分后的两个小数组重复之前的操作，直至数组已经全部排列
快速排序的代码实现：
function QuickSort() {
const array = [];
this.insert = function(item) {
array.push(item);
}
this.toString = function() {
return array.join();
}
this.quickSort = function() {
quick(array, 0, array.length-1);
}
const quick = function(array, left, right) {
let index = 0;
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);
}
}
}
const partition = function(array, left, right) {
var pivot = array[Math.floor((left + right) / 2)],
i = left,
j = right;
while(i <= j) {
while(array[i] < pivot) {
i++
}
while(array[j] > pivot) {
j--;
}
if(i <= j) {
swapQuickSort(array, i, j);
i++;
j--;
}
}
return i;
}
const swapQuickSort = function(array, index1, index2) {
var aux = array[index1];
array[index1] = array[index2];
array[index2] = aux;
}
}
var arr = new QuickSort();
arr.insert(3);
arr.insert(13);
arr.insert(32);
arr.insert(23);
arr.insert(11);
arr.insert(8);
arr.insert(33);
arr.insert(28);
console.log(arr.toString()); // 3,13,32,23,11,8,33,28
arr.quickSort();
console.log(arr.toString());
网友评论