哈希空间

C语言快速排序代码 算法 讲解

快速排序(Quick Sort)是一种基于分治思想的高效排序算法,是经典的排序算法之一。它的核心思想是选择一个元素作为基准(pivot),将序列分成两个子序列,其中一个子序列的所有元素都比基准小,另一个子序列的所有元素都比基准大,然后对这两个子序列分别递归地进行快速排序。

具体实现过程如下:

  1. 选择一个元素作为基准(pivot)。

  2. 将序列分成两个子序列,其中一个子序列的所有元素都比基准小,另一个子序列的所有元素都比基准大。可以采用双指针法实现,即使用两个指针i和j分别从序列的左端和右端开始扫描,当i指向的元素大于等于基准时,停止扫描;当j指向的元素小于等于基准时,停止扫描;然后交换i和j指向的元素。

  3. 递归地对子序列进行快速排序。

下面是C语言实现的快速排序代码:

void quick_sort(int arr[], int left, int right) { if (left >= right) return; // 如果左指针大于等于右指针,直接返回 int i = left, j = right, pivot = arr[left]; // 选择左端元素作为基准 while (i < j) { while (i < j && arr[j] >= pivot) j--; // 从右端开始扫描,找到第一个小于基准的元素 if (i < j) arr[i++] = arr[j]; // 将该元素放到左端 while (i < j && arr[i] < pivot) i++; // 从左端开始扫描,找到第一个大于等于基准的元素 if (i < j) arr[j--] = arr[i]; // 将该元素放到右端 } arr[i] = pivot; // 将基准放到最终位置 quick_sort(arr, left, i - 1); // 递归地对左子序列进行快速排序 quick_sort(arr, i + 1, right); // 递归地对右子序列进行快速排序 }

在主函数中调用该函数即可对数组进行快速排序:

int main() { int arr[] = {5, 2, 8, 4, 7, 1, 9, 3, 6}; int n = sizeof(arr) / sizeof(arr[0]); quick_sort(arr, 0, n - 1); for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } return 0; }

输出结果为:1 2 3 4 5 6 7 8 9。

本文 最佳观看地址:https://www.hashspace.cn/c-quicksort.html 阅读 647

打开 哈希空间 微信小程序中查看更佳