打算在学期结束之前（1月19日）看完，目前94页，总共六百页，不完全做习题及思考题（不细致考虑各种时间）。
之所以发表这个是公开一下，算是对自己的监督吧。以下进入正题
实现各种算法时都OK，在快速排序这里第一次遇到问题，算法出错，hoarePartition是快速排序中用到的一个比较古老的分块算法。
伪代码
HOARE-PARTITION(A,p,r)
{
x=A[p]
i=p-1
j=r+1
while(1)
{
do repeat j--
until A[j]<=x
repeat i++
until A[i]>=x
if i<j
then exchange A[i] and A[j]
else return j
}
}
思维比较清晰的算法，当同时找到坐标x两端的异常值时，左右互换
C代码
1 #include <stdio.h>
2
3 void RandomDoSort(int A[],int begin,int end);
4 int Hoare_Partition(int A[],int begin,int end);
5
6 void ChangeTwoInt(int* a,int* b);
7
8 void main()
9 {
10 int A[12]={13,19,9,5,12,8,7,4,21,2,6,11};
11 RandomDoSort(A,0,11);
12 for (int i=0;i<12;i++)
13 {
14 printf("%d\n",A[i]);
15 }
16 }
17
18
19 void RandomDoSort(int A[],int begin,int end)
20 {
21 int q=0;
22 if(begin<end)
23 {
24 q=Hoare_Partition(A,begin,end);
25 DoSort(A,begin,q-1);
26 DoSort(A,q+1,end);
27 }
28 }
29
30 int Hoare_Partition(int A[],int begin,int end)
31 {
32 int xtemp=A[begin];
33 int i=begin-1;
34 int j=end+1;
35 while (1)
36 {
37 j--;
38 if (A[j]<=xtemp)
39 {
40 while(A[i]<xtemp)
41 {
42 i++;
43 }
44 }
45 if (i<j)
46 {
47 ChangeTwoInt(&A[i],&A[j]);
48 }
49 else
50 {
51 return j;
52 }
53 }
54 }
55
56 void ChangeTwoInt(int* a,int* b)
57 {
58 int temp=*a;
59 *a=*b;
60 *b=temp;
61 }
最后结果出错，有一个数没排序上，睡觉去，明早起来调试解决这问题
其实问题并不出在Partition这个函数里，而是在Dosort函数里。上面这个Dosort函数简单地修改了之前另一个Partition搭配的Dosort，两者思想有细微区别。
先来看之前的Partition。
int Partition(int A[],int begin,int end) { int x=A[end]; int i=begin-1; int temp=0; for(int j=begin;j<=end-1;j++) { if(A[j]<x) { i++; temp=A[j]; A[j]=A[i]; A[i]=temp; } } temp=A[i+1]; //将坐标轴元素放在排序好的位置上 A[i+1]=A[end]; A[end]=temp; return i+1; }
再来看HoarePartition
int Hoare_Partition(int A[],int begin,int end) { int xtemp=A[begin]; int i=begin-1; int j=end+1; while (1) { j--; if (A[j]<=xtemp) { while(A[i]<xtemp) { i++; } } if (i<j) { ChangeTwoInt(&A[i],&A[j]); } else { return j; } } }
两者的区别是：前面那种在Partition过程中就将坐标轴元素放在排序好的位置上，自然在DOsort的迭代过程中不用再考虑该元素，但Hoare则没有这样做，在Hoare匹配的Dosort迭代时自然要将该元素也纳入迭代的考虑范围。
来看两个Dosort
之前那一种
void DoSort(int A[],int begin,int end) { int q=0; if(begin<end) { q=Partition(A,begin,end); DoSort(A,begin,q-1); //A[q]不需要再处理 DoSort(A,q+1,end); } }
Hoare对应的Dosort
void HoareDoSort(int A[],int begin,int end) { int q=0; if(begin<end) { q=Hoare_Partition(A,begin,end); DoSort(A,begin,q); //需要对A[q]再处理 DoSort(A,q+1,end); } }
以上。