【C++十大排序】

• 介绍
• • 冒泡排序
  • 插入排序
  • 选择排序
  • 快速排序
  • 归并排序
  • 希尔排序
  • 桶排序
  • 计数排序
  • 基数排序
• 代码

排序算法的稳定性指假定在待排序的记录序列中，存在多个具有相同的关键字的记录，经过排序这些记录的相对次序保持不变，则是稳定的，否则为不稳定。不稳定的算法在某种条件下可以变为稳定的算法，而稳定的算法在某种条件下也可以变为不稳定的算法

排序名称 平均时间复杂度 最好情况 最坏情况 空间复杂度 稳定性
冒泡排序 O(n2) O(n) O(n2) O(1) 稳定
插入排序 O(n2) O(n) O(n2) O(1) 稳定
选择排序 O(n2) O(n2) O(n2) O(1) 不稳定
快速排序 O(nlogn) O(nlogn) O(n2) O(logn) 不稳定
归并排序 O(nlogn) O(nlogn) O(nlogn) O(n) 稳定(外部排序)
希尔排序 O(nlogn) O(nlog2n) O(nlog2n) O(1) 不稳定
堆排序 O(nlogn) O(nlogn) O(nlogn) O(1) 不稳定
桶排序 O(n+k) O(n+k) O(n2) O(n+k) 稳定(外)
计数排序 O(n+k) O(n+k) O(n+k) O(k) 稳定(外)
基数排序 O(nk) O(nk) O(n*k) O(n+k) 稳定（外）

每次将最大值向后面移动

依次将未排序的数字插入到已排好序的序列中去

每次从未排序的数字中选择最小的数字，将数字放在已排好序的序列结尾

使用双指针l,r,分别指向序列的两端，先确定一个值作为中间值，在原来的序列中根据这个值进行划分，比这个值小的元素排前面；比这个元素小的排后面，然后以相同的做法处理两端的两个序列（递归）

使用递归，与快速排序不同的是，先进入深层，先对小数量合并排序，再对大数量合并排序。合并时可以先创建一个临时空间，来保存遍历两组有序的序列，合并完成后写回原空间中。

通过将比较的全部元素分为几个区域来提升插入排序的性能。这样可以让一个元素一次性地朝最终位置前进一大步。然后算法再取越来越小的步长进行排序，算法的最后一步就是普通的插入排序，但是到了这一步，需排序的数据几乎是排好的。（局部的插入排序）
堆排序：首先将数组初始化为大顶堆或者小顶堆，再每次取出堆顶的数字，那么就可以获得一个有序的序列了。
（1） 利用给定的数组创建一个堆H(0…n-1)(小顶堆或大顶堆)，输出堆顶元素
（2） 以最后一个元素代替堆顶，调整成堆，输出堆顶元素
（3） 把堆的尺寸缩小1
（4） 重复步骤2，直到堆的尺寸为1
建堆：将数组原地建成一个堆，不借助额外的空间，采用从上往下的堆化（对于完全二叉树来说，下标是n/2+1到n的节点都是叶子节点，不需要堆化）
排序：“删除堆顶元素”：当堆顶元素移除后，把下标为n的元素放到堆顶，然后再通过堆化的方法，将剩下的n-1个元素重新构建成堆，堆化完成后，再取堆顶的元素，放到下标为n-1的位置，一直重复这个过程，直到最后堆中只剩下标为1的一个元素。

将数组分到有限数量的桶里。每个桶再个别排序（有可能使用别的排序方法或是以递归的方式继续使用桶排序进行排序）如果桶的大小为1，有点像计数排序

用待排序的数作为计数数组的下标，统计每个数字的个数。然后依次输出即可得到有序的序列

基数排序对要排序的数据是有要求的，需要可以分割出独立的“位”来比较，而且位之间有递进的关系，如果a数据的高位比b数据大，那剩下的低位就不用比较了。除此之外，每一位的数据范围不能太大，要可以用线性排序算法来排序，否则，基数排序的时间复杂度就无法做到O(n)了。（适合有不同位数大小的数字）

#include 
#include
#include
#include
#include
#include "Dict_Trie.h"
using namespace std;

