方法 最好 最坏 平均 空间复杂度 稳定性
冒泡排序 $O(n)$ $O(n^2)$ $O(n^2)$ $O(1)$ 稳定
快速排序 $O(n\log_{2}n)$ $O(n^2)$ $O(n\log_{2}n)$ $O(n\log_{2}n)$ 不稳定
直接插入排序 $O(n)$ $O(n^2)$ $O(n^2)$ $O(1)$ 稳定
希尔排序 $O(n^{1.3})$ $O(1)$ 不稳定
简单选择排序 $O(n^2)$ $O(n^2)$ $O(n^2)$ $O(1)$ 不稳定
堆排序 $O(n\log_{2}n)$ $O(n\log_{2}n)$ $O(n\log_{2}n)$ $O(1)$ 不稳定
归并排序 $O(n\log_{2}n)$ $O(n\log_2{2}n)$ $O(n\log_{2}n)$ $O(n)$ 稳定
基数排序 $O(d(r+n))$ $O(d(r+n))$ $O(d(r+n))$ $O(r)$ 稳定

排序算法的稳定性: 若在原始序列中,$a_i$和$a_j$的关键字相同,$a_i$出现在$a_j$前,经过某种方法排序后,$a_i$的位置仍然在$a_j$前,则称这种算法是稳定的。

交换排序

基本排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void sort(int arr[], int n)
{
	int i,j;
	for(i = 0; i < n-1; i++)
	{
		for(j = i + 1; j < n; j++)
		{
			if(arr[i] < arr[j])
			{
				swap(&arr[i], &arr[j]);
			}
		}
	}
}

冒泡排序

1
2
3
4
5
6
7
8
9
void bubbleSort(int arr[], int n){
	int i, j;
	for(i = 0; i < n; i++){
		for(j = 0; j < n - i - 1; j++){
			if(arr[j] < arr[j+1])
				swap(&arr[j], &arr[j+1]);
		}
	}
}

改进的冒泡排序

在冒泡排序中除了将最小的数据移动到靠后的位置外,还使较小的数据逐渐靠近合适的位置。

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

快速排序

快速排序的基本思想是: 通过一遍排序,,将序列中的数据分割为两部分,其中一部分的所有数据都比另一部分小;然后按照此种方法,对两部分数据分别进行快速排序,直到参与排序的两部分都有序为止。

我们需要一个关键字key来作为分割标准,将数据与key进行比较来把数据分割为两部分。

如下所示,对原始序列5, 0, 9, 8, 1, 4, 6, 3, 7, 5按关键字key = arr[0] = 5进行一次快速排序的过程:

开始 a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9]
开始状态 5(i,key) 0 9 8 1 4 6 3 7 5(j)
a[i] = a[j] 3(i) 0 9 8 1 4 6 3(j) 7 5
a[j] = a[i] 3 0 9(i) 8 1 4 6 9(j) 7 5
a[i] = a[j] 3 0 4(i) 8 1 4(j) 6 9 7 5
a[j] = a[i] 3 0 4 8(i) 1 8(j) 6 9 7 5
a[i] = a[j] 3 0 4 1(i) 1(j) 8 6 9 7 5
a[j] = a[i] 3 0 4 1 1(i,j) 8 6 9 7 5
a[i] = key 3 0 4 1 5(i,j) 8 6 9 7 5

接着对上述结果的两个子序列重复进行上述快速排序过程:

a[0] a[1] a[2] a[3]
3 0 4 1
a[0] a[1] a[2] a[3] a[4]
8 6 9 7 5 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
void QuickSort(int arr[], int left, int right)
{
  if(left >= right)  /* 如果左边索引大于等于右边索引,则排序完毕 */
  {
     return;
  }

  int i = left;
  int j = right;
  int key = arr[i];  /* 关键字key,同时保存此时的arr[i]值 */

  while(i < j) /*本轮排序开始,直到 i == j 结束*/
  {
    while((i < j) && (key <= arr[j]))
    {
      j--; /* 从后边往前早到一个小于key的arr[j] */
    }

    arr[i] = arr[j]; /* 将小于key的arr[j]赋值给arr[i],同时在开始时key保存了arr[i] */

    while((i < j) && (key >= arr[i]))
    {
      i++; /* 从前向后找到一个大于key的arr[i] */
    }

    arr[j] = arr[i]; /* 将大于key的arr[i]赋给arr[j] */

    /* 一次while()循环实现了将一个小于key的arr[j]前移,大于key的arr[i]后移 */
  }

  arr[i] = key;  /* 此时arr[i]=arr[j] */

  /* 对两部分的数据分别在进行快速排序 */
  QuickSort(arr, left, i - 1);
  QuickSort(arr, i + 1, right);
}

插入排序

插入排序的基本思想是: 将一条记录插入到一组已经有序的序列中,继而得到一个有序的,数据个数加1的新序列。

直接插入排序

直接插入排序将序列开始的第一个数据视为有序序列,另一部分视为待排序序列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void InsertSort(int arr[], int n)
{
  int i,j;
  for(i = 1 /* 无序序列开始 */; i < n; i++)
  {
    int tmp = arr[i];
    if(tmp > arr[i - 1])
    {
      /* 从后向前遍历有序序列,找到位置插入新数据 */
      for(j = i - 1; j >= 0 && tmp > arr[j]; j--)
      {
        arr[j+1] = arr[j];
      }
      arr[j+1] = tmp;
    }
  }
}

