首先从最简单的冒泡排序  PS：有哪里不对的地方，请批评直言，望不吝赐教。
这里直接上代码

1. void BubbleSort(int b[],int n)
   
2. {
   
3.         int temp,i,j,count1=0,count2=0;                              
   
4.         for(i=0;i<n-1;i++)
   
5.         {
   
6.                 for(j=n-1;j>i;j--)
   
7.                 {
   
8.                         count1++;
   
9.                         if(b[j-1]>b[j])
   
10.                         {
    
11.                                 count2++;
    
12.                                 temp=b[j-1];
    
13.                                 b[j-1]=b[j];
    
14.                                 b[j]=temp;
    
15.                         }
    
16.                 }
    
17.         }
    
18. printf("一共进行了%d次比较,进行了%d次移动\n",count1,count2);
    
19. 
    
20. }
    
21. int main()
    
22. {
    
23.         int a[10]={9,4,12,15,2,7,11,21,25,3};
    
24.         BubbleSort(a,10);
    
25.         for(int i=0;i<10;i++)
    
26.         {
    
27.                 printf("%-2d ",a[i]);
    
28.         }
    
29.         printf("\n\n");
    
30.         return 0;
    
31. }

复制代码

上面的代码是从后往前两两比较  也可以从前往后两两比较 只要把两个for嵌套改一下就OK了！

1.         for(i=0;i<n-1;i++)
   
2.         {
   
3.                 for(j=0;j<n-1-i;j++)
   
4.                 {
   
5.                         count1++;
   
6.                         if(b[j]>b[j+1])
   
7.                         {
   
8.                                 count2++;
   
9.                                 temp=b[j+1];
   
10.                                 b[j+1]=b[j];
    
11.                                 b[j]=temp;
    
12.                         }
    
13.                 }
    
14.         }

复制代码

总结一下冒泡排序  如果有n个数 就要进行n-1趟 第j趟 就要进行n-1-j趟两两比较

关于冒泡排序的优化处理
直接上代码

1. void BubbleSort(int b[],int n)
   
2. {
   
3.         int temp,i,j,count1=0,count2=0,flag;      
   
4.         flag=1;                                 
   
5.         for(i=0;i<n-1&&flag;i++)
   
6.         {
   
7.                 for(j=n-1;j>i;j--)
   
8.                 {
   
9.                         count1++;
   
10.                         flag=0;
    
11.                         if(b[j-1]>b[j])
    
12.                         {
    
13.                                 count2++;
    
14.                                 temp=b[j-1];
    
15.                                 b[j-1]=b[j];
    
16.                                 b[j]=temp;
    
17.                                 flag=1;
    
18.                         }
    
19.                 }
    
20.         }
    
21. printf("一共进行了%d次比较,进行了%d次移动\n",count1,count2);
    
22. 
    
23. }

复制代码

这里是的优化 省去了不必要的比较 例如数组a[10]={1,0,2,3,4,5,6,7,8,9};当 i=0时 for循环后 排序变为 0 1 2 3 4 5 6 7 8 9 再当i=1时 发现后面的一个数总是大于前面的一个数 这里不进入内部for循环 因此直接跳出for循环 在比较上省去了很多步。

选择排序算法
先上代码

1. void SelectSort(int k[],int n)
   
2. {
   
3.         int i,j,temp,min,count1=0,count2=0;
   
4.         for(i=0;i<n-1;i++)
   
5.         {
   
6.                 min=i;
   
7.                 for(j=i+1;j<n;j++)
   
8.                 {
   
9.                         count1++;
   
10.                         if(k[j]<k[min])
    
11.                         {
    
12.                                 min=j;
    
13.                         }
    
14.                 }
    
15. 
    
16.                 if(min!=i)
    
17.                 {
    
18.                         count2++;
    
19.                         temp=k[min];
    
20.                         k[min]=k[i];
    
21.                         k[i]=temp;
    
22.                 }
    
23.         }
    
24. 
    
25.         printf("总共 进行了%d次比较 进行了%d次移动\n",count1,count2);
    
26. }