//1、冒泡排序
void BubbleSort(vector &nums, int n)
{
	if (n <= 1) return;

	bool is_swap=false;//（提前停止）设计一个标记，若为false，则表示此次循环没有进行交换，也就是待排序列已经有序，排序完成
	for (int i = 1; i < n; i++)
	{
		is_swap = false;
		for (int j = 1; j < n - i + 1; j++)
		{
			if (nums[j] < nums[j - 1])
			{
				swap(nums[j], nums[j - 1]);
				is_swap = true;
			}
		}
		if (!is_swap)
		{
			return;
		}
	}
}
//2、插入排序
void InsertSort(vector &nums, int n)
{
	if (n <= 1) return;
	for (int i = 1; i < n; i++)
	{
		for (int j = i; j > 0 && nums[j] < nums[j - 1]; j--)
		{
			swap(nums[j], nums[j - 1]);
		}
	}
}
//3、选择排序
void SelectSort(vector& nums, int n)
{
	if (n <= 1) return;
	int mid;
	for (int i = 0; i < n - 1; i++)
	{
		mid = i;
		for (int j = i + 1; j < n; j++)
		{
			if (nums[j] < nums[mid])
			{
				mid = j;
			}
		}
		swap(nums[mid], nums[i]);
	}
}
//4、快速排序
void QuickSort(vector& nums, int l, int r)
{
	if (l + 1 >= r) return;
	int first = l, last = r - 1, key = nums[first];
	while (first < last)
	{
		while (first < last&&nums[last] >= key) last--;//右指针从右向左扫描 将小于piv的放到左边
		nums[first] = nums[last];
		while (first < last&&nums[first] <= key) first++;//左指针从左向右扫描 将大于piv的放到右边
		nums[last] = nums[first];
	}
	nums[first] = key;//更新piv

	QuickSort(nums, l, first);
	QuickSort(nums, first + 1, r);
}
//5、归并排序
void Merge(vector& nums, int l, int mid, int r)
{
	int start = l;
	int num1 = l, num2 = mid + 1;
	vector temp(nums.size());
	while (num1 <= mid && num2 <= r)
	{
		if (nums[num1] < nums[num2])
		{
			temp[start] = nums[num1];
			num1++;
			start++;
		}
		else
		{
			temp[start] = nums[num2];
			num2++;
			start++;
		}
	}
	while (num1 <= mid)
	{
		temp[start] = nums[num1];
		start++;
		num1++;
	}
	while (num2 <= r)
	{
		temp[start] = nums[num2];
		num2++;
		start++;
	}
	for (int i = l; i <= r; i++)
	{
		nums[i] = temp[i];
	}
}
void Merge_Sort(vector& nums,int l,int r)
{
	if (l < r)
	{
		int mid = l + (r - l) / 2;
		Merge_Sort(nums, l, mid);
		Merge_Sort(nums, mid + 1, r);
		Merge(nums,l,mid,r);
	}
}
//6、希尔排序:局部的插入排序
void shellSort(vector& nums)
{
	int gap = nums.size() / 2;
	while (gap > 0)
	{
		for (int k = gap; k < nums.size(); k++)
		{
			for (int i = k-gap; i >= 0&&nums[i]>nums[gap+i] ; i -= gap)
			{		
					swap(nums[i], nums[i + gap]);
			}
		}
		gap /= 2;
	}
}
//7、堆排序
//将堆中指定位置i的数字与孩子节点进行对比  直到达到最底层，或者孩子节点全都大于节点i的值
void Heapify(int a[], int n, int i)
{
	while (1)
	{
		int maxPos = i;
		if (i * 2 <= n && a[i] < a[i * 2]) { maxPos = i * 2; }
		if (i * 2 + 1 <= n && a[maxPos] < a[i * 2 + 1]) { maxPos = i * 2 + 1; }
		if (maxPos == i) break;
		swap(a[i], a[maxPos]);
		i = maxPos;

	}
}
//传入的数组下标0位置应该记录数组需要排序的数量，下标为0的数字不会加入到排序过程中
void HeapSort(int a[], int n)
{
	//先初始化堆
	for (int i = n / 2; i >= 1; i--)
	{
		Heapify(a, n, i);
	}
	//每次将首位与未排序的序列中的最小值（最后一个数）交换
	int k = n;
	while (k > 1)
	{
		swap(a[1], a[k]);
		--k;
		Heapify(a, k, 1);
	}
}
//8、桶排序     如果桶的大小为1的话和计数排序有点像
void bucketSort(vector& nums)
{
	if (nums.empty()) return;
	int low = *min_element(nums.begin(), nums.end());
	int high = *max_element(nums.begin(), nums.end());
	int n = high - low + 1;
	vector buckets(n);
	vector res;
	for (auto x : nums)++buckets[x - low];
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < buckets[i]; ++j)
		{
			res.push_back(i + low);
		}
	}
	for (int i = 0; i < res.size(); ++i)
	{
		cout << res[i] << " ";
	}

}
//9、计数排序
void countSort(int *a, int n)
{
	//1、找到最大的值
	int maxV = a[0];
	for (int i = 1; i < n; i++)
	{
		maxV = max(maxV, a[i]);
	}
	//2、初始化计数空间，所有位置值为0
	int *c=new int[maxV+1];
	memset(c, 0, (maxV+1)*4);
	//3、遍历序列对应位置进行计数+1
	for (int i = 0; i < n; i++)
	{
		c[a[i]]++;
	}
	//4、对计数数组顺序求和
	for (int i = 1; i <= maxV; i++)
	{
		c[i] += c[i - 1];
	}
	//5、重新创建一个空间辅助排序
	int *r = new int[n];
	memset(r, 0, n*4);
	//6、根据数值的个数进行排序    position=c[a[i]]-1
	for (int i = n - 1; i >= 0; i--)
	{
		int index = c[a[i]] - 1;
		r[index] = a[i];
		c[a[i]]--;
	}
	//7、将排好序的序列写回原数组中
	for (int i = 0; i < n; i++)
	{
		a[i] = r[i];
	}


}
//10、基数排序  相当于通过循环进行了多次桶排序
int maxBit(vector vec)//返回vector中最长的元素有几位
{
	int max = vec[0];
	for (int i = 1; i < vec.size(); i++)
	{
		if (vec[i] > max) max = vec[i];
	}
	int p = 1;
	while (max / 10 != 0)
	{
		max = max / 10;
		p++;
	}
	return p;
}

