一 排序

1.1 排序的概念

    所谓排序，就是一种使一串数据记录，按照其中的某个或某些关键字的大小，递增或递减地组织起来的操作。

    从排序方式上，排序算法一般被分为比较排序和非比较排序。从比较排序的内容上，它一般被分为插入排序、选择排序、交换排序和归并排序，其中，它们每一种又有更细致的分类。

    本文所讲排序除了计数排序，桶排序，基数排序外，其它为比较排序。

1.2 稳定性

   稳定性是排序最重要的评价方式。假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。

1.3 内部排序和外部排序

   从数据的存储上，它被分为内部排序和外部。内部排序，是排序的元素全部放在内存中的排序。 外部排序，是数据元素太多的时候不能同时放在内存中，根据排序过程的要求又不能在内外存之间移动数据的排序。

二 插入排序

2.1 直接插入排序

   直接插入算法的思路如下：

1.    当插入第 i (i >= 1)个元素时，前面的所有元素已经排好序
2.    此时用第i个元素与排好序的数组，顺序进行比较，寻找我们需要插入的位置，一边将原来位置上的元素顺序后移。  

这个思路很好理解，给出代码如下：

  

// 插入排序
void insert_sort(std::vector<int>& nums) {

	//因为这里我们数组 0 位置只有一个数字，此时数组是排好的
	//也就是说 我们从1位置开始即可
	for (int i = 1; i < nums.size(); i++) { //外部循环控制待插入的数字
		//升序 通过这行代码进行 查找 交换
		for (int j = i; j > 0 && nums[j] < nums[j - 1]; j--) {
			swap(nums[j], nums[j - 1]);
		}
		//降序
	/*	for (int j = i; j > 0 && nums[j] > nums[j - 1]; j--) {
			swap(nums[j], nums[j - 1]);
		}*/
	}
}

直接插入排序的特性总结：

1. 元素集合越接近有序，直接插入排序算法的时间效率越高
2. 时间复杂度：O(N^2):要求升序，但数组实际上是降序，这样的话内循环每个都要进去  最好情况）：o(n))：要求升序，数组实际上也是升序，即一次外循环即可排序好
3. 空间复杂度：O(1)
4. 稳定性：稳定

2.2 希尔排序

  希尔排序实际上是直接插入排序的一种优化，又称缩小增量法，它的基本思想是： 在进行直接插入排序之前，我们进行一次预排序，将待排序的数组往直接插入排序的最好情况靠拢，也就是说，让数组接近有序。

  希尔排序的步骤：
  1 预排序（将数组接近有序）-> 提高直接插入排序的效率  

  2 直接插入排序 -> 最终得到有序数组

 对于预排序，我们采用的方法是， 将间隔为gap的数进行分组，然后对一个个小组进行直接插入排序，注意是间隔为gap，也就是说，我们的一趟分组可能如下所示：

 这样分组可以使我们的数组变得接近有序，但此时我提出一个疑问，gap该设定为多少呢？

  已知：
