各类排序C++实现（冒泡，选择，插入，快排，归并，堆排）

没有加什么模板之类的，全用的int型，下标有的从0开始有的从1开始

1.插入

[cpp] view plaincopy

1. #include <iostream>  
2. #include <cstdio>  
3. #define N 1005  
4. using namespace std;  
5. int n, a[N];  
6. void InsertSort(int a[], int n) //下标从0开始  
7. {  
8.     int i, j, temp;  
9.     for(i = 1; i < n; i++)  
10.     {  
11.         temp = a[i];  
12.         for(j = i; j > 0 && temp < a[j - 1]; j--) a[j] = a[j - 1];  
13.         a[j] = temp;  
14.     }  
15. }  
16. int main()  
17. {  
18.     int i;  
19.     scanf("%d", &n);  
20.     for(i = 0; i < n; i++) scanf("%d", &a[i]);  
21.     InsertSort(a, n);  
22.     for(i = 0; i < n; i++) printf("%d\n", a[i]);  
23.     return 0;  
24. }  

2.选择

[cpp] view plaincopy

1. #include <iostream>  
2. using namespace std;  
3. int a[105];  
4. //下标从1开始  
5. void SelectSort(int a[], int n)  
6. {  
7.     int i, j, pos;  
8.     for(i = 1; i < n; i++)  
9.     {  
10.         pos = i;  
11.         for(j = i; j <= n; j++)  
12.         {  
13.             if(a[j] < a[pos])  
14.             pos = j;  
15.         }  
16.         int temp = a[pos];  
17.         a[pos] = a[i];  
18.         a[i] = temp;  
19.     }  
20. }  
21. int main()  
22. {  
23.     int n, i;  
24.     cin >> n;  
25.     for(i = 1; i <= n; i++) cin >> a[i];  
26.     SelectSort(a, n);  
27.     for(i = 1; i <= n; i++)  
28.     cout << a[i] << " ";  
29.     cout << endl;  
30.     return 0;  
31. }  

3.冒泡

[cpp] view plaincopy

1. #include <iostream>  
2. using namespace std;  
3. int a[105];  
4. //下标从1开始  
5. void BubbleSort(int a[], int n)  
6. {  
7.     int i, j;  
8.     for(i = 1; i < n; i++)  
9.     {  
10.         for(j = 1; j <= n - i; j++)  
11.         {  
12.             if(a[j] > a[j + 1])  
13.             {  
14.                 int temp = a[j + 1];  
15.                 a[j + 1] = a[j];  
16.                 a[j] = temp;  
17.             }  
18.         }  
19.     }  
20. }  
21. int main()  
22. {  
23.     int n, i;  
24.     cin >> n;  
25.     for(i = 1; i <= n; i++)  
26.         cin >> a[i];  
27.     BubbleSort(a, n);  
28.     for(i = 1; i <= n; i++)  
29.     cout << a[i] << " ";  
30.     cout << endl;  
31.     return 0;  
32. }  

4.快排

[cpp] view plaincopy

1. #include <iostream>  
2. using namespace std;  
3. int n;  
4. int a[105];  
5. //下标从0开始  
6. int partition(int a[], int low, int high)  
7. {//快速排序中的一趟  
8.     int key;//作为枢轴来使用  
9.     key = a[low];  
10.     while(low < high)  
11.     {  
12.         while(low < high && a[high] >= key)  
13.         --high;  
14.         a[low] = a[high];  
15.         while(low < high && a[low] <= key)  
16.         ++low;  
17.         a[high] = a[low];  
18.     }  
19.     a[low] = key;  
20.     return low;  
21. }  
22. void qsort(int a[], int low, int high)  
23. {//快速排序的递归形式  
24.     int loc;  
25.     if(low < high)  
26.     {  
27.         loc = partition(a, low, high);//一趟排序结果的调用  
28.         qsort(a, low, loc - 1);  
29.         qsort(a, loc + 1, high);  
30.     }  
31. }  
32. int main()  
33. {  
34.     int i;  
35.     cin >> n;  
36.     for(i = 0; i < n; i++) cin >> a[i];  
37.     qsort(a, 0, n - 1);  
38.     for(i = 0; i < n; i++) cout << a[i] << " ";  
39.     cout << endl;  
40.     return 0;  
41. }  