复制代码

关于选择排序 依然是n-1趟 每进行一趟 就把最小的数放到i的位置上 例如数组a[10]={5,2,6,0,3,9,1,7,4,8};当i=0的时候 2与5比较 显然2的值小于5 这时min=1 再比较6大于2 则min值不做处理 再0的值小于2 这时min=3 以此类推 最后把最小的值的下标给了min 然后把K[min]与K进行交换 显然选择排序的移动次数要小于冒泡排序 这就体现在"选择"上。

直接插入排序
上代码

1. void InsertSort(int k[],int n)
   
2. {
   
3.         int i,j,temp;
   
4.         for(i=1;i<n;i++)
   
5.         {
   
6.                 if(k[i]<k[i-1])
   
7.                 {
   
8.                         temp=k[i];         
   
9. 
   
10.                         for(j=i-1;k[j]>temp;j--)
    
11.                         {
    
12.                                 k[j+1]=k[j];
    
13.                         }
    
14.                         k[j+1]=temp;
    
15.                 }
    
16.         }
    
17. }

复制代码

关于直接插入排序
这里有两点是要注意的
第一：n的范围是1到n-1
第二：每次比较都是小于前继元素的元素依次与所有前继元素比较 直到它的前继元素大于它时 它就插入在该前继元素的后驱上

前面3种排序都是简单的排序算法
接下来是复杂一点排序算法
希尔排序
希尔排序是从直接插入排序演变而来的
代码：

1. void ShellSort(int k[],int n)
   
2. {
   
3.         int i,j,temp;
   
4.         int gap=n;
   
5.         do
   
6.         {
   
7.                 gap=gap/5+1;
   
8.                 for(i=gap;i<n;i++)
   
9.                 {
   
10.                         if(k[i]<k[i-gap])
    
11.                         {
    
12.                                 temp=k[i];                  
    
13.                                 for(j=i-gap;k[j]>temp;j-=gap)
    
14.                                 {
    
15.                                         k[j+gap]=k[j];
    
16.                                 }
    
17.                                 k[j+gap]=temp;
    
18.                         }
    
19.                 }
    
20.         }while(gap>1);
    
21. }

复制代码

希尔排序的实质其实就是分组插入排序  
将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。
代码里的gap就是增量 当gap不大于1时 跳出循环。

堆排序
代码:

1. int count=0;
   
2. void swap(int k[],int i,int j)
   
3. {
   
4.         int temp;
   
5.         temp=k[i];
   
6.         k[i]=k[j];
   
7.         k[j]=temp;
   
8. }
   
9. void HeapAdjust(int k[],int s,int n)
   
10. {
    
11.         int i,temp;
    
12.         temp=k[s];
    
13.         for(i=2*s;i<=n;i*=2)
    
14.         {
    
15.                 count++;
    
16.                 if(i<n&&k[i]<k[i+1])
    
17.                 {
    
18.                         i++;
    
19.                 }
    
20. 
    
21.                 if(temp>=k[i])
    
22.                 {
    
23.                         break;
    
24.                 }
    
25.                 k[s]=k[i];
    
26.                 s=i;
    
27.         }
    
28.         k[s]=temp;
    
29. }
    
30. void HeapSort(int k[],int n)
    
31. {
    
32.         int i;
    
33.         for(i=n/2;i>0;i--)
    
34.         {
    
35.                 HeapAdjust(k,i,n);
    
36.         }
    
37. 
    
38.         for(i=n;i>1;i--)
    
39.         {
    
40.                 swap(k,1,i);
    
41.                 HeapAdjust(k,1,i-1);
    
42.         }
    
43. }
    
44. int main()
    
