抄作業(yè)看這里，快速排序算法多語言代碼來了

快速排序是一種分治算法。它的基本思想是：通過一趟排序?qū)⒋判蛴涗浄指畛瑟?dú)立的兩部分，其中一部分記錄的關(guān)鍵字均比另一部分的關(guān)鍵字小，則分別對這兩部分繼續(xù)進(jìn)行排序，直到整個(gè)序列有序?？焖倥判蚴怯?Tony Hoare 在 1960 年提出的一種排序算法。它通過不斷地劃分序列并對子序列進(jìn)行排序，最終得到有序序列?？焖倥判虻臅r(shí)間復(fù)雜度為 O(nlogn)，是一種非常高效的排序算法。

一般來說，快速排序算法的流程如下:

1. 從數(shù)列中挑出一個(gè)元素，稱為 “基準(zhǔn)”（pivot）。
2. 重新排序數(shù)列，所有元素比基準(zhǔn)值小的擺放在基準(zhǔn)前面，所有元素比基準(zhǔn)值大的擺在基準(zhǔn)的后面（相同的數(shù)可以到任一邊）。在這個(gè)分割之后，該基準(zhǔn)是它的最后位置。
3. 遞歸地把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序。

平均時(shí)間復(fù)雜度為 O(nlogn) , 空間復(fù)雜度為O(logn) ~ O(n)。對于快速排序來說，選擇基準(zhǔn)元素的方式很重要。如果基準(zhǔn)元素是數(shù)列中的最大或最小元素，那么每次分割后的子序列中有一個(gè)為空，遞歸效率就會降低。常用的方法有三種：隨機(jī)選擇一個(gè)元素作為基準(zhǔn)，取數(shù)列的最左端或最右端元素作為基準(zhǔn)，取中間元素作為基準(zhǔn)。

另外，在實(shí)際實(shí)現(xiàn)中，為了避免出現(xiàn)最壞情況，常采用“三數(shù)取中”來選擇基準(zhǔn)元素，即將數(shù)列分成三部分，取左端點(diǎn)，右端點(diǎn)和中間點(diǎn)三個(gè)數(shù)中的中位數(shù)作為基準(zhǔn)元素。

劃重點(diǎn)：快速排序需要注意基準(zhǔn)元素的選擇問題，以及遞歸深度過深導(dǎo)致棧溢出的問題。

下面是抄作業(yè)時(shí)間，常見語言中快速排序算法的代碼例子:

C++:

void quickSort(int arr[], int left, int right) {
int i = left, j = right;
int pivot = arr[(left + right) / 2];
while (i <= j) {
while (arr[i] < pivot) i++;
while (arr[j] > pivot) j–;
if (i <= j) {
swap(arr[i], arr[j]);
i++;
j–;
}
}
if (left < j) quickSort(arr, left, j);
if (i < right) quickSort(arr, i, right);
}

Java:

void quickSort(int arr[], int left, int right) {
int i = left, j = right;
int pivot = arr[(left + right) / 2];
while (i <= j) {
while (arr[i] < pivot) i++;
while (arr[j] > pivot) j–;
if (i <= j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
j–;
}
}
if (left < j) quickSort(arr, left, j);
if (i < right) quickSort(arr, i, right);
}

Python:

def quickSort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quickSort(left) + middle + quickSort(right)

JavaScript:

function quickSort(arr, left, right) {
var len = arr.length,
pivot,
partitionIndex;

if(left < right){
pivot = right;
partitionIndex = partition(arr, pivot, left, right);

quickSort(arr, left, partitionIndex – 1);
quickSort(arr, partitionIndex + 1, right);
}
return arr;
}

function partition(arr, pivot, left, right){
var pivotValue = arr[pivot],
partitionIndex = left;

for(var i = left; i < right; i++){
if(arr[i] < pivotValue){
swap(arr, i, partitionIndex);
partitionIndex++;
}
}
swap(arr, right, partitionIndex);
return partitionIndex;
}

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

C#:

void QuickSort(int[] array, int left, int right)
{
if (left < right)
{
int pivot = Partition(array, left, right);
if (pivot > 1)
{
QuickSort(array, left, pivot – 1);
}
if (pivot + 1 < right)
{
QuickSort(array, pivot + 1, right);
}
}
}
int Partition(int[] array, int left, int right)
{
int pivot = array[left];
while (true)
{
while (array[left] < pivot)
{
left++;
}
while (array[right] > pivot)
{
right–;
}
if (left < right)
{
if (array[left] == array[right])
return right;
int temp = array[left];
array[left] = array[right];
array[right] = temp;
}
else
{
return right;
}
}
}

Visual Basic:

Sub QuickSort(arr() As Integer, left As Integer, right As Integer)
Dim i As Integer = left
Dim j As Integer = right
Dim pivot As Integer = arr((left + right) \ 2)
Do
Do
i += 1
Loop While arr(i) < pivot
Do
j -= 1
Loop While arr(j) > pivot
If i <= j Then
Dim temp As Integer = arr(i)
arr(i) = arr(j)
arr(j) = temp
i += 1
j -= 1
End If
Loop While i <= j
If left < j Then
QuickSort(arr, left, j)
End If
If i < right Then
QuickSort(arr, i, right)
End If
End Sub