快速排序
2018-11-27 本文已影响0人
Jason_Shu
-
原理
(1)从一个数列中选出一个「基准」
(2)然后遍历所有元素,把所有比这个「基准」小的元素放在「基准」的左边,所有比「基准」大的元素放在「基准」的右边,如果与「基准」相等,随意放哪边。一轮分区下来,这样会是该「基础」处于整个数列的中间位置。
(3)递归地,把小于基准值元素的子数列和大于基准值元素的子数列排序。
(4)递归到最底部时,数列的长度只有0或者1,即本身就是排好序的。这个算法一定会结束,因为在每次的迭代中,它至少会把一个元素摆到它最后的位置去。 -
代码
function quickSort(arr) {
function __quickSort__(arr, start, end) {
if(start >= end) return;
let key = arr[end];
let left = start;
let 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] >= key) {
[arr[left], arr[end]] = [arr[end], arr[left]];
} else {
left++;
}
__quickSort__(arr, start, left - 1);
__quickSort__(arr, left + 1, end);
}
__quickSort__(arr, 0, arr.length - 1 );
return arr;
}
- 本代码,以最后一个数为「基准」(key值)
- 从数列首位开始遍历,如果遇到比key小的数,则继续向后扫描,直到遇到比key值大的元素,然后从key值前一个元素开始从后向前扫描,直到遇到比key值小的元素
- 此时交换位置停止的两个元素
- 继续上面的逻辑
- 直到left和right相遇
- 如果相遇时的值大于或者等于key值,则把该相遇的值与key值互换位置
- 如果相遇时的值小于key值,则把left后移一位。