所有排序总结（内排序）
花时间把所有的排序重新 写了一遍。。。。。（应该是认真写过一遍，学的时候根本就没写过）
写得时候才发现，理解不深刻。基本上 只是懂怎么做，不懂为什么。
把我写得记在这里，以后用得着了回来看看。
暂时就到这里吧，以后有时间，继续研究这些东西。在写出来。
三个O(n 2 )的算法
选择排序：
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和测试的代码 我就没贴了
作者： Leo_wl
出处： http://www.cnblogs.com/Leo_wl/
本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利。
版权信息声明：本文来自网络，不代表【好得很程序员自学网】立场，转载请注明出处：http://haodehen.cn/did48285