[JavaScript知识库]JavaScript实现快速排序

快速排序：以数组中一个元素为基准，比其小的全部放到它的左边，比它大的全部放在它的右边，然后以左边和右边的两个部分各为一个数组重复上述过程。

时间复杂度：O(nlog(n));

代码实现：

?? ??? ?let arr = [9, 8, 7, 6, 5, 4, 3, 2, 1, 0];

?? ??? ?function quickSort(arr,left,right) {
?? ??? ??? ?let i = left;
?? ??? ??? ?let j = right;
?? ??? ??? ?let key = arr[left];

?? ??? ??? ?while (i < j) {
?? ??? ??? ??? ?for (; i < j && arr[j] >= arr[left]; j--);
?? ??? ??? ??? ?for (; i < j && arr[i] <= arr[left]; i++);

?? ??? ??? ??? ?if (i < j) {
?? ??? ??? ??? ??? ?let item = arr[i];
?? ??? ??? ??? ??? ?arr[i] = arr[j];
?? ??? ??? ??? ??? ?arr[j] = item;
?? ??? ??? ??? ?}
?? ??? ??? ?}
?? ??? ??? ?
?? ??? ??? ?arr[left] = arr[i];
?? ??? ??? ?arr[i] = key;
?? ??? ??? ?if (left < i) quickSort(arr, left, i - 1);
?? ??? ??? ?if (i < right) quickSort(arr, i + 1, right);
?? ??? ?}

?? ??? ?quickSort(arr, 0, arr.length - 1);
?? ??? ?alert(arr);
?? ??? ?console.log(arr);