算法分析中最常用的几种排序算法（插入排序、希尔排序、冒泡排序、选择排序、快速排序，归并排序）C 语言版

每次开始动手写算法，都是先把插入排序，冒泡排序写一遍，十次有九次是重复的，所以这次下定决心，将所有常规的排序算法写了一遍，以便日后熟悉。

以下代码总用一个main函数和一个自定义的CommonFunction函数

CommonFunction函数中定义了一个交换函数和一个输出函数：

 1 /*
 2  * CommonFunction.h
 3  *
 4  *  Created on: 2015年11月16日
 5  *      Author: hoojjack
 6  */
 7 
 8 #pragma once
 9 namespace section4 {
10 void swap(int *first, int *second) {
11     int temp;
12     temp = *first;
13     *first = *second;
14     *second = temp;
15 }
16 
17 void printfByStep(int *a, int i, int len) {
18     int k;
19     printf("The result of the %dth step
", i);
20     for (k = 0; k < len; k++)
21         printf("%d ", a[k]);
22     printf("
");
23 }
24 }

main函数：

 1 /*
 2  * SortMain.cpp
 3  *
 4  *  Created on: 2015年11月16日
 5  *      Author: hoojjack
 6  */
 7 
 8 #include<stdio.h>
 9 #include<stdlib.h>
10 #include<time.h>
11 #include<sys/timeb.h>
12 #include "BubbleSort.h"
13 #include "SelectionSort.h"
14 #include "InsertionSort.h"
15 #include "ShellSort.h"
16 #include "QuickSort.h"
17 #include "CommonFunction.h"
18 #include "HeapSort.h"
19 #include "MergeSort.h"
20 #define SIZE 10
21 int main() {
22     int array[SIZE], i, options;
23     srand(time(NULL));
24     for (i = 0; i < SIZE; i++) {
25         array[i] = rand() / 1000 + 10;
26     }
27     printf("The array of original sorting
");
28     for (i = 0; i < SIZE; i++) {
29         printf("%d ", array[i]);
30     }
31     printf("
Please choose your options:
 1:BubbleSort	 2:Selection	 ");
32     printf(
33             "3:InsertSort	 4:ShellSort	 5:QuickSort	 6:HeapSort	 7:MergeSort	
");
34 //    scanf("%d", &options);
35 
36     for (i = 1; i <= 7; i++) {
37         options=i;
38         switch (options) {
39         case 1:
40             printf("The result of Bubble sorting is following:
");
41             section4::bubbleSort(array, SIZE);
42             break;
43         case 2:
44             printf("The result of Selection sorting is following:
");
45             section4::selectionSort(array, SIZE);
46             break;
47         case 3:
48             printf("The result of Insertion sorting is following:
");
49             section4::insertionSort(array, SIZE);
50             break;
51         case 4:
52             printf("The result of Shell sorting is following:
");
53             section4::shellSort(array, SIZE);
54             break;
55         case 5:
56             printf("The result of Quick sorting is following:
");
57             section4::quickSort(array, 0, SIZE - 1);
58             section4::printfByStep(array, SIZE, SIZE);
59             break;
60         case 6:
61             printf("The result of Heap sorting is following:
");
62             section4::heapSort(array, SIZE);
63             break;
64         case 7:
65             printf("The result of Merge sorting is following:
");
66             section4::mergeSort(array, SIZE);
67             break;
68         }
69 
70     }
71 
72 //    for (i = 0; i < SIZE; i++) {
73 //        printf("%d ", array[i]);
74 //    }
75 //    printf("
");
76     return 0;
77 }

1、冒泡排序：

 1 /*
 2  * BubbleSort.h
 3  *
 4  *  Created on: 2015年11月16日
 5  *      Author: hoojjack
 6  */
 7 
 8 #pragma once
 9 #include "CommonFunction.h"
10 namespace section4 {
11 /*
12  * 冒泡排序，很简单，相邻的两个元素进行比较，将较大的元素往后挪
13  * 每进行一次循环，排好一个元素
14  */
15 void bubbleSort(int *a, int len) {
16     int i, j;
17     for (i = 1; i < len; i++) {
18         for (j = 0; j < len - i; j++) {
19             if (a[j] > a[j + 1]) {
20                 swap(&a[j],&a[j+1]);
21             }
22         }
23         //The result of the %dth step
24         //section4::printfByStep(a,i,len);
25     }
26     section4::printfByStep(a,i,len);
27 }
28 
29 }

2、选择排序算法：

 1 /*
 2  * SelectionSort.h
 3  *
 4  *  Created on: 2015年11月16日
 5  *      Author: hoojjack
 6  */
 7 
 8 #pragma once
 9 #include "CommonFunction.h"
10 namespace section4 {
11 /*
12  * @author
13  * 选择排序，每第i次循环为第i个位置找到此序列相应的第i个数。
14  */
15 void selectionSort(int *a,int len){
16     int i,j,k;
17     for(i=0;i<len;i++){
18         k=i;//记录此刻要数组中待排的位置
19         for(j=i;j<len;j++){
20             if(a[k]>a[j])
21                 k=j;
22         }
23         if(k!=i){
24             section4::swap(&a[k],&a[i]);
25         }
26         //section4::printfByStep(a,i,len);
27     }
28     section4::printfByStep(a,i,len);
29 }
30 }

3、插入排序算法：

 1 /*
 2  * InsertionSort.h
 3  *
 4  *  Created on: 2015年11月16日
 5  *      Author: hoojjack
 6  */
 7 
 8 #pragma once
 9 #include "CommonFunction.h"
10 namespace section4{
11 /*
12  * 此处的插入排序没有安排哨兵，即没有将a[0]空出来
13  */
14 void insertionSort(int *a,int len){
15     int i,temp,j;
16     for(i=1;i<len;i++){
17         temp=a[i];
18         j=i-1;
19         while(j>=0&&temp<a[j]){
20             a[j+1]=a[j];
21             j--;
22         }
23         a[j+1]=temp;
24     //    section4::printfByStep(a,i,len);
25     }
26     section4::printfByStep(a,i,len);
27 }
28 }

4、希尔排序算法：

 1 /*
 2  * ShellSort.h
 3  *
 4  *  Created on: 2015年11月16日
 5  *      Author: hoojjack
 6  */
 7 #pragma once
 8 #include "CommonFunction.h"
 9 namespace section4 {
10 /*
11  * 希尔排序的思路是：每次以i/2的大小进行插入排序，第一次是以len/2的长度进行比较
12  * i为相隔的步长,每次以i的步长往前进行比较，直到步长为1。
13  *
14  */
15 void shellSort(int *a, int len) {
16     int i, j, temp,k, x = 0;
17     for (i = len / 2; i >= 1; i = i / 2) {
18         for (j = i; j < len; j++) {
19             temp = a[j];
20             k = j - i;
21             while (temp < a[k] && k >= 0) {
22                 a[k + i] = a[k];
23                 k = k - i;
24             }
25             a[k + i] = temp;
26         }
27         x++;
28         //section4::printfByStep(a, x, len);
29     }
30     section4::printfByStep(a, x, len);
31 }
32 }

5、快速排序算法：

 1 /*
 2  * QuickSort.h
 3  *
 4  *  Created on: 2015年11月16日
 5  *      Author: hoojjack
 6  */
 7 
 8 #pragma once
 9 #include "CommonFunction.h"
10 namespace section4 {
11 /*@author
12  * 快速排序：这是自己按照快速排序的思路写的，刚开始出现两个地方的错误
13  * 1、递归循环的时候没有判断(left < low - 1)和(high + 1 < right)导致递归的时候
14  * 出现left值比right值大，以致递归不能结束
15  *
16  * 2、temp <= a[high] 没有判断=号，导致如果数组里出现相同的数字时，low和high的位置没有变化
17  * 导致循环不断地在交换a[low]和a[high]的值，出现死循环。
18  *
19  */
20 void quickSort(int *a, int left, int right) {
21     int low, high, temp;
22     low = left;
23     high = right;
24     temp = a[low];
25     while (low < high) {
26         while (temp <= a[high] && low < high) {
27             high--;
28         }
29         a[low] = a[high];
30         while (temp >= a[low] && low < high) {
31             low++;
32         }
33         a[high] = a[low];
34 
35     }
36     a[low] = temp;
37 //    printf("low=%d,high=%d
", low, high);
38     if (left < low - 1)
39         quickSort(a, left, low - 1);
40     if (high + 1 < right)
41         quickSort(a, high + 1, right);
42 
43 }
44 
45 }

6堆排序算法：

 1 /*
 2  * HeapSort.h
 3  *
 4  *  Created on: 2015年11月17日
 5  *      Author: hoojjack
 6  */
 7 
 8 #pragma once
 9 #include "CommonFunction.h"
10 
11 namespace section4 {
12 /*
13  * @author
14  * 堆排序应该注意的几点：
15  * 1、首先从最后一个父节点开始往上堆排序，在计算的时候考虑数组下标，计算
16  * 最后一个父节点的计算公式是len/2-1(因为数组从0开始编号)，然而在算它的孩子几点时
17  * 左孩子节点不再是2*parent，而是2*parent+1;
18  * 2、对数组进行从小到大排序，需要建立大根堆，因为数字大的排在数组后面
19  */
20 void heapSort(int *a, int len) {
21     int child, parent, t, i, j, z;
22     for (i = 0; i < len; i++) {
23         z = len - 1 - i;
24         for (j = ((z + 1) / 2) - 1; j >= 0; j--) {
25             parent = j;
26             while ((2 * parent + 1) <= z) {
27                 child = 2 * parent + 1;
28                 if ((child + 1) <= z) {
29                     if (a[child] > a[child + 1]) {
30                         t = child;
31                     } else {
32                         t = child + 1;
33                     }
34                 } else {
35                     t = child;
36                 }
37                 if (a[parent] < a[t]) {
38                     section4::swap(&a[parent], &a[t]);
39                 } else {
40                     break;
41                 }
42             }
43         }
44         section4::swap(&a[0],&a[z]);
45         //section4::printfByStep(a,i,len);
46     }
47     section4::printfByStep(a,i,len);
48 }
49 
50 }

7、归并排序算法：

 1 /*
 2  * MergeSort.h
 3  *
 4  *  Created on: 2015年11月17日
 5  *      Author: hoojjack
 6  */
 7 
 8 #pragma once
 9 #include<stdlib.h>
10 #include "CommonFunction.h"
11 namespace section4 {
12 /*
13  * @author
14  * 分步归并函数
15  *
16  */
17 void mergeOne(int *a, int *b, int n, int len) {
18     int i, j, s, t, e, k;
19     s = 0;
20     while (s < len) {
21         i = s;
22         t = n + s;
23         j = s + n;
24         e = s + 2 * n - 1;
25         k = s;
26         /*其中，i代表第一个归并子序列的首位，t代表此序列的末位
27          * j代表第二个归并子序列的首位，e代表此序列的末位
28          * k代表另一个数组的下标
29          * e的大小没有进行判断，容易导致最后一次归并时，
30          * 导致下标越界，故一定要判断e是否>=len
31          */
32         if(e>=len){
33             e=len-1;
34         }
35         while (i < t && j <= e) {
36             if (a[i] < a[j]) {
37                 b[k++] = a[i++];
38             } else {
39                 b[k++] = a[j++];
40             }
41         }
42         while (i < t) {
43             b[k++] = a[i++];
44         }
45         while (j <= e) {
46             b[k++] = a[j++];
47         }
48         //s在此刻第二个归并子序列e的基础前进1
49         s = e + 1;
50     }
51 //    if (s < len) {
52 //        for (; s < len; s++)
53 //            b[s] = a[s];
54 //    }
55 }
56 /*
57  * 归并函数，b为开辟一个新数组的首地址，f为标志符，
58  * 当f=1时，将数组a中的数复制到数组b中,否则，进行相反操作
59  * s为每次归并的长度，1,2,2^2,2^3,......
60  * 直到数组子序列归并为一个，即s<len
61  */
62 void mergeSort(int *a, int len) {
63     int *b;
64     int f = 1, s = 1, count = 0, h;
65     if (!(b = (int *) malloc(sizeof(int) * len))) {
66         printf("内存分配失败
");
67         exit(0);
68     }
69     while (s < len) {
70         if (f == 1) {
71             mergeOne(a, b, s, len);
72         //    section4::printfByStep(b, count++, len);
73         } else {
74             mergeOne(b, a, s, len);
75         //    section4::printfByStep(a, count++, len);
76         }
77         f = 1 - f;
78         s = s * 2;
79 
80     }
81     if (!f) {
82         for (h = 0; h < len; h++)
83             a[h] = b[h];
84     }
85     section4::printfByStep(a, count, len);
86     free(b);
87 }
88 }

最后的结果是：

The array of original sorting
31 35 29 12 40 35 24 38 29 38 
Please choose your options:
 1:BubbleSort     2:Selection     3:InsertSort     4:ShellSort     5:QuickSort     6:HeapSort     7:MergeSort    
The result of Bubble sorting is following:
The result of the 10th step
12 24 29 29 31 35 35 38 38 40 
The result of Selection sorting is following:
The result of the 10th step
12 24 29 29 31 35 35 38 38 40 
The result of Insertion sorting is following:
The result of the 10th step
12 24 29 29 31 35 35 38 38 40 
The result of Shell sorting is following:
The result of the 3th step
12 24 29 29 31 35 35 38 38 40 
The result of Quick sorting is following:
The result of the 10th step
12 24 29 29 31 35 35 38 38 40 
The result of Heap sorting is following:
The result of the 10th step
12 24 29 29 31 35 35 38 38 40 
The result of Merge sorting is following:
The result of the 0th step
12 24 29 29 31 35 35 38 38 40