45. {
    
46.         int a[10]={-1,5,2,6,0,3,9,1,7,4};  //元素从下标为1开始存放
    
47.         HeapSort(a,9);
    
48. 
    
49.         printf("总共进行了%d次比较!\n",count);
    
50.         for(int i=1;i<10;i++)
    
51.         {
    
52.                 printf("%-2d ",a[i]);
    
53.         }
    
54.         printf("\n\n");
    
55.         return 0;
    
56. }

复制代码

关于推排序  首先要把给定数组变成一个大顶堆（从小到大排序）  小顶堆（从大到小排序）
例如 a[10]={-1,5,2,6,0,3,9,1,7,4};
它的层序遍历是
要转换为完全二叉树且父亲的值总是大于左右孩子的值 就构成了大顶堆
也就是代码中的HeapAdjust(k,i,n);这一步就是将数组转换为大顶堆

点赞，总结的不错，很好！

这里主要说说HeapAdjust(k,i,n);函数
首先从最低层开始 按代码里的看 首先当i=9/2=4  所以temp=k[4]=0  然后找出父亲为0的孩子中最大的一个儿子 由上图可以看出是左孩子7
temp>k[8]=7,所以将k[4]=k[7]  s=8  然后再往下遍历(由于父亲为7没有孩子) 所以直接执行最后把temp的值给k  然后依次i=3 2 1 这里说一下i= 4和i=2如下图所示

构成大顶堆后 再层序遍历是9 7 6 4 3 5 1 0 2 把第一个元素即（大顶堆的堆顶）与最后一个元素交换 这样最大值就跑到了最右边 然后再次把剩下的 2 7 6 4 3 5 1 0 构成新的大顶堆 依次做上述操作 就完成了从小到大的排序

归并排序
代码：

1. #define MAXSIZE 10
   
2. void merging(int *list1,int list1_size,int *list2,int list2_size)
   
3. {
   
4.         int i,j,k,m;
   
5.         i=j=k=0;
   
6.         int temp[MAXSIZE];
   
7.         while(i<list1_size&&j<list2_size)
   
8.         {
   
9.                 if(list1[i]<list2[j])
   
10.                 {
    
11.                         temp[k++]=list1[i++];
    
12.                 }
    
13.                 else
    
14.                 {
    
15.                         temp[k++]=list2[j++];
    
16.                 }
    
17.         }
    
18. 
    
19.         while(i<list1_size)
    
20.         {
    
21.                 temp[k++]=list1[i++];
    
22.         }
    
23. 
    
24.         while(j<list2_size)
    
25.         {
    
26.                 temp[k++]=list2[j++];
    
27.         }
    
28. 
    
29.         for(m=0;m<(list1_size+list2_size);m++)   //实现归并 并把结果放到list1里
    
30.         {
    
31.                 list1[m]=temp[m];
    
32.         }
    
33. }
    
34. void MergeSort(int k[],int n)
    
35. {
    
36.         if(n>1)
    
37.         {
    
38.                 int *list1=k;
    
39.                 int list1_size=n/2;
    
40.                 int *list2=k+n/2;
    
41.                 int list2_size=n-list1_size;
    
42. 
    
43.                 MergeSort(list1,list1_size);
    
44.                 MergeSort(list2,list2_size);
    
45. 
    
46.                 merging(list1,list1_size,list2,list2_size);
    
47. 
    
48.         }
    
49. }
    
50. int main()
    
51. {
    
52.         int a[10]={5,2,6,0,3,9,1,7,4,8};
    
53.         MergeSort(a,10);
    
54.         for(int i=0;i<10;i++)
    
55.         {
    
56.                 printf("%-2d ",a[i]);
    
57.         }
    
58.         printf("\n\n");
    
59.         return 0;
    
60. }

复制代码

上面的代码是递归实现 同样也可以迭代实现 代码如下

1. #define LEN 10
   
2. 
   
3. void merge_sort(int *list, int length)
   
