【快速排序算法詳解】Java/Go/Python/JS/C不同語言實(shí)現(xiàn)
說明
快速排序（QuickSort），又稱分區(qū)交換排序（partition-exchange sort）五垮，簡(jiǎn)稱快排抠忘。快排是一種通過基準(zhǔn)劃分區(qū)塊结耀，再不斷交換左右項(xiàng)的排序方式留夜，其采用了分治法，減少了交換的次數(shù)图甜。它的基本思想是：通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分碍粥，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序黑毅，整個(gè)排序過程可以遞歸或迭代進(jìn)行嚼摩，以此讓整個(gè)數(shù)列變成有序序列。
實(shí)現(xiàn)過程
- 在待排序區(qū)間找到一個(gè)基準(zhǔn)點(diǎn)(pivot)，便于理解一般是位于數(shù)組中間的那一項(xiàng)枕面。
- 逐個(gè)循環(huán)數(shù)組將小于基準(zhǔn)的項(xiàng)放左側(cè)愿卒，將大于基準(zhǔn)的項(xiàng)放在右側(cè)。一般通過交換的方式來實(shí)現(xiàn)潮秘。
- 將基準(zhǔn)點(diǎn)左側(cè)全部項(xiàng)和基點(diǎn)右側(cè)全部項(xiàng)分別通過遞歸(或迭代)方式重復(fù)第1項(xiàng)掘猿，直到所有數(shù)組都交換完成。
示意圖
quick1.png
quick2.gif
性能分析
平均時(shí)間復(fù)雜度：O(NlogN)
最佳時(shí)間復(fù)雜度：O(NlogN)
最差時(shí)間復(fù)雜度：O(N^2)
空間復(fù)雜度：根據(jù)實(shí)現(xiàn)方式的不同而不同唇跨，可以查看不同版本的源碼
代碼
Java
/* 方式1,標(biāo)準(zhǔn)遞歸版本稠通。需要左右不斷交換，無需新建數(shù)組买猖。 */
static int[] quickSort1(int arr[], int low, int high) {
int i = low > 0 ? low : 0;
int j = high;
int midIndex = (i + j) / 2;
int pivot = arr[midIndex];
System.out.println(
" i=" + i + ", j=" + j + ", midIndex=" + midIndex + ", pivot=" + pivot + " arr[]=" + Arrays.toString(arr));
// 當(dāng)左側(cè)小于等于右側(cè)則表示還有值沒有對(duì)比改橘，需要繼續(xù)
while (i <= j) {
// 當(dāng)左側(cè)小于基準(zhǔn)時(shí)查找位置右移，直到找出比基準(zhǔn)值大的位置來
while (arr[i] < pivot) {
System.out.println("arr[i] < pivot: i=" + i + ", j=" + j + ", pivot=" + pivot);
i++;
}
// 當(dāng)前右側(cè)大于基準(zhǔn)時(shí)左移玉控，直到找出比基準(zhǔn)值小的位置來
while (arr[j] > pivot) {
System.out.println("arr[i] > pivot: i=" + i + ", j=" + j + ", pivot=" + pivot);
j--;
}
System.out.println("low=" + low + ", high=" + high + ", i=" + i + ", j=" + j + ", pivot=" + pivot);
// 當(dāng)左側(cè)位置小于右側(cè)時(shí)飞主，將數(shù)據(jù)交換，小的交換到基準(zhǔn)左側(cè)高诺，大的交換到右側(cè)
if (i <= j) {
int tmp = arr[j];
arr[j] = arr[i];
arr[i] = tmp;
// 縮小搜查范圍碌识，直到左側(cè)都小于基數(shù)，右側(cè)都大于基數(shù)
i++;
j--;
}
}
// 左側(cè)小于基數(shù)位置虱而，不斷遞歸左邊部分
if (low < j) {
System.out.println(" low < j:recursion: low=" + low + ", high=" + high + ", i=" + i + ", j=" + j + ", midIndex="
+ midIndex + ", pivot=" + pivot);
quickSort1(arr, low, j);
}
// 基數(shù)位置小于右側(cè)筏餐，不斷遞歸右側(cè)部分
if (i < high) {
System.out.println(" i < high:recursion: low=" + low + ", high=" + high + ", i=" + i + ", j=" + j + ", midIndex="
+ midIndex + ", pivot=" + pivot);
quickSort1(arr, i, high);
}
return arr;
}
Python
# 標(biāo)準(zhǔn)遞歸版本。需要左右不斷交換牡拇，無需新建數(shù)組魁瞪。
def quick_sort2(arr, left=None, right=None):
i = left = left if left is not None else 0
j = right = right if right is not None else len(arr) - 1
mid_index = (i + j) / 2
pivot = arr[mid_index]
# 當(dāng)左側(cè)小于等于右側(cè)則表示還有值沒有對(duì)比，需要繼續(xù)
while (i <= j):
# 當(dāng)左側(cè)小于基準(zhǔn)時(shí)查找位置右移惠呼，直到找出比基準(zhǔn)值大的位置來
while (arr[i] < pivot):
print('arr[i] < pivot:',
' i=' + str(i) + ' j=' + str(j) + ' pivot=' + str(pivot))
i = i + 1
# 當(dāng)前右側(cè)大于基準(zhǔn)時(shí)左移导俘，直到找出比基準(zhǔn)值小的位置來
while (arr[j] > pivot):
print('arr[j] > pivot:',
' i=' + str(i) + ' j=' + str(j) + ' pivot=' + str(pivot))
j -= 1
print(
' left=' + str(left) + ' right=' + str(right) + ' i=' + str(i) +
' j=' + str(j) + ' mid_index=' + str(mid_index) + ' pivot=' +
str(pivot) + ' arr[]=', arr)
# 當(dāng)左側(cè)位置小于右側(cè)時(shí)，將數(shù)據(jù)交換剔蹋，小的交換到基準(zhǔn)左側(cè)旅薄，大的交換到右側(cè)
if (i <= j):
[arr[i], arr[j]] = [arr[j], arr[i]]
# 縮小搜查范圍，直到左側(cè)都小于基數(shù)泣崩，右側(cè)都大于基數(shù)
i += 1
j -= 1
# 左側(cè)小于基數(shù)位置少梁，不斷遞歸左邊部分
if (left < j):
print(
'left < j:recursion: left=' + str(left) + ' right=' + str(right) +
' i=' + str(i) + ' j=' + str(j) + 'arr[]', arr)
quick_sort2(arr, left, j)
# 基數(shù)位置小于右側(cè)，不斷遞歸右側(cè)部分
if (i < right):
print(
'i < right:recursion: left=' + str(left) + ' right=' +
str(right) + ' i=' + str(i) + ' j=' + str(j) + 'arr[]', arr)
quick_sort2(arr, i, right)
return arr
Go
// 把數(shù)組分按照基準(zhǔn)值分為左右兩部分律想，再返回新的中間位置作為排序的pivot
func partition(arr []int, left int, right int) int {
// pivot基準(zhǔn)可以任意挑選猎莲，這里取右側(cè)
var pivotIndex = right
var pivot = arr[pivotIndex]
var swapIndex = left - 1
for i := left; i < right; i++ {
// 如果小于基準(zhǔn)則進(jìn)行交換
if arr[i] < pivot {
swapIndex++
arr[swapIndex], arr[i] = arr[i], arr[swapIndex]
}
}
swapIndex++
arr[swapIndex], arr[pivotIndex] = arr[pivotIndex], arr[swapIndex]
fmt.Println("partition:", arr, swapIndex, arr[swapIndex], arr[left:swapIndex], arr[swapIndex:right])
return swapIndex
}
// 方式2, 標(biāo)準(zhǔn)遞歸版本绍弟。左右不斷分區(qū)交換技即，無需新建數(shù)組。
func quickSort2(arr []int, left int, right int) []int {
if left < right {
var pivot = partition(arr, left, right)
quickSort2(arr, left, pivot-1)
quickSort2(arr, pivot+1, right)
}
return arr
}
JS
// 方式4, 非遞歸版本樟遣。需要交換而叼，無需新建數(shù)組身笤，利用stack或queue遍歷。
function quickSort4(arr, left, right) {
left = left !== undefined ? left : 0
right = right !== undefined ? right : arr.length - 1
var stack = []
var i, j, midIndex, pivot, tmp
// 與標(biāo)準(zhǔn)遞歸版相同葵陵，只是將遞歸改為遍歷棧的方式
// 先將左右各取一個(gè)入棧
stack.push(left)
stack.push(right)
while (stack.length) {
// 如果棧內(nèi)還有數(shù)據(jù)液荸，則一并馬上取出，其他邏輯與標(biāo)準(zhǔn)遞歸版同
j = right = stack.pop()
i = left = stack.pop()
midIndex = Math.floor((i + j) / 2)
pivot = arr[midIndex]
while (i <= j) {
while (arr[i] < pivot) {
console.log('arr[i] < pivot:', ' i=' + i + ' j=' + j + ' pivot=' + pivot + 'arr[]=' + arr)
i++
}
while (arr[j] > pivot) {
console.log('arr[j] > pivot:', ' i=' + i + ' j=' + j + ' pivot=' + pivot + 'arr[]=' + arr)
j--
}
if (i <= j) {
tmp = arr[j]
arr[j] = arr[i]
arr[i] = tmp
i++
j--
}
}
if (left < j) {
// 與遞歸版不同脱篙，這里添加到棧中娇钱，以便繼續(xù)循環(huán)
console.log('left < j:recursion: left=' + left + ' right=' + right + ' i=' + i + ' j=' + j + 'arr[]=' + arr)
stack.push(left)
stack.push(j)
}
if (i < right) {
console.log('i < right:recursion: left=' + left + ' right=' + right + ' i=' + i + ' j=' + j + 'arr[]=' + arr)
stack.push(i)
stack.push(right)
}
}
return arr
}
TS
// 1. 方式1, 遞歸新建數(shù)組版本。無需交換绊困，每個(gè)分區(qū)都是新數(shù)組文搂，數(shù)量龐大
quickSort1(arr: Array<number>) {
// 數(shù)組長(zhǎng)度為1就不再分級(jí)
if (arr.length <= 1) {
return arr
}
console.log('split array:', arr)
var pivot: number
const left = Array<number>()
const right = Array<number>()
// 設(shè)置中間數(shù)
var midIndex = Math.floor(arr.length / 2)
pivot = arr[midIndex]
for (var i = 0, l = arr.length; i < l; i++) {
console.log(
'i=' + i + ' midIndex=' + midIndex + ' pivot=' + pivot + ' arr[]=' + arr
)
// 當(dāng)中間基數(shù)等于i時(shí)，跳過當(dāng)前秤朗。中間數(shù)遞歸完成時(shí)合并
if (midIndex === i) {
continue
}
// 當(dāng)前數(shù)組端里面的項(xiàng)小于基數(shù)則添加到左側(cè)
if (arr[i] < pivot) {
left.push(arr[i])
// 大于等于則添加到右側(cè)
} else {
right.push(arr[i])
}
}
arr = this.quickSort1(left).concat(pivot, this.quickSort1(right))
// 遞歸調(diào)用遍歷左側(cè)和右側(cè)煤蹭，再將中間值連接起來
return arr
}
C
/** 方式1,標(biāo)準(zhǔn)遞歸版本。需要左右不斷交換取视，無需新建數(shù)組硝皂。*/
void *quickSort1(int arr[], int low, int high)
{
int i = low > 0 ? low : 0;
int j = high;
int midIndex = (i + j) / 2;
int pivot = arr[midIndex];
// 當(dāng)左側(cè)小于等于右側(cè)則表示還有值沒有對(duì)比，需要繼續(xù)
while (i <= j)
{
// 當(dāng)左側(cè)小于基準(zhǔn)時(shí)查找位置右移作谭，直到找出比基準(zhǔn)值大的位置來
while (arr[i] < pivot)
{
printf("\r\narr[i] < pivot: i=%d, j=%d, pivot=%d", i, j, pivot);
i++;
}
// 當(dāng)前右側(cè)大于基準(zhǔn)時(shí)左移稽物，直到找出比基準(zhǔn)值小的位置來
while (arr[j] > pivot)
{
printf("\r\narr[i] > pivot: i=%d, j=%d, pivot=%d", i, j, pivot);
j--;
}
printf("\r\n low=%d, high=%d, i=%d, j=%d, midIndex=%d, pivot=%d", low, high, i, j, midIndex, pivot);
// 當(dāng)左側(cè)位置小于右側(cè)時(shí)，將數(shù)據(jù)交換折欠，小的交換到基準(zhǔn)左側(cè)姨裸，大的交換到右側(cè)
if (i <= j)
{
swap(&arr[i], &arr[j]);
// 縮小搜查范圍，直到左側(cè)都小于基數(shù)怨酝，右側(cè)都大于基數(shù)
i++;
j--;
}
}
// 左側(cè)小于基數(shù)位置傀缩，不斷遞歸左邊部分
if (low < j)
{
printf("\r\n low < j:recursion: low=%d, high=%d, i=%d, j=%d, midIndex=%d, pivot=%d", low, high, i, j, midIndex, pivot);
quickSort1(arr, low, j);
}
// 基數(shù)位置小于右側(cè)，不斷遞歸右側(cè)部分
if (i < high)
{
printf("\r\n i < high:recursion: low=%d, high=%d, i=%d, j=%d, midIndex=%d, pivot=%d", low, high, i, j, midIndex, pivot);
quickSort1(arr, i, high);
}
return arr;
}
C++
void swap(int *a, int *b)
{
int temp = *a;
*a = *b;
*b = temp;
}
void printArray(int *arr, int size)
{
for (int i = 0; i < size; i++)
{
std::cout << arr[i] << " ";
}
std::cout << std::right;
}
// 把數(shù)組分按照基準(zhǔn)值分為左右兩部分农猬，再返回新的中間位置作為排序的pivot
int partition(int *arr, int left, int right)
{
// 這里的pivot以右側(cè)為準(zhǔn)
int pivotIndex = right;
int pivot = arr[pivotIndex];
// 記錄交換的位置
int swapIndex = left - 1;
for (int i = left; i < right; i++)
{
// 如果小于基準(zhǔn)則進(jìn)行交換
// 把小于基數(shù)的逐個(gè)往左側(cè)放赡艰，大于基數(shù)的往右側(cè)放
if (arr[i] < pivot)
{
swapIndex++;
swap(&arr[swapIndex], &arr[i]);
}
}
swapIndex++;
// 最后把原基數(shù)調(diào)換到分區(qū)線的位置，并返回分區(qū)線位置
swap(&arr[swapIndex], &arr[pivotIndex]);
return swapIndex;
}
void quickSort(int *arr, int left, int right)
{
if (left < right)
{
int pivot = partition(arr, left, right);
quickSort(arr, left, pivot - 1);
quickSort(arr, pivot + 1, right);
}
}
鏈接
快速排序算法源碼：https://github.com/microwind/algorithms/tree/master/sorts/quicksort
