C++数据结构与算法（十大排序）

超、凢脫俗 2021-12-04 07:37 332阅读 0赞

**目录**

1 冒泡排序（Bubble Sort）

2 快速排序（Quick Sort）

3 插入排序（Insertion Sort）

4 希尔排序（Shell Sort）

5 简单选择排序（Selection Sort）

6 堆排序（Heap Sort）

7 二路归并排序（Merge Sort）

8 基数排序（Radix Sort）

9 桶排序（Bucket Sort）

10 计数排序（Counting Sort）

10种排序算法对比

--------------------

### **1 冒泡排序（Bubble Sort）** ###

**算法思想：**在扫描过程中，比较两两相邻记录，如果反序则交换，最终，最大记录就被“沉到”序列的最后一项，第二遍扫描将第二大“沉到”了倒数第二的位置，重复上述操作，直到n-1遍扫描后，整个序列是有序的。

**算法实现：**

程序说明：两个子函数都可以实现冒泡排序，但是void BubbleSort1(int a\[\], int n)把大的往后放是从后面进行交换的，void BubbleSort2(int a\[\], int n)也是把大的往后放，但是从前面交换的，原理一致。

#include<iostream>
    using namespace std;
    
    void BubbleSort1(int *a, int n);
    void BubbleSort2(int *a, int n);
    
    int main()
    {
    	int i;
    	int a[7] = { 3, 2, 5, 8, 4, 7, 6 };
    	BubbleSort2(a, 7);           //BubbleSort2(a, 7);
    	for (i = 0; i < 7; i++)
    		cout << a[i] << " ";
    	cout << endl;
    	system("pause");
    	return 0;
    }
    
    void BubbleSort1(int a[], int n)
    {
    	int i, j, t;
    	for (i = 1; i<n; i++)
    	{
    		for (j = n - 1; j >= 0; j--)
    		{
    			if (a[j] < a[j - 1])  //交换
    			{
    				t = a[j];
    				a[j] = a[j - 1];
    				a[j - 1] = t;
    			}
    		}
    	}
    }
    
    void BubbleSort2(int a[], int n)
    {
    	int i, j, t;
    	for (i = 1; i<n; i++)                 //可以写为：for(int i=0;i<n;++i)
    	{
    		for (j = 0; j <= n - i - 1; j++)  //可以写为：for(int j=0;j<n-i-1;++j)
    		{
    			if (a[j] > a[j + 1])  //交换
    			{
    				t = a[j];
    				a[j] = a[j + 1];
    				a[j + 1] = t;
    			}
    			
    		}
    
    		for (int k = 0; k < n; k++)
    		{
    			cout << a[k] << " ";
    		}
    		cout << endl;
    	}
    }

### **2 快速排序（Quick Sort）** ###

**算法思想：**通过一趟排序将待排记录隔成独立的两部分，其中一部分记录的关键字比另一部分的关键字小，则可以分别对这两部分记录继续进行排序，以达到整个序列有序。

1）先从数列中取出一个数作为基准数；

2）分区：将基准数大的数全部放到它的右边，小于或者等于它的数全部放在它的左边；

3）再对左右区间重复第二步，直到各分区只剩一个数。

**算法实现：**

程序说明：（从小到大排序中）先从右到左扫描后从左到右扫描，次序不能变化。以下有两种不同的写法：

#include<iostream>
    using namespace std;
    
    void quickSort(int a[],int,int);
    
    int main()
    {
    	int array[]={34,65,12,43,67,5,78,10,3,70},k;
    	int len=sizeof(array)/sizeof(int);
    	cout<<"The orginal arrayare:"<<endl;
    	for(k=0;k<len;k++)
    		cout<<array[k]<<",";
    	cout<<endl;
    	quickSort(array,0,len-1);
    	cout<<"The sorted arrayare:"<<endl;
    	for(k=0;k<len;k++)
    		cout<<array[k]<<",";
    	cout<<endl;
    	system("pause");
    	return 0;
    }
     
    void quickSort(int s[], int l, int r)
    {
    	if (l< r)
    	{      
    		int i = l, j = r, x = s[l];  //选取最左边的数作为基准 
    		while (i < j)
    		{
    			while(i < j && s[j]>= x) // 从右向左找第一个小于x的数
    				j--; 
    			if(i < j)             //跳出循环，说明找到小于x的数 
    				s[i++] = s[j];          //相当于将j处元素拷贝到i，并且i后移 
    			while(i < j && s[i]< x) // 从左向右找第一个大于等于x的数
    				i++; 
    			if(i < j)             //跳出循环，说明找到大于等于x的数 
    				s[j--] = s[i];          //相当于将i处元素拷贝到j，并且j左移 
    		}
    		s[i] = x;        //将基准拷贝到i处 
    		quickSort(s, l, i - 1); // 递归调用  左    因为i是基准，此时i已经确定好在整个序列中的位置 
    		quickSort(s, i + 1, r); // 递归调用  右 
    	}
    }

