快速排序算法
快速排序是一种高效的排序算法，它基于将数据数组划分为更小的数组。将一个大型数组划分为两个数组，其中一个数组保存小于指定值（称为基准值）的值，并以此值为基础进行划分；另一个数组保存大于基准值的值。
快速排序对数组进行划分，然后递归调用自身两次，对得到的两个子数组进行排序。该算法对于大型数据集非常高效，因为其平均复杂度和最坏情况复杂度分别为 O(n²)。
快速排序中的划分
以下动画演示了如何在数组中查找基准值。
基准值将列表分为两部分。然后，我们递归地为每个子列表找到枢轴，直到所有列表都只包含一个元素。
快速排序枢轴算法
基于我们对快速排序中分区的理解，我们现在将尝试为其编写一个算法，如下所示。
1. 选择具有枢轴的最高索引值 2. 取两个变量分别指向列表的左侧和右侧（不包括枢轴） 3. 左侧指向最低索引 4. 右侧指向最高索引 5. 当左侧的值小于枢轴时，向右移动 6. 当右侧的值大于枢轴时，向左移动 7. 如果步骤 5 和步骤 6 均不匹配，则交换左右两侧 8. 如果左侧 ≥没错，它们相交的点就是新的枢轴点
快速排序枢轴点伪代码
上述算法的伪代码可以推导如下 −
function partitionFunc(left, right, pivot)
leftPointer = left
rightPointer = right - 1
while True do
while A[++leftPointer] < pivot do
//do-nothing
end while
while rightPointer > 0 && A[--rightPointer] > pivot do
//do-nothing
end while
if leftPointer >= rightPointer
break
else
swap leftPointer,rightPointer
end if
end while
swap leftPointer,right
return leftPointer
end function
快速排序算法
递归使用枢轴算法，我们最终得到尽可能小的分区。然后对每个分区进行快速排序。我们将快速排序的递归算法定义如下 −
1. 将最右侧索引值作为枢轴 2. 使用枢轴值对数组进行分区 3. 递归对左侧分区进行快速排序 4. 递归对右侧分区进行快速排序
快速排序伪代码
为了更深入地了解，请查看快速排序算法的伪代码 −
procedure quickSort(left, right)
if right-left <= 0
return
else
pivot = A[right]
partition = partitionFunc(left, right, pivot)
quickSort(left,partition-1)
quickSort(partition+1,right)
end if
end procedure
分析
快速排序算法的最坏情况复杂度为 O(n2)。然而，使用这种技术，在平均情况下，我们通常可以在 O(n log n) 时间内得到输出。
实现
以下是各种编程语言中快速排序算法的实现 −
#include <stdio.h>
#include <stdbool.h>
#define MAX 7
int intArray[MAX] = {
4,6,3,2,1,9,7
};
void printline(int count) {
int i;
for (i = 0; i < count - 1; i++) {
printf("=");
}
printf("=
");
}
void display() {
int i;
printf("[");
// navigate through all items
for (i = 0; i < MAX; i++) {
printf("%d ", intArray[i]);
}
printf("]
");
}
void swap(int num1, int num2) {
int temp = intArray[num1];
intArray[num1] = intArray[num2];
intArray[num2] = temp;
}
int partition(int left, int right, int pivot) {
int leftPointer = left - 1;
int rightPointer = right;
while (true) {
while (intArray[++leftPointer] < pivot) {
//do nothing
}
while (rightPointer > 0 && intArray[--rightPointer] > pivot) {
//do nothing
}
if (leftPointer >= rightPointer) {
break;
} else {
printf(" item swapped :%d,%d
", intArray[leftPointer], intArray[rightPointer]);
swap(leftPointer, rightPointer);
}
}
printf(" pivot swapped :%d,%d
", intArray[leftPointer], intArray[right]);
swap(leftPointer, right);
printf("Updated Array: ");
display();
return leftPointer;
}
void quickSort(int left, int right) {
if (right - left <= 0) {
return;
} else {
int pivot = intArray[right];
int partitionPoint = partition(left, right, pivot);
quickSort(left, partitionPoint - 1);
quickSort(partitionPoint + 1, right);
}
}
int main() {
printf("Input Array: ");
display();
printline(50);
quickSort(0, MAX - 1);
printf("Output Array: ");
display();
printline(50);
}
输出
Input Array: [4 6 3 2 1 9 7 ] ================================================== pivot swapped :9,7 Updated Array: [4 6 3 2 1 7 9 ] pivot swapped :4,1 Updated Array: [1 6 3 2 4 7 9 ] item swapped :6,2 pivot swapped :6,4 Updated Array: [1 2 3 4 6 7 9 ] pivot swapped :3,3 Updated Array: [1 2 3 4 6 7 9 ] Output Array: [1 2 3 4 6 7 9 ] ==================================================
#include <iostream>
using namespace std;
#define MAX 7
int intArray[MAX] = {4,6,3,2,1,9,7};
void display() {
int i;
cout << "[";
// navigate through all items
for(i = 0;i < MAX;i++) {
cout << intArray[i] << " ";
}
cout << "]
";
}
void swap(int num1, int num2) {
int temp = intArray[num1];
intArray[num1] = intArray[num2];
intArray[num2] = temp;
}
int partition(int left, int right, int pivot) {
int leftPointer = left -1;
int rightPointer = right;
while(true) {
while(intArray[++leftPointer] < pivot) {
//do nothing
}
while(rightPointer > 0 && intArray[--rightPointer] > pivot) {
//do nothing
}
if(leftPointer >= rightPointer) {
break;
} else {
cout << "item swapped : " << intArray[leftPointer] << "," << intArray[rightPointer] << endl;
swap(leftPointer, rightPointer);
}
}
cout << "
pivot swapped : " << intArray[leftPointer] << "," << intArray[right] << endl;
swap(leftPointer,right);
cout << "Updated Array: ";
display();
return leftPointer;
}
void quickSort(int left, int right) {
if(right-left <= 0) {
return;
} else {
int pivot = intArray[right];
int partitionPoint = partition(left, right, pivot);
quickSort(left, partitionPoint - 1);
quickSort(partitionPoint + 1,right);
}
}
int main() {
cout << "Input Array: ";
display();
quickSort(0, MAX-1);
cout << "
Output Array: ";
display();
}
输出
Input Array: [4 6 3 2 1 9 7 ] pivot swapped : 9,7 Updated Array: [4 6 3 2 1 7 9 ] pivot swapped : 4,1 Updated Array: [1 6 3 2 4 7 9 ] item swapped : 6,2 pivot swapped : 6,4 Updated Array: [1 2 3 4 6 7 9 ] pivot swapped : 3,3 Updated Array: [1 2 3 4 6 7 9 ] Output Array: [1 2 3 4 6 7 9 ]
import java.util.Arrays;
public class QuickSortExample {
int[] intArray = {4,6,3,2,1,9,7};
void swap(int num1, int num2) {
int temp = intArray[num1];
intArray[num1] = intArray[num2];
intArray[num2] = temp;
}
int partition(int left, int right, int pivot) {
int leftPointer = left - 1;
int rightPointer = right;
while (true) {
while (intArray[++leftPointer] < pivot) {
// do nothing
}
while (rightPointer > 0 && intArray[--rightPointer] > pivot) {
// do nothing
}
if (leftPointer >= rightPointer) {
break;
} else {
swap(leftPointer, rightPointer);
}
}
swap(leftPointer, right);
// System.out.println("Updated Array: ");
return leftPointer;
}
void quickSort(int left, int right) {
if (right - left <= 0) {
return;
} else {
int pivot = intArray[right];
int partitionPoint = partition(left, right, pivot);
quickSort(left, partitionPoint - 1);
quickSort(partitionPoint + 1, right);
}
}
public static void main(String[] args) {
QuickSortExample sort = new QuickSortExample();
int max = sort.intArray.length;
System.out.println("数组的内容：");
System.out.println(Arrays.toString(sort.intArray));
sort.quickSort(0, max - 1);
System.out.println("排序后数组的内容：");
System.out.println(Arrays.toString(sort.intArray));
}
}
输出
数组的内容： [4, 6, 3, 2, 1, 9, 7] 排序后数组的内容： [1, 2, 3, 4, 6, 7, 9]
def partition(arr, low, high):
i = low - 1
pivot = arr[high] # pivot element
for j in range(low, high):
if arr[j] <= pivot:
# increment
i = i + 1
arr[i], arr[j] = arr[j], arr[i]
arr[i + 1], arr[high] = arr[high], arr[i + 1]
return i + 1
def quickSort(arr, low, high):
if low < high:
pi = partition(arr, low, high)
quickSort(arr, low, pi - 1)
quickSort(arr, pi + 1, high)
arr = [2, 5, 3, 8, 6, 5, 4, 7]
n = len(arr)
print("数组的内容：")
for i in range(n):
print(arr[i], end=" ")
quickSort(arr, 0, n - 1)
print("
排序数组的内容：")
for i in range(n):
print(arr[i], end=" ")
输出
数组的内容： 2 5 3 8 6 5 4 7 排序数组的内容： 2 3 4 5 5 6 7 8
