快排 ​

Array.prototype.quickSort = function () {
	var arr = this.slice(0);

	function swap(i, j) {
		var temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}

	// function partition(left, right) {
	// 	let pivot = left;
	// 	while (left < right) {
	// 		// 从右至左找第一个小于基准的数
	// 		while (left < right && arr[right] >= arr[pivot]) right--;
	// 		// 从左至右找第一个大于基准的数
	// 		while (left < right && arr[left] <= arr[pivot]) left++;
	// 		swap(left, right);
	// 	}

	// 	swap(left, pivot);

	// 	return left;
	// }

	function partition(left, right) {
		let pivot = left;
		while (left < right) {
			// 从左至右找第一个大于基准的数
			while (left < right && arr[left] <= arr[pivot]) left++;
			// 从右至左找第一个小于基准的数
			while (left < right && arr[right] >= arr[pivot]) right--;
			swap(left, right);
		}

		swap(left - 1, pivot);

		return left - 1;
	}

	function sort(left, right) {
		if (left >= right) return;

		let index = partition(left, right);

		console.log({ index });

		sort(left, index - 1);
		sort(index + 1, right);
	}

	sort(0, arr.length - 1);
	return arr;
};

var arr = [2, 1, 2, 3, 5, 1, 6];

console.log(arr.quickSort());