#define _CRT_SECURE_NO_WARNINGS
    #include <iostream>
    #include <string>
    #include <vector>
    #include <algorithm>
    #include <time.h>
    using namespace std;
    
    
    int partition(int arr[], int left, int right)  //找基准数 划分
    {
    	int i = left + 1;
    	int j = right;
    	int temp = arr[left];
    
    	while (i <= j)
    	{
    		while (arr[i] < temp)
    		{
    			i++;
    		}
    		while (arr[j] > temp)
    		{
    			j--;
    		}
    		if (i < j)
    			swap(arr[i++], arr[j--]);
    		else i++;
    	}
    	swap(arr[j], arr[left]);
    	return j;
    
    }
    
    void quick_sort(int arr[], int left, int right)
    {
    	if (left > right)
    		return;
    	int j = partition(arr, left, right);
    	quick_sort(arr, left, j - 1);
    	quick_sort(arr, j + 1, right);
    }
    
    //打印数组
    void PrintArray(int array[], int len)
    {
    	for (int i = 0; i < len; i++)
    	{
    		cout << array[i] << " ";
    	}
    	cout << endl;
    }
    
    int main(void)
    {
    	const int NUM = 7;
    	int array[NUM] = { 0 };
    	srand((unsigned int)time(nullptr));
    	for (int i = 0; i < NUM; i++)
    	{
    		array[i] = rand() % 100 + 1;
    	}
    	cout << "排序前：" << endl;
    	PrintArray(array, NUM);
    	cout << "排序后：" << endl;
    	quick_sort(array, 0, NUM - 1);
    	PrintArray(array, NUM);
    
    	system("pause");
    	return 0;
    }

//快排   手动设置标志位 
    #include<iostream>
    #include<algorithm>
    using namespace std;
    int a[100],n;
    void quickSort(int l,int r)
    {
    	int m=a[l]; //以中间元素作为关键数据时     int m=(l+r)/2; 
    	int i=l,j=r;
    	while(i<j)
    	{ //直到i>j
    		while(a[i]<m) i++; //从i开始向前搜索(i++)，找到第一个大于m的值
    		while(a[j]>m) j--; //从j开始向前搜索(j--)，找到第一个小于m的值
    		if(i<=j)
    		{
    			swap(a[i],a[j]);//交换a[i]和a[j]的值
    			i++,j--; //同时i++,j--
    		}
    	}
    	if(l<j) quickSort(l,j); //接下来分别对左边段[l,j]和右边段[i,r]利用同样的方法排序
    	if(i<r) quickSort(i,r);
    }
    
    int main()
    {
    	cin>>n;
    	for(int i=1;i<=n;i++) cin>>a[i];
    	quickSort(1,n);
    	for(int i=1;i<=n;i++) cout<<a[i]<<" ";
    	return 0;
    }

### **3 插入排序（Insertion Sort）** ###

**算法思想：**在一个已排好序的记录子集的基础上，每一步将下一个待排序的记录有序插入到已排好序的记录子集中，直到将所有待排记录全部插入为止。

**算法实现：**

程序说明：第一个程序是简单插入排序，第二个程序包含简单插入排序和折半插入排序。

#include <iostream>
    using namespace std;
    
    void insertSort(int* a, int n)
    {
    	int i, j, k;
    
    	for (i = 1; i < n; i++)
    	{
    		//为a[i]在前面的a[0...i-1]有序区间中找一个合适的位置
    		for (j = i - 1; j >= 0; j--)
    		if (a[j] < a[i])
    			break;
    
    		//如找到了一个合适的位置
    		if (j != i - 1)
    		{
    			//将比a[i]大的数据向后移
    			int temp = a[i];
    			for (k = i - 1; k > j; k--)
    				a[k + 1] = a[k];
    			//将a[i]放到正确位置上
    			a[k + 1] = temp;
    		}
    	}
    }
    
    int main()
    {
    	int i;
    	int a[] = { 20, 40, 30, 10, 60, 50 };
    	int ilen = (sizeof(a)) / (sizeof(a[0]));
    
    	cout << "before sort:";
    	for (i = 0; i<ilen; i++)
    		cout << a[i] << " ";
    	cout << endl;
    
    	insertSort(a, ilen);
    
    	cout << "after  sort:";
    	for (i = 0; i<ilen; i++)
    		cout << a[i] << " ";
    	cout << endl;
    
    	system("pause");
    	return 0;
    }

