c 快速排序总是不对
本帖最后由 march_on 于 2013-04-25 22:58:16 编辑
34 void quick_sort( int* array, int length)
35 {
36 assert( array != NULL );
37 assert( length > 1);
38 sort( array, 0, length );
39 }
40
41
42 void sort(int* array, int begin, int end)
43 {
44 assert( array != NULL );
45 if( begin >= end )
46 return;
47
48 int pivot = partition( array, begin, end);
49
50 sort( array, begin, pivot-1 );
51 sort( array, pivot+1, end );
52
53 }
54
55 int partition( int* array, int begin, int end )
56 {
57 int key = array[begin];
58
59 int i = begin;
60 int j = end;
61
62 while( i < j )
63 {
64 while( array[++i] < key && i < j ) ;
65 while( array[--j] > key && i < j ) ;
66
67 if( i < j )
68 {
69 int tmp = array[i];
70 array[i] = array[j];
71 array[j] = tmp;
72 }
73 }
74
75 array[begin] = array[j];
76 array[j] = key;
77 int k;
78 for( k = 0; k < 20; ++k )
79 printf("%d ",array[k]);
80 printf("\n");
81 return j;
82 }
既然你的sort约定是排[begin,end)（半开半闭区间），那么你这里应该用begin,pivot来调用而不是begin,pivot-1。
[解决办法]
while(array[--j]>key&&i<j)这里出问题了，arr[end]没比较，j直接--了，意思是比较arr[end]的前一个数。
将j = end + 1;试试
