花时间把所有的排序重新 写了一遍。。。。。（应该是认真写过一遍，学的时候根本就没写过）
写得时候才发现，理解不深刻。基本上 只是懂怎么做，不懂为什么。
把我写得记在这里，以后用得着了回来看看。
暂时就到这里吧，以后有时间，继续研究这些东西。在写出来。
三个O(n2)的算法
选择排序：
1 void SelectionSort(
int *a,
int n)
2 {
3 for(
int i=0;i<n;i++)
4 {
5 int lowindex = i;
6 for(
int j=i+1;j<n;j++)
7 if(a[j]<a[lowindex])lowindex=j;
8 swap(&a[i],&a[lowindex]);
//选择，比bubble交换次数少得多。
9 }
10 }
冒泡排序：
1 void Bubblesort(int *a,int n)
2 {
3 for(int i=0;i<n;i++)
4 for(int j=0;j<n-1;j++)
5 if(a[j]>a[j+1])swap(&a[j],&a[j+1]);
6 }
插入排序：
1 void insertsort(
int *a,
int n)
2 {
3 int i,j;
4 int tmp;
5 for(i = 1;i<n;i++)
6 {
7 tmp = a[i];
8 for(j=i;j>0&&tmp<a[j-1];j--)
9 {
10 a[j] = a[j-1];
//从后往前面数
11 }
12 a[j] = tmp;
// 1 2 3 5 6 7 4 ==> 1 2 3 4 5 6 7
13 }
14 }
下面几个高级的算法。。。 有些把我折腾的够惨。。。DEBUG 几个小时 才弄出来。 （鄙视自己。。）
希尔排序：
1 void shellsort(
int *a,
int n)
2 {
3 int tmp;
4 int i,j;
5 int gap;
//增量
6 for(gap=n/2;gap>0;gap/=2)
//增量为n/2
7 {
8 for(i=gap;i<n;i++)
9 {
10 tmp = a[i];
11 for(j =i;j>=gap&&tmp<a[j-gap];j-=gap)
//增量交换。
12 a[j] = a[j-gap];
13 a[j] = tmp;
14 }
15 }
16 }
归并排序：
1 void merge(
int *array,
int *tmp,
int start,
int center,
int end)
//合并的程序。
2 {
3 int i=0;
4 int arrayCount = end - start + 1;
5 int s = start;
6 int c = center;
7 int e = end;
//不损坏原来的变量
8 while(s<=c-1&&c<=e)
9 {
10 if(array[s]<=array[c])
11 tmp[i++] = array[s++];
12 else if(array[s]>=array[c])
13 tmp[i++] = array[c++];
14 }
15 while(s<=c-1)
16 tmp[i++] = array[s++];
17 while(c<=end)
18 tmp[i++] = array[c++];
19 for(i=start;i<arrayCount;i++)
20 array[i] = tmp[i-start];
21 }
22 void MergeSort(
int *a,
int *tmp,
int start,
int end)
23 {
24 int center;
25 if(start<end)
26 {
27 center = (start+end)/2 + 1;
//第二个部分的开始
28 MergeSort(a,tmp,start,center-1);
29 MergeSort(a,tmp,center,end);
30 merge(a,tmp,start,center,end);
31 }
32 }
归并的一个改进。。。。。改进不大 参照某本书上来的
1 void merge(int *array,int *tmp,int start,int center,int end)//合并的程序。
2 {
3 //第二个子串逆序复制。 不用判断是否处理完毕
4 int i,j,k;
5 for(i=start;i<center;i++)tmp[i]=array[i];
6 for(j=0;j<end-center+1;j++)tmp[end-j] = array[center+j];
7 for(i=start,j=end,k=start;k<=end;k++)
8 if(tmp[i]<=tmp[j])array[k] = tmp[i++];
9 else array[k] = tmp[j--];
10 }
然后就是传说中的快排了
快速排序 hoare版 参照某博文 july的快速排序分析。
1 int HoarePartition(int *A,int p,int r)
2 {
3 int i,j,x;
4 x = A[p];
5 i = p-1;
6 j = r+1;
7 while(true)
8 {
9 do
10 {
11 j--;
12 }while(A[j]>x);//找到小于等于的
13 do
14 {
15 i++;
16 }while(A[i]<x);//找到大于等于的
17 if(i<j)
18 swap(&A[i],&A[j]);
19 else
20 return j;
21 }
22 }
23 /* 用do while 的原因 */
24 /*如果data数组有相同元素就可能陷入死循环，比如：
25 2 3 4 5 6 2
26 l->| |<-h
27
28 交换l和h单元后重新又回到：
29 2 3 4 5 6 2
30 l->| |<-h
31
32 而第一个程序不存在这种情况，因为它总是在l和h调整后比较，也就是l终究会大于等于h。
33 */
34 void QuickSort(int *A,int p,int r)
35 {
36 int q;
37 if(p<r)
38 {
39 q = HoarePartition(A,p,r);
40 QuickSort(A,p,q);
41 QuickSort(A,q+1,r);
42 }
43 }
快速排序Hoare变形版
1 int HoarePartition_1(int *A,int p,int r)
2 {
3 int i,j,x;
4 x = A[p];
5 i = p;
6 j = r;
7 while(i<j)
8 {
9 while(A[j]>=x&&i<j)j--;
10 A[i] = A[j];
11 while(A[i]<=x&&i<j)i++;
12 A[j] = A[i];
13 }
14 A[i] = x;
15 return i;
16 }
17 void QuickSort(int *A,int p,int r)
18 {
19 int q;
20 if(p<r)
21 {
22 q = HoarePartition_1(A,p,r);
23 QuickSort(A,p,q-1);
24 QuickSort(A,q+1,r);
25 }
26 }
快速排序 算法导论版
1 int partition(int *A,int p,int r)
2 {
3 int i,j,x;
4 x = A[r];
5 i = p-1;
6 for(j = p;j<r;j++)
7 {
8 if(A[j]<=x)
9 {
10 i+=1;
11 swap(&A[i],&A[j]);
12 }
13 }
14 swap(&A[i+1],&A[r]);
15 return i+1;
16 }
17 void quicksort(int *A,int p,int r)
18 {
19 if (p<r)
20 {
21 int q = partition(A,p,r);
22 quicksort(A,p,q-1);
23 quicksort(A,q+1,r);
24 }
25 }
啰嗦一句就是，快排 里面的partition 的返回值一定要搞明白。。。。。
这个几个快速排序 都是参照 july 的博文来的。。。 感谢他。
最后
堆排序：（莫名其妙 调试了很久。。。。。。）
1 void buildmaxHeap(int *heap,int num)//建大顶堆 完全二叉树数组存放
2 {
3 int leftchild,rightchild;
4 int maxchild;
5 for(int i=num/2-1;i>=0;i--)
6 {
7 leftchild = 2*i+1;//子节点 根节点 从0开始
8 rightchild =2*i+2;
9 if(leftchild<num && rightchild>=num)
10 maxchild = leftchild;
11 else if(leftchild>=num)
12 maxchild = i;//不存在这种情况
13 else if(rightchild<num)
14 {
15 if( heap[leftchild]<=heap[rightchild] )
16 maxchild = rightchild;
17 else if(heap[leftchild]>heap[rightchild])
18 maxchild = leftchild;
19 }
20
21 if(heap[i]<heap[maxchild])
22 swap(&heap[i],&heap[maxchild]);
23 }
24 }
25 void HeapSort(int *heap,int n)
26 {
27 for(int i=n;i>0;i--)
28 {
29 buildmaxHeap(heap,i);
30 swap(&heap[0],&heap[i-1]);//最大的值交换到最后面
31 }
32 }
恩，归并的递归 堆排序 都纠结了较长时间
有时间，我还要把递归好好看一看。。。。。
注：这上面的swap和测试的代码 我就没贴了