在线观看不卡亚洲电影_亚洲妓女99综合网_91青青青亚洲娱乐在线观看_日韩无码高清综合久久

鍍金池/ 問答/C  C++/ 快速排序的partition函數(shù)中判斷條件為什么不能用low！=high進行循環(huán)

快速排序的partition函數(shù)中判斷條件為什么不能用low！=high進行循環(huán)，輸出時cmd卡住

#include<iostream>
#include<ctime>
#include<cstdlib>
using namespace std;

}
int main()
{
    int num[11];
    srand(time(0));
    for(int i=1;i<=10;i++)
        num[i]=rand()%100+1;
    for(int i=1;i<=5;i++)
        cout<<" "<<num[i];
    int low=1,high=5;
    num[0]=num[1];
//問什么不能用low!=high做判斷條件
    while(low!=high)
    {
        while(low!=high&&num[high]>=num[0])
            high--;
        num[low]=num[high];
        if(low==high)
        while(low!=high&&num[low]<=num[0])
            low++;
        num[high]=num[low];
    }
    num[low]=num[0];
    cout<<endl<<num[0]<<endl;
    for(int i=1;i<=10;i++)
        cout<<" "<<num[i];
    return 0;
}
回答
編輯回答
風清揚

你先不用5個數(shù)，我給你個測試數(shù)據(jù):[2,1,3]
你自己在紙上跟著程序單步跑一跑你就明白你問題出來在哪了。

2018年5月20日 03:37
編輯回答
夏木
#include<iostream>
#include<ctime>

using namespace std;

int partition(int a[], int low, int high)
{
  int key = a[low];
  while (low != high)
  {
    while (low != high && a[high] >= key) high--;
    a[low] = a[high];
    //if(low==high) 問題所在！
    while (low != high && a[low] <= key) low++;
    a[high] = a[low];
  }
  a[low] = key;
  return low;
}

void qs(int a[], int low, int high)
{
  if (low < high)
  {
    int mid = partition(a, low, high);
    qs(a, low, mid - 1);
    qs(a, mid + 1, high);
  }
}

int main()
{
  int num[11];
  srand(time(NULL));
  for (int i = 1; i <= 10; i++)
    num[i] = rand() % 100 + 1;
  for (int i = 1; i <= 10; i++)
    cout << " " << num[i];
  cout << endl;
  qs(num, 1, 10);
  for (int i = 1; i <= 10; i++)
    cout << " " << num[i];
  return 0;
}

幫你修改了一下，封裝成了partition函數(shù)，順手補全了整個快排算法╰(￣▽￣)╭

先回答你的問題，當然是可以用low != high這樣的判斷，但是不推薦，如果一開始傳入的參數(shù)比如(10, 1)，雖然滿足條件，但明顯會死循環(huán)，最好寫成low<=high這樣語義性很強的表達式

代碼出問題的地方我標了出來，你想想嘛：

  1. 外層while要求low!=high
  2. while內(nèi)部要求low==high
  3. 2的要求導致low得不到更新，low永遠不可能與high相等，這就造成了死循環(huán)
2018年8月24日 23:37