归并，快速，堆排序~

1 void adjust(int i,int n)//调整为小顶堆
2 {
3 int j &＃61; i,k;
4 a[0] &＃61; a[i];
5 j &＃61; 2*i;
6 while(j<&＃61;n)
7 {
8 if(j a[j&＃43;1])//左右孩子结点的最小值
9 j&＃43;&＃43;;
10 if(a[0]>a[j])//如果比最小值大
11 {
12 a[i] &＃61; a[j];//当前最小值孩子结点上移 i变为当前j值 继续与下面比较
13 i &＃61; j;
14 j &＃61; 2*j;
15 }
16 else
17 break;
18 }
19 a[i] &＃61; a[0];//放在合适位置
20 }
21 void heapsort(int n)
22 {
23 int i,t;
24 for(i &＃61; n/2 ; i>0 ; i--)//最初调整为堆
25 adjust(i,n);
26 for(i &＃61; n ; i>1 ; i--)//依次交换根节点和尾结点
27 {
28 t &＃61; a[1];
29 a[1] &＃61; a[i];
30 a[i] &＃61; t;
31 adjust(1,i-1);
32 }
33 }

1 /*
2 一趟快速排序的算法是&＃xff1a; 　　
3 找一个记录&＃xff0c;以它的关键字作为“枢轴”&＃xff0c;
4 凡其关键字小于枢轴的记录均移动至该记录之前&＃xff0c;
5 反之&＃xff0c;凡关键字大于枢轴的记录均移动至该记录之后。
6 A[0] A[1] A[2] A[3] A[4] A[5] A[6]&＃xff1a; 　　
7 49 38 65 97 76 13 27 　　 8 进行第一次交换后&＃xff1a;
9 27 38 65 97 76 13 49 　　
10 进行第二次交换后&＃xff1a;
11 27 38 49 97 76 13 65 　　
12 进行第三次交换后&＃xff1a;27 38 13 97 76 49 65 　　　
13 进行第四次交换后&＃xff1a;27 38 13 49 76 97 65
14 */
15 int fqsort(int low,int high,int a[])
16 {
17 int i &＃61; low,j &＃61; high,k &＃61; a[low];//找一个比较的点
18 while(i<j)
19 {
20 while(i//从右向左移直至找到比k大的数
21 j--;
22 a[i] &＃61; a[j];//比这个数大的放左边
23 while(i&＃61;k)//从左向右移直至找到比k小的数
24 i&＃43;&＃43;;
25 a[j] &＃61; a[i];//比这个数大的放右边
26 }
27 a[i] &＃61; k;
28 return j;//j左右两边已经被k分割开 再把j&＃43;1当作右边一组的low j-1当作左边一组的high进行下一次的快排
29 }
30 void qsort(int low,int high,int a[])
31 {
32 int q;
33 if(low<high)
34 {
35 q &＃61; fqsort(low,high,a);//找到分割点
36 qsort(low,q-1,a);//左右两边进行快排
37 qsort(q&＃43;1,high,a);
38 }
39 }

1 void msort(int low,int mid,int high)//将两部分归并
2 {
3 int i,j,n1 &＃61; mid-low&＃43;1,n2 &＃61; high-mid,x[10001],y[10001];
4 for(i &＃61; 1 ; i <&＃61; n1 ; i&＃43;&＃43;)//存于两个数组中
5 x[i] &＃61; a[low&＃43;i-1];
6 for(i &＃61; 1 ; i <&＃61; n2 ; i&＃43;&＃43;)
7 y[i] &＃61; a[mid&＃43;i];
8 int k &＃61; low;
9 i &＃61; 1;
10 j &＃61; 1;
11 while(i<&＃61;n1&&j<&＃61;n2)//排序
12 {
13 if(x[i]<y[j])
14 a[k] &＃61; x[i&＃43;&＃43;];
15 else
16 a[k] &＃61; y[j&＃43;&＃43;];
17 k&＃43;&＃43;;
18 }
19 while(i<&＃61;n1)
20 a[k&＃43;&＃43;] &＃61; x[i&＃43;&＃43;];
21 while(j<&＃61;n2)
22 a[k&＃43;&＃43;] &＃61; y[j&＃43;&＃43;];
23 }
24 void merge(int low,int high)//二分递归合并
25 {
26 int mid;
27 if(low<high)
28 {
29 mid &＃61; (low&＃43;high)/2;
30 merge(low,mid);
31 merge(mid&＃43;1,high);
32 msort(low,mid ,high);
33 }
34 }