// Java
public static void quickSort(int[] array, int begin, int end) {
if (end <= begin) return;
int pivot = partition(array, begin, end);
quickSort(array, begin, pivot - 1);
quickSort(array, pivot + 1, end);
}
static int partition(int[] a, int begin, int end) {
// pivot: 标杆位置，counter: 小于pivot的元素的个数
int pivot = end, counter = begin;
for (int i = begin; i < end; i++) {
if (a[i] < a[pivot]) {
int temp = a[counter]; a[counter] = a[i]; a[i] = temp;
counter++;
}
}
int temp = a[pivot]; a[pivot] = a[counter]; a[counter] = temp;
return counter;
}
//C/C++
int random_partition(vector<int>& nums, int l, intr) {
int random_pivot_index = rand() % (r - l +1) + l; //随机选择pivot
int pivot = nums[random_pivot_index];
swap(nums[random_pivot_index], nums[r]);
int i = l - 1;
for (int j=l; j<r; j++) {
if (nums[j] < pivot) {
i++;
swap(nums[i], nums[j]);
}
}
int pivot_index = i + 1;
swap(nums[pivot_index], nums[r]);
return pivot_index;
}
void random_quicksort(vector<int>& nums, int l, int r) {
if (l < r) {
int pivot_index = random_partition(nums, l, r);
random_quicksort(nums, l, pivot_index-1);
random_quicksort(nums, pivot_index+1, r);
}
}
#Python
def quick_sort(begin, end, nums):
if begin >= end:
return
pivot_index = partition(begin, end, nums)
quick_sort(begin, pivot_index-1, nums)
quick_sort(pivot_index+1, end, nums)
def partition(begin, end, nums):
pivot = nums[begin]
mark = begin
for i in range(begin+1, end+1):
if nums[i] < pivot:
mark +=1
nums[mark], nums[i] = nums[i], nums[mark]
nums[begin], nums[mark] = nums[mark], nums[begin]
return mark
// JavaScript
const quickSort = (nums, left, right) => {
if (nums.length <= 1) return nums
if (left < right) {
index = partition(nums, left, right)
quickSort(nums, left, index-1)
quickSort(nums, index+1, right)
}
}
const partition = (nums, left, right) => {
let pivot = left, index = left + 1
for (let i = index; i <= right; i++) {
if (nums[i] < nums[pivot]) {
[nums[i], nums[index]] = [nums[index], nums[i]]
index++
}
}
[nums[pivot], nums[index-1]] = [nums[index-1], nums[pivot]]
return index -1
}