Re: [問題] QuickSort的問題
看板C_and_CPP (C/C++)作者AffogatoDog (秋天的風)時間16年前 (2010/03/04 23:39)推噓6(6推 0噓 11→)留言17則, 3人參與討論串2/2 (看更多)
我了解了
非常謝謝大家的幫助!
不過這邊有另外一個問題
我改寫了一下中間兩個往左右邊找值的while迴圈寫法
把中間的一個避免i,j跑過頭的判斷式去掉
void QuickSort(int A[], int left, int right)
{
int i, j,temp;
i = left;
j = right;
//指標設定於左邊起始點，即 A[left]
if(i < j)
{
while(i<j) //當i在j左方時
{
while(A[++i] < A[left])// i由左向右找大於A[left]者
{
/*
if(i> MAX-2)
break;
*/
}
while(A[j] >A[left]) // j由右向左找小於A[left]者
{
j--;
/*
if(j< 1)
break;
*/
}
if(i < j)
{
//交換A[i]與A[j]
temp = A[i];
A[i] = A[j];
A[j] = temp;
PrintQuickSort(A, MAX);
}
}
//交換A[left]與A[j]
temp=A[j];
A[j]=A[left];
A[left]=temp;
PrintQuickSort(A, MAX);
QuickSort(A, left, j-1); // 對左邊進行遞迴
QuickSort(A, j+1, right); // 對右邊進行遞迴
}
}
似乎是不會出問題
但理論上i往右找值的時候若是找不到比A[left]大的
或是 j往左找值的時候找不到比 A[left]小的
難道while不會使i,j超過原本array的範圍嗎?
甚至是成為無窮迴圈?
試過都用一樣的十個數，但似乎不會發生上述的狀況
是為什麼呢?
※ 引述《AffogatoDog (秋天的風)》之銘言：
: ( *[1m *[m 為色碼，可以按 Ctrl+V 預覽會顯示的顏色 )
: ( 未必需要依照此格式，文章條理清楚即可 )
: 遇到的問題： (題意請描述清楚)
: QuickSort當有重複值時出問題，程式停住
: 希望得到的正確結果：
: 希望QuickSort能跑出正確的排序結果
: 程式跑出來的錯誤結果：
: 多次的試驗發現，當10個數中沒有相同值的時候程式可以跑
: 但如果有相同值就不動了= =
: 找了很久卻搞不清楚問題出在哪裡....
: 希望版友們幫忙解惑...
: 開發平台： (例: VC++ or gcc/g++ or Dev-C++, Windows or Linux)
: C++
: 有問題的code： (請善用置底文標色功能)
: #include <iostream>
: #include <time.h>
: #define MAX 10
: int A[10]={0};
: void RandomNum() //產生10個亂數值之副程式
: {
: int i;
: srand((unsigned)time(NULL)); //亂數值初始化
: printf("產生10個亂數值：");
: for (i = 0; i < MAX; i++)
: {
: A[i] = rand() % 90+10; //產生10~99的整數亂數值
: printf("%4d",A[i]);
: }
: }
: void QuickSort(int A[], int left, int right)
: {
: int i, j,temp,pivot;
: //s = A[(left+right)/2];
: i = left;
: j = right;
: pivot=A[left]; //指標設定於左邊起始點
: if(i < j)
: {
: while(i<j) //當i在j左方時
: {
: while(A[i] < pivot)
: {
: i++; // i向右找大於pivot者
: if(i> MAX-2)
: break;
: }
: while(A[j] >pivot)
: {
: j--; // j向左找小於pivot者
: if(j< 1)
: break;
: }
: if(i < j)
: {
: //交換A[i]與A[j]
: temp = A[i];
: A[i] = A[j];
: A[j] = temp;
: }
: }
: //交換pivot與A[j]
: temp=A[j];
: A[j]=pivot;
: pivot=temp;
: QuickSort(A, left, j-1); // 對左邊進行遞迴
: QuickSort(A, j+1, right); // 對右邊進行遞迴
: }
: }
: void PrintQuickSort(int A[], int n)
: {
: printf("排序10個亂數值：");
: for (int i = 0; i < n; i++)
: {
: printf("%4d",A[i]);
: }
: }
: int main() //主程式
: {
: RandomNum(); //呼叫產生10個亂數值的副程式
: printf("\n");
: QuickSort(A, 0, MAX-1); //呼叫快速排序法的副程式
: PrintQuickSort(A, MAX); //呼叫快速排序後的結果之副程式
: printf("\n");
: //system("PAUSE");
: return(0);
: }
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.122.76.177
※ 編輯: AffogatoDog 來自: 140.122.76.177 (03/04 23:43)
推
03/04 23:52, , 1F
03/04 23:52, 1F
→
03/04 23:56, , 2F
03/04 23:56, 2F
→
03/04 23:57, , 3F
03/04 23:57, 3F
推
03/05 00:00, , 4F
03/05 00:00, 4F
→
03/05 00:01, , 5F
03/05 00:01, 5F
→
03/05 00:01, , 6F
03/05 00:01, 6F
→
03/05 00:01, , 7F
03/05 00:01, 7F
推
03/05 00:01, , 8F
03/05 00:01, 8F
→
03/05 00:02, , 9F
03/05 00:02, 9F
→
03/05 00:04, , 10F
03/05 00:04, 10F
→
03/05 00:05, , 11F
03/05 00:05, 11F
→
03/05 00:05, , 12F
03/05 00:05, 12F
推
03/05 00:18, , 13F
03/05 00:18, 13F
我已經沒有用pivot囉
這是1,2,3...10 所跑出來的結果
沒有異常
所以我覺得好奇怪
產生10個亂數值： 1 2 3 4 5 6 7 8 9 10
left=0,j=0
交換A[left]與A[j]
交換1與1
排序10個亂數值： 1 2 3 4 5 6 7 8 9 10
left=1,j=1
交換A[left]與A[j]
交換2與2
排序10個亂數值： 1 2 3 4 5 6 7 8 9 10
left=2,j=2
交換A[left]與A[j]
交換3與3
排序10個亂數值： 1 2 3 4 5 6 7 8 9 10
left=3,j=3
交換A[left]與A[j]
交換4與4
排序10個亂數值： 1 2 3 4 5 6 7 8 9 10
left=4,j=4
交換A[left]與A[j]
交換5與5
排序10個亂數值： 1 2 3 4 5 6 7 8 9 10
left=5,j=5
交換A[left]與A[j]
交換6與6
排序10個亂數值： 1 2 3 4 5 6 7 8 9 10
left=6,j=6
交換A[left]與A[j]
交換7與7
排序10個亂數值： 1 2 3 4 5 6 7 8 9 10
left=7,j=7
交換A[left]與A[j]
交換8與8
排序10個亂數值： 1 2 3 4 5 6 7 8 9 10
left=8,j=8
交換A[left]與A[j]
交換9與9
排序10個亂數值： 1 2 3 4 5 6 7 8 9 10
排序10個亂數值： 1 2 3 4 5 6 7 8 9 10
請按任意鍵繼續 . . .
※ 編輯: AffogatoDog 來自: 140.122.76.177 (03/05 00:23)
推
03/05 00:26, , 14F
03/05 00:26, 14F
→
03/05 00:28, , 15F
03/05 00:28, 15F
推
03/05 00:30, , 16F
03/05 00:30, 16F
→
03/05 00:31, , 17F
03/05 00:31, 17F
※ 編輯: AffogatoDog 來自: 140.122.76.177 (03/05 00:46)
討論串 (同標題文章)
C_and_CPP 近期熱門文章
PTT數位生活區 即時熱門文章