4. {
   
5.     int i, left_min, left_max, right_min, right_max, next;
   
6.     int *tmp = (int*)malloc(sizeof(int) * length);
   
7. 
   
8.     if (tmp == NULL)
   
9.     {
   
10.          fputs("Error: out of memory\n", stderr);
    
11.         abort();
    
12.      }
    
13. 
    
14.     for (i = 1; i < length; i *= 2) // i为步长，1,2,4,8……
    
15.     {
    
16.          for (left_min = 0; left_min < length - i; left_min = right_max)
    
17.        {
    
18.             right_min = left_max = left_min + i;
    
19.             right_max = left_max + i;
    
20. 
    
21.            if (right_max > length)
    
22.                 right_max = length;
    
23. 
    
24.             next = 0;
    
25.             while (left_min < left_max && right_min < right_max)
    
26.                 tmp[next++] = list[left_min] > list[right_min] ? list[right_min++] : list[left_min++];
    
27. 
    
28.             while (left_min < left_max)
    
29.                 list[--right_min] = list[--left_max];
    
30. 
    
31.             while (next > 0)
    
32.                  list[--right_min] = tmp[--next];
    
33.          }
    
34.      }
    
35. 
    
36.     free(tmp);
    
37. 
    
38. }
    
39. 
    
40. 
    
41. int main(void)
    
42. {
    
43.      int a[LEN] = { 5, 2, 4, 7, 1, 3, 8, 6 ,9 ,0 };
    
44.      merge_sort(a, LEN);
    
45.      int i;
    
46.      for (i = 0; i < LEN; i++)
    
47.         printf("%d ", a[i]);
    
48.          printf("\n");
    
49. 
    
50.      return 0;
    
51. }

复制代码

这里就说一下递归的实现原理



原理很简单 也就是上图所示  先用递归实现分裂 然后再归并 递归的返回条件就是n=1  所以递归外部要if(n>1)做返回判断
这里主要说一下归并函数merging(list1,list1_size,list2,list2_size)


然后就是依次合并 最后形成一个有序的序列

最后一个排序 快速排序
代码

1. void swap(int k[],int low,int high)
   
2. {
   
3.         int temp;
   
4.         temp=k[low];
   
5.         k[low]=k[high];
   
6.         k[high]=temp;
   
7. }
   
8. int Partition(int k[],int low,int high)
   
9. {
   
10.         int point;
    
11.         point=k[low];
    
12.         while(low<high)
    
13.         {
    
14.                 while(low<high&&k[high]>=point)
    
15.                 {
    
16.                         high--;
    
17.                 }
    
18.                 swap(k,low,high);
    
19. 
    
20.                 while(low<high&&k[low]<=point)
    
21.                 {
    
22.                         low++;
    
23.                 }
    
24.                 swap(k,low,high);
    
25. 
    
26.         }
    
27.         return low;
    
28. }
    
29. void Quick(int k[],int low,int high)
    
30. {
    
31.         int point;
    
32.         if(low<high)
    
33.         {
    
34.                 point=Partition(k,low,high);
    
35.                 Quick(k,low,point-1);
    
36.                 Quick(k,point+1,high);
    
37.         }
    
38. }
    
39. void QuickSort(int k[],int n)
    
40. {
    
41.         Quick(k,0,n-1);
    
42. }
    
43. int main()
    
44. {
    
45.         int a[10]={5,2,6,0,3,9,1,7,4,8};
    
46.         QuickSort(a,10);
    
47.         for(int i=0;i<10;i++)
    
48.         {
    
49.                 printf("%-2d ",a[i]);
    
50.         }
    
51.         printf("\n\n");
    
52.         return 0;
    
53. }

复制代码

这个原理就很简单了
例如数组a[10]={5,2,6,0,3,9,1,7,4,8};
代码里一开始是第一个元素作为point 也就是5

Partition(k,low,high)函数里面每次当low=high 的时候遍历一次结束  然后递归将序列分成两半 然后依次执行point=Partition(k,low,high)把中间点找到 然后再往下递归 当low=high时递归返回

最后是优化后的快速排序算法代码

1. #define MAX_LENGTH_SIZE 7
   
