各种排序算法总结

1 /*
 2 * @brief shell sort
 3 * @param [in] arr: the array be sorted
 4 *          [in] length: the array size
 5 * @return void
 6 */
 7 void ShellSort(int arr[], int length)
 8 {
 9     for (int inc = length / 2; inc > 0; inc /= 2) {
10         for (int i = inc; i < length; i++) {
11             for (int j = i; j >= inc && arr[j - inc] > arr[j]; j -= inc) {
12                 swap(arr[j], arr[j - inc]);
13             }
14         }
15     }
16 }

5、快速排序

快速排序的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

1 /*
 2  * 快速排序
 3  * 快速排序是一种分治的排序算法，它将一个数组分成两个子数组，将两部分独立地排序。
 4  * 快速排序和归并排序是互补的：归并排序将数组分成两个子数组分别排序，并将有序的子数组归并以将整个数组排序；
 5  * 而快速排序的方式是当两个子数组有序时整个数组也就自然有序了。归并排序中，递归发生在处理整个数组之前，
 6  * 一个数组被分为两半；快速排序中，递归调用发生在处理整个数组之后，切分的位置取决于数组的内容。
 7  */
 8 int Partion(int arr[], int left, int right)
 9 {
10     int x = arr[right];
11     int i, j;
12 
13     for (i = j = left; i < right; i++) {
14         if (arr[i] <= x) {
15             swap(arr[i], arr[j++]);
16         }
17     }
18     swap(arr[j], arr[right]);
19 
20     return j;
21 }
22 void QuickSort(int arr[], int left, int right)
23 {
24     if (left < right) {
25         int mid = Partion(arr, left, right);
26         QuickSort(arr, left, mid - 1);
27         QuickSort(arr, mid + 1, right);
28     }
29 }
30 void QuickSort(int arr[], int length)
31 {
32     QuickSort(arr, 0, length - 1);
33 }

 6、归并排序

归并排序是将两个有序的数组归并成一个更大的有序数组。要将一个数组排序，可以先（递归的）将他分成两半分别排序，让后将结果归并起来。它能够保证将任意长度为N的数组排序所需时间和NlogN成正比；它的主要缺点就是所需的额外空间和N成正比。归并排序是稳定的排序算法。

1 /*
 2  * 归并排序
 3  * 归并排序将数组分成两个子数组分别排序，并将有序的子数组归并以将整个数组排序
 4  */
 5 void Merge(int arr[], int aux[], int left, int mid, int right) 
 6 {
 7     int i = left;
 8     int j = mid + 1;
 9     int k = left;
10 
11     while (i <= mid && j <= right) {
12         if (arr[i] > arr[j]) {
13             aux[k++] = arr[j++];
14         }
15         else {
16             aux[k++] = arr[i++];
17         }
18     }
19     while (i <= mid) {
20         aux[k++] = arr[i++];
21     }
22     while (j <= right) {
23         aux[k++] = arr[j++];
24     }
25     for (int i = left; i <= right; i++) {
26         arr[i] = aux[i];
27     }
28 }
29 void MergeSort(int arr[], int aux[], int left, int right)
30 {
31     if (left < right) {
32         int mid = left + (right - left) / 2;
33         MergeSort(arr, aux, left, mid);
34         MergeSort(arr, aux, mid + 1, right);
35         Merge(arr, aux, left, mid, right);
36     }
37 }
38 void MergeSort(int arr[], int length)
39 {
40     int *aux = new int[length];
41     MergeSort(arr, aux, 0, length - 1);
42     delete []aux;
43 }

7、 堆排序

堆排序可以分为两个阶段。在堆的构造阶段，我们将元使数组重新组织安排进一个堆中；然后在下沉阶段，我们从堆中按递减顺序取出所有元素并得到排序结果。堆排序主要工作都是在堆的下沉阶段完成的，这里我们将堆中最大的元素删除，然后放入堆缩小后数组中空出的位置。

1 /*
 2  * 堆排序
 3  * 堆排序是用堆来实现的一种排序算法，堆排序分为两个阶段，在堆的构造阶段中，我们将原始数据重新组织安排
 4  * 进一个堆中；然后在下沉排序阶段，我们从堆中按照递减顺序取出所有元素并得到排序算法
 5  */
 6 void Sink(int arr[], int i, int length)
 7 {
 8     while (2 * i <= length) {
 9         int child = 2 * i;
10         if (child < length && arr[child] < arr[child + 1]) {
11             child++;
12         }
13         if (arr[i] >= arr[child]) {
14             break;
15         }
16 
17         swap(arr[i], arr[child]);
18         i = child;
19     }
20 }
21 void HeapSort(int arr[], int length)
22 {
23     length--; /* 此时length代表数组最后一个元素下标 */
24     for (int i = length / 2; i >= 0; i--) { /* 这里一定要 i>=0，否则建堆不完全 */
25         Sink(arr, i, length);
26     }
27     
28     while(length >= 0) {
29         swap(arr[0], arr[length--]);
30         Sink(arr, 0, length);
31     }
32 }

8、各种排序算法的稳定性和时间复杂度分析

什么是排序的稳定性呢？如果一个排序算法能够保留数组中重复元素的相对位置则可以称为是稳定的。以下是各个排序算法稳定性总结：

• 选择排序、快速排序、希���排序、堆排序不是稳定的排序算法，
• 冒泡排序、插入排序、归并排序和基数排序是稳定的排序算法。

• 冒泡法：这是最原始，也是众所周知的最慢的算法了。他的名字的由来因为它的工作看来象是冒泡：复杂度为O(n*n)。当数据为正序，将不会有交换。复杂度为O(n^2)。
• 直接插入排序：O(n^2)
• 选择排序：O(n^2)
• 快速排序：平均时间复杂度log2(n)*n，所有内部排序方法中最高好的，大多数情况下总是最好的。
• 归并排序：log2(n)*n
• 堆排序：log2(n)*n
• 希尔排序：算法的复杂度为log2(n)*n

 下面是一个总的表格，大致总结了我们常见的所有的排序算法的特点。