## 麻烦高手帮忙看个问题，关于快速排序法

xinzaibing 发布于 2012/04/16 15:19

#include <stdio.h>
2
3 static void swap(int *a, int *b)
4 {
5 |   int tmp = *a;
6 |   *a = *b;
7 |   *b =tmp;
8 }
9
10 static int findPivot(int *a, int left, int right)
11 {
12 |   int center = (int)(left+right)/2;
13
14 |   if(a[left]>a[right])
15 |   |   swap(&a[left], &a[right]);
16 |   if(a[center]>a[right])
17 |   |   swap(&a[center], &a[right]);
18 |   if(a[center]<a[left])
19 |   |   swap(&a[center], &a[left]);
20
21 |   swap(&a[center], &a[right-1]);
22
23 |   return a[right-1];
24 }
25
26 void quickSort(int *a, int left, int right)
27 {
28 |   if(left<right)
29 |   {
30 |   |   int i=left,j=right-1;
31
32 |   |   int pivot = findPivot(a, left, right);
33 |   |   for(;;)
34 |   |   {
35
36 |   |   |   while(a[++i]<pivot);
37 |   |   |   while(a[--j]>pivot);
38 |   |   |   if(i<j)
39 |   |   |   |   swap(&a[i], &a[j]);
40 |   |   |   else
41 |   |   |   |   break;
42 |   |   }
43 |   |
44 |   |   swap(&a[i], &a[right-1]);
45
46 |   |   quickSort(a, left, i-1);
47 |   |   quickSort(a, i+1, right);
48
49 |   }
50
51 }
52
53 int main(int argc, char** argv)
54 {
55 |   int a[] = {23,545,568,8985,4,1,567,0,8976,35423,1};
56 |   printf("%s\n", "Before quick Sort");
57 |   int i = 0;
58 |   for(i=0;i<sizeof(a)/sizeof(int);i++)
59 |   |   printf("%d\t", a[i]);
60
61 |   printf("\n");
62
63 |   quickSort(a, 0, sizeof(a)/sizeof(int)-1);
64 |
65 |   printf("%s\n", "After quick Sort"); for(i=0;i<sizeof(a)/sizeof(int);i++)
68 |   |   printf("%d\t", a[i]);
69
70 |   printf("\n");
71 |   return 0;
72 }

0
FT。你竟然用递归！！！！！本来想帮你改的。 帮你编辑了代码，跑到quick_sort函数时才发现。我马上写个和你这个比较贴近的算法。你自己对比一下。
0

P.S. 我当年调了大约7个小时

0

```int push_buf[1024];
int push_sp = 0;
#define PUSH(a) do{push_buf[push_sp++] = a;}while(0)
#define POP(a) do {a = push_buf[--push_sp];}while (0)
#define EMPTY() (push_sp == 0)

void QuickSort(int data[], int left, int right)
{
register int temp = data[left];
int p = left;
int i = left, j = right;
PUSH(left);
PUSH(right);
while (!EMPTY()){
while (i <= j){
while (data[j] >= temp && j >= p ){
j--;
}
if(j >= p){
data[p] = data[j];
p = j;
}
while (data[i] <= temp && i <= p){
i++;
}
if (i <= p){
data[p] = data[i];
p = i;
}
}
data[p] = temp;
if(p-left > 1){
PUSH(left);
PUSH(p-1);
}
if(right - p > 1){
PUSH(p+1);
PUSH(right);
}
POP(right);
POP(left);
j = right;
i = left;
p = left;
temp = data[left];
}
}```

0