5.归并

[cpp] view plaincopy

1. #include <iostream>  
2. #define N 105  
3. using namespace std;  
4. int n;  
5. int a[N], t[N];  
6. /* 归并 */  
7. //下标从0开始  
8. void Merge(int a[], int l, int m, int r)  
9. {  
10.     /* p指向输出区间 */  
11.     int p = 0;  
12.     /* i、j指向2个输入区间 */  
13.     int i = l, j = m + 1;  
14.     /* 2个输入区间都不为空时 */  
15.     while(i <= m && j <= r)  
16.     {/* 取关键字小的记录转移至输出区间 */  
17.         if (a[i] > a[j])  
18.             t[p++] = a[j++];  
19.         else  
20.             t[p++] = a[i++];  
21.     }  
22.     /* 将非空的输入区间转移至输出区间 */  
23.     while(i <= m) t[p++] = a[i++];  
24.     while(j <= r) t[p++] = a[j++];  
25.     /* 归并完成后将结果复制到原输入数组 */  
26.     for (i = 0; i < p; i++)  
27.         a[l + i] = t[i];  
28. }  
29.   
30. /* 归并排序 */  
31. void MergeSort(int a[], int l, int r)  
32. {  
33.     int m;  
34.     if (l < r)  
35.     {/* 将长度为n的输入序列分成两个长度为n/2的子序列 */  
36.         m = (l + r) / 2;  
37.         /* 对两个子序列分别进行归并排序 */  
38.         MergeSort(a, l, m);  
39.         MergeSort(a, m + 1, r);  
40.         /* 将2个排好的子序列合并成最终有序序列 */  
41.         Merge(a, l, m, r);  
42.     }  
43. }  
44. int main()  
45. {  
46.     int i;  
47.     cin >> n;  
48.     for(i = 0; i < n; i++) cin >> a[i];  
49.     MergeSort(a, 0, n - 1);  
50.     for(i = 0; i < n; i++) cout << a[i] << " ";  
51.     cout << endl;  
52.     return 0;  
53. }  

6.堆排

[cpp] view plaincopy

1. #include <iostream>  
2. using namespace std;  
3. int n;  
4. int a[105];  
5. //下标从1开始  
6. void HeapAdjust(int A[], int a, int z)   
7. {  
8.     int i, j;  
9.     for(i = a, j = 2 * i; j <= z; i = j, j = 2 * i)  
10.     { //i为父，j为子  
11.         if(j < z && A[j + 1] > A[j]) j++;   //大顶堆，沿大孩子方向下行  
12.         if(A[i] < A[j])  
13.             swap(A[i], A[j]);  
14.         else break;  
15.     }  
16. }  
17. void HeapSort(int A[], int n)  
18. {  
19.     int i;  
20.     for(i = n / 2; i >= 1; i--) //从倒数第一个非叶子结点，自下而上堆化  
21.         HeapAdjust(A, i, n);  
22.     for(i = n; i > 1; i--)  
23.     { //交换A[1]与最后元素A[i]（i=n, ..., 1）, 再堆化  
24.         swap(A[1], A[i]);  
25.         HeapAdjust(A, 1, i - 1);  
26.     }  
27. }  
28. int main()  
29. {  
30.     int i;  
31.     cin >> n;  
32.     for(i = 1; i <= n; i++)  
33.     cin >> a[i];  
34.     HeapSort(a, n);  
35.     for(i = 1; i <= n; i++) cout << a[i] << " ";  
36.     cout << endl;  
37.     return 0;  
38. }