JavaScript (Implement Quicksort with first element as pivot)以第一个元素为枢轴元素实现快速排序-编程阁

如果您喜欢此文章，请收藏、点赞、评论，谢谢，祝您快乐每一天。

快速排序是一种分治算法。它选择一个元素作为枢轴，并围绕该枢轴对给定数组进行分区。快速排序有很多不同的版本，它们选择枢轴的方式各不相同。

·始终选择第一个元素作为枢轴。
·始终选择最后一个元素作为枢轴点。
·随机选择一个元素作为枢轴。
·选择中位数作为枢轴点。

注意：这里我们将通过选择第一个元素作为枢轴来实现快速排序。

选择第一个元素作为枢轴进行快速排序：

快速排序的关键功能是分区。分区的目标是在数组已排序的情况下，将枢轴元素放置在正确的位置，并将较小的（或相等的）元素放在其左侧，较大的元素放在其右侧，并且所有这些都要在线性时间内完成。

分区算法：

分区的方法有很多种，以下伪代码采用了 CLRS 书中给出的方法。

我们从最左边的元素开始，并将较小（或相等）元素的索引记为i。
在遍历过程中，如果我们找到一个更小（或相等）的元素，我们将当前元素与 arr[i] 交换。
否则，我们将忽略当前元素。

递归快速排序函数的伪代码：

// low –> Starting index, high –> Ending index

quickSort(arr[], low, high) {
if (low < high) {

// pi is partitioning index, arr[pi] is now at right place
pi = partition(arr, low, high);
quickSort(arr, low, pi – 1); // Before pi
quickSort(arr, pi + 1, high); // After pi
}
}

partition() 函数的伪代码

/* 此函数以数组首元素为基准元素，将基准元素放置在排序数组中的正确位置，并将所有小于或等于基准元素的元素放置在基准元素的左侧，所有大于基准元素的元素放置在基准元素的右侧。*/

partition(arr[], low, high) {
// 第一个元素作为枢轴
pivot = arr[low]
k = high
for (i = high; i > low; i--) {
if (arr[i] > pivot){
swap arr[i] and arr[k];
k--;
}
}
swap arr[k] and arr[low]
return k;
}

分区的图示 partition() ：

Consider: arr[] = { 7, 6, 10, 5, 9, 2, 1, 15, 7 }

第一次分区： low = 0，high = 8，pivot = arr[low] = 7
初始化最右边元素的索引 k = high = 8。

·从 i = 高处到低处横移：
如果 arr[i] 大于 pivot：
交换 arr[i] 和 arr[k]。
减去 k；

·最后交换 arr[low] 和 arr[k]。

现在枢轴的正确位置是索引5。

第二次分区： low = 0，high = 4，pivot = arr[low] = 2
类似地初始化 k = high = 4；

2 的正确位置变为索引 1。左侧部分只有一个元素，右侧部分有 {6, 5, 7}。

另一方面，划分发生在段 [6, 8] 上，即数组 {10, 9, 15}。
这里 low = 6，high = 8，pivot = 10，k = 8。

10 的正确位置变为索引 7，左右两部分都只有一个元素。

第三划分：这里划分线段 {6, 5, 7}。低位 = 2，高位 = 4，枢轴 = 6，k = 4。
如果应用相同的过程，我们将得到 6 的正确位置，即索引 3，并且左右两部分都只有一个元素。

这样一来，整个数组就排序完成了。请查看下图了解递归树。

请按照以下步骤实施该方法。

使用递归函数（例如快速排序）来初始化该函数。
调用分区函数对数组进行分区，并在分区函数内部执行以下操作：
- 以第一个元素为枢轴并初始化迭代器k = high。
- 使用 for 循环从i = high 到 low+1 迭代：
  - 如果 arr[i] 大于 pivot，则交换arr[i]和arr[k]并将 k 减 1。
- 迭代后，将枢轴与arr[k]交换。
- 返回 k-1 作为分割点。
现在递归地对分区索引的左半部分和右半部分调用快速排序。

上述方法的代码示例：

function partition(function partition(array, low, high) {
// First Element as pivot
let pivot = array[low];

// st points to the starting of array
let start = low + 1;

// end points to the ending of the array
let end = high;

while (true) {
// It indicates we have already moved all the elements to their correct side of the pivot
while (start <= end && array[end] >= pivot) {
end--;
}

// Opposite process
while (start <= end && array[start] <= pivot) {
start++;
}

// Case in which we will exit the loop
if (start <= end) {
[array[start], array[end]] = [array[end], array[start]];
// The loop continues
} else {
// We exit out of the loop
break;
}
}

[array[low], array[end]] = [array[end], array[low]];
// As we got pivot element index is end
// now pivot element is at its sorted position
// return pivot element index (end)
return end;
}

function quick_sort(array, start, end) {
// If low is lesser than high
if (start < end) {
// idx is index of pivot element which is at its
// sorted position
let idx = partition(array, start, end);

// Separately sort elements before
// partition and after partition
quick_sort(array, start, idx - 1);
quick_sort(array, idx + 1, end);
}
}

function print_arr(arr) {
console.log(arr.join(" "));
}

// Driver Code
let arr1 = [7, 6, 10, 5, 9, 2, 1, 15, 7];
quick_sort(arr1, 0, arr1.length - 1);
console.log("Sorted array: ");
print_arr(arr1);

//contributed by Aditya Sharma

输出