C++十种排序方法（快速排序、冒泡排序等等）

一、冒泡排序
1、概念及思路：冒泡排序顾名思义就是大的数沉下去，小的数浮上来，就跟气泡在水底浮上来一样；基本的思路很简单，就是相邻的两个数相比较，如果前面那个数比后面那个数大，则换位置，否则不需要换。以此循环下去（这里指的是从小到大排序，当然也可以从大到小）

2、代码演示：

#include<iostream>
using namespace std;
int main() {
	
	int i;
	int arr[10] = { 1,5,2,3,6,8,7,9,4 ,0};//初始化数组
	for (int i = 0; i < 9;i++) {//一共循环10次

		for (int j = 0; j < 9-i; j++) {//执行的次数依次递减
			if (arr[j]>arr[j + 1]) {
				int temp = arr[j + 1];
				arr[j + 1] = arr[j];
				arr[j] = temp;//交换值
			}
		}
	}
		
		
	
	for (int j = 0; j < 10; j++)//打印数组
	{
		cout << arr[j] << endl;
	}
	system("pause");
	return 0;
}

二、选择排序

1、思路：第一个数依次跟后面9个数比较，找出最小的那个数，放到前面来，在每次两两比较过程中，前面的数若比后面的数大，则交换其下标值，以此循环9次就可以找出10个数中的最小那个。再那第二个数与后面8个数比较找出当中的最小值，以此类推…（这里也是以从小到大为例）

2、代码演示：

#include<iostream>
using namespace std;
int main() {
	
	int i;
	int arr[10] ;//初始化数组
	
	for (i = 0; i < 10; i++)
	{
		cin >> arr[i];//输入10要排序的数
	}

	for (int i = 0; i < 10;i++) {//一共循环10次

		for (int j = 0; j < 10; j++) {//找到10个数当中的最小值
			if (arr[j]>arr[i ]) {
				int temp = arr[i];
				arr[i] = arr[j];
				arr[j] = temp;//交换值
			}
		}
	}
		
		
	
	for (int j = 0; j < 10; j++)//打印数组
	{
		cout << arr[j] << endl;
	}
	system("pause");
	return 0;
}

三、插入排序
1、思路：从第二个数开始与第一个数比较，小的插入到前面，这样就排好前面两个数的位置了，第二次循环，把第三个数与前面两个数依次比较，如果小于第二个数的数，则把它插到第二个数的位置（实际上是交换两个数的值），然后再与第一个数比较，如果小则插到第一个数的位置，这样前面三个数就拍好的位置，以此类推，循环两次可以把前面三个数排好位置，循环9次就可以把10个数的位置顺序排好了。

2、代码演示

#include<iostream>
using namespace std;
int main() {
	
	int i;
	int arr[10] ;//初始化数组
	
	for (i = 0; i < 10; i++)
	{
		cin >> arr[i];//输入10要排序的数
	}

	for (int i = 1; i < 10;i++) {//10个数循环9次

		for (int j = i; j >0; j--) {//从第二个数开始与第一个数比较，小的插入到前面
			if (arr[j-1]>arr[j]) {
				int temp = arr[j-1];
				arr[j-1] = arr[j];
				arr[j] = temp;//插到前面来（交换值）
			}
		}
	}
		
		
	
	for (int j = 0; j < 10; j++)//打印数组
	{
		cout << arr[j] << endl;
	}
	system("pause");
	return 0;
}

四、希尔排序
1、思路：首先定义一个gap,从第0个数开始，每隔一个gap取出一个数，将取出来的数进行比较，方法类似插入排序。第二轮从第二个数开始，每隔一个gap取出一个数再进行插入排序。四轮就可以取完（假如数组有15个数）。之后再将gap倍减，进行前面的步骤，直至gap为1.

2、代码演示：

