排序

一.归并排序

 1 #include<iostream>
 2 using namespace std;
 3 
 4 template<typename T>
 5 void Merge(T A[], int p, int q, int r)
 6 {
 7     int n1 = q - p + 1;
 8     int n2 = r - q;
 9 
10     T *B = new T[n1];
11     T *C = new T[n2];
12 
13     for (int i = p; i <= q; i++)
14     {
15         B[i - p] = A[i];
16     }
17     for (int i = q + 1; i <= r; i++)
18     {
19         C[i - q - 1] = A[i];
20     }
21 
22     int m = 0, n = 0;
23     for (int i = p; i <= r; i++)
24     {
25         if (m == n1 && n != n2)
26         {
27             while (n != n2)
28             {
29                 A[i] = C[n];
30                 i++;
31                 n++;
32             }
33             break;
34         }
35         if (m != n1 && n == n2)
36         {
37             while (m != n1)
38             {
39                 A[i] = B[m];
40                 i++;
41                 m++;
42             }
43             break;
44         }
45         if (B[m] <= C[n])
46         {
47             A[i] = B[m];
48             m++;
49         }
50         else
51         {
52             A[i] = C[n];
53             n++;
54         }
55     }
56 }
57 
58 template<typename T>
59 void MergeSort(T A[], int p, int r)
60 {
61     if (A != NULL && p >= 0 && r >= 0 && p < r)
62     {
63         int q = (p + r) / 2;
64         MergeSort(A, p, q);
65         MergeSort(A, q + 1, r);
66         Merge(A, p, q, r);
67     }
68 }
69 
70 int main()
71 {
72     double A[] = { 1.1, -2.1, 3, 3, 4, -10, 4, 2.6 };
73     MergeSort(A, 0, 7);
74     for (int i = 0; i < 8; i++)
75     {
76         cout << A[i] << " ";
77     }
78     cout << endl;
79     return 0;
80 }

归并排序最大的特色就是它是一种稳定的排序算法。归并过程中是不会改变元素的相对位置的。缺点是，它需要O(n)的额外空间。但是很适合于多链表排序。

适用于排序大列表，基于分治法。

二.插入排序

 1 #include<iostream>
 2 using namespace std;
 3 
 4 template <typename T>
 5 void InsertionSort(T A[], int length)
 6 {
 7     if (A == NULL || length <= 0)
 8         return;
 9     for (int i = 1; i < length; i++)
10     {
11         T num = A[i];
12         int j = i - 1;
13         while (j >= 0 && num < A[j])
14         {
15             A[j + 1] = A[j];
16             j--;
17         }
18         A[j + 1] = num;
19     }
20 }
21 
22 int main()
23 {
24     double A[] = { 1.1, -2.1, 3, 3, 4, -10, 4, 2.6 };
25     InsertionSort(A, 8);
26     for (int i = 0; i < 8; i++)
27     {
28         cout << A[i] << " ";
29     }
30     cout << endl;
31     return 0;
32 }

