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

C语言 (Implement Quicksort with first element as pivot)以第一个元素为枢轴元素实现快速排序

news 2026/6/2 3:19:29

如果您喜欢此文章，请收藏、点赞、评论，谢谢，祝您快乐每一天。

快速排序是一种分治算法。它选择一个元素作为枢轴，并围绕该枢轴对给定数组进行分区。快速排序有很多不同的版本，它们选择枢轴的方式各不相同。

·始终选择第一个元素作为枢轴。
·始终选择最后一个元素作为枢轴点。
·随机选择一个元素作为枢轴。
·选择中位数作为枢轴点。

注意：这里我们将通过选择第一个元素作为枢轴来实现快速排序。

选择第一个元素作为枢轴进行快速排序：

快速排序的关键功能是分区。分区的目标是在数组已排序的情况下，将枢轴元素放置在正确的位置，并将较小的（或相等的）元素放在其左侧，较大的元素放在其右侧，并且所有这些都要在线性时间内完成。

分区算法：

分区的方法有很多种，以下伪代码采用了 CLRS 书中给出的方法。

我们从最左边的元素开始，并将较小（或相等）元素的索引记为i。
在遍历过程中，如果我们找到一个更小（或相等）的元素，我们将当前元素与 arr[i] 交换。
否则，我们将忽略当前元素。

递归快速排序函数的伪代码：

// low –> Starting index, high –> Ending index

quickSort(arr[], low, high) {
if (low < high) {

// pi is partitioning index, arr[pi] is now at right place
pi = partition(arr, low, high);
quickSort(arr, low, pi – 1); // Before pi
quickSort(arr, pi + 1, high); // After pi
}
}

partition() 函数的伪代码

/* 此函数以数组首元素为基准元素，将基准元素放置在排序数组中的正确位置，并将所有小于或等于基准元素的元素放置在基准元素的左侧，所有大于基准元素的元素放置在基准元素的右侧。*/

partition(arr[], low, high) {
// 第一个元素作为枢轴
pivot = arr[low]
k = high
for (i = high; i > low; i--) {
if (arr[i] > pivot){
swap arr[i] and arr[k];
k--;
}
}
swap arr[k] and arr[low]
return k;
}

分区的图示 partition() ：

Consider: arr[] = { 7, 6, 10, 5, 9, 2, 1, 15, 7 }

第一次分区： low = 0，high = 8，pivot = arr[low] = 7
初始化最右边元素的索引 k = high = 8。

·从 i = 高处到低处横移：
如果 arr[i] 大于 pivot：
交换 arr[i] 和 arr[k]。
减去 k；

·最后交换 arr[low] 和 arr[k]。

现在枢轴的正确位置是索引5。

第二次分区： low = 0，high = 4，pivot = arr[low] = 2
类似地初始化 k = high = 4；

2 的正确位置变为索引 1。左侧部分只有一个元素，右侧部分有 {6, 5, 7}。

另一方面，划分发生在段 [6, 8] 上，即数组 {10, 9, 15}。
这里 low = 6，high = 8，pivot = 10，k = 8。

10 的正确位置变为索引 7，左右两部分都只有一个元素。

第三划分：这里划分线段 {6, 5, 7}。低位 = 2，高位 = 4，枢轴 = 6，k = 4。
如果应用相同的过程，我们将得到 6 的正确位置，即索引 3，并且左右两部分都只有一个元素。

这样一来，整个数组就排序完成了。请查看下图了解递归树。

请按照以下步骤实施该方法。

使用递归函数（例如快速排序）来初始化该函数。
调用分区函数对数组进行分区，并在分区函数内部执行以下操作：
- 以第一个元素为枢轴并初始化迭代器k = high。
- 使用 for 循环从i = high 到 low+1 迭代：
  - 如果 arr[i] 大于 pivot，则交换arr[i]和arr[k]并将 k 减 1。
- 迭代后，将枢轴与arr[k]交换。
- 返回 k-1 作为分割点。
现在递归地对分区索引的左半部分和右半部分调用快速排序。

上述方法的代码示例：

#include <stdio.h>

void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}

int partition(int arr[], int low, int high) {
int pivot = arr[low]; // Choosing the pivot element
int start = low;
int end = high;
int k = high;

// Iterate from the end of the array to the start
for (int i = high; i > low; i--) {
// If the current element is greater than the pivot,
// swap it with the element at index k and decrement k
if (arr[i] > pivot)
swap(&arr[i], &arr[k--]);
}

// Swap the pivot element with the element at index k
swap(&arr[low], &arr[k]);

return k; // Return the index of the pivot element after partitioning
}

void quickSort(int arr[], int low, int high) {
if (low < high) {
// Partition the array and get the index of the pivot element
int idx = partition(arr, low, high);

// Recursively sort the subarrays before and after the pivot element
quickSort(arr, low, idx - 1);
quickSort(arr, idx + 1, high);
}
}

void printArray(int arr[], int size) {
for (int i = 0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}

int main() {
int arr[] = {7, 6, 10, 5, 9, 2, 1, 15, 7};
int n = sizeof(arr) / sizeof(arr[0]);

// Call quickSort to sort the array
quickSort(arr, 0, n - 1);

printf("Sorted array: \n");
printArray(arr, n);

return 0;
}

输出