/*
    直接插入排序
    */
    #include<iostream>
    using namespace std;
    
    void InsertCode(int a[], int n);
    void BinaryInsertSort(int * array, int n);
    
    int main()
    {
    	int i;
    	int a[7] = { 3, 2, 5, 8, 4, 7, 6 };
    	cout << "排序前：" << endl;
    	for (i = 0; i<7; i++)
    		cout << a[i] << " ";
    	cout << endl;
    	BinaryInsertSort(a, 7);    //InsertCode(a, 7);
    	cout << "排序后：" << endl;
    	for (i = 0; i<7; i++)
    		cout<< a[i] <<" ";
    	cout << endl;
    
    	system("pause");
    	return 0;
    }
    
    void InsertCode(int a[], int n)
    {
    	int i, j, x;
    	for (i = 1; i<n; i++)
    	{
    		//每次取无序空间的第一个元素
    		x = a[i];
    		//与有序空间的元素从后进行比较，选择合适的位置插入即可
    		for (j = i - 1; j >= 0; j--)
    		{
    			if (a[j]>x)
    				a[j + 1] = a[j];
    			else break;
    		}
    		a[j + 1] = x;
    	}
    }
    
    void BinaryInsertSort(int * array, int n) //array为待排序数组,n为数组大小
    {              
    	int i, j, mid, low, high, temp;
    	for (i = 1; i < n; i++)
    	{
    		temp = array[i];                               //把第i+1个元素赋值给temp(数组从下标0开始)
    		low = 0;                                       //初始化low，array[low]代表数组中第1个元素
    		high = i;                                      //初始化high，array[high]代表已插入的最后一个元素
    		while (low <= high){                           //不断的折半1/2 1/4 ....
    			mid = (low + high) / 2;                    //计算中间位置										 
    			if (temp > array[mid]){                    //插入值大于中间值
    				low = mid + 1;
    			}
    			else {                                     //插入值小于中间值
    				high = mid - 1;
    			}
    		}
    
    		for (j = i - 1; j >= low; j--){               //将需要移动的数组向后移
    			array[j + 1] = array[j];
    		}
    
    		//将值插入到指定位置
    		array[low] = temp;
    
    		for (int k = 0; k < n; k++)
    			cout << array[k] << " ";
    		cout << endl;
    	}
    }

### **4 希尔排序（Shell Sort）** ###

**算法思想：**先将待排序记录序列分割成若干个“较稀疏”的子序列，分别进行直接插入排序，经过上述粗略调整，整个序列中的记录已经基本有序，最后再对全部记录进行一次直接插入排序。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzc1MzIxNQ_size_16_color_FFFFFF_t_70][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzc1MzIxNQ_size_16_color_FFFFFF_t_70 1][]

**算法实现：**

/*
    希尔排序
    */
    #include<iostream>
    using namespace std;
    
    void insert_sort(int a[], int n, int start, int step)
    {
    	int i = 0;
    	for (i = start + step; i < n; i += step)
    	{
    		int temp = a[i];
    		int j = 0;
    		for (j = i - step; j >= start && a[j] > temp; j -= step)
    		{
    			a[j + step] = a[j];//移动
    		}
    		a[j + step] = temp;//插入
    
    	}
    }
    
    void shell(int a[], int n)
    {
    	int step = n / 2;
    	while (step > 0)
    	{
    		int i = 0;
    		for (i = 0; i < step; i++)
    		{
    			insert_sort(a, n, i, step);
    		}
    		step /= 2;
    	}
    }
    int main()
    {
    	int a[] = { 8, 3, 6, 2, 4, 5, 7, 1, 9, 0 };
    	shell(a, 10);
    	cout << "排序后的结果为: " << endl;
    	for (int i = 0; i < 10; i++)
    		cout << a[i] << " ";
    	cout << endl;
    	system("pause");
    	return 0;
    }

### **5 简单选择排序（Selection Sort）** ###

**算法思想：**第一趟简单选择排序时，从第一个记录开始，通过n-1次关键字的比较，从第n个记录中选出关键字最小的记录，并和第1个记录进行交换；第二趟简单选择排序时，从第一个记录开始，通过n-2次关键字的比较，从第n-1个记录中选出关键字最小的记录，并和第2个记录进行交换......第i趟简单选择排序时，从第i个记录开始，通过n-i次关键字的比较，从第n-i+1个记录中选出关键字最小的记录，并和第i个记录进行交换......

**算法实现：**

