/// 快速排序法(遞增)，使用遞迴。此為用來遞迴呼叫的函數。
pub fn quick_sort_recursively(array: &mut [i32], start: usize, end: usize) {
if end <= start {
return;
}
let pivot = array[start];
let mut l = start + 1;
let mut r = end;
loop {
while r > start && array[r] >= pivot {
r -= 1;
}
while l <= r && array[l] <= pivot {
l += 1;
}
if l < r {
array.swap(l, r);
} else {
if r > start {
array.swap(start, r);
}
break;
}
}
if r > start {
quick_sort_recursively(array, start, r - 1);
}
if r < end {
quick_sort_recursively(array, r + 1, end);
}
}
/// 快速排序法(遞增)，使用遞迴。
pub fn quick_sort(array: &mut [i32]) {
quick_sort_recursively(array, 0, array.len() - 1)
}
/// 快速排序法(遞減)，使用遞迴。此為用來遞迴呼叫的函數。
pub fn quick_sort_desc_recursively(array: &mut [i32], start: usize, end: usize) {
if end <= start {
return;
}
let pivot = array[end];
let mut l = start;
let mut r = end - 1;
loop {
while l < end && array[l] >= pivot {
l += 1;
}
while r >= l && array[r] <= pivot {
if r == 0 {
break;
}
r -= 1;
}
if l < r {
array.swap(l, r);
} else {
if l < end {
array.swap(l, end);
}
break;
}
}
if l > start {
quick_sort_desc_recursively(array, start, l - 1);
}
if l < end {
quick_sort_desc_recursively(array, l + 1, end);
}
}
/// 快速排序法(遞減)，使用遞迴。
pub fn quick_sort_desc(array: &mut [i32]) {
quick_sort_desc_recursively(array, 0, array.len() - 1)
}
/**
* 快速排序法(遞增)，使用遞迴。此為用來遞迴呼叫的函數。
*/
public static void quickSortRecursively(final int[] array, final int start, final int end) {
if (end <= start) {
return;
}
final int pivot = array[start];
int l = start + 1;
int r = end;
while (true) {
while (r > start && array[r] >= pivot) {
--r;
}
while (l <= r && array[l] <= pivot) {
++l;
}
if (l < r) {
int temp = array[l];
array[l] = array[r];
array[r] = temp;
} else {
if (r > start) {
int temp = array[start];
array[start] = array[r];
array[r] = temp;
}
break;
}
}
if (r > start) {
quickSortRecursively(array, start, r - 1);
}
if (r < end) {
quickSortRecursively(array, r + 1, end);
}
}
/**
* 快速排序法(遞增)，使用遞迴。
*/
public static void quickSort(final int[] array) {
quickSortRecursively(array, 0, array.length - 1);
}
/**
* 快速排序法(遞減)，使用遞迴。此為用來遞迴呼叫的函數。
*/
public static void quickSortDescRecursively(final int[] array, final int start, final int end) {
if (end <= start) {
return;
}
final int pivot = array[end];
int l = start;
int r = end - 1;
while (true) {
while (l < end && array[l] >= pivot) {
++l;
}
while (r >= l && array[r] <= pivot) {
--r;
}
if (l < r) {
int temp = array[l];
array[l] = array[r];
array[r] = temp;
} else {
if (l < end) {
int temp = array[l];
array[l] = array[end];
array[end] = temp;
}
break;
}
}
if (l > start) {
quickSortDescRecursively(array, start, l - 1);
}
if (l < end) {
quickSortDescRecursively(array, l + 1, end);
}
}
/**
* 快速排序法(遞減)，使用遞迴。
*/
public static void quickSortDesc(final int[] array) {
quickSortDescRecursively(array, 0, array.length - 1);
}
/**
* 快速排序法(遞增)，使用遞迴。此為用來遞迴呼叫的函數。
*/
function quickSortRecursively(array: number[], start: number, end: number) {
if (end <= start) {
return;
}
const pivot = array[start];
let l = start + 1;
let r = end;
for (; ;) {
while (r > start && array[r] >= pivot) {
r -= 1;
}
while (l <= r && array[l] <= pivot) {
l += 1;
}
if (l < r) {
const temp = array[l];
array[l] = array[r];
array[r] = temp;
} else {
if (r > start) {
const temp = array[start];
array[start] = array[r];
array[r] = temp;
}
break;
}
}
if (r > start) {
quickSortRecursively(array, start, r - 1);
}
if (r < end) {
quickSortRecursively(array, r + 1, end);
}
}
/**
* 快速排序法(遞增)，使用遞迴。
*/
function quickSort(array: number[]) {
quickSortRecursively(array, 0, array.length - 1);
}
/**
* 快速排序法(遞減)，使用遞迴。此為用來遞迴呼叫的函數。
*/
function quickSortDescRecursively(array: number[], start: number, end: number) {
if (end <= start) {
return;
}
const pivot = array[end];
let l = start;
let r = end - 1;
for (; ;) {
while (l < end && array[l] >= pivot) {
l += 1;
}
while (r >= l && array[r] <= pivot) {
r -= 1;
}
if (l < r) {
const temp = array[l];
array[l] = array[r];
array[r] = temp;
} else {
if (l < end) {
const temp = array[l];
array[l] = array[end];
array[end] = temp;
}
break;
}
}
if (l > start) {
quickSortDescRecursively(array, start, l - 1);
}
if (l < end) {
quickSortDescRecursively(array, l + 1, end);
}
}
/**
* 快速排序法(遞減)，使用遞迴。
*/
function quickSortDesc(array: number[]) {
quickSortDescRecursively(array, 0, array.length - 1);
}
// 快速排序法(遞增)，使用遞迴。此為用來遞迴呼叫的函數。
func QuickSortRecursively(array []int, start int, end int) {
if end <= start {
return
}
pivot := array[start]
l := start + 1
r := end
for {
for r > start && array[r] >= pivot {
r -= 1
}
for l <= r && array[l] <= pivot {
l += 1
}
if l < r {
array[l], array[r] = array[r], array[l]
} else {
if r > start {
array[start], array[r] = array[r], array[start]
}
break
}
}
if r > start {
QuickSortRecursively(array, start, r-1)
}
if r < end {
QuickSortRecursively(array, r+1, end)
}
}
// 快速排序法(遞增)，使用遞迴。
func QuickSort(array []int) {
QuickSortRecursively(array, 0, len(array)-1)
}
// 快速排序法(遞減)，使用遞迴。此為用來遞迴呼叫的函數。
func QuickSortDescRecursively(array []int, start int, end int) {
if end <= start {
return
}
pivot := array[end]
l := start
r := end - 1
for {
for l < end && array[l] >= pivot {
l += 1
}
for r >= l && array[r] <= pivot {
r -= 1
}
if l < r {
array[l], array[r] = array[r], array[l]
} else {
if l < end {
array[l], array[end] = array[end], array[l]
}
break
}
}
if l > start {
QuickSortDescRecursively(array, start, l-1)
}
if l < end {
QuickSortDescRecursively(array, l+1, end)
}
}
// 快速排序法(遞減)，使用遞迴。
func QuickSortDesc(array []int) {
QuickSortDescRecursively(array, 0, len(array)-1)
}
/// 快速排序法(遞增)，使用迴圈來迭代。
pub fn quick_sort(array: &mut [i32]) {
let mut stack = Vec::new();
stack.push(0);
stack.push(array.len() - 1);
while let Some(end) = stack.pop() {
let start = stack.pop().unwrap();
if end > start {
let pivot = array[start];
let mut l = start + 1;
let mut r = end;
loop {
while r > start && array[r] >= pivot {
r -= 1;
}
while l <= r && array[l] <= pivot {
l += 1;
}
if l < r {
array.swap(l, r);
} else {
if r > start {
array.swap(start, r);
}
break;
}
}
if r > start {
stack.push(start);
stack.push(r - 1);
}
if r < end {
stack.push(r + 1);
stack.push(end);
}
}
}
}
/// 快速排序法(遞減)，使用迴圈來迭代。
pub fn quick_sort_desc(array: &mut [i32]) {
let mut stack = Vec::new();
stack.push(0);
stack.push(array.len() - 1);
while let Some(end) = stack.pop() {
let start = stack.pop().unwrap();
if end > start {
let pivot = array[end];
let mut l = start;
let mut r = end - 1;
loop {
while l < end && array[l] >= pivot {
l += 1;
}
while r >= l && array[r] <= pivot {
if r == 0 {
break;
}
r -= 1;
}
if l < r {
array.swap(l, r);
} else {
if l < end {
array.swap(l, end);
}
break;
}
}
if l > start {
stack.push(start);
stack.push(l - 1);
}
if l < end {
stack.push(r + 1);
stack.push(end);
}
}
}
}
/**
* 快速排序法(遞增)，使用迴圈來迭代。
*/
public static void quickSort(final int[] array) {
final Stack<Integer> stack = new Stack<>();
stack.push(0);
stack.push(array.length - 1);
while (!stack.isEmpty()) {
final int end = stack.pop();
final int start = stack.pop();
if (end > start) {
final int pivot = array[start];
int l = start + 1;
int r = end;
while (true) {
while (r > start && array[r] >= pivot) {
--r;
}
while (l <= r && array[l] <= pivot) {
++l;
}
if (l < r) {
int temp = array[l];
array[l] = array[r];
array[r] = temp;
} else {
if (r > start) {
int temp = array[start];
array[start] = array[r];
array[r] = temp;
}
break;
}
}
if (r > start) {
stack.push(start);
stack.push(r - 1);
}
if (r < end) {
stack.push(r + 1);
stack.push(end);
}
}
}
}
/**
* 快速排序法(遞減)，使用迴圈來迭代。
*/
public static void quickSortDesc(final int[] array) {
final Stack<Integer> stack = new Stack<>();
stack.push(0);
stack.push(array.length - 1);
while (!stack.isEmpty()) {
final int end = stack.pop();
final int start = stack.pop();
if (end > start) {
final int pivot = array[end];
int l = start;
int r = end - 1;
while (true) {
while (l < end && array[l] >= pivot) {
++l;
}
while (r >= l && array[r] <= pivot) {
--r;
}
if (l < r) {
int temp = array[l];
array[l] = array[r];
array[r] = temp;
} else {
if (l < end) {
int temp = array[l];
array[l] = array[end];
array[end] = temp;
}
break;
}
}
if (l > start) {
stack.push(start);
stack.push(l - 1);
}
if (l < end) {
stack.push(l + 1);
stack.push(end);
}
}
}
}
/**
* 快速排序法(遞增)，使用迴圈來迭代。
*/
function quickSort(array: number[]) {
const stack: number[] = [];
stack.push(0);
stack.push(array.length - 1);
while (stack.length > 0) {
// eslint-disable-next-line @typescript-eslint/no-non-null-assertion
const end = stack.pop()!;
// eslint-disable-next-line @typescript-eslint/no-non-null-assertion
const start = stack.pop()!;
if (end > start) {
const pivot = array[start];
let l = start + 1;
let r = end;
for (; ;) {
while (r > start && array[r] >= pivot) {
r -= 1;
}
while (l <= r && array[l] <= pivot) {
l += 1;
}
if (l < r) {
const temp = array[l];
array[l] = array[r];
array[r] = temp;
} else {
if (r > start) {
const temp = array[start];
array[start] = array[r];
array[r] = temp;
}
break;
}
}
if (r > start) {
stack.push(start);
stack.push(r - 1);
}
if (r < end) {
stack.push(r + 1);
stack.push(end);
}
}
}
}
/**
* 快速排序法(遞減)，使用迴圈來迭代。
*/
function quickSortDesc(array: number[]) {
const stack: number[] = [];
stack.push(0);
stack.push(array.length - 1);
while (stack.length > 0) {
// eslint-disable-next-line @typescript-eslint/no-non-null-assertion
const end = stack.pop()!;
// eslint-disable-next-line @typescript-eslint/no-non-null-assertion
const start = stack.pop()!;
if (end > start) {
const pivot = array[end];
let l = start;
let r = end - 1;
for (; ;) {
while (l < end && array[l] >= pivot) {
l += 1;
}
while (r >= l && array[r] <= pivot) {
r -= 1;
}
if (l < r) {
const temp = array[l];
array[l] = array[r];
array[r] = temp;
} else {
if (l < end) {
const temp = array[l];
array[l] = array[end];
array[end] = temp;
}
break;
}
}
if (l > start) {
stack.push(start);
stack.push(l - 1);
}
if (l < end) {
stack.push(l + 1);
stack.push(end);
}
}
}
}
type stack []int
func (s stack) Push(v int) stack {
return append(s, v)
}
func (s stack) Pop() (stack, int) {
l := len(s)
return s[:l-1], s[l-1]
}
// 快速排序法(遞增)，使用迴圈來迭代。
func QuickSort(array []int) {
stack := make(stack, 0)
stack = stack.Push(0)
stack = stack.Push(len(array) - 1)
for len(stack) > 0 {
var start, end int
stack, end = stack.Pop()
stack, start = stack.Pop()
if end > start {
pivot := array[start]
l := start + 1
r := end
for {
for r > start && array[r] >= pivot {
r -= 1
}
for l <= r && array[l] <= pivot {
l += 1
}
if l < r {
array[l], array[r] = array[r], array[l]
} else {
if r > start {
array[start], array[r] = array[r], array[start]
}
break
}
}
if r > start {
stack = stack.Push(start)
stack = stack.Push(r - 1)
}
if r < end {
stack = stack.Push(r + 1)
stack = stack.Push(end)
}
}
}
}
// 快速排序法(遞減)，使用迴圈來迭代。
func QuickSortDesc(array []int) {
stack := make(stack, 0)
stack = stack.Push(0)
stack = stack.Push(len(array) - 1)
for len(stack) > 0 {
var start, end int
stack, end = stack.Pop()
stack, start = stack.Pop()
if end > start {
pivot := array[end]
l := start
r := end - 1
for {
for l < end && array[l] >= pivot {
l += 1
}
for r >= l && array[r] <= pivot {
r -= 1
}
if l < r {
array[l], array[r] = array[r], array[l]
} else {
if l < end {
array[l], array[end] = array[end], array[l]
}
break
}
}
if l > start {
stack = stack.Push(start)
stack = stack.Push(l - 1)
}
if l < end {
stack = stack.Push(l + 1)
stack = stack.Push(end)
}
}
}
}
為了避免遭遇固定的最差案例，支點的選擇不應該每次都用最左邊的索引位置，隨機選擇會比較保險。
/// 快速排序法(遞增)，使用迴圈來迭代，並使用隨機支點。
pub fn quick_sort_random_pivot(array: &mut [i32]) {
let mut stack = Vec::new();
stack.push(0);
stack.push(array.len() - 1);
let mut rng = rand::thread_rng();
while let Some(end) = stack.pop() {
let start = stack.pop().unwrap();
if end > start {
array.swap(start, rng.gen_range(start..=end));
let pivot = array[start];
let mut l = start + 1;
let mut r = end;
loop {
while r > start && array[r] >= pivot {
r -= 1;
}
while l <= r && array[l] <= pivot {
l += 1;
}
if l < r {
array.swap(l, r);
} else {
if r > start {
array.swap(start, r);
}
break;
}
}
if r > start {
stack.push(start);
stack.push(r - 1);
}
if r < end {
stack.push(r + 1);
stack.push(end);
}
}
}
}
/// 快速排序法(遞減)，使用迴圈來迭代，並使用隨機支點。
pub fn quick_sort_random_pivot_desc(array: &mut [i32]) {
let mut stack = Vec::new();
stack.push(0);
stack.push(array.len() - 1);
let mut rng = rand::thread_rng();
while let Some(end) = stack.pop() {
let start = stack.pop().unwrap();
if end > start {
array.swap(end, rng.gen_range(start..=end));
let pivot = array[end];
let mut l = start;
let mut r = end - 1;
loop {
while l < end && array[l] >= pivot {
l += 1;
}
while r >= l && array[r] <= pivot {
if r == 0 {
break;
}
r -= 1;
}
if l < r {
array.swap(l, r);
} else {
if l < end {
array.swap(l, end);
}
break;
}
}
if l > start {
stack.push(start);
stack.push(l - 1);
}
if l < end {
stack.push(r + 1);
stack.push(end);
}
}
}
}
使用了rand套件來完成某範圍內的整數隨機抽取功能。
/**
* 快速排序法(遞增)，使用迴圈來迭代，並使用隨機支點。
*/
public static void quickSortRandomPivot(final int[] array) {
final Stack<Integer> stack = new Stack<>();
stack.push(0);
stack.push(array.length - 1);
while (!stack.isEmpty()) {
final int end = stack.pop();
final int start = stack.pop();
if (end > start) {
final int p = (int) (Math.random() * (end - start + 1) + start);
final int pivot = array[p];
array[p] = array[start];
array[start] = pivot;
int l = start + 1;
int r = end;
while (true) {
while (r > start && array[r] >= pivot) {
--r;
}
while (l <= r && array[l] <= pivot) {
--l;
}
if (l < r) {
int temp = array[l];
array[l] = array[r];
array[r] = temp;
} else {
if (r > start) {
int temp = array[start];
array[start] = array[r];
array[r] = temp;
}
break;
}
}
if (r > start) {
stack.push(start);
stack.push(r - 1);
}
if (r < end) {
stack.push(r + 1);
stack.push(end);
}
}
}
}
/**
* 快速排序法(遞減)，使用迴圈來迭代，並使用隨機支點。
*/
public static void quickSortRandomPivotDesc(final int[] array) {
final Stack<Integer> stack = new Stack<>();
stack.push(0);
stack.push(array.length - 1);
while (!stack.isEmpty()) {
final int end = stack.pop();
final int start = stack.pop();
if (end > start) {
final int p = (int) (Math.random() * (end - start + 1) + start);
final int pivot = array[p];
array[p] = array[end];
array[end] = pivot;
int l = start;
int r = end - 1;
while (true) {
while (l < end && array[l] >= pivot) {
++l;
}
while (r >= l && array[r] <= pivot) {
--r;
}
if (l < r) {
int temp = array[l];
array[l] = array[r];
array[r] = temp;
} else {
if (l < end) {
int temp = array[l];
array[l] = array[end];
array[end] = temp;
}
break;
}
}
if (l > start) {
stack.push(start);
stack.push(l - 1);
}
if (l < end) {
stack.push(l + 1);
stack.push(end);
}
}
}
}
/**
* 快速排序法(遞增)，使用迴圈來迭代，並使用隨機支點。
*/
function quickSortRandomPivot(array: number[]) {
const stack: number[] = [];
stack.push(0);
stack.push(array.length - 1);
while (stack.length > 0) {
// eslint-disable-next-line @typescript-eslint/no-non-null-assertion
const end = stack.pop()!;
// eslint-disable-next-line @typescript-eslint/no-non-null-assertion
const start = stack.pop()!;
if (end > start) {
const p = Math.floor((Math.random() * (end - start + 1)) + start);
const pivot = array[p];
array[p] = array[start];
array[start] = pivot;
let l = start + 1;
let r = end;
for (; ;) {
while (r > start && array[r] >= pivot) {
r -= 1;
}
while (l <= r && array[l] <= pivot) {
l += 1;
}
if (l < r) {
const temp = array[l];
array[l] = array[r];
array[r] = temp;
} else {
if (r > start) {
const temp = array[start];
array[start] = array[r];
array[r] = temp;
}
break;
}
}
if (r > start) {
stack.push(start);
stack.push(r - 1);
}
if (r < end) {
stack.push(r + 1);
stack.push(end);
}
}
}
}
/**
* 快速排序法(遞減)，使用迴圈來迭代，並使用隨機支點。
*/
function quickSortRandomPivotDesc(array: number[]) {
const stack: number[] = [];
stack.push(0);
stack.push(array.length - 1);
while (stack.length > 0) {
// eslint-disable-next-line @typescript-eslint/no-non-null-assertion
const end = stack.pop()!;
// eslint-disable-next-line @typescript-eslint/no-non-null-assertion
const start = stack.pop()!;
if (end > start) {
const p = Math.floor((Math.random() * (end - start + 1)) + start);
const pivot = array[p];
array[p] = array[end];
array[end] = pivot;
let l = start;
let r = end - 1;
for (; ;) {
while (l < end && array[l] >= pivot) {
l += 1;
}
while (r >= l && array[r] <= pivot) {
r -= 1;
}
if (l < r) {
const temp = array[l];
array[l] = array[r];
array[r] = temp;
} else {
if (l < end) {
const temp = array[l];
array[l] = array[end];
array[end] = temp;
}
break;
}
}
if (l > start) {
stack.push(start);
stack.push(l - 1);
}
if (l < end) {
stack.push(l + 1);
stack.push(end);
}
}
}
}
type stack []int
func (s stack) Push(v int) stack {
return append(s, v)
}
func (s stack) Pop() (stack, int) {
l := len(s)
return s[:l-1], s[l-1]
}
// 快速排序法(遞增)，使用迴圈來迭代，並使用隨機支點。
func QuickSortRandomPivot(array []int) {
stack := make(stack, 0)
stack = stack.Push(0)
stack = stack.Push(len(array) - 1)
rand.Seed(time.Now().UnixNano())
for len(stack) > 0 {
var start, end int
stack, end = stack.Pop()
stack, start = stack.Pop()
if end > start {
p := rand.Intn(end-start+1) + start
array[start], array[p] = array[p], array[start]
pivot := array[start]
l := start + 1
r := end
for {
for r > start && array[r] >= pivot {
r -= 1
}
for l <= r && array[l] <= pivot {
l += 1
}
if l < r {
array[l], array[r] = array[r], array[l]
} else {
if r > start {
array[start], array[r] = array[r], array[start]
}
break
}
}
if r > start {
stack = stack.Push(start)
stack = stack.Push(r - 1)
}
if r < end {
stack = stack.Push(r + 1)
stack = stack.Push(end)
}
}
}
}
// 快速排序法(遞減)，使用迴圈來迭代，並使用隨機支點。
func QuickSortRandomPivotDesc(array []int) {
stack := make(stack, 0)
stack = stack.Push(0)
stack = stack.Push(len(array) - 1)
rand.Seed(time.Now().UnixNano())
for len(stack) > 0 {
var start, end int
stack, end = stack.Pop()
stack, start = stack.Pop()
if end > start {
p := rand.Intn(end-start+1) + start
array[end], array[p] = array[p], array[end]
pivot := array[end]
l := start
r := end - 1
for {
for l < end && array[l] >= pivot {
l += 1
}
for r >= l && array[r] <= pivot {
r -= 1
}
if l < r {
array[l], array[r] = array[r], array[l]
} else {
if l < end {
array[l], array[end] = array[end], array[l]
}
break
}
}
if l > start {
stack = stack.Push(start)
stack = stack.Push(l - 1)
}
if l < end {
stack = stack.Push(l + 1)
stack = stack.Push(end)
}
}
}
}
