标题: C语言输出快速排序递归算法隐含递归树的后序遍历序列程序和示意图 [打印本页]
作者: Anza    时间: 2024-1-15 21:33
标题: C语言输出快速排序递归算法隐含递归树的后序遍历序列程序和示意图

  1. #define _CRT_SECURE_NO_WARNINGS
  2. #include<stdio.h>

  4. void QSort(int L[100], int low, int high);
  5. int Partition(int L[100], int low, int high);

  7. int main()
  8. {
  9.         int n;
  10.         int i;
  11.         int L[100] = { 0 };
  12.         scanf("%d", &n);
  13.         for (i = 1; i <= n; i++)
  14.                 scanf("%d", &L[i]);
  15.         QSort(L, 1, n);
  16.         return 0;
  17. }

  19. void QSort(int L[100], int low, int high)
  20. {
  21.     //排序的时候可以是小于，因为最后一个数不用再处理，但是要输出，
  22.     //故尽管不处理，也一定要进入if条件判断，来打印这个值，也就是一定要low <= high
  23.         if (low <= high)
  24.         {
  25.     //这里的理解和二叉树的遍历思路是一样的，也就是先打印左边的枢轴量，
  26.     //再打印右边的枢轴量，最后打印根的值
  27.                 int pivotloc = Partition(L, low, high);
  28.                 QSort(L, low, pivotloc - 1);//可以理解为打印左边的枢轴量
  29.                 QSort(L, pivotloc + 1, high);//打印右边的值
  30.                 printf("%d ", L[pivotloc]);//打印根的值
  31.         }
  32. }

  34. int Partition(int L[100], int low, int high)
  35. {
  36.         L[0] = L[low];
  37.         int pivotkey = L[low];
  38.         while (low < high)
  39.         {
  40.                 while (low < high && L[high] >= pivotkey)
  41.                         high--;
  42.                 L[low] = L[high];
  43.                 while (low < high && L[low] <= pivotkey)
  44.                         low++;
  45.                 L[high] = L[low];
  46.         }
  47.         L[low] = L[0];
  48.         return low;
  49. }
复制代码

vc++代码工程: 输出快速排序递归算法隐含递归树的后序遍历序列.7z (1.84 MB, 下载次数: 4)




欢迎光临 (http://www.51hei.com/bbs/) Powered by Discuz! X3.1