/*简单选择排序*/
    #include<iostream>
    using namespace std;
    
    void SelectSort(int a[], int n)
    {
    	int i, j, iMin, t;
    	for (i = 0; i<n - 1; i++)
    	{
    		iMin = i;
    		for (j = i + 1; j<n; j++)
    		{
    			if (a[j]<a[iMin])
    				iMin = j;
    		}
    		if (i - iMin)
    		{
    			t = a[i];
    			a[i] = a[iMin];
    			a[iMin] = t;
    		}
    	}
    }
    
    int main()
    {
    	int a[7] = { 3, 2, 5, 8, 4, 7, 6 };
    	SelectSort(a, 7);
    	for (int i = 0; i < 7; i++)
    		cout << a[i] << " ";
    	cout << endl;
    	system("pause");
    	return 0;
    }

### **6 堆排序（Heap Sort）** ###

堆排序的过程主要需要解决两个问题：1）按堆定义建初堆；2）去掉最大元之后重建堆，得到次大元。以此类推......

**算法思想：**

a）将无序序列构成一个堆，根据升序降序需求选择大顶堆和小顶堆；

b）将堆顶元素与末尾元素交换，将最大元素沉到数组末端；

c）重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末端元素，反复执行调整和交换步骤，直到整个序列有序。

**算法实现：**

#include<iostream>
    using namespace std;
    
    /**
    * 堆排序demo
    */
    /**
    * 调整大顶堆（仅是调整过程，建立在大顶堆已构建的基础上）
    * @param arr
    * @param i
    * @param length
    */
    void adjustHeap(int arr[], int i, int length)
    {
    	int temp = arr[i];//先取出当前元素i
    	for (int k = i * 2 + 1; k<length; k = k * 2 + 1){//从i结点的左子结点开始，也就是2i+1处开始
    		if (k + 1<length && arr[k]<arr[k + 1]){//如果左子结点小于右子结点，k指向右子结点
    			k++;
    		}
    		if (arr[k] >temp){//如果子节点大于父节点，将子节点值赋给父节点（不用进行交换）
    			arr[i] = arr[k];
    			i = k;
    		}
    		else{
    			break;
    		}
    	}
    	arr[i] = temp;//将temp值放到最终的位置
    }
    
    /**
    * 交换元素
    * @param arr
    * @param a
    * @param b
    */
    void swap(int arr[] , int a, int b){
    	int temp = arr[a];
    	arr[a] = arr[b];
    	arr[b] = temp;
    }
    
    void sort(int arr[], int n)
    {
    	//1.构建大顶堆
    	for (int i = n / 2 - 1; i >= 0; i--){
    		//从第一个非叶子结点从下至上，从右至左调整结构
    		adjustHeap(arr, i, n);
    	}
    	//2.调整堆结构+交换堆顶元素与末尾元素
    	for (int j = n - 1; j > 0; j--){
    		swap(arr, 0, j);//将堆顶元素与末尾元素进行交换
    		adjustHeap(arr, 0, j);//重新对堆进行调整
    	}
    }
    
    int main()
    {
    	int arr[] = {10, 4, 3, 5, 1}; //9, 8, 7, 6, 5, 4, 3, 2, 1
    	int n = sizeof(arr) / sizeof(arr[0]);
    	sort(arr, n);
    	cout << "排序后:" << endl;
    	for (int i = 0; i < n; i++)
    	{
    		cout << arr[i] << " ";
    	}
    	cout << endl;
    	system("pause");
    }

### **7 二路归并排序（Merge Sort）** ###

**算法思想：**假设初始序列含有n个记录，首先将这n个记录看成n个有序的子序列，每个子序列的程度为1，然后两两合并，得到\[n/2\]个长度为2（n为奇数时，最后一个序列长度为1）的有序子序列。在此基础上，再对长度为2的有序子序列信息两两归并，得到若干个长度为4的有序子序列......如此反复，直至得到一个长度为n的有序序列为止。

**算法实现：**

程序说明：第一个是递归实现，第二个是非递归实现。

