数据结构&算法 快速排序
-
快速排序
快速排序是一种高效的排序算法,它基于将数据数组划分为较小的数组。将一个大数组分为两个数组,其中一个数组的值小于指定值(例如,枢轴),基于该数组进行分区,另一个数组的值大于该枢轴值。快速排序对数组进行分区,然后递归调用两次以对两个结果子数组进行排序。该算法对于大型数据集非常有效,因为其平均和最坏情况下的复杂度分别为O(nLogn)和O(logn2)。 -
快速排序分区
下面的动画表示法说明了如何在数组中查找枢轴值。枢轴值将列表分为两部分。递归地,我们找到每个子列表的枢纽,直到所有列表仅包含一个元素。 -
快速排序枢轴算法
基于对快速分区的理解,我们现在尝试为它编写一个算法,如下所示。步骤 1 − 选择指标值最高的pivot 步骤 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 − 使用pivot值对数组进行分区 步骤 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
-
实现
以下是C语言的实现
尝试一下#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("=\n"); } void display() { int i; printf("["); // navigate through all items for(i = 0;i < MAX;i++) { printf("%d ",intArray[i]); } printf("]\n"); } 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\n", intArray[leftPointer],intArray[rightPointer]); swap(leftPointer,rightPointer); } } printf(" pivot swapped :%d,%d\n", 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); }