稳定性，就是有两个相同的元素，排序先后的相对位置是否变化，主要用在排序时有多个排序规则的情况下。在插入排序中，K1是已排序部分中的元素，当K2和K1比较时，直接插到K1的后面(没有必要插到K1的前面，这样做还需要移动，因此，插入排序是稳定的。

适用于排序小列表若列表基本有序，则插入排序比冒泡、选择更有效率。

三.快速排序

 1 #include<iostream>
 2 using namespace std;
 3 
 4 template <typename T>
 5 int Partition(T A[], int p, int r)
 6 {
 7     T x = A[r];
 8     int i = p - 1;
 9     for (int j = p; j <= r - 1; j++)
10     {
11         if (A[j] <= x)
12         {
13             i++;
14             T temp = A[j];
15             A[j] = A[i];
16             A[i] = temp;
17         }
18     }
19     T temp = A[i + 1];
20     A[i + 1] = A[r];
21     A[r] = temp;
22     return i + 1;
23 }
24 
25 template <typename T>
26 void QuickSort(T A[], int p, int r)
27 {
28     if (A != NULL && p >= 0 && r >= 0 && p < r)
29     {
30         int q = Partition(A, p, r);
31         QuickSort(A, p, q - 1);
32         QuickSort(A, q + 1, r);
33     }
34 }
35 
36 int main()
37 {
38     double A[] = { 1.1, -2.1, 3, 3, 4, -10, 4, 2.6 };
39     QuickSort(A, 0, 7);
40     for (int i = 0; i < 8; i++)
41     {
42         cout << A[i] << " ";
43     }
44     cout << endl;
45     return 0;
46 }

由于每次都需要和中轴元素交换，因此原来的顺序就可能被打乱。如序列为 5 3 3 4 9 8 9 10 6 会将9的顺序打乱。所以说，快速排序是不稳定的！

平均效率O（nlogn），适用于排序大列表。
此算法的总时间取决于枢纽值的位置；选择第一个元素作为枢纽，可能导致O（n²）的最糟用例效率。若数基本有序，效率反而最差。选项中间值作为枢纽，效率是O（nlogn）。
基于分治法。

若要快排稳定，开额外O(n)空间.每轮partition都直接扫一遍p~r, 小于key的放一个数组,大于key的放另外一个数组. 然后再合并到原数组当中.这样就是稳定的了

快排改进：

 1 #include<iostream>
 2 #include<stdlib.h>
 3 using namespace std;
 4 
 5 template <typename T>
 6 void InsertionSort(T A[], int p, int r)
 7 {
 8     for (int i = p + 1; i <= r; i++)
 9     {
10         T key = A[i];
11         int j = i - 1;
12         while (j >= p && A[j] > key)
13         {
14             A[j + 1] = A[j];
15             j--;
16         }
17         A[j + 1] = key;
18     }
19 }
20 
21 template <typename T>
22 int Partition(T A[], int p, int r)
23 {
24     T x = A[r];
25     int i = p - 1;
26     for (int j = p; j <= r - 1; j++)
27     {
28         if (A[j] <= x)
29         {
30             i++;
31             T temp = A[j];
32             A[j] = A[i];
33             A[i] = temp;
34         }
35     }
36     T temp = A[i + 1];
37     A[i + 1] = A[r];
38     A[r] = temp;
39     return i + 1;
40 }
41 
42 template <typename T>
43 int RandomizedPartition(T A[], int p, int r)
44 {
45     int i = rand() % (r - p + 1) + p;
46     T temp = A[r];
47     A[r] = A[i];
48     A[i] = temp;
49     return Partition(A, p, r);
50 }
51 
52 template <typename T>
53 void QuickSort(T A[], int p, int r)
54 {
55     if (A != NULL && p >= 0 && r >= 0)
56     {
57         if (r - p < 5)
58         {
59             InsertionSort(A, p, r);
60         }
61         else
62         {
63             int q = RandomizedPartition(A, p, r);
64             QuickSort(A, p, q - 1);
65             QuickSort(A, q + 1, r);
66         }
67     }
68 }
69 
70 int main()
71 {
72     double A[] = { 1.1, -2.1, 3, 3, 4, -10, 4, 2.6 ,20, 10};
73     QuickSort(A, 0, 9);
74     for (int i = 0; i < 10; i++)
75     {
76         cout << A[i] << " ";
77     }
78     cout << endl;
79     return 0;
80 }

四.选择排序

 1 #include<iostream>
 2 #include<stdlib.h>
 3 using namespace std;
 4 
 5 template <typename T>
 6 void SelectionSort(T A[], int length)
 7 {
 8     if (A != NULL && length > 0)
 9     {
10         for (int i = 0; i < length - 1; i++)
11         {
12             int smallest = i;
13             for (int j = i + 1; j < length; j++)
14             {
15                 if (A[j] < A[smallest])
16                 {
17                     smallest = j;
18                 }
19             }
20             T temp = A[i];
21             A[i] = A[smallest];
22             A[smallest] = temp;
23         }
24     }
25 }
26 
27 int main()
28 {
29     double A[] = { 1.1, -2.1, 3, 3, 4, -10, 4, 2.6 ,20, 10};
30     SelectionSort(A, 10);
31     for (int i = 0; i < 10; i++)
32     {
33         cout << A[i] << " ";
34     }
35     cout << endl;
36     return 0;
37 }

由于每次都是选取未排序序列A中的最小元素x与A中的第一个元素交换，因此跨距离了，很可能破坏了元素间的相对位置，因此选择排序是不稳定的！比如：3 3 2

效率O（n²），适用于排序小的列表

五.冒泡排序

 1 #include<iostream>
 2 #include<stdlib.h>
 3 using namespace std;
 4 
 5 template <typename T>
 6 void BubbleSort(T A[], int length)
 7 {
 8     if (A != NULL && length > 0)
 9     {
10         for (int i = length - 1; i > 0; i--)
11         {
12             for (int j = 0; j < i; j++)
13             {
14                 if (A[j] > A[j + 1])
15                 {
16                     T temp = A[j + 1];
17                     A[j + 1] = A[j];
18                     A[j] = temp;
19                 }
20             }
21         }
22     }
23 }
24 
25 int main()
26 {
27     double A[] = { 1.1, -2.1, 3, 3, 4, -10, 4, 2.6 ,20, 10};
28     BubbleSort(A, 10);
29     for (int i = 0; i < 10; i++)
30     {
31         cout << A[i] << " ";
32     }
33     cout << endl;
34     return 0;
35 }

排序过程中只交换相邻两个元素的位置。因此，当两个数相等时，是没必要交换两个数的位置的。所以，它们的相对位置并没有改变，冒泡排序算法是稳定的！

效率 O（n²）,适用于排序小列表

六.堆排序

 1 #include<iostream>
 2 #include<stdlib.h>
 3 using namespace std;
 4 
 5 int Parent(int i)
 6 {
 7     return i / 2;
 8 }
 9 
10 int Left(int i)
11 {
12     return 2 * i;
13 }
14 
15 int Right(int i)
16 {
17     return 2 * i + 1;
18 }
19 
20 template <typename T>
21 void MaxHeapify(T A[], int i, int length)
22 {
23     if (i > 0)
24     {
25         int l = Left(i);
26         int r = Right(i);
27         int largest;
28         if (l <= length && A[l - 1] > A[i - 1])
29         {
30             largest = l;
31         }
32         else
33         {
34             largest = i;
35         }
36         if (r <= length && A[r - 1] > A[largest - 1])
37         {
38             largest = r;
39         }
40         if (largest != i)
41         {
42             T temp = A[i - 1];
43             A[i - 1] = A[largest - 1];
44             A[largest - 1] = temp;
45             MaxHeapify(A, largest, length);
46         }
47     }
48 }
49 
50 template <typename T>
51 void BuildMaxHeap(T A[], int length)
52 {
53     for (int i = length / 2; i >= 1; i--)
54     {
55         MaxHeapify(A, i, length);
56     }
57 }
58 
59 template <typename T>
60 void HeapSort(T A[], int length)
61 {
62     if (A != NULL && length > 0)
63     {
64         int heapSize = length;
65         BuildMaxHeap(A, length);
66         for (int i = length; i >= 2; i--)
67         {
68             T temp = A[0];
69             A[0] = A[i - 1];
70             A[i - 1] = temp;
71 
72             heapSize--;
73             MaxHeapify(A, 1, heapSize);
74         }
75     }
76 }
77 
78 int main()
79 {
80     double A[] = { 1.1, -2.1, 3, 3, 4, -10, 4, 2.6 ,20, 10};
81     HeapSort(A, 10);
82     for (int i = 0; i < 10; i++)
83     {
84         cout << A[i] << " ";
85     }
86     cout << endl;
87     return 0;
88 }

堆排序的最坏时间复杂度为O(nlgn)。堆排序的平均性能较接近于最坏性能。由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。堆排序是就地排序，辅助空间为O(1)，它是不稳定的排序方法。

七.计数排序

 1 #include<iostream>
 2 using namespace std;
 3 
 4 void CountingSort(int A[], int k, int length)
 5 {
 6     if (A == NULL || k < 0 || length <= 0)
 7     {
 8         return;
 9     }
10     int *C = new int[k + 1];
11     int *B = new int[length];
12     for (int i = 0; i <= k; i++)
13     {
14         C[i] = 0;
15     }
16     for (int j = 0; j < length; j++)
17     {
18         C[A[j]]++;
19     }
20     for (int i = 1; i <= k; i++)
21     {
22         C[i] += C[i - 1];
23     }
24     for (int j = length - 1; j >= 0; j--)
25     {
26         B[C[A[j]] - 1] = A[j];
27         C[A[j]]--;
28     }
29     for (int j = 0; j < length; j++)
30     {
31         A[j] = B[j];
32     }
33 }
34 
35 
36 int main()
37 {
38     int A[] = { 11, 2, 3, 3, 4, 10, 0, 6 ,20, 10};
39     CountingSort(A, 20, 10);
40     for (int i = 0; i < 10; i++)
41     {
42         cout << A[i] << " ";
43     }
44     cout << endl;
45     return 0;
46 }

稳定，适用范围比较局限，非负整数，最大值不是很大的情况，数值分布跨度比较小。

八.基数排序

 1 #include<iostream>
 2 #include<math.h>
 3 using namespace std;
 4 
 5 void CountingSort(int A[], int k, int length, int i)
 6 {
 7     int *C = new int[k];
 8     int *B = new int[length];
 9     for (int i = 0; i < k; i++)
10     {
11         C[i] = 0;
12     }
13     for (int j = 0; j < length; j++)
14     {
15         C[(int)(A[j] / pow(10.0, i - 1)) % 10]++;
16     }
17     for (int i = 1; i < k; i++)
18     {
19         C[i] += C[i - 1];
20     }
21     for (int j = length - 1; j >= 0; j--)
22     {
23         B[C[(int)(A[j] / pow(10.0, i - 1)) % 10] - 1] = A[j];
24         C[(int)(A[j] / pow(10.0, i - 1)) % 10]--;
25     }
26     for (int j = 0; j < length; j++)
27     {
28         A[j] = B[j];
29     }
30 }
31 
32 void RadixSort(int A[], int n, int radix, int length)
33 {
34     if (A == NULL || n <= 0 || radix <= 1 || length <= 0)
35     {
36         return;
37     }
38     for (int i = 1; i <= n; i++)
39     {
40         CountingSort(A, radix, length, i);
41     }
42 }
43 
44 int main()
45 {
46     int A[] = { 111, 2, 37, 3, 4, 100, 0, 600, 20, 10};
47     RadixSort(A, 3, 10, 10);
48     for (int i = 0; i < 10; i++)
49     {
50         cout << A[i] << " ";
51     }
52     cout << endl;
53     return 0;
54 }

基数排序过程中不改变元素的相对位置，因此是稳定的！特别适用于非负整数且length >> n的情况。