/*递归实现归并排序*/
    #include<iostream>
    using namespace std;
    
    void Merge(int a[], int low, int mid, int high);
    void MergeSort(int a[], int low, int high);
    
    //将两个非降序序列low--mid,mid+1--high合并为一个新的非降序序列
    void Merge(int a[], int low, int mid, int high)
    {  //low为第1有序区的第1个元素，i指向第1个元素, mid为第1有序区的最后1个元素
    	int len = high - low + 1;
    	int *temp = new int[len];
    	int i = low, j = mid + 1;    //i，j分别为两个子序列的游标
    	int k = 0;     //为新合并序列的游标
    	while (i <= mid && j <= high){
    		if (a[i] <= a[j]){
    			temp[k++] = a[i++];
    		}
    		else{
    			temp[k++] = a[j++];
    		}
    	}
    	while (i <= mid){    //若第一个子序列有剩余，则直接接到尾部
    		temp[k++] = a[i++];
    	}
    	while (j <= high){    //若第二个子序列有剩余，则直接接到尾部
    		temp[k++] = a[j++];
    	}
    	//copy到a[]
    	for (k = 0; k<len; k++)
    		a[low + k] = temp[k];
    	delete []temp;
    }
    
    //low high为待排序列左右边界
    void MergeSort(int a[], int low, int high)
    {
    	if (low<high){
    		int mid = (low + high) / 2;
    		//递归的划分左右两个子序列
    		MergeSort(a, low, mid);
    		MergeSort(a, mid + 1, high);
    		//合并
    		Merge(a, low, mid, high);
    	}
    }
    
    int main()
    {
    	int data[] = { 9, 6, 7, 22, 20, 33, 16, 23 };
    	const int length = 8;
    	cout << "Before sorted:" << endl;
    	for (int i = 0; i < length; ++i)
    		cout << data[i] << "  ";
    	cout << endl;
    	cout << "After sorted:" << endl;
    	MergeSort(data, 0, length - 1);
    	for (int i = 0; i < length; ++i)
    		cout << data[i] << "  ";
    	cout << endl;
    	system("pause");
    	return 0;
    }

/*非递归实现*/
    #include<iostream>
    using namespace std;
    void Merge(int arr[], int low, int mid, int high)//递归和非递归均一样 
    {//将两个有序区归并为一个有序区
    	int i = low, j = mid + 1, k = 0;
    	int *temp = new(nothrow) int[high - low + 1];
    	while (i <= mid&&j <= high)
    	{
    		if (arr[i] <= arr[j])
    			temp[k++] = arr[i++];
    		else
    			temp[k++] = arr[j++];
    	}
    	while (i <= mid) temp[k++] = arr[i++];
    	while (j <= high) temp[k++] = arr[j++];
    	for (i = low, k = 0; i <= high; i++, k++)
    		arr[i] = temp[k];
    	delete[]temp;
    }
    //void MergeSort(int arr[],int low,int high)//递归版本的形参表 
    void MergeSort(int arr[], int n)//参数和递归略不同，n代表数组中元素个数，即数组最大下标是n-1 
    {//非递归实现 
    	int size = 1, low, mid, high;
    	while (size <= n - 1)
    	{
    		low = 0;
    		while (low + size <= n - 1)
    		{
    			mid = low + size - 1;
    			high = mid + size;
    			if (high>n - 1)//第二个序列个数不足size 
    				high = n - 1;
    			Merge(arr, low, mid, high);//调用归并子函数 
    			cout << "low:" << low << " mid:" << mid << " high:" << high << endl;//打印出每次归并的区间 
    			low = high + 1;//下一次归并时第一关序列的下界 
    		}
    		size *= 2;//范围扩大一倍 
    	}
    }
    int main()
    {
    	int x[] = { 4, -5, 0, 3, -1, 12, 9, -7, 8, -4, 11 };
    	MergeSort(x, 11);
    	for (int i = 0; i<11; i++)
    		cout << x[i] << " ";
    	cout << endl;
    	system("pause");
    	return 0;
    }

### **8 基数排序（Radix Sort）** ###

**算法思想：**基数排序是按照低位先排序，然后收集，再照高位排序，然后再收集；依次类推，直到最高位。先取得数组中的最大数和位数，然后从低位开始取每个位组成radix数组，最后对radix进行计数排序（利用计数排序适用于小范围数的特点）。

**算法实现：**

程序说明：第一个是基于数组的基数排序算法实现，第二个是基于链表的基数排序算法实现。