#include<iostream>
using namespace std;
int main() {
	
	int i;
	int arr[15] = {9,6,11,3,5,12,8,7,10,15,14,4,1,13,2};//初始化数组
	
	
	
	for (int gap = 4; gap > 0; gap /=2)//定义一个空隙为4，依次减倍
	{
		for (int i = gap; i < 15; i++) {

			for (int j = i; j >gap - 1; j -= gap) {
				//从第0个数开始，每隔4个数进行两两比较
				if (arr[j - gap]>arr[j]) {
					int temp = arr[j - gap];
					arr[j - gap] = arr[j];
					arr[j] = temp;//插到前面来（交换值）
				}
			}
		}
	}
	
		
		
	
	for (int j = 0; j < 15; j++)//打印数组
	{
		cout << arr[j] << endl;
	}
	system("pause");
	return 0;
}

五、归并排序
1、思路：设定一个中间值，把数组分成两组：第一组和第二组（假定两组已排好序），然后定义一个全新的数组，用来存放排好序的数。开始比较两个数组的数的大小，小的放全新数组里面，第一个数组跳到下一个位置，然后跟第二个数组比较，小的继续放全新的数组里面，以此循环下去，去到不符合条件为止（写着程序里了）

2、代码演示：

#include<iostream>
using namespace std;
int main() {
	int arr[7] = {1,4,7,8,3,6,9};//初始化数组
	int mid = 7 / 2;//设定一个中间值，把数组分成两组（假定两组已排好序）
	//cout << mid << endl;
	int i=0,j=mid+1, k=0;//设定三个变量，i,j表示两组数组的开始下标
	int temp[7] = {};//定义一个全新的数组，用来存放排好序的数
	while (i <= mid&&j < 7) {//判断i,j的值是否到达临界
		if (arr[i] < arr[j]) {
			temp[k] = arr[i];
			k++;
			i++;
			

		}
		else {
			temp[k] = arr[j];
			k++;
			j++;
		}
	}
	while (i <= mid) temp[k++] = arr[i++];//补全另外两种情况，未能同时满足&&
	while (j < 7) temp[k++] = arr[j++];

	for (int k = 0; k < 7; k++)//打印数组
	{
		cout << temp[k] << endl;
	}
	system("pause");
	return 0;
}

六、快速排序

1、思路：快速排序和归并排序一样，都采用了分至和递归的思想。首先选取一个数字pivot作为中心轴，然后把数组中比pivot大的数放在pivot的右边，比pivot小的事放在pivot的左边。通过第一次排序就可以得到一个有顺序的pivot，再将左子序列或者右子序列重复进行上面的操作，直至左子序列或者右子序列的数字为一。

2、代码演示：

#include<iostream>
using namespace std;
void quickSort(int a[], int, int);//原型声明
int main()
{
	int array[] = { 32,64,12,43,69,5,78,10,3,70 },k;
	int len = sizeof(array) / sizeof(int);//数组长度
//cout << len << endl;
	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)
				s[i++] = s[j];
			while (i < j && s[i]< x) // 从左向右找第一个大于等于x的数
				i++;
			if (i < j)
				s[j--] = s[i];
		}
		s[i] = x;
		quickSort(s, l, i - 1); // 递归调用
		quickSort(s, i + 1, r);
	}
}

七、计数排序
1、思路：基数排序是一种非比较排序，常用于规模大，数字种类小的排序中，如考试成绩排名、人口年龄等等。思路很简单，但实现起来不容易，首先得定义两个数组，一个用于存放数字种类的个数，另一个用于存放排好序的数组。然后遍历整个数组，记录下数组中各数字的个数存放于第一个数组中，比如1出现一次，就存放于temp[arr[1]]中，然后再将这些出现的个数一次存放在新的数组中，从而达到排好序。

2、代码演示：

#include<iostream>
using namespace std;
int arr[] = {3,2,3,1,5,6,8,6}, temp[1001], result[1001], n;
int main() {
	int len = sizeof(arr)/sizeof(int);//数组长度
	cout << len << endl;
	//cin >> n;
	for (int i = 0; i < len; i++)
	{
		temp[arr[i]]++;
	}
	for (int i = 0; i < len; i++)
	{
		temp[i+1]+=temp[i];
	}
	for (int i = len - 1; i >= 0; i--)
	{
		result[--temp[arr[i]]] = arr[i];
	}
	for (int i = 0; i < len; i++)//打印数组
	{
		
		cout << result[i] << " ";
	}
	system("pause");
	return 0;
}