折半插入排序

在直接插入排序中,主要的时间消耗在数据的比较和移动上,由于前半部分的数据已经有序,则可以采取折半查找的方法来提高查找速度。

折半插入排序节省了排序过程中的比较次数,但是移动次数与直接插入排序相同,所以时间复杂度还是$O(n^2)$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int BinarySort(int arr[],int n)
{
  int i, j;
  int low, hight, m;
  int tmp;
  for(i = 1; i < n; i++)
  {
    tmp = arr[i];
    low = 0;
    high = i - 1;
    while(low <= hight)
    {
      m = (low + high) / 2;
      if(tmp > arr[m])
        high = m - 1;
      else
        low = m + 1;
    }

    for(j = i - 1; j >= high + 1; j--)
      arr[j+1] = arr[j];
    arr[high+1] = tmp;
  }
}

希尔排序

无论是直接插入排序还是折半插入排序,都是将待排序序列视为一个分组,而希尔排序将原始序列按照下标的一定增量分为多个序列,在每个序列中执行直接插入排序。

希尔排序即解决了比较次数的问题,也解决了移动位数的问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void ShellSort(int arr[], int n)
{
  int i, j, d;
  int tmp;
  d = n / 2;
  
  while(d > 0)
  {
    for(i = d; i < n; i++)
    {
      tmp = arr[i];
      j= i - d;
      while(j >= 0 && tmp > arr[j])
      {
        arr[j+d] = arr[j];
        j = j - d;
      }
      arr[j+d] = tmp;
    }
    d = d / 2;
  }
}

选择排序

选择排序是从待排序的序列中选择出最大(最小)值,交换该元素与待排序序列头元素,直到所有待排序的数据有序为止

简单选择排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void SelectSort(int arr[], int n)
{
  int i,j,max;
  for(i = 0; i < n; i++)
  {
    max = i;
    for(j = i; j < n; j++)
    {
      if(arr[max] < arr[j])
        max = j;
    }
    if(i != max)
      swap(&arr[i], &arr[max]);
  }
}

堆排序

二叉堆中所有非终端结点的值均不小于(大于)其左右孩子的值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void HeapAdjust(int arr[], int i, int n)
{
  int nChild;
  int tmp;
  for(; 2 * i + 1 < n; i = nChild)
  {
    nChild = 2 * i + 1;
    if(nChild < n - 1; && arr[nChild+1] > arr[nChild])
      ++nChild;
    if(arr[i] < arr[nChild])
    {
      tmp = arr[i];
      arr[i] = arr[nChild];
      arr[nChild] = tmp;
    }
    else
      break;
  }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void HeapSort(int arr[], int n)
{
  int i;
  
  for(i = (n - 1) / 2; i >= 0; i--)
    HeapAdjust(arr, i, n);

  for(i = n -1; i > 0; i--)
  {
    arr[i] = arr[0] ^ arr[i];
    arr[0] = arr[0] ^ arr[i];
    arr[i] = arr[0] ^ arr[i];
    
    HeapAdjust(arr, 0, i);
	}
}

归并排序

归并排序就是将两个序列合并在一起,并使其有序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void Merge(int arr[], int tmp[], int start, int mid, int  end)
{
  int i = start, j = mid+1; k = start;
  
  while(i != mid+1 && j != end+1)
  {
    if(arr[i] >= arr[j])
      tmp[k++] = arr[j++];
    else
      tmp[k++] = arr[i++];
  }

  while(i != mid+1)
    tmp[k++] = arr[i++];
  while(j != end+1)
    tmp[k++] = arr[j++];

  for(i = start; i <= end; i++)
    arr[i] = tmp[i];
}
1
2
3
4
5
6
7
8
9
10
11
void MergeSort(int arr[], int tmp, int start, int end)
{
  int mid;
  if(start < end)
  {
    mid = (start + end) / 2;
    MergeSort(arr, tmp, start, mid);
    MergeSort(arr, tmp, mid+1, end);
    Merge(arr, tmp, start, midi, end);
  }
}

基数排序

计数排序,桶排序,多关键字排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#define MAXD 8
typedef struct node
{
  char key[MAXD]; //关键字字符串
  struct node* next;
}RecType;

void RadixSort(RecType* &p, int r, int d)
{
  RecType * head[MAXR], *tail[MAXR], *t;
  int i, j, k;
  for(i = d - 1; i >= 0; i--)
  {
    for(j = 0; j < r; j++)
      head[j]=tail[j]=NULL;
   
    while(p != NULL)
    {
      k = p->key[i] - '0';
      if(head[k]==NULL)
      {
        head[k] = p;
        tail[k] = p;
      }
      else
      {
        tail[k]->next = p;
        tail[k] = p;
      }
      p = p->next;
    }
    p = NULL;
   
    for(j = 0; j < r; j++)
     if(head[j] != NULL) 
     {
       if(p == NULL)
       {
         p = head[j];
         t = tail[j];
       }
       else
       {
         t->next = head[j];
         t = tail[j];
       }
     }
     t->next = NULL;
  }
}