/*实现一：基于数组的基数排序算法*/
    #include <iostream>  
    #include <cstdlib>  
    #include <ctime>  
    
    using namespace std;
    
    //得到某个整数第i位的数值  
    int getDigitNun(int a, int digit);
    //按位排序  
    void DigitSort(int *a, int n, int digit, int *result);
    //基数排序算法  
    void RadixSort(int *a, int n, int d);
    
    int main()
    {
    	int n = 7, i;
    	int *a = new int[n];
    	srand(time(NULL));
    	for (i = 0; i < n; ++i)
    		*(a + i) = rand();
    	//int a[7] = { 3, 2, 5, 8, 4, 7, 6 };
    	//判断最大的数的位数  
    	int MaxVal = -1, d = 0;
    	cout << "Before sort : " << endl;
    	for (i = 0; i < n; ++i)
    	{
    		cout << *(a + i) << " ";
    		MaxVal = MaxVal < *(a + i) ? *(a + i) : MaxVal;
    	}
    	cout << endl;
    	while (MaxVal > 0)
    	{
    		++d;
    		MaxVal /= 10;
    	}
    
    	RadixSort(a, n, d);
    
    	cout << "After sort : " << endl;
    	for (i = 0; i < n; ++i)
    		cout << *(a + i) << " ";
    	cout << endl;
    	system("pause");
    	return 0;
    }
    
    //基数排序算法  
    void RadixSort(int *a, int n, int d)
    {
    	int *result = new int[n + 5];
    	//循环执行按位排序操作  
    	for (int i = 1; i <= d; ++i)
    	{
    		DigitSort(a, n, i, result);
    		for (int j = 0; j < n; ++j)
    		{
    			*(a + j) = *(result + j + 1);
    		}
    	}
    
    	delete[] result;
    }
    
    //得到某个整数第i位的数值  
    int getDigitNun(int a, int digit)
    {
    	while (--digit)
    	{
    		a /= 10;
    	}
    
    	return a % 10;
    }
    
    //按位排序  
    //这里采用选择排序  
    void DigitSort(int *a, int n, int digit, int *result)
    {
    	//记录中间结果  
    	const int num = 15;
    	int *tempResult = new int[num];
    	for (int i = 0; i < num; ++i)
    		*(tempResult + i) = 0;//初始化  
    
    	//tempResult[i]记录数组中等于i的数的个数  
    	for (int i = 0; i < n; ++i)
    		*(tempResult + getDigitNun(*(a + i), digit)) = *(tempResult + getDigitNun(*(a + i), digit)) + 1;
    
    	//tempResult[i]记录数组中小于等于i的数的个数  
    	for (int i = 1; i < num; ++i)
    		*(tempResult + i) = *(tempResult + i) + *(tempResult + i - 1);
    
    	//将n个元素直接放入正确的位置  
    	for (int i = n - 1; i >= 0; --i)
    	{
    		*(result + *(tempResult + getDigitNun(*(a + i), digit))) = *(a + i);
    		*(tempResult + getDigitNun(*(a + i), digit)) = *(tempResult + getDigitNun(*(a + i), digit)) - 1;
    	}
    
    	delete[] tempResult;
    }

/*基于链表的基数排序*/
    #include <iostream>
    using namespace std;
    
    typedef struct list  //静态链表结构体类型
    {
    	int data;
    	int next;
    }List;
    List bucket[10];   //构造十个桶
    List d[10];        //将待排序数据构造成list类型的数组
    int maxbit(int data[], int n)   //计算待排序数组元素的最长的位数
    {
    	int d = 1;
    	for (int i = 0; i<n; i++)
    	{
    		int c = 1;
    		int p = data[i];
    		while (p / 10)
    		{
    			p = p / 10;
    			c++;
    		}
    		if (c>d)
    			d = c;
    	}
    	return d;
    }
    void init(int data[], int n)  //清桶的过程，以及将临时的数组放到d【10】数组中
    {
    	int j = 0;
    	for (j = 0; j<n; j++)
    	{
    		bucket[j].next = -1;
    		bucket[j].data = j;
    	}
    	for (j = 0; j<n; j++)
    	{
    		d[j].data = data[j];
    		d[j].next = -1;
    	}
    }
    void RadixSort(int data[], int n)   //基数排序的过程
    {
    
    	int p = maxbit(data, n);   //先求出最长的位数
    	int r = 1;
    	for (int i = 0; i<p; i++)   //执行装桶倒桶的次数
    	{
    		init(data, n);   //复位清桶的过程
    		if (i != 0)   //第一次装桶的时候从小到大开始装，之后都从大到小装桶
    		{
    			for (int k = n - 1; k >= 0; k--)
    			{
    				int a = d[k].data / r;
    				int b = a % 10;
    				d[k].next = bucket[b].next;
    				bucket[b].next = k;
    			}
    		}
    		else
    		{
    			for (int k = 0; k<n; k++)
    			{
    				int a = d[k].data / r;
    				int b = a % 10;
    				d[k].next = bucket[b].next;
    				bucket[b].next = k;
    			}
    		}
    
    		int c = 0;
    		for (int k = 0; k<n; k++)   //倒桶的过程，将其放到data数组当中
    		{
    
    			if (bucket[k].next != -1)
    			{
    				int p = bucket[k].next;
    				data[c++] = d[p].data;
    				while (d[p].next != -1){
    					data[c++] = d[d[p].next].data;
    					p = d[p].next;
    				}
    			}
    		}
    		r = r * 10;  //为了后面对十位数以及高位求当前位置上的数字
    	}
    }
    int main()
    {
    	int data[10] = { 73, 22, 93, 43, 55, 14, 28, 65, 39, 81 };  //待排序的数组
    	cout << "基于静态链表的基数排序c++实现" << endl;
    
    	//cout<<maxbit(data,10)<<endl;
    	cout << "排序之前的数值：";
    	for (int i = 0; i<10; i++)
    		cout << data[i] << " ";
    	cout << endl;
    
    	RadixSort(data, 10);
    
    	cout << "排序之后的数值：";
    	for (int i = 0; i<10; i++)
    		cout << data[i] << " ";
    	cout << endl;
    	system("pause");
    	return 0;
    }

