排序 | 个人简介

方法	最好	最坏	平均	空间复杂度	稳定性
冒泡排序	$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	void sort(int arr[], int n)
2	{
3	int i,j;
4	for(i = 0; i < n-1; i++)
5	{
6	for(j = i + 1; j < n; j++)
7	{
8	if(arr[i] < arr[j])
9	{
10	swap(&arr[i], &arr[j]);
11	}
12	}
13	}
14	}

冒泡排序

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

改进的冒泡排序

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

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

快速排序

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

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

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

开始	a[0]	a[2]	a[3]	a[4]	a[5]	a[6]	a[7]	a[8]	a[9]
开始状态	5(i,key)	9	8	1	4	6	3	7	5(j)
a[i] = a[j]	3(i)	9	8	1	4	6	3(j)	7	5
a[j] = a[i]	3	9(i)	8	1	4	6	9(j)	7	5
a[i] = a[j]	3	4(i)	8	1	4(j)	6	9	7	5
a[j] = a[i]	3	4	8(i)	1	8(j)	6	9	7	5
a[i] = a[j]	3	4	1(i)	1(j)	8	6	9	7	5
a[j] = a[i]	3	4	1	1(i,j)	8	6	9	7	5
a[i] = key	3	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	void QuickSort(int arr[], int left, int right)
2	{
3	if(left >= right) /* 如果左边索引大于等于右边索引,则排序完毕 */
4	{
5	return;
6	}
7
8	int i = left;
9	int j = right;
10	int key = arr[i]; /* 关键字key,同时保存此时的arr[i]值 */
11
12	while(i < j) /本轮排序开始,直到 i == j 结束/
13	{
14	while((i < j) && (key <= arr[j]))
15	{
16	j--; /* 从后边往前早到一个小于key的arr[j] */
17	}
18
19	arr[i] = arr[j]; /* 将小于key的arr[j]赋值给arr[i],同时在开始时key保存了arr[i] */
20
21	while((i < j) && (key >= arr[i]))
22	{
23	i++; /* 从前向后找到一个大于key的arr[i] */
24	}
25
26	arr[j] = arr[i]; /* 将大于key的arr[i]赋给arr[j] */
27
28	/* 一次while()循环实现了将一个小于key的arr[j]前移,大于key的arr[i]后移 */
29	}
30
31	arr[i] = key; /* 此时arr[i]=arr[j] */
32
33	/* 对两部分的数据分别在进行快速排序 */
34	QuickSort(arr, left, i - 1);
35	QuickSort(arr, i + 1, right);
36	}

插入排序

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

直接插入排序

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

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

折半插入排序

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

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

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

选择排序

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

简单选择排序

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

堆排序

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

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	void HeapSort(int arr[], int n)
2	{
3	int i;
4
5	for(i = (n - 1) / 2; i >= 0; i--)
6	HeapAdjust(arr, i, n);
7
8	for(i = n -1; i > 0; i--)
9	{
10	arr[i] = arr[0] ^ arr[i];
11	arr[0] = arr[0] ^ arr[i];
12	arr[i] = arr[0] ^ arr[i];
13
14	HeapAdjust(arr, 0, i);
15	}
16	}

归并排序

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

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];
}

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);
  }
}

基数排序

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

#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;
  }
}

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

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

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

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

1	#define MAXD 8
2	typedef struct node
3	{
4	char key[MAXD]; //关键字字符串
5	struct node* next;
6	}RecType;
7
8	void RadixSort(RecType* &p, int r, int d)
9	{
10	RecType * head[MAXR], tail[MAXR], t;
11	int i, j, k;
12	for(i = d - 1; i >= 0; i--)
13	{
14	for(j = 0; j < r; j++)
15	head[j]=tail[j]=NULL;
16
17	while(p != NULL)
18	{
19	k = p->key[i] - '0';
20	if(head[k]==NULL)
21	{
22	head[k] = p;
23	tail[k] = p;
24	}
25	else
26	{
27	tail[k]->next = p;
28	tail[k] = p;
29	}
30	p = p->next;
31	}
32	p = NULL;
33
34	for(j = 0; j < r; j++)
35	if(head[j] != NULL)
36	{
37	if(p == NULL)
38	{
39	p = head[j];
40	t = tail[j];
41	}
42	else
43	{
44	t->next = head[j];
45	t = tail[j];
46	}
47	}
48	t->next = NULL;
49	}
50	}

排序