感谢菜鸟教程：十大经典排序算法

基础桶排序

进来一个数就丢数组的那个位置里，很好理解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<stdio.h>
int a[100],n;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        int tmp;
        scanf("%d",&tmp);
        a[tmp]++;
    }
    for(int i=0;i<=99;i++)
    if(a[i])for(int j=1;j<=a[i];j++)
            printf("%d ",i);
}

冒泡排序

比较相邻的元素。如果第一个比第二个大，就交换他们两个。

对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。

针对所有的元素重复以上的步骤，除了最后一个。

持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<stdio.h>
int a[100000],n;
void swap(int *a,int *b)
{
    int tmp=*a;
    *a=*b;
    *b=tmp;
}
void bubble_sort(int l,int r)
{
    for (int i = l; i <= r; i++)
    for (int j = l; j <= r - i - 1; j++)
        if (a[j] > a[j + 1])
        swap(&a[j], &a[j+1]);
}
int main()
{
    scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	bubble_sort(1,n);
    for(int i=1;i<=n;i++)printf("%d ",a[i]);
}

选择排序

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。

再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。

重复第二步，直到所有元素均排序完毕。

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
#include <stdio.h>
int a[100000], n;
void swap(int *a, int *b)
{
    int tmp = *a;
    *a = *b;
    *b = tmp;
}
void selection_sort(int l, int r)
{
    for (int i = l; i <= r; i++)
    {
        int min = i;
        for (int j = i + 1; j <= r; j++) //走访未排序的元素
            if (a[j] < a[min])
                min = j;      //找到目前最小值
        swap(&a[min], &a[i]); //做交換
    }
}
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    selection_sort(1, n);
    for (int i = 1; i <= n; i++)
        printf("%d ", a[i]);
}

插入排序

将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。

从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）

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
#include <stdio.h>
int a[100000], n;
void insertion_sort(int l, int r)
{
    for (int i = l + 1; i <= r; i++)
    {
        int key = a[i];
        int j = i - 1;
        while ((j >= 0) && (key < a[j]))
        {
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = key;
    }
}
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    insertion_sort(1, n);
    for (int i = 1; i <= n; i++)
        printf("%d ", a[i]);
}

快速排序

从数列中挑出一个元素，称为 “基准”（pivot）;

重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；

递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；

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
#include <stdio.h>
int a[100000], n;
void swap(int *a, int *b)
{
    int tmp = *a;
    *a = *b;
    *b = tmp;
}
void quick_sort(int l, int r)
{
    int i = l, j = r, mid = a[(l + r) / 2]; //将当前序列在中间位置的数定义为分隔数
    do
    {
        while (a[i] < mid)i++; //在左半部分寻找比中间数大的数
        while (a[j] > mid)j--; //在右半部分寻找比中间数小的数
        if (i <= j)
        { 
            swap(&a[i], &a[j]);//若找到一组与排序目标不一致的数对则交换它们
            i++;
            j--; //继续找
        }
    } while (i <= j); //注意这里不能有等号
    if (l < j) quick_sort(l, j); //若未到两个数的边界，则递归搜索左右区间
    if (i < r) quick_sort(i, r);
}
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    quick_sort(1, n);
    for (int i = 1; i <= n; i++)
        printf("%d ", a[i]);
}

归并排序

申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；

设定两个指针，最初位置分别为两个已经排序序列的起始位置；

比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；

重复步骤 3 直到某一指针达到序列尾；

将另一序列剩下的所有元素直接复制到合并序列尾。

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
#include <stdio.h>
int a[100000], r[100000], n;
void msort(int s, int t)
{
	if (s == t) return; //如果只有一个数字则返回，无须排序
	int mid = (s + t) / 2;
	msort(s, mid);				   //分解左序列
	msort(mid + 1, t);			   //分解右序列
	int i = s, j = mid + 1, k = s; //接下来合并
	while (i <= mid && j <= t)
	{
		if (a[i] <= a[j]) r[k++] = a[i++];
		else r[k++] = a[j++];
	}
	while (i <= mid) r[k++] = a[i++]; //复制左边子序列剩余
	while (j <= t) r[k++] = a[j++]; //复制右边子序列剩余
	for (int i = s; i <= t; i++) a[i] = r[i];
}
int main()
{
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
	msort(1, n);
	for (int i = 1; i <= n; i++) printf("%d ", a[i]);
}