这个非递归快速排序有一步没看懂，求教。解决思路

这个非递归快速排序有一步没看懂，求教。
下面是从网上下载的程序，有一步没看懂；

#include "stdafx.h"
#include "stdio.h"
struct node
{
 int min;
 int max;
};
void fun(int min,int max,int a[])
{
 int key = a[min];
 int i = min;
 int j = max;
 int temp;
    struct node Stack[100];
    int top = 0;
    Stack[top].min = min;
    Stack[top].max = max;
 while(top>-1)
 {
    
    i = min = Stack[top].min;
    j = max = Stack[top].max;
    top--;

    key = a[min];
    while(i<j)
    {
         while((i<j) && (key <= a[j]))
         {j--;}
        if(i < j)
        {
          temp = a[i];a[i] = a[j];a[j] = temp;  
          i++;
        }
        while((i<j) && (key >= a[i]))
        {i++;}
       if(i < j)
       {
         temp = a[i];a[i] = a[j];a[j] = temp; 
         j--;
       } 
     }
    if(min < i-1)
    {
        top++;
        Stack[top].min = min;
        Stack[top].max = i-1;
    }
    if(max>i+1)
    {
        top++;
        Stack[top].min = i+1;
        Stack[top].max = max;
    }
 } 
}

int main(void)
{
 int i;
 int a[10] = {49,38,65,97,76,13,27,9,2,1}; 
 
 for(i=0;i<10;i++)
  printf(" %d   ",a[i]);
 printf("\n");
   fun(0,9,a);
 for(i=0;i<10;i++)
  printf(" %d   ",a[i]);
 printf("\n");
 return 0;
}

我想问最外层的while里面的两个if

   

if(min < i-1)
    {
        top++;
        Stack[top].min = min;
        Stack[top].max = i-1;
    }
    if(max>i+1)
    {
        top++;
        Stack[top].min = i+1;
        Stack[top].max = max;
    }

我总觉得这两个if只用一个才行，是非此即彼的关系，但是实际好像不是，有时候上一个if保存着stack[0]的值，下一个if保存着stack[1]的值，如果是这样的话，循环到这一步时
    

i = min = Stack[top].min;
    j = max = Stack[top].max;

该用哪个呀，是用stack[0]还是stack[1]呀?我对这两个if为什么要用min < i-1与max>i+1也没有明白

请大家指教。
[解决办法]
一趟排序完成，min和max区间内的数据被分成2部分，i是分界线。
两个if分别判断左边和右边的数据个数是否大于1个。
大于的话就把对应部分的2个边界压入栈，继续排序。
[解决办法]

引用:

上面的代码有点乱，我再发一次。

   

 i = min = Stack[top].min;
    j = max = Stack[top].max;

该用那个if里的stack[top]值呢？

假设数组下标从0到9，十个数据
刚开始栈中有整个数组的上下边界。（0， 9）
while循环开始，
取出第一组数据，开始排序。这时，栈空了
第一次排序完成，假设i的值是5
这时候第一个if把 （0， 4）压入栈，第二个if把（6， 9）压入栈。
回到while循环处，
第二次取数据，取的是 （6， 9）的一组，栈中还有（0， 4）一组
栈先进后出，所以取的是后面入栈的部分。
对（6，9）排序
。。。。
直到栈空，排序完成

[解决办法]
代码功能归根结底不是别人帮自己看或讲解或注释出来的；而是被自己静下心来花足够长的时间和精力亲自动手单步或设断点或对执行到某步获得的中间结果显示或写到日志文件中一步一步分析出来的。
提醒：再牛×的老师也无法代替学生自己领悟和上厕所！

单步调试和设断点调试是程序员必须掌握的技能之一。

[解决办法]
看看数据结构先！理解理解栈

查看更多 下一篇