八、基数排序

1、思路：基数排序和计数排序一样都是非比较排序，思路比较简单，但是代码实现还是有点难度的。假定一组数只有三位数组成，先将个位上的数按顺序好，如个位上是1就放在数组index为1的数组中；将个位上排好序之后，将数从上到下取出来（先进先出）进行十位上的排序，再进行百位上的排序。三轮排序之后就会呈现出一个有序的数组。

2、代码实现

#include <iostream>
using namespace std;
//打印数组
void printArray(int array[], int length)
{
	for (int i = 0; i < length; ++i)
	{
		cout << array[i] << " ";
	}
	cout << endl;
}
//求数据的最大位数,决定排序次数

int maxbit(int data[], int n)
{
	int d = 1; //保存最大的位数
	int p = 10;
	for (int i = 0; i < n; ++i)
	{
		while (data[i] >= p)
		{
			p *= 10;
			++d;
		}
	}
	return d;
}
void radixsort(int data[], int n) //基数排序
{
	int d = maxbit(data, n);
	int temp[10];
	int count[10]; //计数器
	int i, j, k;
	int radix = 1;
	for (i = 1; i <= d; i++) //进行d次排序
	{
		for (j = 0; j < 10; j++)
			count[j] = 0; //每次分配前清空计数器
		for (j = 0; j < n; j++)
		{
			k = (data[j] / radix) % 10; //统计每个桶中的记录数
			count[k]++;
		}
		for (j = 1; j < 10; j++)
			count[j] = count[j - 1] + count[j]; //将temp中的位置依次分配给每个桶
		for (j = n - 1; j >= 0; j--) //将所有桶中记录依次收集到temp中
		{
			k = (data[j] / radix) % 10;
			temp[count[k] - 1] = data[j];
			count[k]--;
		}
		for (j = 0; j < n; j++) //将临时数组的内容复制到data中
			data[j] = temp[j];
		radix = radix * 10;
	}
}

int main()
{
	int array[10] = { 73,22,93,43,55,14,28,65,39,81 };
	radixsort(array, 10);
	printArray(array, 10);
	system("pause");
	return 0;
}

九、堆排序
1、思路：步骤一：建立大根堆–将n个元素组成的无序序列构建一个大根堆，
步骤二：交换堆元素–交换堆尾元素和堆首元素，使堆尾元素为最大元素；
步骤三：重建大根堆–将前n-1个元素组成的无序序列调整为大根堆
2、代码演示：`

#include<iostream>
using namespace std;
void adjust(int arr[], int len, int index)
{
	int left = 2 * index + 1;
	int right = 2 * index + 2;
	int max = index;
	if (left<len && arr[left] > arr[max]) max = left;
	if (right<len && arr[right] > arr[max]) max = right;  // max是3个数中最大数的下标
	if (max != index)                 // 如果max的值有更新
	{
		swap(arr[max], arr[index]);
		adjust(arr, len, max);       // 递归调整其他不满足堆性质的部分
	}

}
void heapSort(int arr[], int size)
{
	for (int i = size / 2 - 1; i >= 0; i--)  // 对每一个非叶结点进行堆调整(从最后一个非叶结点开始)
	{
		adjust(arr, size, i);
	}
	for (int i = size - 1; i >= 1; i--)
	{
		swap(arr[0], arr[i]);           // 将当前最大的放置到数组末尾
		adjust(arr, i, 0);              // 将未完成排序的部分继续进行堆排序
	}
}

int main()
{
	int array[8] = { 6, 0, 15, 4, 21, 5, 7, 10 };
	heapSort(array, 8);
	for (auto it : array)
	{
		cout << it << endl;
	}
	system("pause");
	return 0;
}

十、桶排序
略