小甲鱼 排序算法 快速排序
程序员文章站
2022-03-02 08:13:23
...
小甲鱼 排序算法 快速排序
#include <stdio.h>
//交换
void swap(int k[], int low, int high)
{
int temp;
temp = k[low];
k[low] = k[high];
k[high] = temp;
}
//计算基准点的函数
//把将所有小于基准点的所有元素放在基准点的左边
//把将所有大于基准点的所有元素放在基准点的右边
int Partition(int k[], int low, int high)
{
//low和high这里是指针
int point;
point = k[low];//基准点定位第一个元素
//当退出这个循环时,low和high接触在一块
while (low < high)
{
//比较右边
while (low < high && k[high] >= point)
{
high--;
}
//比较右边,如果比基准点少,把基准点传过去,把小的数传进来
swap(k, low, high);//需要移动,交换,low相当于point基准点
//比较左边
while (low < high && k[low] <= point)
{
low++;//指向下一个
}
//如果出了循环,出现左边的大于基准点,该与基准点进行交换
swap(k, low, high);//需要移动,交换
}
return low;//返回中间点
}
//low起始位置,high结束位置
void QSort(int k[], int low, int high)
{
int point;//基准点
//左边的指针和右边的指针都会移动,当指针重叠的时候,进行一轮比较了
if (low < high)
{
point = Partition(k, low, high);//基准点的定位
QSort(k, low, point-1);//对左边进行递归调用
QSort(k, point+1, high);//对右边进行递归调用
}
}
//外层函数,封装
void QuickSort(int k[], int n)
{
//实际的操作函数
//参数:数组,初始位置,最大元素的位置
QSort(k, 0, n-1);
}
int main(void)
{
int i, a[10] = {5, 2, 6, 0, 3, 9, 1, 7, 4, 8};
QuickSort(a, 10);
printf("排序后的结果是:");
for(i = 0; i < 10; i++)
{
printf("%d", a[i]);
}
printf("\n\n");
return 0;
}