排序算法

八种排序

三种 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
25
26
27
28
29
#include <iostream>
using namespace std;
int main()
{
    //给定乱序数组a
    int a[10] = { 1, 10, 4, 2, 3, 8, 5, 9, 7, 6 };
    //这里令n = 10，方便给出通解
    int n = 10;
    //两层循环，内层做从左到右遍历数组中未排序元素，并进行比较操作；外层每次去除已定序元素，限制下一次内循环排序范围。
    //外循环一共循环n - 1次，因为每一次外循环结束可以定下一个元素的位置，到第n - 1次排序完成，就只剩下一个元素，自然不用再排序。
    for (int i = 0; i < n - 1; i++)
    {
        //内循环从数组最左边元素到未定序的最右边元素遍历，注意！下面使用a[j+1]，这里的j范围要注意，不要越界了！
        for (int j = 0; j < n - 1 - i; j++)
        {
            //比较，此判断是将数组按升序排，降序反之即可
            if (a[j] > a[j + 1])
            {
                //临时变量temp，完成交换数组相邻两个元素
                int temp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = temp;
            }
        }
    }
    for (int i = 0; i < n; i++)
        cout << a[i] << ' ';
	return 0;
}

二.选择排序

较简单，直接代码注释结合理解即可

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
#include <iostream>
using namespace std;
int main()
{
    //给定乱序数组a
    int a[10] = { 1, 10, 4, 2, 3, 8, 5, 9, 7, 6 };
    //这里令n = 10，方便给出通解
    int n = 10;
    //两层循环，外层循环每次更新未定序最左元素下标mmin，然后到内循环进行数组遍历寻找未定序元素中更小值，循环结束后判断是否有更小值，如果有，就替换。
    //外循环一共循环n - 1次，因为每一次外循环结束可以定下一个元素的位置，到第n - 1次排序完成，就只剩下一个元素，自然不用再排序。
    for (int i = 0; i < n - 1; i++)
    {
        //每次更新未定序最左元素下标
        int mmin = i;
        //内循环进行数组遍历寻找未定序元素中更小值
        for (int j = i + 1; j < n; j++)
        {
            if (a[j] < a[mmin]) mmin = j;
        }
        //判断未定序元素中是否有更小值，如果有，就替换。
        if (mmin != i)
        {
            int temp = a[i];
            a[i] = a[mmin];
            a[mmin] = temp;
        }
    }
    for (int i = 0; i < n; i++)
        cout << a[i] << ' ' ;
	return 0;
}

三.插入排序

打扑克牌时，当第一张摸到 6，然后第二张摸到 5，会自然的与第一张比较，并把 5 插入到 6 的左边，第三张摸到 8，又把 8 插入到 6 的右边（不同个人习惯，就会有升降序不同的情况）总而言之，这就是插入排序法！下面代码实现

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
#include <iostream>
using namespace std;
int main()
{
    //给定乱序数组a
    int a[10] = { 1, 10, 4, 2, 3, 8, 5, 9, 7, 6 };
    //这里令n = 10，方便给出通解
    int n = 10;
    for (int i = 1; i < n; i++)
    {
        //摸一张新牌a[i],i之前的都是手牌，如果新牌大不用往回插，直接放右边就行，反之进行下面操作。
        if (a[i] < a[i - 1])
        {
            //临时变量temp存储新牌点数
            int temp = a[i];
            //j变量循环外单独定义，因为循环结束还会用到它，不然会报错未定义
            int j;
            //要插入新牌，循环往回找新牌点数介于哪个位置，结束条件要注意，因为这些牌都是升序排好的，所以从序数大到小直到找到第一张小于新牌为止
            for (j = i - 1; j >= 0 && a[j] > temp; j--)
            {
                //还没找到第一张小于新牌前，每张牌都要为新牌腾位置往右移。
                a[j + 1] = a[j];
            }
            //找到后，在这张牌后一个位子插入新牌即可。
            a[j + 1] = temp;
        }
    }
    for (int i = 0; i < n; i++)
        cout << a[i] << ' ';
    return 0;
}

四.桶排序

五.基数排序

六.计数排序

七.归并排序

分分—->合合

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
#include <iostream>
using namespace std;
int a[1005];
int b[1005];
int n;
void bin(int z, int mid, int y)
{
	int q = z, p = mid + 1;
	for (int i = z; i <= y; i++)
	{
		if (p > y || (q <= mid && a[q] <= a[p]))
		{
			b[i] = a[q++];
		}
		else b[i] = a[p++];
	}
	for (int i = z; i <= y; i++)
		a[i] = b[i];
}
void sot(int z, int y)
{
	if (z == y) return;
	int mid = (y + z) / 2;
	sot(z, mid);
	sot(mid + 1, y);
	bin(z, mid, y);
}
int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	sot(1, n);
	for (int i = 1; i <= n; i++)
		cout << a[i] << ' ';
	return 0;
}

八.快速排序

找基数，换换换

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
#include <iostream>
using namespace std;
int a[1005];
int n;
void sot(int z, int y)
{
	int mid = (z + y) / 2;
	int x = a[mid];
	int i = z, j = y;
	while (i <= j)
	{
		while (a[i] < x) i++;
		while (a[j] > x) j--;
		if (i <= j)
		{
			swap(a[i], a[j]);
			i++;
			j--;
		}
	}
	if (z < j) sot(z, j);
	if (i < y) sot(i, y);
}
int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	sot(1, n);
	for (int i = 1; i <= n; i++)
		cout << a[i] << ' ';
	return 0;
}