排序算法大概分为:交换类(快速排序和冒泡排序),插入类(简单插入排序和希尔排序),选择类(简单选择排序和堆排序),归并类(二路归并排序和多路归并排序),以下算法全部以增序为例

交换类排序:

冒泡排序

一共进行$n-1$轮次(最后一轮没必要,因为就剩一个了顺序已经排好),每一轮把第$[0,1,2,3…,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
29
30
31
32
#include<iostream>
#include<vector>
#include<string>
#include<ctime>
using namespace std;
void bubbleSort(vector<int>& array);
int main()
{
	clock_t startTime, endTime;
	startTime = clock();//计时开始
	vector<int> array = {5, 1, 9, 3, 7, 4, 8, 6, 2 };
	bubbleSort(arrray);
	endTime = clock();//计时结束
	cout << "总计时长" << (double)(endTime - startTime) / CLOCKS_PER_SEC << "s" << endl;
	return 0;
}
void bubbleSort(vector<int>& array)
{
	bool flag = true;//flag为false的意义为i之后的已经不需要排序了
	for (int i = 0; i < array.size() && flag; i++)
	{
		flag = false;
		for (int j = array.size() - 2; j >= i; j--)
		{
			if (array[j] > array[j + 1])
			{
				swap(array[j], array[j + 1]);
				flag = true;
			}
		}
	}
}

总结分析:

名称 时间 最好 最坏 空间 稳定 备注
冒泡排序 $O(n^2)$ $O(n)$ $O(n^2)$ $O(1)$ 是 每一轮都有一个元素到最终位置上

快速排序

把一个序列,选一个数(第一个数)进行划分。左边小于x,中间x,右边大于x。再依次递归划分左右两边。

实例代码:

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
#include<iostream>
#include<vector>
#include<string>
#include<ctime>
using namespace std;

void Qsort(vector<int>& array,int low,int high);//快速排序
int Partition(vector<int>& array, int low, int high);
int main()
{
	clock_t startTime, endTime;
	startTime = clock();//计时开始
	vector<int> array = {5, 1, 9, 3, 7, 4, 8, 6, 2 };
	Qsort(array,0,array.size()-1);
	endTime = clock();//计时结束
	cout << "总计时长" << (double)(endTime - startTime) / CLOCKS_PER_SEC << "s" << endl;
	return 0;
}
void Qsort(vector<int>& array, int low, int high)
{
	int privot;
	if (low<high)
	{
		privot = Partition(array, low, high);
		Qsort(array,low,privot-1);
		Qsort(array, privot + 1, high);
	}
}
int Partition(vector<int>& array, int low, int high)
{
    int privotKey = array[low];
	while (low<high)
	{
		while (low<high&&array[high]>=privotKey)//改为>则会使结果相同的数字在最终枢轴坐标左侧
		{
			high--;
		}
		array[low] = array[high];
		while (low < high&&array[low] <= privotKey)//改为<则会使结果相同的数字在最终枢轴坐标右侧
		{
			low++;
		}
		array[high] = array[low];
	}
	array[low] = privotKey;
	return low;
}

总结分析:

名称 时间 最好 最坏 空间 稳定 备注
快速排序 $O(nlogn)$ $O(nlogn)$ $O(n^2)$ 栈的深度$O(log_2n)$ 否 基本有序或者基本逆序，效果最差

二路快速排序

目的是处理数组中重复数据多,容易使时间复杂度退化到$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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include<iostream>
#include<vector>
#include<cstdlib>
#include<ctime>
#include<ctime>
using namespace std;

void swap(vector<int>& array, int p, int q);
void Qsort(vector<int>& array, int low, int high);//二路快速排序+随机化
int Partition2(vector<int>& array, int low, int high);
int main()
{
	clock_t startTime, endTime;
	srand((unsigned)time(NULL));
	startTime = clock();//计时开始
	vector<int> array = { 5, 1, 9, 3, 7, 4, 8, 6, 2 };
	Qsort(array, 0, array.size() - 1);
	endTime = clock();//计时结束
	cout << "总计时长" << (double)(endTime - startTime) / CLOCKS_PER_SEC << "s" << endl;
	return 0;
}
void Qsort(vector<int>& array, int low, int high)
{
	int privot;
	if (low<high)
	{
		privot = Partition2(array, low, high);
		Qsort(array, low, privot - 1);
		Qsort(array, privot + 1, high);
	}
}

int Partition2(vector<int>& array, int low, int high)
{
	swap(array,low,low + rand()%(high-low+1));
	int privotKey = array[low];
	int lowP = low+1;
	int highP = high;
	while (true)
	{
		while (lowP<=highP&&array[lowP] < privotKey)
		{
			lowP++;
		}
		while (highP>= lowP+1&&array[highP] > privotKey)
		{
			highP--;
		}
		if (lowP > highP) break;
		swap(array,lowP,highP);
		highP--;
		lowP++;
	}
	swap(array,low,highP);
	return highP;
}
void swap(vector<int>& array, int p, int q)
{
	int temp = array[p];
	array[p] = array[q];
	array[q] = temp;
}

三路快速排序

目的是处理数组中重复数据多,容易使时间复杂度退化到$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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include<iostream>
#include<vector>
#include<cstdlib>
#include<ctime>
#include<ctime>
using namespace std;

void swap(vector<int>& array, int p, int q);
void Qsort3(vector<int>& array, int low, int high);
vector<int> Partition3(vector<int>& array, int low, int high);
int main()
{
	clock_t startTime, endTime;
	srand((unsigned)time(NULL));
	startTime = clock();//计时开始
	vector<int> array = { 5, 1, 9, 3, 7, 4, 8, 6, 2 };
	Qsort3(array, 0, array.size() - 1);
	endTime = clock();//计时结束
	cout << "总计时长" << (double)(endTime - startTime); // CLOCKS_PER_SEC << "s" << endl;
	return 0;
}
void Qsort3(vector<int>& array, int low, int high)
{
	vector<int> privots;
	if (low<high)
	{
		privots = Partition3(array, low, high);
		Qsort3(array, low, privots[0]);
		Qsort3(array, privots[1], high);
	}
}
vector<int> Partition3(vector<int>& array, int low, int high)
{
	vector<int> privots;
	swap(array, low, low + rand() % (high - low + 1));
	int privotKey = array[low];
	int lowP = low;
	int highP = high+1;
	int pos = low + 1;
	while (pos<highP)
	{
		if (array[pos]<privotKey)
		{
			swap(array,lowP+1,pos);
			pos++;
			lowP++;
		}
		else if (array[pos] > privotKey)
		{
			swap(array,highP-1,pos);
			highP--;
		}
		else
		{
			pos++;
		}
	}
	swap(array, low, lowP);
	privots.push_back(lowP-1);
	privots.push_back(highP);
	return privots;
}

void swap(vector<int>& array, int p, int q)
{
	int temp = array[p];
	array[p] = array[q];
	array[q] = temp;
}

单链表快速排序

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <iostream>

using namespace std;

struct ListNode
{
    ListNode *next;
    int val;

    ListNode(int val) : val(val), next(nullptr)
    {}
};
//个函数很重要需要特别主意，它可以用一次遍历把一个单链表分为{小于key}key{大于key}三部分
ListNode *partition(ListNode *start, ListNode *end)
{
    int key = start->val;
    ListNode *slow = start;
    ListNode *fast = slow->next;
    while (fast != end)
    {
        if (fast->val <= key)
        {
            slow=slow->next;
            swap(fast->val, slow->val);
        }
        fast = fast->next;
    }
    swap(start->val, slow->val);
    return slow;
}

void quickSort(ListNode *start, ListNode *end)
{
    if (start != end)
    {
        ListNode *index = partition(start, end);
        quickSort(start, index);
        quickSort(index->next, end);
    }
}


int main()
{
    ListNode *head = new ListNode(3);
    ListNode *work = head;
    ListNode *p = new ListNode(1);
    work->next = p;
    work = work->next;
    p = new ListNode(3);
    work->next = p;
    work = work->next;
    p = new ListNode(5);
    work->next = p;
    work = work->next;
    p = new ListNode(4);
    work->next = p;
    work = work->next;
    quickSort(head,NULL);
    while (head)
    {
        cout<<head->val<<" ";
        head=head->next;
    }
    return 0;
}

插入排序

直接插入排序

前面的已经有序,把后面的插入到前面有序的元素中,不断增长有序序列。
1.找到待插入位置
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
30
31
#include<iostream>
#include<vector>
#include<string>
#include<ctime>
using namespace std;

void directInsertSort(vector<int>& array);
int main()
{
	clock_t startTime, endTime;
	startTime = clock();//计时开始
	vector<int> array = {5, 1, 9, 3, 7, 4, 8, 6, 2 };
	directInsertSort(array);
	endTime = clock();//计时结束
	cout << "总计时长" << (double)(endTime - startTime) / CLOCKS_PER_SEC << "s" << endl;
	return 0;
}
void directInsertSort(vector<int>& array)
{
	for (int i = 1; i < array.size(); i++)
	{
		int temp = array[i];
		int j = i - 1;
		while (j >= 0 && temp < array[j])
		{
			array[j + 1] = array[j];
			j--;
		}
		array[j + 1] = temp;
	}
}

总结分析:

名称 时间 最好 最坏 空间 稳定 备注
直接插入排序 $O(n^2)$ $O(n)$ $O(n^2)$ $O(1)$ 是 适用于顺序存储

希尔排序

希尔排序又称为缩小增量排序,把整个列表分成多个$L[i,i+d,i+2d…i+kd]$
这样的列表，每个进行直接插入排序。每一轮不断缩小d的值,直到全部有序(最后的d是1)。

实例代码:

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
#include<iostream>
#include<vector>
#include<string>
#include<ctime>
using namespace std;

void shellSort(vector<int>& array);//其实就相当于直接插入排序
int main()
{
	clock_t startTime, endTime;
	startTime = clock();//计时开始
	vector<int> array = {5, 1, 9, 3, 7, 4, 8, 6, 2 };
	shellSort(array);
	endTime = clock();//计时结束
	cout << "总计时长" << (double)(endTime - startTime) / CLOCKS_PER_SEC << "s" << endl;
	return 0;
}
void shellSort(vector<int>& array)
{
	int increment = array.size();
	do
	{
		increment = increment / 3 + 1;
		for (int i = increment; i<array.size(); i++)
		{
			int temp = array[i];
			int j = i - increment;
			while (j>=0 && temp<array[j])
			{
				array[j + increment] = array[j];
				j -= increment;
			}
			array[j + increment] = temp;
		}
	} while (increment>1);
}

总结分析:

名称 时间 最好 最坏 空间 稳定 备注
希尔排序 $O(n^{1.3})$ $O(n^2)$ $O(1)$ 否

选择类排序

简单选择排序

前面已经有序,后面选择最小的与前面交换,从有序序列尾不断增长有序序列

实例代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<iostream>
#include<vector>
#include<string>
#include<ctime>
using namespace std;

void easySelectSort(vector<int>& array);//简单选择排序(适用于数组，链表涉及到交换)
int main()
{
	clock_t startTime, endTime;
	startTime = clock();//计时开始
	vector<int> array = {5, 1, 9, 3, 7, 4, 8, 6, 2 };
	easySelectSort(array);
	endTime = clock();//计时结束
	cout << "总计时长" << (double)(endTime - startTime) / CLOCKS_PER_SEC << "s" << endl;
	return 0;
}

总结分析:

名称 时间 最好 最坏 空间 稳定 备注
简单选择排序 $O(n^2)$ $O(n^2)$ $O(n^2)$ $O(1)$ 否

堆排序

最好索引从1开始!!!!设当前节点是号是n,当索引从1开始时2*n正处于子树中,而索引从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
38
39
40
41
42
43
44
45
46
47
48
#include<iostream>
#include<vector>
#include<string>
#include<ctime>
using namespace std;

void heapSort(vector<int>& array);//堆排序必须从1开始，因为若是从0开始当前下标乘以2后的位置就不是当前节点的孩子节点了
void heapAdjust(vector<int>& array, int start, int end);
int main()
{
	clock_t startTime, endTime;
	startTime = clock();//计时开始
	vector<int> array = {5, 1, 9, 3, 7, 4, 8, 6, 2 };
	heapSort(array);
	endTime = clock();//计时结束
	cout << "总计时长" << (double)(endTime - startTime) / CLOCKS_PER_SEC << "s" << endl;
	return 0;
}
void heapSort(vector<int>& array)
{
	for (int i = (array.size()-1)/2; i >=1; i--)
	{
		heapAdjust(array, i, array.size()-1);
	}
	for (int i = array.size()-1; i > 1; i--)//之所以是>1而不是>=1是因为只剩一个没必要了
	{
		swap(array[1],array[i]);
		heapAdjust(array,1,i-1);
	}
}
void heapAdjust(vector<int>& array,int start,int end)
{
	int temp = array[start];
	for (int i = start*2; i <= end ; i*=2)
	{
		if (i+1<=end && array[i]<array[i+1])//判断+1后是否越界
		{
			i++;
		}
		if (temp>=array[i])
		{
			break;//注意！！！！！无需continue,因为开始建堆的时候就是从下向上调整的，上面不变动下面就肯定不需要变动
		}
		array[start] = array[i];
		start = i;
	}
	array[start] = temp;
}

分析总结:

名称 时间 最好 最坏 空间 稳定 备注
堆排序 $O(nlogn)$ $O(nlogn)$ $O(nlogn)$ $O(1)$ 否

归并排序(二路)

由上向下-递归

归并排序的形式是一颗二叉树，遍历的次数就是二叉树的深度$O(logn)$,一共n个数

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
递归:
#include<iostream>
#include<vector>
#include<string>
#include<ctime>
using namespace std;

void mergeSort(vector<int>& array, int left, int right);//归并排序
void merge(vector<int>& array, int left, int mid, int right);
int main()
{
	clock_t startTime, endTime;
	startTime = clock();//计时开始
	vector<int> array = {5, 1, 9, 3, 7, 4, 8, 6, 2 };
	mergeSort(array,0,array.size()-1);
	endTime = clock();//计时结束
	cout << "总计时长" << (double)(endTime - startTime) / CLOCKS_PER_SEC << "s" << endl;
	return 0;
}
void mergeSort(vector<int>& array,int left,int right)
{
	if (left<right)
	{
		int mid = (left + right) / 2;
		mergeSort(array,left,mid);
		mergeSort(array, mid+1, right);
		merge(array,left,mid,right);
	}
}
void merge(vector<int>& array,int left,int mid,int right)
{
	int i = left;
	int j = mid + 1;
	vector<int> temp;
	while (i<=mid && j<=right)
	{
		if (array[i]<array[j])
		{
			temp.push_back(array[i++]);
		}
		else
		{
			temp.push_back(array[j++]);
		}
	}
	while (i<=mid)
	{
		temp.push_back(array[i++]);
	}
	while (j<=right)
	{
		temp.push_back(array[j++]);
	}
	for (int i = 0; i < temp.size(); i++)
	{
		array[left+i] = temp[i];
	}
}
非递归:
#include<iostream>
#include<vector>
#include<string>
#include<ctime>
using namespace std;
void merge(vector<int>& array, int left, int mid, int right);
void merge_sort_down2up(vector<int> &array);
void merge_groups(vector<int>& array, int gap);
int main()
{
	clock_t startTime, endTime;
	startTime = clock();//计时开始
	vector<int> array = {5, 1, 9, 3, 7, 4, 8, 6, 2 };
	merge_sort_down2up(array);
	endTime = clock();//计时结束
	cout << "总计时长" << (double)(endTime - startTime) / CLOCKS_PER_SEC << "s" << endl;
	return 0;
}
void merge(vector<int>& array,int left,int mid,int right)
{
	int i = left;
	int j = mid + 1;
	vector<int> temp;
	while (i<=mid && j<=right)
	{
		if (array[i]<array[j])
		{
			temp.push_back(array[i++]);
		}
		else
		{
			temp.push_back(array[j++]);
		}
	}
	while (i<=mid)
	{
		temp.push_back(array[i++]);
	}
	while (j<=right)
	{
		temp.push_back(array[j++]);
	}
	for (int i = 0; i < temp.size(); i++)
	{
		array[left+i] = temp[i];
	}
}
void merge_sort_down2up(vector<int>& array) 
{
	for (int i = 1; i < array.size(); i = i * 2)
	{
		merge_groups(array, i);
	}
}
void merge_groups(vector<int>& array, int gap)
{
	int twolen = 2 * gap;
	int i;
	for (i = 0; i + twolen - 1 < array.size(); i += twolen) {
		int start = i;
		int mid = i + gap - 1;
		int end = i + twolen - 1;
		merge(array, start, mid, end);
	}
	// 最后还有一个gap
	if (i + gap - 1 < array.size() - 1) {
		merge(array, i, i + gap - 1, array.size() - 1);
	}
}

单链表归并排序

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <iostream>

using namespace std;

struct ListNode
{
    ListNode *next;
    int val;

    ListNode(int val) : val(val), next(nullptr)
    {}
};

ListNode *getMidNode(ListNode *head)
{
    ListNode *slow = head;
    ListNode *fast = head->next;
    while (fast)
    {
        fast = fast->next;
        if (fast)
        {
            fast = fast->next;
            slow = slow->next;
        }
    }
    return slow;
}
//归并方式合并两个单链表需要记住
ListNode *mergeList(ListNode *l1, ListNode *l2)
{
    if (!l1) return l2;
    if (!l2) return l1;
    if (l1->val <= l2->val)
    {
        l1->next = mergeList(l1->next, l2);
        return l1;
    }
    l2->next = mergeList(l1, l2->next);
    return l2;
}

ListNode *sortList(ListNode *head)
{
    if (head && head->next)
    {
        ListNode *mid = getMidNode(head);
        ListNode *left = head;
        ListNode *right = mid->next;
        mid->next = NULL;
        left = sortList(left);
        right = sortList(right);
        return mergeList(left, right);
    }
    return head;
}

int main()
{
    ListNode *head = new ListNode(3);
    ListNode *work = head;
    ListNode *p = new ListNode(1);
    work->next = p;
    work = work->next;
    p = new ListNode(3);
    work->next = p;
    work = work->next;
    p = new ListNode(5);
    work->next = p;
    work = work->next;
    p = new ListNode(4);
    work->next = p;
    work = work->next;
    head = sortList(head);
    while (head)
    {
        cout << head->val << " ";
        head = head->next;
    }
    return 0;
}

分析总结:

名称 时间 最好 最坏 空间 稳定 备注
归并排序 $O(nlogn)$ $O(nlogn)$ $O(nlogn)$ $O(n)$ 是

计数排序

其实就是计算待排序数组中每个数字的个数,用下标来代替原数，因此只适用于整型,计算max-min是为了减少countArray的size

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
#include <iostream>
#include <vector>

using namespace std;

void countingSort(vector<int> &array)
{
    int max = INT_MIN;
    int min = INT_MAX;
    for (auto num:array)
    {
        if (num > max)
        {
            max = num;
        }
        if (num < min)
        {
            min = max;
        }
    }
    vector<int> countArray(max - min + 1, 0);
    for (auto num:array)
    {
        countArray[num - min]++;
    }
    for (int i = 0; i < countArray.size(); ++i)
    {
        for (int j = 0; j < countArray[i]; ++j)
        {
            cout << min + i << " ";
        }
    }
}

int main()
{
    vector<int> array = {1, 5, 3, 7, 6, 2, 8, 9, 4, 3, 3};
    countingSort(array);
    return 0;
}

分析总结:

名称 时间 最好 最坏 空间 稳定 备注
计数排序 $O(n+d)$ $O(n+d)$ $O(n+d)$ $O(k)$ 是

桶排序

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
51
52
#include <iostream>
#include <vector>
#include <list>
using namespace std;
void insert(list<int>& bucket,int val)
{
    auto iter = bucket.begin();
    while(iter != bucket.end() && val >= *iter) ++iter;
    //insert会在iter之前插入数据，这样可以稳定排序
    bucket.insert(iter,val);
}

void bucketSort(vector<int>& arr)
{
    int len = arr.size();
    if(len <= 1)
        return;
    int min = arr[0],max = min;
    for(int i=1;i<len;++i)
    {
        if(min>arr[i]) min = arr[i];
        if(max<arr[i]) max = arr[i];
    }
    int k = 10;//k为数字之间的间隔
    //向上取整，例如[0,9]有10个数，(9 - 0)/k + 1 = 1;
    int bucketsNum = (max - min)/k + 1;
    vector<list<int>> buckets(bucketsNum);
    for(int i=0;i<len;++i)
    {
        int value = arr[i];
        //(value-min)/k就是在哪个桶里面
        insert(buckets[(value-min)/k],value);
    }
    int index = 0;
    for(int i=0;i<bucketsNum;++i)
    {
        if(buckets[i].size())
        {
            for(auto& value:buckets[i])
                arr[index++] = value;
        }
    }
}
int main()
{
    vector<int> A={-100,13,14,94,33,82,25,59,94,65,23,45,27,43,25,39,10,35,54,90,-200,58};
    for(auto value:A)
        cout<<value<<" ";
    cout<<endl;
    bucketSort(A);
    return 0;
}

分析总结:

名称 时间 最好 最坏 空间 稳定 备注
桶排序 $O(n+d)$ $O(n+d)$ $O(n*n)$ $O(n+k)$ 是

基数排序

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
51
#include<iostream>
#include<vector>

using namespace std;

void countSort(vector<int>& array, int exp)
{
    vector<int> range(10, 0);
    int length = array.size();
    vector<int> tmpVec(length, 0);
    for (int i = 0; i < length; ++i)
    {
        range[(array[i] / exp) % 10]++;
    }
    for (int i = 1; i < range.size(); ++i)
    {
        range[i] += range[i - 1];//统计本应该出现的位置
    }
    for (int i = length - 1; i >= 0; --i)
    {
        tmpVec[range[(array[i] / exp) % 10] - 1] = array[i];
        range[(array[i] / exp) % 10]--;
    }
    array = tmpVec;
}

void radixSort(vector<int> &array)
{
    int length = array.size();
    int max = -1;
    for (int i = 0; i < length; ++i)
    {
        if (array[i] > max)
            max = array[i];
    }
    //提取每一位并进行比较，位数不足的高位补0
    for (int exp = 1; max / exp > 0; exp *= 10)
        countSort(array, exp);
}

int main()
{
    vector<int> array{53, 3, 542, 748, 14, 214, 154, 63, 616, 589};
    radixSort(array);
    for (int i = 0; i < array.size(); ++i)
    {
        cout << array[i] << " ";
    }
    cout << endl;
    return 0;
}

分析总结:

名称 时间 最好 最坏 空间 稳定 备注
桶排序 $O(n+d)$ $O(n+d)$ $O(n*n)$ $O(n+k)$ 是