排序算法-快速排序
描述：[*]基准值选择：选取数组的末了一个元素 arr 作为基准值 p。
[*]初始化索引：i 初始化为 low - 1，其作用是指向比基准值小的末了一个元素的索引。
[*]遍历数组：借助 for 循环从 low 到 high - 1 遍历数组。若当前元素 arr 小于等于基准值 p，就把 i 加 1，而且调用 change 函数将 arr 和 arr 交换，以此把小于等于基准值的元素移到数组左边。
[*]更新基准值位置：遍历结束后，把基准值 arr 和 arr 交换，让基准值处于正确位置。
[*]返回基准值索引：返回基准值的终极位置 i + 1。
[*]递归终止条件：当 low 小于 high 时，意味着子数组中至少有两个元素，需要举行排序。
[*]分区操纵：调用 paiXu 函数对数组举行分区，得到基准值的索引 pi。
[*]递归排序：对基准值左边的子数组 arr 和右边的子数组 arr 分别递归调用 quickSort 函数举行排序。
#include <stdio.h>
//实现值的互换
void change(int *a, int *b)
{
int temp = *a;
*a = *b;
*b = temp;
}
//实现分区函数
//将数组划分为两个部分
int paiXu(int arr[], int low, int high)
{
int p = arr;//这里选择最后一共元素作为基准
int i = low - 1;//指向比基准值小的最后一共元素的索引
for (int j = low; j < high; j++)
{
if (arr <= p)//如果当前的元素小于基准值
{
i++;//将小于基准值的索引++
change(&arr, &arr);//将当前元素交换到左边
}
}
change(&arr, &arr);//更新基准元素的位置
return (i + 1);//返回基准值的位置
}
void quickSort(int arr[], int low, int high)
{
if(low < high)
{
//分区得到基准值的索引
int pi = paiXu(arr, low, high);
quickSort(arr, low, pi - 1);//对基准值的左边进行排序
quickSort(arr, pi + 1, high);//对基准值的右边进行排序
}
}
int main(int argc, char const *argv[])
{
int arr[] = {6,9,1,7,3,2,5,8,4};
int n = sizeof(arr)/sizeof(arr);
quickSort(arr, 0, n);
for(int i = 0; i < n ; i++)
{
printf("%d",arr);
}
printf("\n");
return 0;
}
运行效果：
https://i-blog.csdnimg.cn/direct/715fa6037ea64a03854c1016eac64f36.png
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]