链表排序示例：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzc1MzIxNQ_size_16_color_FFFFFF_t_70 2][]

### **9 桶排序（Bucket Sort）** ###

**算法思想：**首先建立一堆buckets，然后遍历原始数组，并将数据放入到各自的buckets中，接着对非空的buckets进行排序，最后按照顺序遍历这些buckets并放回到原始数组中即可构成排序后的数组。

图示：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzc1MzIxNQ_size_16_color_FFFFFF_t_70 3][]

**算法实现：**

#include <iostream>
    #include <iomanip>
    using namespace std;
    
    #define NARRAY 8  /* array size */
    #define NBUCKET 5 /* bucket size */
    #define INTERVAL 10 /* bucket range */
    
    struct Node
    {
    	int data;
    	struct Node *next;
    };
    
    void BucketSort(int arr[]);
    struct Node *InsertionSort(struct Node *list);
    void print(int arr[]);
    void printBuckets(struct Node *list);
    int getBucketIndex(int value);
    
    void BucketSort(int arr[])
    {
    	int i, j;
    	struct Node **buckets;
    
    	/* allocate memory for array of pointers to the buckets */
    	buckets = (struct Node **)malloc(sizeof(struct Node*) * NBUCKET);
    
    	/* initialize pointers to the buckets */
    	for (i = 0; i < NBUCKET; ++i) {
    		buckets[i] = NULL;
    	}
    
    	/* put items into the buckets */
    	for (i = 0; i < NARRAY; ++i) {
    		struct Node *current;
    		int pos = getBucketIndex(arr[i]);
    		current = (struct Node *) malloc(sizeof(struct Node));
    		current->data = arr[i];
    		current->next = buckets[pos];
    		buckets[pos] = current;
    	}
    
    	/* check what's in each bucket */
    	for (i = 0; i < NBUCKET; i++) {
    		cout << "Bucket[" << i << "] : ";
    		printBuckets(buckets[i]);
    		cout << endl;
    	}
    
    	/* sorting bucket using Insertion Sort */
    	for (i = 0; i < NBUCKET; ++i) {
    		buckets[i] = InsertionSort(buckets[i]);
    	}
    
    	/* check what's in each bucket */
    	cout << "-------------" << endl;
    	cout << "Bucktets after sorted" << endl;
    	for (i = 0; i < NBUCKET; i++) {
    		cout << "Bucket[" << i << "] : ";
    		printBuckets(buckets[i]);
    		cout << endl;
    	}
    
    	/* put items back to original array */
    	for (j = 0, i = 0; i < NBUCKET; ++i) {
    		struct Node *node;
    		node = buckets[i];
    		while (node) {
    			arr[j++] = node->data;
    			node = node->next;
    		}
    	}
    
    	/* free memory */
    	for (i = 0; i < NBUCKET; ++i) {
    		struct Node *node;
    		node = buckets[i];
    		while (node) {
    			struct Node *tmp;
    			tmp = node;
    			node = node->next;
    			free(tmp);
    		}
    	}
    	free(buckets);
    	return;
    }
    
    /* Insertion Sort */
    struct Node *InsertionSort(struct Node *list)
    {
    	struct Node *k, *nodeList;
    	/* need at least two items to sort */
    	if (list == 0 || list->next == 0) {
    		return list;
    	}
    
    	nodeList = list;
    	k = list->next;
    	nodeList->next = 0; /* 1st node is new list */
    	while (k != 0) {
    		struct Node *ptr;
    		/* check if insert before first */
    		if (nodeList->data > k->data)  {
    			struct Node *tmp;
    			tmp = k;
    			k = k->next;
    			tmp->next = nodeList;
    			nodeList = tmp;
    			continue;
    		}
    
    		for (ptr = nodeList; ptr->next != 0; ptr = ptr->next) {
    			if (ptr->next->data > k->data) break;
    		}
    
    		if (ptr->next != 0){
    			struct Node *tmp;
    			tmp = k;
    			k = k->next;
    			tmp->next = ptr->next;
    			ptr->next = tmp;
    			continue;
    		}
    		else{
    			ptr->next = k;
    			k = k->next;
    			ptr->next->next = 0;
    			continue;
    		}
    	}
    	return nodeList;
    }
    
    int getBucketIndex(int value)
    {
    	return value / INTERVAL;
    }
    
    void print(int ar[])
    {
    	int i;
    	for (i = 0; i < NARRAY; ++i) {
    		cout << setw(3) << ar[i];
    	}
    	cout << endl;
    }
    
    void printBuckets(struct Node *list)
    {
    	struct Node *cur = list;
    	while (cur) {
    		cout << setw(3) << cur->data;
    		cur = cur->next;
    	}
    }
    
    int main()
    {
    	int array[NARRAY] = { 29, 25, 3, 49, 9, 37, 21, 43 };
    
    	cout << "Initial array" << endl;
    	print(array);
    	cout << "-------------" << endl;
    
    	BucketSort(array);
    	cout << "-------------" << endl;
    	cout << "Sorted array" << endl;
    	print(array);
    	system("pause");
    	return 0;
    }

