排序算法-快速排序

 描述：

• 基准值选择：选取数组的末了一个元素 arr[high] 作为基准值 p。
  
• 初始化索引：i 初始化为 low - 1，其作用是指向比基准值小的末了一个元素的索引。
  
• 遍历数组：借助 for 循环从 low 到 high - 1 遍历数组。若当前元素 arr[j] 小于等于基准值 p，就把 i 加 1，而且调用 change 函数将 arr 和 arr[j] 交换，以此把小于等于基准值的元素移到数组左边。
  
• 更新基准值位置：遍历结束后，把基准值 arr[high] 和 arr[i + 1] 交换，让基准值处于正确位置。
  
• 返回基准值索引：返回基准值的终极位置 i + 1。
  
• 递归终止条件：当 low 小于 high 时，意味着子数组中至少有两个元素，需要举行排序。
  
• 分区操纵：调用 paiXu 函数对数组举行分区，得到基准值的索引 pi。
  
• 递归排序：对基准值左边的子数组 arr[low...pi - 1] 和右边的子数组 arr[pi + 1...high] 分别递归调用 quickSort 函数举行排序。
  

1. #include <stdio.h>
2. //实现值的互换
3. void change(int *a, int *b)
4. {
5.     int temp = *a;
6.     *a = *b;
7.     *b = temp;
8. }
10. //实现分区函数
11. //将数组划分为两个部分
12. int paiXu(int arr[], int low, int high)
13. {
14.     int p = arr[high];//这里选择最后一共元素作为基准
15.     int i = low - 1;//指向比基准值小的最后一共元素的索引
16.     for (int j = low; j < high; j++)
17.     {
18.         if (arr[j] <= p)//如果当前的元素小于基准值
19.         {
20.             i++;//将小于基准值的索引++
21.             change(&arr[i], &arr[j]);//将当前元素交换到左边
22.         }
23.     }
24.     change(&arr[i + 1], &arr[high]);//更新基准元素的位置
25.     return (i + 1);//返回基准值的位置
26. }
28. void quickSort(int arr[], int low, int high)
29. {
30.     if(low < high)
31.     {
32.         //分区得到基准值的索引
33.         int pi = paiXu(arr, low, high);
34.         quickSort(arr, low, pi - 1);//对基准值的左边进行排序
35.         quickSort(arr, pi + 1, high);//对基准值的右边进行排序
36.     }
37. }
39. int main(int argc, char const *argv[])
40. {
41.     int arr[] = {6,9,1,7,3,2,5,8,4};
42.     int n = sizeof(arr)/sizeof(arr[0]);
44.     quickSort(arr, 0, n);
46.     for(int i = 0; i < n ; i++)
47.     {
48.         printf("%d  ",arr[i]);
49.     }
50.     printf("\n");
51.     return 0;
52. }

复制代码

运行效果：

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。