排序算法汇总_1.1 2排序

1.三大基本排序

1.1 冒泡排序

#include <iostream>
using namespace std;
int main()
{
	int arr[]={2,1,4,21,4,24,9,18};
	int len = sizeof(arr)/sizeof(arr[0]);
	for(int i = 0;i < len; ++i)
	{
		for(int j = i+1;j<len;++j)
		{
			if(arr[i]<arr[j])
			{
				arr[i]= arr[i]^arr[j];
				arr[j]= arr[i]^arr[j];
				arr[i]= arr[i]^arr[j];
			}
		}
	}
	for(int i =0;i<len;++i)
	cout<<arr[i]<<endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

1.2 选择排序

#include <iostream>
using namespace std;
int main(void)
{
 int arr[] = { 2, 1, 4, 21, 4, 24, 9, 18 };
 int len = sizeof(arr) / sizeof(arr[0]);
 int minindex;
 for (int i = len - 1; i > 0; --i)
 {
  minindex = 0;
  for (int j = i; j >0; --j)
  {
   if (arr[j] < arr[minindex])
   {
    minindex = j;
   }
  }
  if (minindex != i)
  {
   arr[minindex] = arr[i] ^ arr[minindex];
   arr[i] = arr[i] ^ arr[minindex];
   arr[minindex] = arr[i] ^ arr[minindex];
  }
 }
 for (int i = 0; i < len; ++i)
  cout << arr[i] << endl;
}
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

1.3 插入排序

int main(void)
{
 int arr[] = { 2, 1, 4, 21, 4, 24, 9, 18 };
 int len = sizeof(arr) / sizeof(arr[0]);
 for (int i = 1; i < len; ++i)
 {
  for (int j = i - 1; j >= 0; --j)
  {
   if (arr[j]<arr[j + 1])
   {
    arr[j + 1] = arr[j] ^ arr[j + 1];
    arr[j] = arr[j] ^ arr[j + 1];
    arr[j + 1] = arr[j] ^ arr[j + 1];
   }
   else break;
  }
 }
 for (int i = 0; i < len; ++i)
  cout << arr[i] << endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

2.希尔排序

希尔排序是在插入排序上做了优化，方式如下：即利用二分的方式，每分一次将后一部分的每个数据依次按照类似插入排序的方式插入到前一部分。直至不能再分就完成了排序,如下图：

<1> 将数组按一分为二，比较步长为数组长度的一半。如上图，将后一部分插入到前一部分，下图两个指针分别指向第一部分和第二部分

绿色指针下标为4时，与红色指针下标为0做比较，若满足条件则交换，并且将红指针向后移一位。否则直接将绿色指针后移一位，进入下次判断。显然11>3,则交换。然后将绿色和红色下标后移。如下图：

绿色指针下标为5时，与红色指针下标为1做比较，若满足条件则交换，并且将红指针向后移一位。否则直接将绿色指针后移一位，进入下次判断。显然4<16,直接进入下次判断。将绿色和红色下标后移。如下图：

绿色指针下标为6时，与红色指针下标为2做比较，若满足条件则交换，并且将红指针向后移一位。否则直接将绿色指针后移一位，进入下次判断。显然7>5,则交换，绿色不动，红色后移一位，如下图：

绿色指针下标为6时，与红色指针下标为3做比较，若满足条件则交换，并且将红指针向后移一位。否则直接将绿色指针后移一位，进入下次判断。显然2<7直接进入下次判断。如下图：

绿色指针下标为7时，与红色指针下标为3做比较，若满足条件则交换，并且将红指针向后移一位。否则直接将绿色指针后移一位，进入下次判断。显然2<7直接进入下次判断。如下图：

绿色指针下标为8时，与红色指针下标为4做比较，若满足条件则交换，并且将红指针向后移一位。否则直接将绿色指针后移一位，进入下次判断。显然11>2,则交换，绿色不动，红色后移一位，如下图：

绿色指针下标为8时，与红色指针下标为5做比较，若满足条件则交换，并且将红指针向后移一位。否则直接将绿色指针后移一位，进入下次判断。显然16>11,则交换，绿色不动，红色后移一位，如下图：

绿色指针下标为8时，与红色指针下标为6做比较，若满足条件则交换，并且将红指针向后移一位。否则直接将绿色指针后移一位，进入下次判断。显然2<7直接进入下次判断。此时绿色下标会越界，则进入下一次二分。
<2> 将将比较长度变为<1>的一般，类推1过程。得到：

<3> 将比较长度变为<2>的一半，类推1过程。得到：

此时交换步长二分后为0，排序完成。

实现算法如下：

#include<iostream>
using namespace std;
int main(void)
{
 int arr[] = { 11,4,7,2,3,16,5,9,2 };
 int len = sizeof(arr) / sizeof(arr[0]);
 int step= len >> 1;//step表示比较步长
 while (step)
 {
  for (int i = step; i<len; ++i)
  {
   for (int j = i - step; j >= 0; j -= step)
   {
    if (arr[j]>arr[j + step])
    {
     arr[j] = arr[j] ^ arr[j + step];
     arr[j + step] = arr[j] ^ arr[j + step];
     arr[j] = arr[j] ^ arr[j + step];
    }
    else break;
   }
  }
  step= step>> 1;
 }
 for (int i = 0; i < len; ++i)
  cout << arr[i] << endl;
}
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

3.归并排序

归并排序的思想：利用递归和二分的方法，首先将数组按下标分为左右两部分，然后对左右两部分进行递归排序，最后对分开后的两部分进行排序。当数组下标不可再分的时候，递归结束。
对数组分开后的两部分进行排序的合并算法为：
因为数组按照下标分为两部分，由mid=(L+R)/2将这两部分分开，而且这两部分是已经利用递归排好序的两部分，那么我们使用三个指针，L,R，分别指向左右部分的头。如图：

然后准备一个额外空间help来保存排好序的数据。对比两个指针所指向的数据，谁小将谁放到help中，同时将小的那个指针后移。若某一个指针移到了最后，但另外一个没移到最后，就将没移到最后的那个指针剩下的数据再依次放入help。最后将原数组用help数组跟新即可。
如下图：
第一步，2>1,绿色后移：

然后2<3,红色后移

依次类推，直至某个指针越界，然后将另外一个指针剩下的数据放入help中，最后将arr=help即可。
程序实现

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<vector>
using namespace std;
void mergeSort(vector<int>&arr);
void mergeSort(vector<int>&arr, int l, int r);
void merge(vector<int>&arr, int l, int mid, int r);
void mergeSort(vector<int>&arr)//主算法，使用vector来存储数据
{
 if (arr.size() < 2)
 {
  return;
 }
 mergeSort(arr, 0, arr.size()-1);//进入排序
}
void mergeSort(vector<int>&arr,int l,int r)
{
 if (l == r)return;//当左右下标重合时，说明不可再分了
 int mid = (l + r) / 2;//将当前数组一分为二
 mergeSort(arr, l, mid);//对左部分排序
 mergeSort(arr, mid + 1, r);//对右部分排序
 merge(arr, l, mid, r);//使用合并算法，完成合并
}
void merge(vector<int>&arr, int l, int mid, int r)
{
 int len = r - l + 1;
 int *help = new int[len];//开辟的额外空间
 int i = 0;
 int p1 = l;
 int p2 = mid + 1;
 while (p1<=mid&&p2<=r)
 {
  help[i++] = arr[p1] > arr[p2] ? arr[p1++] : arr[p2++];//哪个小将那个放入help中，然后将小指针+1
 }
 //接下来将剩下的数据放到help中
 while (p1<=mid)
 {
  help[i++] = arr[p1++];
 }
 while (p2 <= r)
 {
  help[i++] = arr[p2++];
 }
 //更新arr
 for (int i = 0; i < len; ++i)
 {
  arr[i + l] = help[i];
 }
 delete[]help;//释放help
}
int main03(void)
{
 vector<int>arr;
 arr.push_back(1);
 arr.push_back(3);
 arr.push_back(2);
 arr.push_back(45);
 arr.push_back(5);
 mergeSort(arr);
 for (int i = 0; i < arr.size(); ++i)
 {
  cout << arr[i] << endl;
 }
 system("pause");
 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
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

4.快速排序

在了解快速排序以前，我们先知道一个问题，就是“荷兰国旗问题”：

荷兰国旗问题

给定一个数组arr，和一个数num，将小于num的数放在数组左边，等于num的数放下数组中间，大于num的数放在数组右边。要求时间复杂度为O(N)，额外空间复杂度为O(1)
解决方法：给定一个数组，用less指针与more指针分别指向数组两端。(less more刚刚越界)如图：

接下来，再准备一个指针cur，从下标为0开始。

然后比较arr[0]与num的大小，若相等，直接将cur+1，若小于则将红指针+1，并将+1后的红指针对应的数与arr[cur[交换。然后cur+1.若大于num则将绿指针-1，将-1后的绿指针对应的数据与arr[cur]交换，然后再让arr[cur]重新um对比。当cur与绿指针重合，说明排列完毕。
程序算法

int main(void)
{
 int arr[] = { 11,3,7,2,3,16,5,9,2 };
 int len = sizeof(arr) / sizeof(arr[0]);
 int num = 3;
 int L = -1;//less
 int M = len;//more
 int cur = 0;//cur
 while (cur!=M)//cur==M时，说明排列完毕
 {
  if (arr[cur] < num)
  {
   //若小于
   L++;
   arr[L] = arr[L] ^ arr[cur];
   arr[cur] = arr[L] ^ arr[cur];
   arr[L] = arr[L] ^ arr[cur];
   cur++;
  }
  else if (arr[cur] > num)
  {
   //若大于
   M--;
   arr[M] = arr[M] ^ arr[cur];
   arr[cur] = arr[M] ^ arr[cur];
   arr[M] = arr[M] ^ arr[cur];
  }
  else
  {
   cur++;
  }
 }
 for (int i = 0; i < len; ++i)
  cout << arr[i] << endl;
}
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

快速排序，就是利用荷兰国旗问题的解决思想，使用递归的方式，每个子过程将子过程的数组的最后一个数，当做荷兰国旗问题的num。如图：假设主过程最后一个数为x

子过程对>x,与<x两部分进行递归，大于子过程最后一个数放左边，小于放右边。如图，假设，>x部分最后一个数为x1，<x部分最后一个为x2.

依次递归，直至不可再分。

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include <time.h>
using namespace std;
//分为改进后的快速排序、随机快速排序
void quick(int arr[],int l,int r)
{
 if (l < r)
 {
  //加上下面这几行代码编程随机快排：
  int t = arr[r];
  int rand_pos = rand() % (r-l+1) + l;
  arr[r] = arr[rand_pos];
  arr[rand_pos] = t;
  //就是在l-r中随机挑一个数与最尾部交换
  int c = l;
  int less = l - 1;
  int more = r;
  while (c < more)
  {
   if (arr[c] < arr[r])
   {
    less++;
    int temp = arr[less];
    arr[less] = arr[c];
    arr[c] = temp;
    c++;
   }
   else if (arr[c]>arr[r])
   {
    more--;
    int temp = arr[more];
    arr[more] = arr[c];
    arr[c] = temp;
   }
   else
   {
    c++;
   }
  }//以上是按照荷兰国旗问题将0到r-1的数排列
  int temp = arr[more];
  arr[more] = arr[r];
  arr[r] = temp;//将第r个元素与more处元素交换，使其完全变为符合要求的数组
  quick(arr, l, less);
  quick(arr, more+1, r);//采用递归对这两部分进行处理
 }
}
int main04(void)
{
 srand(time(NULL));
 int a[] = { 3, 4, 2, 5, 1, 7, 6, 88, 2 };
 int len = sizeof(a) / 4;
 quick(a, 0, len - 1);
 for (int i = 0; i < len; ++i)
 {
  cout << a[i] << endl;
 }
 system("pause");
 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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

5.堆排序

堆在结构上其实就是一个完全二叉树结构，满二叉树一定是一个完全二叉树，非满二叉树只要满足树的结构从左到右的结点是依次补齐的，这样的树结构也称为完全二叉树。
若使用数组来模拟完全二叉树，则可以使用下标，第i个结点的左孩子为：2xi+1,第i个结点的右孩子为2xi+2,第i个结点的父节点为(i-1)/2.
大根堆： 整个树的最大值为根节点，任何一颗子树的头部均为这棵树子树的最大值。(c++优先级队列的底层就是大根堆0
小根堆： 整个树的最小值为根节点，任何一颗子树的头部均为这棵树子树的最小值。

5.1 如何构建一个堆----以大根堆为例：

结点的插入
对于一组数据：int arr[] = {2,1,3,6,0,4};假设该数组内部数据已经按照完全二叉树排好。

然后我们依次访问数组元素，因为arr[0]=2时无父节点，故为根节点，因此从arr[1]=1处开始构建大根堆。流程如下：
首先访问arr[1]，通过下标找到其父节点arr[(1-1)/2]=2,因为2>1,故不做处理。然后访问下一个节点arr[2]=3,通过下标找到其父节点arr[(2-1)/2]=2，因为2<3,故交换这两个值。则树结构变为：

然后再访问arr[3]=6，通过下标找到其父节点arr[(3-1)/2]=1,因为1<6,故交换这两个值。交换后，通过下标找到其父节点arr[(1-1)/2]=3，因为3<6,故交换这两个值。则树结构变为：

然后再访问arr[4]=0，通过下标找到其父节点arr[(4-1)/2]=3,因为3>0,故不做处理。然后访问下一个节点arr[5]=4,通过下标找到其父节点arr[(5-1)/2]=2，因为2<4,故交换这两个值。交换后，通过下标找到其父节点arr[(2-1)/2]=6，因为6>4,故不做处理。则树结构变为：

代码实现：

void heapInsert(int *arr,int len)
{
	for(int i =1;i<len;++i)
	{
		int index = i;//先将待插入的数据的下标标记为index
		while(index >= 0 && arr[index]>arr[(index-1)/2])//若子大于父且下标不越界
		{
			arr[index]=arr[index]^arr[(index-1)/2];
			arr[(index-1)/2]=arr[index]^arr[(index-1)/2];
			arr[index]=arr[index]^arr[(index-1)/2];//交换
			index=(index-1)/2;//跟新index保证能访问到父节点
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13

结点的删除
首先先考虑当根节点发生变化时，应该如何操作。如下图：

6变为了1，此时采用向下调整的方式，具体过程为，首先通过arr[0]的下标0，找到左arr[(2x0+1)]右(arr[2x0+2])两个孩子中最大的那个,即arr[1]=5，显然5>1,则交换这两个值，树变为

然后通过arr[1]的下标1，找到左arr[(2x1+1)]右(arr[2x1+2])两个孩子中最大的那个,即arr[5]=5，显然5>1,则交换这两个值，树变为：

完成调整。
根据以上过程，我们要删除根节点时，只需删除根节点后，再将最后一个节点放到根节点位置，然后使用上面的额方法进行调整即可。
代码实现：

void heapify(int arr[], int len)//将大根堆堆顶元素进行修改后，重新构建大根堆
{
 	int index = 0;//堆顶元素即为数组下标为0的元素，即首元素
 	int left = index * 2 + 1;//左孩子
 	int right = index * 2 + 2;//右孩子
 	while (left<len)//当左孩子大于等于整个数组长度时，说明数组(堆)访问完了
 	{
  		int large = right<len&&arr[right]>arr[left] ? right : left;//判断当右子树下标不越界的情况下，左子树与右子树哪个元素大， 
  		large = arr[large] > arr[index] ? large : index;//看arr[larg]e与arr[index]哪个大
  		if (large == index)break;//若下标一样，则说明这两个数是一样大的，即最大的数就位于左右孩子结点的父节点上，此时直接跳出循环，不用往下比较了
  		int temp = arr[large];
  		arr[large]=arr[index];
  		arr[index]=temp;//交换数据
  		index = large;//将index更新为最大的那个结点下标，下面在对这个结点的左右孩子进行跟新
  		left = index * 2 + 1;
  		right = index * 2 + 2;
	}
}
void deleteNode(int *arr,int len)
{
	int temp = arr[0];
	arr[0] = arr[len];
	arr[len]=temp;//交换堆头，堆尾
	len--;//数据长度-1
	heapify(arr,len);//调整
}
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

5.2 堆排序算法

如何实现堆排序呢？由大根堆，小根堆我们只要大根堆的堆顶永远是最大的，小根堆的堆顶永远是最小的。因此，实现堆排序只需将数据入堆，然后类似于删除过程，每次将数组尾部数据放在头部，进行调整就行了。
示例程序：

void heapInsert(int arr[], int index)//将数组的第index个元素入大根堆
{
 	while (arr[index] > arr[(index - 1) / 2])//若子大于父数据
 	{
  		//交换父子数据
  		int temp = arr[index];
  		arr[index] = arr[(index - 1) / 2];
  		arr[(index - 1) / 2] = temp;
  		//并将该元素下标变为其父节点的下标，这样能够一直向上访问父节点
  		index = (index - 1) / 2;
 	}
}
void heapify(int arr[], int len)//将大根堆堆顶元素进行修改后，重新构建大根堆
{
 	int index = 0;//堆顶元素即为数组下标为0的元素，即首元素
 	int left = index * 2 + 1;//左孩子
 	int right = index * 2 + 2;//右孩子
 	while (left<len)//当左孩子大于等于整个数组长度时，说明数组(堆)访问完了
 	{
  		int large = right<len&&arr[right]>arr[left] ? right : left;//判断当右子树下标不越界的情况下，左子树与右子树哪个元素大， 
  		large = arr[large] > arr[index] ? large : index;//看arr[larg]e与arr[index]哪个大
  		if (large == index)break;//若下标一样，则说明这两个数是一样大的，即最大的数就位于左右孩子结点的父节点上，此时直接跳出循环，不用往下比较了
  		int temp = arr[large];
  		arr[large]=arr[index];
  		arr[index]=temp;//交换数据
  		index = large;//将index更新为最大的那个结点下标，下面在对这个结点的左右孩子进行跟新
  		left = index * 2 + 1;
  		right = index * 2 + 2;
 	}
}
void heapsort(int arr[], int len)
{
 	for (int i = 1; i < len; ++i)//arr[0]为根节点
 	{
  		heapInsert(arr, i);
 	}//构建一个大根堆
 	len--;
 	int temp = arr[len];
 	arr[len] = arr[0];
 	arr[0] = temp;//先将堆顶元素与最后一个元素交换
 	while (len)
 	{
  		heapify(arr, len);//重构大根堆
  		len--;
  		int temp = arr[len];
  		arr[len] = arr[0];
  		arr[0] = 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

6.计数排序

对于一组数据，他们的最大值为N，那么我们将准备N+1个桶(编号为0~N)，桶内初始数据均为0。然后我们遍历数组，当数组元素等于桶对应编号时，将对应编号的数据+1。遍历完数组后，将桶内数据依次写到源数据即可。
如图：

程序实例：

void countSort(int *arr,int len)
{	
	//寻找数组中的最大值
	int max=arr[0];
	for(int i =1;i<len;++i)
	{
		max=max>arr[i]?max:arr[i];
	}
	//安排max+1个桶
	int *bucket = new int[max+1];
	memset(bucket,0,4*(max+1));
	//桶计数，桶的标号为arr中的数据，桶的内容为某个数据的个数，某个标号的桶内内筒为0时，说明arr中没有该标号对应的数据。
	for(int i=0;i<len;++i)
	{
		bucket[arr[i]]++;
	}
	//桶数据倒出到源数组
	int j=0;
	for(int i =0;i<=max;++i)
	{
		while(bucket[i]--)//当桶内数据为0时，说明该桶内没有arr中对应的数据
		arr[j++]=i;//当桶内有数据时，循环将bucket的标号赋给arr，因为痛的标号就是arr中的数据
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

7.基数排序

基数排序实际上是对计数排序的优化，显然，当一组数中的最大值非常大时，我们使用计数排序的开销是非常大的。而且空间浪费严重。如何避免这种问题，就采用了基数排序的思想：基数排序可以分为LSD(从低位向高位排序),MSD(从高位向低位排序)。接下来我将用LSD来解释基数排序的过程。

基数排序，就是分别根据这组数据的最高"位数"，依次给出用于表示"个位桶"，“十位桶”，“百位桶”,…“最高位桶”。而桶的标号仅仅为0~9.
以下面一组数为例：
123 ， 234，564 ， 765， 876，324，651，874，432
从低位向高位排序：
首先，准备低位桶，编号为0~9，将数组中每个数按照个位数依次放桶中，如下图：

然后将个位桶内数据依次倒入数组中：
651 432 123 234 564 324 874 765 876。
接着，准备十位桶，编号为0~9，将数组中每个数按照十位数依次放桶中，如下图：

然后将十位桶内数据依次倒入数组中：
123 324 432 234 654 564 765 874 876.
接着，准备百位桶，编号为0~9，将数组中每个数按照百位数依次放桶中，如下图：

然后将百位桶内数据依次倒入数组中：
123 234 324 432 564 654 765 874 876.
完成排序。
算法步骤：
<1> 使用一个动态二维数组，lenx10维，len表示数组长度，10表示有10个桶，那么lenx10就表示有十个桶，每个桶中最多存len个数。用该二维数组表示一个二维桶，初始值为0。以一个简单的数组举例：
如图：

<2> 获得该数组的最大值所对应的位数，如423对应的位数为3。54对应的位数为2。上图中最大值位数为2.

<3> 将数组内的数据根据位数，放在桶中。放的规则为：

• 遍历数组，在遍历的时候，获取每个数的“位数值”，如arr[0]=87时，”个位数值"为7。然后将87放在7号桶的0号位置。即二维数组的(0,7)位置。依次的arr[1]=15放在二维数组的(1,5)位置。arr[2]=21—>(2,1);arr[3]=33—>(3,3);arr[4]=53—>(4,3);arr[5]=68—>(5,8);然后再将桶中元素重新放入源数组中。如图：
  -
  将数据从桶中取出，放入arr中，则arr={21,33,53,15,87,68};
  <4> 进入十位进行桶排序，方法与<3>相同。在放数据前要将桶清空。
  注意：我们要使用一个变量来保证循环次数

示例程序

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include <math.h>
using namespace std;
//采用从低位往高位排序，即LSD
int getMaxWei(int arr[],int len)//得到arr中最大的数所对应的位数
{
 int max = arr[0];
 for (int i = 1; i < len; ++i)
  max = max>arr[i] ? max : arr[i];
 int re = 1;//至少有一位
 while (max/=10)
  re++;
 return re;
}
void radixSort(int arr[], int len)
{
 //在堆上创建二维数组len*10，表示有10个桶，每个桶最多元素有len个
 int** bucket = new int*[len];
 for (int i = 0; i < len; ++i)
  bucket[i] = new int[10];
 //得到arr中最大值所对应的最高位数
 int maxHigh = getMaxWei(arr, len);
 maxHigh = pow(10, (maxHigh-1));//让最高位变为10^（maxHigh-1），也就是当最高位为3时，maxHige=100
 int n = 1;//表示循环次数，这个循环次数根据最高位数决定
 while (n<=maxHigh)
 {
  for (int i = 0; i < len; ++i)
  {
   for (int j = 0; j < 10; ++j)
   {
    bucket[i][j] = 0;//初始化桶内数据为0,该值应该为非arr中数据就行
   }
  }
  //给桶内对应的位置填入arr中数据
  for (int i = 0; i < len; ++i)
  {
   int bucket_lieIndex = (arr[i] / n) % 10;
   bucket[i][bucket_lieIndex] = arr[i];
  }
  //将桶内数据依次恢复至arr中
  int k = 0;//每次恢复数组时，数组的下标
  for (int i = 0; i < 10; ++i)
  {
   for (int j = 0; j < len; ++j)
   {
    if (bucket[j][i]!=0)//bucket[j][i]不等于桶内的初始化数据就行了
    {
     arr[k++] = bucket[j][i];
    }
   }
  }
  n *= 10;//升高一位
 }
 //释放开辟的空间
 for (int i = 0; i < len; ++i)
  delete[] bucket[i];
 delete[] bucket;
}
int main(void)
{
 int arr[] = {2,32,54,321,54,76,990,53,43 };
 radixSort(arr, sizeof(arr) / 4);
 for (int i = 0; i < sizeof(arr) / 4; ++i)
 {
  cout << arr[i] << endl;
 }
 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
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