几种常见的排序算法

1.插入类排序

在一个已经有序的序列中，插入一个新的记录。有直接插入排序、折半插入排序、希尔排序。

插入类排序

直接插入排序

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

最坏情况下，时间复杂度为O(n^2)，最好的情况下为O(n)。平均时间复杂度为O(n^2)。

算法所需额外空间只有一个temp，所以空间复杂度为O(1)。

希尔排序

希尔排序又叫缩小增量排序，其本质还是插入排序，只是将待排序的序列按照某种规则分成几个子序列，分别对这几个子序列进行直接插入排序。这个规则就是增量，按照缩小增量的规则，希尔排序的每趟排序都会使整个序列更加有序。等到基本有序，再来一趟直接插入排序，使排序效率更高。

希尔排序的平均时间复杂度为O(nlogn)，空间复杂度为O(1)。

2.交换类排序

每一趟排序，都通过一系列交换动作，让一个记录排到它最终的位置上。有冒泡排序。快速排序。

冒泡排序

冒泡排序算法结束的条件是在一趟排序过程中没有发生元素交换。

冒泡排序

冒泡排序算法结束的条件是在一趟排序过程中没有发生元素交换。

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

最坏情况下，时间复杂度为O(n^2)，最好的情况下为O(n)。平均时间复杂度为O(n^2)。

算法所需额外空间只有一个temp，所以空间复杂度为O(1)。

快速排序

 1 void QuickSort(int R[], int l, int r)
 2 {
 3     if (l < r)
 4     {
 5         int i = l, j = r, temp = R[l];
 6         while (i < j)
 7         {
 8             while (i < j && temp < R[j])
 9                 --j;
10             if (i < j)
11             {
12                 R[i++] = R[j];
13             }
14             while (i < j && temp > R[i])
15                 ++i;
16             if (i < j)
17             {
18                 R[j--] = R[i];
19             }
20         }
21         R[i] = temp;
22         QuickSort(R, l, i - 1);
23         QuickSort(R, i + 1, r);
24     }
25 }

快排最好情况下时间复杂度为O(nlogn)，序列越接近无序；最坏情况下为O(n^2)。平均时间复杂度为O(nlogn)。就平均时间而言，快排是所有排序算法中最好的。快排的排序趟数和初始序列有关。空间复杂度为O(logn)，因为递归需要栈的辅助。

3.选择类排序

每一趟排序，都选出一个最小（或最大）的记录，把它和序列中的第一个（或最后一个）记录交换，这样一个最值记录到位。有简单选择排序、堆排序。

简单选择排序

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

简单选择排序的时间复杂度为O(n^2)，空间复杂度为O(1)。

4.归并类排序

归并就是将两个或以上的有序序列合并成一个新的有序序列。

5.基数类的排序

基于多关键字的思想，将一个逻辑关键字拆分成多个关键字。