[問題] 關於Quick Sort的問題
遇到的問題： (題意請描述清楚)
寫了一段Quicl Sort的程式，在排序時看起來只排了左邊(小於"旗標"的部份>，而大於
旗標的部份都沒有正確排序. 看了很久還是沒有進展，只好上來請教高手了. PS:旗標位
置設於最左邊第一個數值
演算法主要由兩部份構成
1:由Partition()找出小於旗標的數，把旗標SWAP到數列中正確的位置, 再把位置
return出來.
2:QuickSort()利用Partition()找出旗標的swap位置後，再分別對旗標的左邊及右邊
做Sorting.
程式碼如下:
#include <stdio.h>
#include <stdlib.h>
#define MAX 7
#define SWAP(x,y) {unsigned short t; t = x; x = y; y = t;}
void QuickSort(unsigned short array[],int , int );
int Partition(unsigned short array[], int , int );
unsigned short array[MAX]={25,70,90,20, 80,70,10};
int main(void)
{
QuickSort(array,0,MAX-1);
return 0;
}
int Partition(unsigned short *array,int left,int right)
{
int i=0,j=0;
//middle=(left+right)/2;
//SWAP(array[left],array[middle]);
i=left+1;
j=right;
while(1)
{
for(;i<=j;i++)
if(array[i]>=array[left]) break;
for(;i<=j;j--)
if(array[j]<array[left]) break;
if(i<j)
{
SWAP(array[i],array[j]);
}
else
{
SWAP(array[left],array[j]);
return j;
}
}
}
void QuickSort(unsigned short *array, int left, int right)
{
int k;
if(right>left)
{
k=Partition(array, left, right);
QuickSort(array, left, k-1);
QuickSort(array, k+1, right);
}
}
開發平台： (例: VC++ or gcc/g++ or Dev-C++, Windows or Linux)
Keil C 平台
有問題的code： (請善用置底文標色功能)
同上所述，目前已確認 Partition()的function正常，應該是遞迴的部份出問題.
在右邊sorting好的情況下 ==> k=1 ==> 使得紅色部份 k+1 (left)=2, right=0, 所以
跳出遞迴. 這是有問題的地方。 但要如何修改才好呢 ?
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 122.124.1.15
→
12/05 02:52, , 1F
12/05 02:52, 1F
推
12/05 03:17, , 2F
12/05 03:17, 2F
→
12/05 04:10, , 3F
12/05 04:10, 3F
→
12/05 04:11, , 4F
12/05 04:11, 4F
→
12/05 04:14, , 5F
12/05 04:14, 5F
推
12/05 10:02, , 6F
12/05 10:02, 6F
→
12/05 11:26, , 7F
12/05 11:26, 7F
→
12/05 11:27, , 8F
12/05 11:27, 8F
推
12/05 13:43, , 9F
12/05 13:43, 9F