当前位置：首页 > news >正文

数据结构——快速排序

news 2024/11/8 3:37:56

快速排序

算法思想:在待排序表L[1..n]中任取一个元素pivot作为枢轴(或基准，通常取首元素)，通过一趟排序将待排序表划分为独立的两部分[[1...k-1]和L[k+1..n]，使得L[1..K-1]中的所有元素小pivot,L[k+1..n]中的所有元素大于等于pivot，则pivot放在了其最终位置L(k)上，这个过程称为一次“划分”。然后分别递归地对两个子表重复上述过程，直至每部分内只有一个元素或空为止，即所有元素放在了其最终位置上。

下面进行演示：

low和high指针作用：若low/high指向的元素大于/小于基准，进行右移/左移。

这里有一个数组A[8]= { 4,0,1,6,5,3,2,7 }，我们设定两个指针low和high，指向数组两头，并取数组第一个元素4作为基准，此时4作为一个判断的根据。然后开始快速排序：

以4作为基准，现在对A[high]与4进行判断，此时7>4不用移动，high--，移动到这里：

此时A[high]=2<4，将A[high]的值赋给A[low]并让low指针开始操作，有几个low指向的元素都小于4，low一直移动到6那个位置：

此时A[low]大于4，将A[low]的值赋给A[high]：

这时到high指针进行移动：

此时A[high]=3<4，将A[high]的值赋给A[low]：

现在轮到low指针进行移动，low指针进行右移，此时A[low]=5>4

将A[low]的值赋给A[high]：

然后轮到high指针进行左移，此时low和high指针重合，将pivot=4变量赋值到A[low]的位置，并结束这一次排序。

以4作为分界线，分开左右两个子表，此时{2，0，1，3}与{5，6，7}进行上面的排序，排序完之后继续细分，最终结束排序。

下面是代码：

#include<stdio.h>
int Partition(int A[], int low, int high)
{int pivot = A[low];while (low < high){while (low < high && A[high] >= pivot)--high;A[low] =A[high];while (low < high && A[low] <= pivot)++low;A[high] = A[low];}A[low] = pivot;return low;
}
void QuickSort(int A[], int low, int high)
{if (low < high){int pivotpos = Partition(A, low, high);QuickSort(A, low, pivotpos - 1);QuickSort(A, pivotpos + 1, high);}
}
int main()
{int A[8] = { 4,0,1,6,5,3,2,7 };int n = 8;QuickSort(A, 0, 7);for (int i = 0; i < 8; i++){printf("%d ", A[i]);}return 0;
}

结果：