排序算法-快速排序
描述：
- 基准值选择：选取数组的最后一个元素
arr[high]作为基准值p。 - 初始化索引：
i初始化为low - 1，其作用是指向比基准值小的最后一个元素的索引。 - 遍历数组：借助
for循环从low到high - 1遍历数组。若当前元素arr[j]小于等于基准值p，就把i加 1，并且调用change函数将arr[i]和arr[j]交换，以此把小于等于基准值的元素移到数组左边。 - 更新基准值位置：遍历结束后，把基准值
arr[high]和arr[i + 1]交换，让基准值处于正确位置。 - 返回基准值索引：返回基准值的最终位置
i + 1。 - 递归终止条件：当
low小于high时，意味着子数组中至少有两个元素，需要进行排序。 - 分区操作：调用
paiXu函数对数组进行分区，得到基准值的索引pi。 - 递归排序：对基准值左边的子数组
arr[low...pi - 1]和右边的子数组arr[pi + 1...high]分别递归调用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[high];//这里选择最后一共元素作为基准int i = low - 1;//指向比基准值小的最后一共元素的索引for (int j = low; j < high; j++){if (arr[j] <= p)//如果当前的元素小于基准值{i++;//将小于基准值的索引++change(&arr[i], &arr[j]);//将当前元素交换到左边}}change(&arr[i + 1], &arr[high]);//更新基准元素的位置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[0]);quickSort(arr, 0, n);for(int i = 0; i < n ; i++){printf("%d ",arr[i]);}printf("\n");return 0;
}
运行结果：