- gap越大，跳得越快，但越不接近有序
- gap越小，跳得越慢，但越接近有序，为1时变为直接插入排序

  因为我们的预排序结果要接近有序，所以我们的gap应该更小，但是希尔排序又是直接插入排序的一种优化，如果gap很小，比如说gap为1，那么效率无疑是十分低下的。

  希尔排序设定gap是一个不断缩减的数字(一般最大为数组长度除2或者除3），因为当我们将gap设定为一个大值的时候，优化的效率差但是运行快，然后gap变小的话，就可以借助上一次的优化，缩减运行时间，当gap缩减为1，变为直接插入排序。

  如下图显示，d1即为gap:

代码如下，gap设定为数组长度/3；

//希尔排序
void shell_sort(vector<int>& nums) {
   
	int gap = nums.size();
	while (gap > 1) { //大循环分组排序
		gap = gap / 3 + 1;// 因为C语言的向下取整 要保证最后一次为1 以进行直接插入排序 
		//外循环进行直接插入排序 要保证范围 为 [i-gap+1,i]  
		//因为下标的问题(gap+1)了我们这里第0位数字不参与分组，在最后直接插入
		for (int i = gap; i < nums.size(); i++) { 
			//升序 
			for (int j = i; j > i-gap && nums[j] < nums[j - 1]; j--) {
				swap(nums[j], nums[j - 1]);
			}
			//降序
			/*for (int j = i; j > i - gap && nums[j] > nums[j - 1]; j--) {
				swap(nums[j], nums[j - 1]);
			}*/
		}
	}
}

 希尔排序的特性总结：

1. 希尔排序是对直接插入排序的优化。
1. 当gap > 1时，进行的都是预排序，目的是让数组更接近于有序；当gap == 1时，数组已经接近有序，此时进行直接插入排序会非常快（整体而言可以达到优化的效果）；
希尔排序的时间复杂度并不好计算，实际中gap的取值方法很多，导致很难去计算，因此在许多教材中给出的希尔排序的时间复杂度都不固定：

  因为上文代码中的gap是按照Knuth提出的方式取值的，且Knuth进行了大量的试验统计，具有足够信服力，故本博客按照：O(N^1.25)到O(1.6 * N^1.25)（约为O(N^1.3)）来算。

三 选择排序

3.1 直接选择排序

 这个算法的思想是非常简单的，基本思想是：比较+交换

 假设我们要排升序

1.    我们在这当前数组中，找到第一个最小的数字
2. 假设这个数字不是第一个数字，将其两个交换。
3.  从余下的个元素中，找出关键字最小的元素，重复(1)、(2)步，直到排序结束。

同时我们也可以发现，这个排序也只需要两个循环就可以解决，第一个循环依次遍历数组中的每个元素，第二个循环用来记录最小数字以及交换。

代码如下：
 

//选择排序
void select_sort(vector<int>& nums) {


	//i来负责遍历每一个数字,同时，最后一个数字就不用排序了, mid来记录最小数字 
	for (int i = 0,mid = 0; i < nums.size()-1; i++) {
		mid = i;
		//但是查询的时候依旧需要把最后一个数字算进去
		for (int j = i + 1; j < nums.size(); j++) {
			//升序
			if (nums[mid] > nums[j]) {
				mid = j;
			}
			//降序
		/*	if (nums[mid] < nums[j]) {
				mid = j;
			}*/
		}
		swap(nums[mid], nums[i]);
	}
}

直接选择排序的特性总结：

1. 时间复杂度：O(N^2)（效率较为低下）
2. 空间复杂度：O(1)
3. 稳定性：不稳定

3.2 堆排序

  堆的本质是一段数组，这段数组我们通过树的视角去看待它，也就是说，堆具有以下性质：

1.   具有根节点（一般规定为0位置节点）
2.   具有父节点和叶子节点的概念
3.   分为大根堆和小根堆，大顶堆要求节点的元素都要大于其孩子，小顶堆要求节点元素都小于其左右孩子，两者对左右孩子的大小关系不做任何要求。

堆排序的基本思想如下：

1.     建大根堆，以升序为例（ 如果要排升序，需要大根堆，排降序，需要小根堆，这点结合下两步来看）
2.    将头节点与尾节点替换，这样最大的值就排在了数组末端
3.    此时堆结构已被打乱，我们需要将新头节点调整，重新建堆
4.   重复1，2，3步

  我们一步步开始来，首先，我们需要建立堆，需要借用向下排序算法，这也是我们堆排序的核心算法，大根堆的向下调整算法的思路如下：

1.    先找到最后一个元素的父节点与左节点
2.    判断有没有右节点，选择子节点较大值
3.    假如子节点较大值，大于父节点，交换两个节点，并且将子节点成为下一个父节点，向下查找
4.    直到最后一个节点，此时查找倒数第二个元素的父节点，重复1，2，3步

由这些思路我们可以知道，当每一个节点都调整一遍之后，根节点一定是最大值，同时每个子节点都小于父节点，可以结合代码理解。

  

// 大根堆 升序排法
void adjust_down_big(vector<int> &num,int n,int root) {

	int parent = root;
	int child = parent * 2 + 1;

	while (child < n) {

		//判断是否有右节点并且选出子节点最大值
		if (child + 1 < n && num[child+1] > num[child] ) {
			child++;
		}
		//父和子节点比较 并交换
		if (num[child] > num[parent]) {
			swap(num[child], num[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		//如果父子节点不需要交换，说明从父节点往下走是符合堆的规范的，退出循环
		else {
			break;
		}
	}
}

void heap_sort(vector<int>& num) {

	// num.size()-1-1 /2 就可以找到最后的父节点
	for (int i = (num.size() - 1 - 1) / 2; i>=0; i--) {
		adjust_down_big(num, num.size(), i);
	}


}

 然后我们将头部和尾部交换，并且将头部向下调整。

//小堆的向下调整算法 降序
void adjust_down_small(vector<int> &num, int n, int root) {

	int parent = root;
	int child = parent * 2 + 1;

	while (child < n) {

		if (child + 1 < n && num[child + 1] < num[child]) {
			child++;
		}

		if (num[child] < num[parent]) {
			swap(num[child], num[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else {
			break;
		}
	}
}
// 大根堆 升序排法
void adjust_down_big(vector<int> &num,int n,int root) {

	int parent = root;
	int child = parent * 2 + 1;

	while (child < n) {

		//判断是否有右节点并且选出子节点最大值
		if (child + 1 < n && num[child+1] > num[child] ) {
			child++;
		}
		//父和子节点比较 并交换
		if (num[child] > num[parent]) {
			swap(num[child], num[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		//如果父子节点不需要交换，说明从父节点往下走是符合堆的规范的，退出循环
		else {
			break;
		}
	}
}

void heap_sort(vector<int>& num) {

	// num.size()-1-1 /2 就可以找到最后的父节点
	for (int i = (num.size() - 1 - 1) / 2; i>=0; i--) {
		adjust_down_big(num, num.size(), i);
	}

	//找到尾部节点
	int end = num.size()-1;
	while (end) {
		//交换，并且向下调整
		swap(num[end], num[0]);
		//这里的end是排除掉尾端排除好的数字
		adjust_down_big(num, end, 0);
		//end-- 就可以排除数组尾部排序好的数字
		end--;
	}
}

 堆排序的特性总结：

1. 如果用来选最大（小）数字的话，效率极高
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(1)
4. 稳定性：不稳定

四 交换排序

  所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置。交换排序的特点是，将键值较大的记录向序列的尾部移动，键值较小的记录向序列的头部移动。

4.1 冒泡排序

   冒泡排序的思想也较为简单，基本思想如下：

1. 将序列当中的左右两个元素，依次比较和交换，保证右边的元素始终大于左边的元素
   （ 第一轮结束后，序列最后一个元素一定是当前序列的最大值；）
2.  对下一个元素重复 第1步，直到数组倒数第二个元素
3. 我们也可以设置一个标记位，如果这一轮没有任何交换，那么冒牌排序就已经有序，直接退出排序即可

如图所式： 

// 冒泡排序
void bubble_sort(vector<int>& arr) {
	
	//这里我们控制右边的数字，因此从1开始
	for (int i = 1; i < arr.size(); i++) {
		//标记位
		bool flags = true;
		// 已经排好序的数字就不必参与交换
		for (int j = 1; j < arr.size() - i + 1; j++) {
			//升序
			if (arr[j] < arr[j - 1]) {
				swap(arr[j], arr[j - 1]);
				flags = false;
			}
			//降序
			/*if (arr[j] > arr[j - 1]) {
				swap(arr[j], arr[j - 1]);
				flags = 0;
			}*/
		}
		//没有发生交换 退出循环
		if (true == flags) {
			return;
		}
	}
}

 冒泡排序的特性总结：

1. 时间复杂度：O(N^2)
2. 空间复杂度：O(1)
3. 稳定性：稳定 

4.2 快速排序

  快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的任一元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

4.2.1 hoare版本

      选出一个基准值（key），我们要把它放到正确的位置（即最终排好序时要在的位置），一般选择数组的头部数据或尾部数据作为基准值。

        如图：比6小的放左边，比6大的放右边。right下标指针（图为R小人）从数组末尾向头找小的，left下标指针（图为L小人）从数组开头向尾找大的，两者都找到后，交换两者所在位置的值，当 left == right 时，则将当前位置与基准值交换。

 4.2.2 挖坑法

挖坑法是后人基于Hoare版本实现的改进版。

  拿走key的值，留下一个坑位。right下标指针找小，找到后将值填到该坑位上，并留下一个新坑位；left下标指针找大，找到后将值填到新坑位上，且再留下一个坑，以此往复。
直到left与right相遇，就将key的值填到 left == right 的坑位。  

4.2.3 前后指针法

      对于前指针prev（左）、后指针cur（右）、基准值key（数组头部），若cur找到比key小的值，则++prev，cur与prev位置的值交换；若cur找到比key大的值，则++cur。相当于把比key大的值翻转到右边（大的值往右边运），比key小的值翻转到左边（把小的值往左边运）。

【ps】prev要么紧跟cur（即prev的下一个位置就是cur/prev紧跟在比key大的值后面），要么跟cur中间间隔着一段由比key大的值组成的区间。

4.2.4 左右指针法

  快速排序的左右指针法（双指针法）是一种常见的实现方式，它利用两个指针从数组的两端开始，逐步向中间移动，并进行元素的比较和交换，以实现数组的分区和排序，思想步骤如下：
 

1. 选择基准元素，确定左右指针
2. 利用左右指针来划分空间，左指针往左存放比key小的值，右指针往右存放比key大的值
3. 划分完毕后，此时key位置的值就已经被确认，并且左区间小于key，右区间大于key
4. 递归，分别从左右两个区间范围，重复1，2，3

  首先，我们要确认基准函数，在这里我们需要用到一些算法，常见的三数取中，或者随机数选择都可以

   若对接近有序的数组进行快速排序，每一次key取开头的数都是最小的，那么每一次比key大的数都在key的右边；进行递归时只有对右边递归。这种情况下，若有N个数则递归的次数接近N方，这样我们的算法就会退化为冒牌排序，因此我们需要用算法来避免这种情况：

三数取中，选择中位数：
 

//快速排序
//三数取中
//通过比较begin ，end和mid位置三个数，得到中位数
//每一次递归调用快排，把中位数置于key的位置。防止对接近有序数组排序时多次递归
int findmid(vector<int>& nums, const int& l, const int& r) //三数取中
{
	int mid = (l+r)>>2;
	if (nums[mid] > nums[l]) {
		if (nums[mid] < nums[r]) {
			return mid;
		}
		else if (nums[r] > nums[l]){
			return r;
		}
		else {
			return l;
		}
	}
	else{
		if (nums[l] < nums[r]) {
			return l;
		}
		else if (nums[r] > nums[mid]) {
			return r;
		}
		else{
			return mid;
		}
	}
}

随机数选择，直接选择随机数：

//随机数选择 直接选择一个随机数
int middle_num(vector<int>& nums, const int& l, const int& r) {
    srand(time(0));
	int x = rand();
	return nums[x % (r - l + 1) + l];
}

 4.2.5 完整左右指针法的代码实现

完整快速排序代码如下：
 

//随机数选择 直接选择一个随机数
int middle_num(vector<int>& nums, const int& l, const int& r) {
	srand(time(0));
	int x = rand();
	return nums[x % (r - l + 1) + l];
}

// 这里我们要控制传入的为 0-n-1区间
void quick_sort(vector<int>& nums, const int& l, const int& r) {


	//递归出口
	if (r <= l) {
		return;
	}
	//随机数选择
	int key = middle_num(nums, l, r);
	//因为一开始左右区间没有存储值，因此设置为l-1和r-1 ，表示没有数
	int left = l - 1;
	int right = r + 1;
	//遍历传入的整个区间
	int i = l;

	//升序
	while (i < right) {
		if (nums[i] < key) {
			//寻找到小值，保存在左区间
			//直接++left即可，i++遍历下一个，因为left位置的值一定是小key，交换后可以直接i++

			swap(nums[i++], nums[++left]);
		}
		else if (nums[i] > key) {
			// i不能直接++，right在i的右区间，没有遍历过，不确定和key的关系
			swap(nums[i], nums[--right]);
		}
		else {
			i++;
		}
	}

	//降序
	/*while (i < right) {
		if (nums[i] > key) {
			swap(nums[i++], nums[++left]);
		}
		else if (nums[i] < key) {
			swap(nums[i], nums[--right]);
		}
		else {
			i++;
		}
	}*/

	//l-left 区间
	quick_sort(nums, l, left);
	//right - r 区间继续遍历
	quick_sort(nums, right, r);

}

快速排序的特性总结：

1. 快速排序整体的综合性能比较好，加上适用场景最多，因而得名快速排序
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(logN)
4. 稳定性：不稳定

 4.2.6 非递归左右指针法快速排序

    我们上面写的快速排序是通过递归来实现的，我们也可以通过栈来模拟递归的过程。

    上文的递归是不断地分空间进行递归，因此我们的栈应该存放的是对应空间的左值和右值，通过循环，不断地进行空间分化，具体代码如下：
 

//非递归快排
void quick_stack_sort(vector<int>& nums, const int& ll, const int& rr) {

	if (rr <= ll) {
		return;
	}
	//注意进栈顺序
	stack<int> st;
	st.push(rr);
	st.push(ll);


	while (!st.empty()) {

		//基本一样
		int l = st.top();
		st.pop();
		int r = st.top();
		st.pop();

		int left = l - 1;
		int right = r + 1;

		int key = middle_num(nums, l, r);

		int i = l;


		//升序
		while (i < right) {
			if (nums[i] < key) {
				swap(nums[i++], nums[++left]);
			}
			else if (nums[i] > key) {
				swap(nums[i], nums[--right]);
			}
			else {
				i++;
			}
		}

		//降序
	/*	while (i < right) {
			if (nums[i] > key) {
				swap(nums[i++], nums[++left]);
			}
			else if (nums[i] < key) {
				swap(nums[i], nums[--right]);
			}
			else {
				i++;
			}
		}*/

		//注意进栈顺序
		if (right < r) {
			st.push(r);
			st.push(right);
		}

		if (l < left) {
			st.push(left);
			st.push(l);
		}
	}
}

五 归并排序

   归并排序是建立在归并操作上的一种排序算法,采用了分治法中一个非常典型的应用。先从待排序的序列中分出多个子序列，使每个子序列有序，然后，将已有序的子序列合并，得到整体有序的序列。故实现归并排序的基本步骤即为：先分解，再归并。将两个有序表合并成一个有序表的操作，称为二路归并。

5.1 递归实现

  归并排序的思路如下：

1. 需要一个拷贝数组
2. 对数组进行分化，分成两个区间，一直分化到最小，即左右只有两个数字
3. 排序，将原有数组的两个区间，将左右区间按顺序写入新数组
4. 将新数组的内容拷贝入原数组
5. 重复2，3，4

//归并排序
// 拷贝数组
vector<int> tmp;
void merge_sort(vector<int>& nums, const int &l, const int &r) {

	//递归出口
	if (l >= r) {
		return;
	}

	int mid = (l + r) >> 1;
	//不断进行分化，直到不能分
	merge_sort(nums, l, mid);
	merge_sort(nums, mid + 1, r);

	//往拷贝数组写入
	int cur1 = l, cur2 = mid + 1, i = 0;
	//升序
	while (cur1 <= mid && cur2 <= r) {
		tmp[i++] = nums[cur1] < nums[cur2] ? nums[cur1++] : nums[cur2++];
	}

	//降序
	/*while (cur1 <= mid && cur2 <= r) {
		tmp[i++] = nums[cur1] > nums[cur2] ? nums[cur1++] : nums[cur2++];
	}*/

	//注意这里，假设我们的左右任一数组走完了，都必须退出上面的循环，可能有个数组没有排完
	// 下面的循环是为了 避免左右数组还有数字，因此继续遍历
	while (cur1 <= mid){
		tmp[i++] = nums[cur1++];
	}

	while (cur2 <= r) {
		tmp[i++] = nums[cur2++];
	}

	//按照下标顺序写入原数组
	for (int j = l; j <= r; j++) {
		nums[j] = tmp[j - l];
	}

}

int main() {

	vector<int> b{ 34,66,2,5,95,4,46,27 };
	tmp.resize(b.size());
	merge_sort(b, 0, b.size() - 1); //cout => 2 4 5 27 34 46 66 95

	for (auto& x : b) {
		cout << x << " ";
	}
	cout << endl;
	return 0;

}

 归并排序的特性总结：

1. 归并的缺点在于空间损耗较大，而实际中它解决的更多是在磁盘中的外排序问题。
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(N)
4. 稳定性：稳定

5.2 非递归实现

  上文我们提到，归并排序是一个不断分化再组合的过程，而我们的递归算法是对整个数组进行不断分化，到了只有两个数字的情况，停止递归，那么我们的非递归归并就可以从两个数字的情况开始，逐步合并，一直到合并数组完毕。

  算法思路如下：

1. 创建拷贝函数，设置一个gap，为一组大小，刚开始为1
2. 根据gap分化数组
3. 两两一组合并
4. 再次分组，这次分为两个数字一组，即gap*=2
5. 重复2，3，4 直到一组内包含的数字，超过素组大小的一半，即gap>n/2 时，但我们也可以直接gap<n 

   从思路中我们不难理解，非递归归并的关键就是gap变量，当我们合并两个区间时，我们两个区间的大小分别为(假设区间从0位置开始，并且gap为1）：

int begin1 = i;
int end1 = begin1 + gap - 1;

int begin2 = end1 + 1;
int end2 = begin2 + gap - 1;

   这个可以自己设想理解一下，但我们还发现了一个问题，假设数组是个奇数，当数组分组到末尾的时候，这几个变量会不会越界呢？

  这要结合我们的分组循环来看，在我们的程序中，是这样循环的：

	// i+= （gap*2）是为了分组
   for (int i = 0; i < n; i += (gap * 2)) {

		int begin1 = i;
		int end1 = begin1 + gap - 1;

		int begin2 = end1 + 1;
		int end2 = begin2 + gap - 1;
     }

  首先，begin1肯定是不会越界的，end1 也是不会越界的，但是begin2 和end2 我们不确定，因为我们需要判断。

	for (int i = 0; i < n; i += (gap * 2)) {
		int begin1 = i;
		int end1 = begin1 + gap - 1;

		int begin2 = end1 + 1;
		int end2 = begin2 + gap - 1;

		if (begin2 >= n) {
			break;
		}

		if (end2 >= n) {
			end2 = n - 1;
		}
  }

完整代码如下：
 

//非递归归并排序
void merge_sort_no(vector<int>& nums, const int& l, const int& r) {

	size_t n = nums.size();
	//设置分化数组大小
	int gap = 1;

	vector<int> tmp;
	tmp.resize(nums.size());

	//外部大循环，控制gap变量
	while (gap < n) {
		//根据gap变量控制分化
		for (int i = 0; i < n; i += (gap * 2)) {
			int begin1 = i;
			int end1 = begin1 + gap - 1;

			int begin2 = end1 + 1;
			int end2 = begin2 + gap - 1;

			if (begin2 >= n) {
				break;
			}

			if (end2 >= n) {
				end2 = n - 1;
			}

			int j = 0;
			//分化完毕，控制排序的循环
			//升序
			while (begin1 <= end1 && begin2 <= end2) {
				tmp[j++] = nums[begin1] < nums[begin2] ? nums[begin1++] : nums[begin2++];
			}
			while (begin1 <= end1) {
				tmp[j++] = nums[begin1++];
			}
			while (begin2 <= end2) {
				tmp[j++] = nums[begin2++];
			}
			//控制合并的循环
			for (int x = i; x <= end2; x++) {
				nums[x] = tmp[x - i];
			}

		}
		gap *= 2;
	}
}

六 基数排序

  以下三个排序皆为非比较排序。

  基数排序一般用来排序整数，其基本思想是将整数按位数切割成不同的数字，然后按每个位数分别比较。具体来说，基数排序将整数拆分成个位、十位、百位等，然后按照每一位进行排序。例如，首先按照个位进行排序，然后是十位，接着是百位，以此类推，直到最高位。

  

 具体思路如下：

1. 找到数组的最大值，通过最大值的位数确定循环
2. 创建一个数组队列，内含十个队列
3. 比较个位位置的大小，依次入队列
4. 依次出队列，返回原数组，更改比较位置
5. 重复3，4

完整代码如下：
 

#include <queue>
#include<algorithm>
void radix_sort(vector<int>& arr) {

	int maxDigit = *std::max_element(arr.begin(), arr.end());
	int exp = 1;

	std::queue<int> q[10]; // 创建10个队列，每个队列对应一个数位

	//通过最大数的位数进行循环，有几位循环几次
	while (maxDigit / exp > 0) {
		//入队列
		for (int i = 0; i < arr.size(); i++) {
			int digit = (arr[i] / exp) % 10;
			q[digit].push(arr[i]);
		}

		int index = 0;
		for (int i = 0; i < 10; i++) {
			while (!q[i].empty()) {
				arr[index++] = q[i].front();
				q[i].pop();
			}
		}

		exp *= 10;//*10 代表要比较下一位上的数字了
	}
	//注意，因为个位数字只有十个，当我们要比较大于10的数字时，
	//小于10的位置只会存储在0这个队列里，也就是说，当我们比较下一位的时候
	//也在对上一位进行整合排序
}

基数排序总结：
优点

1. 基数排序的时间复杂度为O(nlog(r)m)，其中n是元素数量，r是基数，m是最大数位的位数‌，这在大量数据时表现十分出色。
2. ‌稳定性‌：基数排序是一种稳定的排序算法，能够保持相等元素的相对顺序不变‌。

基数排序的局限性：

1. ‌基数选择‌：基数排序的效率依赖于基数的选择。通常基数选择10（十进制），但这并不是最优选择。选择不同的基数可能会影响排序效率‌2。
2. ‌负数处理‌：基数排序无法直接用于负数，需要将所有数转换为非负数进行排序，这增加了处理的复杂性‌。
3. ‌适用范围较小：基数排序不仅适用于整数排序，还可以用于字符串和特定格式的浮点数排序‌，但依旧效率较小

七 桶排序

   桶排序是一个借助了快速排序的排序，也是基数排序的一种优化，‌桶排序的核心思想就是将要排序的数据分到几个有序的桶里，每个桶里的数据再单独进行排序。桶排序完之后，再把每个桶里的数据按照顺序依次取出，组成的序列就是有序的了。

   基数排序是按照位数划分区间的，但是桶排序需要我们自己操控，这就避免了基数排序所用范围小的问题。

    比如说当我们排序整数的时候，我们可以设置 0-10 为一个区间 11-20为一个区间 ，这一个个区间我们就叫做桶，当我们排序小数时，又可以自己设定空间大小。

     但桶排序肯定不能像基数排序一样，借助整数的特性对每个队列排序，在桶排序中，因为排序的内容不同，我们需要不同的排序函数，在这里，我们可以借用库的排序函数，以此来对每个桶的范围进行排序。

  每个桶的思路和范围为（假设数组存放整数）：
 

//计算每个桶的范围和数量 
	///范围 size = (max-min)/n+1 
	// 数量 cnt = (max-min)/size+1;

	size_t size = (maxnum - minnum) / nums.size() + 1;

	size_t cnt = (maxnum - minnum) / size + 1;

   整体思路如下:

1. 根据数组特征，选择合适的处理函数，
2. 创建桶，同时对每个桶的大小，范围，进行最佳选择
3. 遍历数组，插入桶
4. 对每个桶进行排序
5. 将桶中数字插入原数组

得出代码如下：
  

//桶排序
#include<algorithm>
void bucket_sort(vector<int> &nums) {

	//直接当整数写了
	// max_element函数是C++标准库中的算法函数，它可以用于数组中的最大值。
    //整数直接求大小值便可取得应该设定的范围
	auto maxnum = *std::max_element(nums.begin(), nums.end());
	auto minnum = *std::min_element(nums.begin(), nums.end());

	//计算每个桶的范围和数量 
	///范围 size = (max-min)/n+1 
	// 数量 cnt = (max-min)/size+1;

	size_t size = (maxnum - minnum) / nums.size() + 1;

	size_t cnt = (maxnum - minnum) / size + 1;

	//创建容器
	vector<vector<int>> buckets(cnt);

	for (int j = 0; j < nums.size(); j++) {
		for (int i = 0; i < cnt; i++) {
			//假设数字小于一个某一个桶的最大值，入桶
			if (nums[j] < (i + 1) * size) {
				buckets[i].push_back(nums[j]);
				break;
			}
		}
	}

	//借助快速排序，进行排序
	for (auto& bucket : buckets) {
		//升序
		sort(bucket.begin(), bucket.end(), less<int>());
	}

	//把所有数据返回原数组
	nums.clear();
	for (auto& bucket : buckets) {
		for (auto& x : bucket) {
			nums.push_back(x);
		}
	}
}

桶排序总结：
 

1. ‌适用场景‌：桶排序适用于数据分布均匀的情况，当数据可以均匀分配到各个桶中时，桶排序的效率非常高。它特别适合于数据范围较大但分布均匀的场景‌。

2. ‌时间复杂度‌：在最佳情况下，桶排序的时间复杂度为O(n)，即线性时间复杂度。这是因为当数据均匀分布时，每个桶内的数据量相对较少，排序效率高。但在最差情况下，即所有数据都被分配到同一个桶中，时间复杂度退化为O(n^2)‌。

3. ‌空间复杂度‌：桶排序的空间复杂度较高，因为需要额外的空间来存储桶和桶中的数据。每个桶需要足够大的空间来存储分配给它的数据‌。

4. ‌稳定性‌：桶排序是稳定的排序算法，因为相同键值的元素在排序后会保持它们原有的顺序‌。

5. ‌实现方式‌：桶排序的实现方式灵活，可以选择不同的排序算法对每个桶内的数据进行排序，例如快速排序、归并排序等。此外，桶排序还可以递归地应用自身对桶内的数据进行进一步排序‌。

八 计数排序

   计数排序的作用是，按照大小顺序排列每个数据，并保留每个数据重复出现的次数。它又称为鸽巢原理，是对哈希直接定址法的变形应用。实现它的基本步骤为：1. 统计相同元素出现次数；2. 根据统计的结果将序列回收到原来的序列中。

 思路如下：
 

1. 寻找数组最大值最小值max和min，确定数组大小n
2. 创建排序数组，把数组中的每个数字-min，通过下标映射入排序数组
3. 将0-n之间的数字，通过v[i]控制，存入原数组

代码如下:

//计数排序

void count_sort(vector<int>& nums) {
	int max = *std::max_element(nums.begin(), nums.end());
	int min = *std::min_element(nums.begin(), nums.end());

	//需要开辟的空间
	int n = (max - min) + 1;
	vector<int> v(n);

	for (auto& x : nums) {
		v[x-min]++;
	}

	nums.clear();
	//输入到原来的数组
	// 升序
	for (int i = 0; i < n; i++) {
		while (v[i]--) {
			nums.push_back(i + min);
		}
	}
	//降序
	/*for (int i = n - 1; i>=0; i--) {
		while (v[i]--) {
			nums.push_back(i + min);
		}
	}*/
}

计数排序的特性总结：

1. 适合范围集中且范围不大的整型数组，不适合范围分散或非整型（字符串、浮点数等）的数组；
2. 时间复杂度：o(N+range)；
3. 空间复杂度：o(range)；
4. 稳定性：稳定。

 九 各大算法总结