### **10 计数排序（Counting Sort）** ###

**算法思想：**对于有限个一定范围内的整数，可以采用遍历的方式得到每个数的个数，放入相应的值所对应的下标数组的位置中，再通过将原数组从后往前遍历，并对照与计数数组之间的关系，将原始数组数据排好序后放入到新数组中。

步骤：1）找出待排序数组的最大值和最小值；

2）统计数组中的每个值为i的元素出现的次数，存放到数组C的第i项（C是计数数组）；

3）对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）；

4）返回填充的目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减1.

**算法实现：**

#include<iostream>
    using namespace std;
    
    void CountSort(int arr[], int nLength)
    {
    	int *pCount = NULL;
    	int i;
    	int j;
    	int nMin, nMax;
    
    	if (arr == NULL || nLength <= 0)return;
    
    	//找最大值和最小值
    	nMax = arr[0];
    	nMin = arr[0];
    	for (i = 1; i<nLength; i++)
    	{
    		if (arr[i] > nMax)
    		{
    			nMax = arr[i];
    		}
    		if (arr[i] < nMin)
    		{
    			nMin = arr[i];
    		}
    	}
    	//开辟计数数组
    	pCount = (int *)malloc(sizeof(int)* (nMax - nMin + 1));
    	memset(pCount, 0, sizeof(int)* (nMax - nMin + 1));
    	//计数
    	for (i = 0; i<nLength; i++)
    	{
    		pCount[arr[i] - nMin]++;
    	}
    	//放回原数组
    	j = 0;
    	for (i = 0; i< nMax - nMin + 1; i++)
    	{
    		while (pCount[i] != 0)
    		{
    			arr[j] = i + nMin;
    			j++;
    			pCount[i]--;
    		}
    	}
    }
    
    void printArray(int *a, int len)
    {
    	for (int i = 0; i < len; i++)
    	{
    		cout << a[i] << " ";
    	}
    	cout << endl;
    }
    
    int main()
    {
    	int a[] = { 1, 5, 3, 7, 6, 2, 8, 9, 4, 3, 3 };
    	int len = sizeof(a) / sizeof(a[0]);
    	cout << "排序前：" << endl;
    	printArray(a, len);
    	CountSort(a, len);
    	cout << "排序后：" << endl;
    	printArray(a, len);
    	system("pause");
    	return 0;
    }

### **10种排序算法对比** ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzc1MzIxNQ_size_16_color_FFFFFF_t_70 4][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzc1MzIxNQ_size_16_color_FFFFFF_t_70 5][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzc1MzIxNQ_size_16_color_FFFFFF_t_70]: /images/20211204/f0afef6066144aa6b31a19fcdfedf0e3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzc1MzIxNQ_size_16_color_FFFFFF_t_70 1]: /images/20211204/b980d845dfa341e585d6c22257a78613.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzc1MzIxNQ_size_16_color_FFFFFF_t_70 2]: /images/20211204/96a1643cce664dbbbb126f3b93688d62.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzc1MzIxNQ_size_16_color_FFFFFF_t_70 3]: /images/20211204/74f41a8dc4b14fbeb209b1756f64c2f9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzc1MzIxNQ_size_16_color_FFFFFF_t_70 4]: /images/20211204/b914af68ebc543c791e8059864b5d089.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzc1MzIxNQ_size_16_color_FFFFFF_t_70 5]: /images/20211204/4e0fb1029e67490c94345b52c1f58f0f.png