C语言输出快速排序递归算法隐含递归树的后序遍历序列程序和示意图

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
void QSort(int L[100], int low, int high);
int Partition(int L[100], int low, int high);
int main()
{
int n;
int i;
int L[100] = { 0 };
scanf("%d", &n);
for (i = 1; i <= n; i++)
scanf("%d", &L[i]);
QSort(L, 1, n);
return 0;
}
void QSort(int L[100], int low, int high)
{
//排序的时候可以是小于,因为最后一个数不用再处理,但是要输出,
//故尽管不处理,也一定要进入if条件判断,来打印这个值,也就是一定要low <= high
if (low <= high)
{
//这里的理解和二叉树的遍历思路是一样的,也就是先打印左边的枢轴量,
//再打印右边的枢轴量,最后打印根的值
int pivotloc = Partition(L, low, high);
QSort(L, low, pivotloc - 1);//可以理解为打印左边的枢轴量
QSort(L, pivotloc + 1, high);//打印右边的值
printf("%d ", L[pivotloc]);//打印根的值
}
}
int Partition(int L[100], int low, int high)
{
L[0] = L[low];
int pivotkey = L[low];
while (low < high)
{
while (low < high && L[high] >= pivotkey)
high--;
L[low] = L[high];
while (low < high && L[low] <= pivotkey)
low++;
L[high] = L[low];
}
L[low] = L[0];
return low;
}
#define _CRT_SECURE_NO_WARNINGS #include<stdio.h> void QSort(int L[100], int low, int high); int Partition(int L[100], int low, int high); int main() { int n; int i; int L[100] = { 0 }; scanf("%d", &n); for (i = 1; i <= n; i++) scanf("%d", &L[i]); QSort(L, 1, n); return 0; } void QSort(int L[100], int low, int high) { //排序的时候可以是小于,因为最后一个数不用再处理,但是要输出, //故尽管不处理,也一定要进入if条件判断,来打印这个值,也就是一定要low <= high if (low <= high) { //这里的理解和二叉树的遍历思路是一样的,也就是先打印左边的枢轴量, //再打印右边的枢轴量,最后打印根的值 int pivotloc = Partition(L, low, high); QSort(L, low, pivotloc - 1);//可以理解为打印左边的枢轴量 QSort(L, pivotloc + 1, high);//打印右边的值 printf("%d ", L[pivotloc]);//打印根的值 } } int Partition(int L[100], int low, int high) { L[0] = L[low]; int pivotkey = L[low]; while (low < high) { while (low < high && L[high] >= pivotkey) high--; L[low] = L[high]; while (low < high && L[low] <= pivotkey) low++; L[high] = L[low]; } L[low] = L[0]; return low; }
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>

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

int main()
{
        int n;
        int i;
        int L[100] = { 0 };
        scanf("%d", &n);
        for (i = 1; i <= n; i++)
                scanf("%d", &L[i]);
        QSort(L, 1, n);
        return 0;
}

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

int Partition(int L[100], int low, int high)
{
        L[0] = L[low];
        int pivotkey = L[low];
        while (low < high)
        {
                while (low < high && L[high] >= pivotkey)
                        high--;
                L[low] = L[high];
                while (low < high && L[low] <= pivotkey)
                        low++;
                L[high] = L[low];
        }
        L[low] = L[0];
        return low;
}

 

版权声明:本文内容来源于网络搜集无法获知原创作者,仅供个人学习用途,若侵犯到您的权益请联系我们及时删除。邮箱:1370723259@qq.com

发表评论

Slide to verify