2. 
   
3. void Insert(int k[],int n)      
   
4. {
   
5.         int i,j,temp;
   
6.         for(i=1;i<n;i++)
   
7.         {
   
8.                 if(k[i]<k[i-1])
   
9.                 {
   
10.                         temp=k[i];         
    
11. 
    
12.                         for(j=i-1;k[j]>temp;j--)
    
13.                         {
    
14.                                 k[j+1]=k[j];
    
15.                         }
    
16.                         k[j+1]=temp;
    
17.                 }
    
18.         }
    
19. }
    
20. 
    
21. void InsertSort(int k[],int low,int high)
    
22. {
    
23.         Insert(k+low,high-low+1);
    
24. }
    
25. 
    
26. void swap(int k[],int low,int high)
    
27. {
    
28.         int temp;
    
29.         temp=k[low];
    
30.         k[low]=k[high];
    
31.         k[high]=temp;
    
32. }
    
33. int Partition(int k[],int low,int high)
    
34. {
    
35.         int point;
    
36. 
    
37.         int m=low+(high-low)/2;  //优化处1
    
38.         if(k[low]>k[high])
    
39.         {
    
40.                 swap(k,low,high);
    
41.         }
    
42.         if(k[m]>k[high])
    
43.         {
    
44.                 swap(k,m,high);
    
45.         }
    
46.         if(k[m]>k[low])
    
47.         {
    
48.                 swap(k,low,m);
    
49.         }
    
50. 
    
51.         point=k[low];
    
52.         while(low<high)
    
53.         {
    
54.                 while(low<high&&k[high]>=point)
    
55.                 {
    
56.                         high--;
    
57.                 }
    
58.                 k[low]=k[high];   //优化处2
    
59. 
    
60.                 while(low<high&&k[low]<=point)
    
61.                 {
    
62.                         low++;
    
63.                 }
    
64.                 k[high]=k[low];
    
65.         }
    
66.         k[low]=point;
    
67. 
    
68.         return low;
    
69. }
    
70. void Quick(int k[],int low,int high)
    
71. {
    
72.         int point;
    
73.         if((high-low)>MAX_LENGTH_SIZE)  //优化处3
    
74.         {
    
75.                 while(low<high)
    
76.                 {
    
77.                         point=Partition(k,low,high);
    
78.                         if(point-low<high-point)   // 优化4
    
79.                         {
    
80.                                 Quick(k,low,point-1);
    
81.                                 low=point+1;
    
82.                         }
    
83.                         else
    
84.                         {
    
85.                                 Quick(k,point+1,high);
    
86.                                 high=point-1;
    
87.                         }
    
88.                 }
    
89.         }
    
90.         else
    
91.         {
    
92.                 InsertSort(k,low,high);
    
93.         }
    
94. }
    
95. void QuickSort(int k[],int n)
    
96. {
    
97.         Quick(k,0,n-1);
    
98. }
    
99. int main()
    
100. {
     
101.         int a[10]={5,2,6,0,3,9,1,7,4,8};
     
102.         QuickSort(a,10);
     
103.         for(int i=0;i<10;i++)
     
104.         {
     
105.                 printf("%-2d ",a[i]);
     
106.         }
     
107.         printf("\n\n");
     
108.         return 0;
     
109. }
     

复制代码

一共是4出优化操作 代码里已分别标出优化位置

最后总结一下关于各排序算法的时间复杂度问题

排序算法	平均情况	最好情况	最坏情况
冒泡排序	O(n^2)	O(n)	O(n^2)
选择排序	O(n^2)	O(n^2)	O(n^2)
直接插入排序	O(n^2)	O(n)	O(n^2)
希尔排序	O(nlogn)~O(n^2)	O(n^1.3)	O(n^2)
堆排序	O(nlogn)	O(nlogn)	O(nlogn)
归并排序	O(nlogn)	O(nlogn)	O(nlogn)
快速排序	O(nlogn)	O(nlogn)	O(n^2)