抄作业看这里，快速排序算法多语言代码来了

快速排序是一种分治算法。它的基本思想是：通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则分别对这两部分继续进行排序，直到整个序列有序。快速排序是由 Tony Hoare 在 1960 年提出的一种排序算法。它通过不断地划分序列并对子序列进行排序，最终得到有序序列。快速排序的时间复杂度为 O(nlogn)，是一种非常高效的排序算法。

一般来说，快速排序算法的流程如下:

1. 从数列中挑出一个元素，称为 “基准”（pivot）。
2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分割之后，该基准是它的最后位置。
3. 递归地把小于基准值元素的子数列和大于基准值元素的子数列排序。

平均时间复杂度为 O(nlogn) , 空间复杂度为O(logn) ~ O(n)。对于快速排序来说，选择基准元素的方式很重要。如果基准元素是数列中的最大或最小元素，那么每次分割后的子序列中有一个为空，递归效率就会降低。常用的方法有三种：随机选择一个元素作为基准，取数列的最左端或最右端元素作为基准，取中间元素作为基准。

另外，在实际实现中，为了避免出现最坏情况，常采用“三数取中”来选择基准元素，即将数列分成三部分，取左端点，右端点和中间点三个数中的中位数作为基准元素。

划重点：快速排序需要注意基准元素的选择问题，以及递归深度过深导致栈溢出的问题。

下面是抄作业时间，常见语言中快速排序算法的代码例子:

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