vector  countSort(vector vec, int place) {//按指定位置的值进行计数排序
	vector temp(vec); //临时数组，存储place位置的值
	vector ordered(vec); //排好序的数组放进ordered
	int count[10] = { 0 };
	for (int i = 0; i < vec.size(); i++) {
		temp[i] = (int)(vec[i] / pow(10, place - 1)) % 10; //找到每个元素place位置上的数字存在temp中
	}
	for (int i = 0; i < vec.size(); i++) {
		count[temp[i]] ++; //统计数字出现的频率
	}
	for (int i = 1; i < 10; i++) {
		count[i] = count[i] + count[i - 1]; //此时count中存放着temp中每个数字的索引
	}
	for (int i = vec.size() - 1; i >= 0; i--) {
		int index = count[temp[i]] - 1;
		count[temp[i]]--;
		ordered[index] = vec[i];
	}
	cout << "next:" << endl;
	for (int i = 0; i < vec.size(); i++) {
		cout << ordered[i] << "  ";
	}
	cout << endl;
	return ordered;
}

void radixSort(vector& vec)
{
	int maxbit = maxBit(vec);//最长位数是多少，代表要进行几次排序
	for (int i = 1; i <= maxbit; i++)
	{
		vec = countSort(vec, i);
	}
}
int main()
{
	vector a = { 33,66,2,2,5,95,4,46,27 };
	cout << a.size()<<" "<10, 33,66,2,2,5,95,4,46,27 };
	//HeapSort(a0, sizeof(a0)/sizeof(a0[0])-1);
	//bucketSort(a);
	//countSort(a0, 10);
	radixSort(a);
	cout << endl;
	for (auto item : a)
	{
		cout << item<