哈希空间
C语言快速排序代码 算法 讲解
快速排序(Quick Sort)是一种基于分治思想的高效排序算法,是经典的排序算法之一。它的核心思想是选择一个元素作为基准(pivot),将序列分成两个子序列,其中一个子序列的所有元素都比基准小,另一个子序列的所有元素都比基准大,然后对这两个子序列分别递归地进行快速排序。
具体实现过程如下:
-
选择一个元素作为基准(pivot)。
-
将序列分成两个子序列,其中一个子序列的所有元素都比基准小,另一个子序列的所有元素都比基准大。可以采用双指针法实现,即使用两个指针i和j分别从序列的左端和右端开始扫描,当i指向的元素大于等于基准时,停止扫描;当j指向的元素小于等于基准时,停止扫描;然后交换i和j指向的元素。
-
递归地对子序列进行快速排序。
下面是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 阅读 827