分类

复杂度

排序稳定性定义：
假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，A1=A2，且A1在A2之前，而在排序后的序列中，A1仍在A2之前，则称这种排序算法是稳定的；否则称为不稳定的。

原理

讲的很清楚的up主

小灰的讲解让你完全拿捏10大排序算法

C++代码实现

#include <iostream>
#include <vector>
#include <map>
#include <string>

template<class T>
void swap(T &a, T &b) { T tmp = a;a = b;b = tmp; }
template<class T>
void print(std::vector<T> &v) { for(auto x : v) std::cout << x << " "; std::cout << std::endl; }

// 1.冒泡排序 
// 算法描述：比较相邻的元素，如果第一个比第二个大，就交换它们两个；
// 对每一对相邻元素作同样的工作，从第一对到最后一对，这样在最后的元素应该会是最大的数
// 针对所有的元素重复以上的步骤，除了最后一个；
// 重复步骤 1~3，直到排序完成 
void BubbleSort(std::vector<int> &v, int n) {
	bool flag;
	for(int i = 0; i < n - 1; ++i) {
		flag = true;
		for(int j = 1; j < n - i; ++j) {
			if(v[j] < v[j-1]) {
				swap(v[j], v[j-1]);
				flag = false;
			}
		}
		if(flag) break;
	}
	print(v);
}

// 2.插入排序 
// 算法描述：把区间分为左边已排序和右边未排序，初始已排序区间只有一个元素，就是数组第一个
// 每轮针对未排序区间的第一个元素，在已排序区间里找到合适的位置插入并保证数据一直有序
void InsertSort(std::vector<int> &v, int n) {
	for(int i = 1; i < n; ++i) {
		for(int j = i; j > 0 && v[j] < v[j-1]; --j) {
			swap(v[j], v[j-1]);
		}
	}
}

// 3.选择排序
// 算法描述：把区间分为左边已排序和右边未排序， 初始已排序区间没有元素 
// 每轮从未排序区间中找到最小值，然后置换到已排序区间的末尾 
void SelectSort(std::vector<int> &v, int n) {
	int Min_pos;
	for(int i = 0; i < n - 1; ++i) {
		Min_pos = i;
		for(int j = i; j < n; ++j) {
			if(v[Min_pos] > v[j]) Min_pos = j;
		}
		swap(v[i], v[Min_pos]);
	}
	print(v);
}

// 4. 堆排序 O(nlogn)
// 算法描述：利用堆这种数据结构所涉设计的一种排序算法。堆积是一个近似完全二叉树的结构
// 并同时满足堆积的性质：即子节点的键值或索引总是小于（或者大于）它的父节点。
// 堆排序可以用到上一次排序的结果，所以不像其他一般的排序方法一样，每次都要进行 n-1 此的比较 
void Heapify(std::vector<int> &v, int n, int i) { // 维护堆的性质 
	while(1) { // 循环代替递归，调整节点i位置 
		int Max_pos = i; // 判断节点 i 是否满足大顶堆的性质 
		if(i * 2 + 1 < n && v[Max_pos] < v[i * 2 + 1]) Max_pos = i * 2 + 1;
		if(i * 2 + 2 < n && v[Max_pos] < v[i * 2 + 2]) Max_pos = i * 2 + 2;
		if(Max_pos == i) break; // 节点 i 满足性质 
		swap(v[i], v[Max_pos]); // 将Max值上浮，i节点下沉，大顶堆 
		i = Max_pos; // 继续调整 
	}
}
void HeapSort(std::vector<int> &v, int n) {
	// 1. 建堆 复杂度O(n) ，从完全二叉树的末端的父节点开始维护堆的性质
	for(int i = (n - 1) / 2; i >= 0; --i) { 
		Heapify(v, n, i);
	} 
	std::cout << v[0] << std::endl; 
	// 2. 进行堆排序, 将完全二叉树末端的元素与堆顶元素交换，然后删除完全二叉树末端的节点
	// 不断重复上述操作，直至堆中只有一个元素 
	// 排序过程中，就是从数组末端，不断放入当前堆顶的元素
	// 因此使用大顶堆排序出来就是升序 
	while(n > 1) {
		swap(v[0], v[n-1]);
		--n;
		Heapify(v, n, 0); // 对0号节点进行下沉调整，维护小顶堆性质 
	}
	print(v);
}

// 5. 希尔排序  也称递减增量排序  
// 算法描述：通过不断缩小增量进行插入排序，算法的最后一步就是普通的插入排序
// 就是取越来越小的步长进行插入排序，这样在最后步长为 1 的时候，只需要调整很少的几次就可以完成 
// 对插入排序的改进   可以让一个元素可以一次性地朝最终位置前进一大步
void ShellSort(std::vector <int> &v, int n) {
	for(int len = n / 2; len >= 1; len /= 2) {
		for(int i = len; i < n; ++i) {
			for(int j = i; j - len >= 0 && v[j - len] > v[j]; j -= len) {
				swap(v[j - len], v[j]);
			}
		}
	}
	print(v);
} 

// 6. 计数排序  
// 算法描述：先确定数据范围range，然后统计每个数字的个数，然后依次输出即可得到有序序列
// 适用范围：数据范围比较集中且为整数序列
void CountSort(std::vector<int> &v, int n) {
	// 1.计算元素范围 
	int Max = v[0], Min = v[0];
	for(auto x : v) {
		if(x < Min) Min = x;
		if(x > Max) Max = x;
	}
	// 2.统计元素个数 
	int range = Max - Min + 1;
	std::vector <int> c(range, 0); // 统计数组 
	for(auto x : v) c[x - Min]++; // 映射一下 
	// 如果不考虑排序稳定性， 在这就可以直接从小到大按个数输出了 
	
	// 保证其稳定性需要继续操作 
	// 3.求统计数组前缀和，此时的 c[x]-1 就等于元素x在排序完的序列中的最大位置 
	for(int i = 1; i < range; ++i) c[i] += c[i-1];
	// 4.倒序遍历原始数据，从统计数组中找到正确位置并输出
	std::vector <int> tmp_v(v);
	for(int i = n - 1; i >= 0; --i) {
		int x = tmp_v[i] - Min; // 得到映射值 
		v[c[x] - 1] = tmp_v[i]; // 在 c[x]-1 的位置上填上 tmp_v[i] 
		--c[x]; // 下个tmp_v[i]要在第c[x]-1个位置左边填上 
	}
	print(v);
} 


// 7. 桶排序
// 当数列取值范围过大，或者不是整数的时候，就无法用计数排序了 
// 类似于计数排序需要创建统计数组，桶排序需要创建若干个桶 
// 算法描述：分治的思想
template<class T>
void MergeSort(std::vector <T> &v, int l, int r); // 提前声明归并排序类模板 

void BucketSort(std::vector <double> &v, int n) {
	// 1.确定数列的范围 
	double Max = v[0], Min = v[0];
	for(auto x : v) {
		if(x < Min) Min = x;
		if(x > Max) Max = x;
	}
	// 2.初始化桶 
	int bknum = n;	// 一般创建的桶数量等于原始数列的元素数量
	std::vector<std::vector<double> > bk_list(bknum);
	// 除了最后一个桶只包含数列最大值，其余的桶均分最大值和最小值的差值. 按照比例确定
	// 桶的区间范围 = (最大值-最小值) / (桶的数量 - 1) 
	// 3.把元素都放入桶中
	double bk_range = (Max - Min) / (bknum - 1); 
	for(auto x : v) {
		// num = (x-Min) 除以区间跨度 
		int num = (int)((x - Min) / bk_range);
		bk_list[num].emplace_back(x);
	}
	// 4. 对桶内部排序   可以采用归并排序，也可以采用快速排序之类的
	for(int i = 0; i < bknum; ++i) {
		MergeSort(bk_list[i], 0, bk_list[i].size() - 1);
	}
	int j = 0;
	for(auto &x : bk_list) {
		for(auto &d : x) {
			v[j++] = d;
		}
	} 
	print(v);
}

// 8. 基数排序
// 针对手机号，英文单词等复杂元素的排序 
// 算法描述：把排序工作拆分成多个阶段，每一个阶段只根据一个字符进行计数排序，一共排序k轮 (k是元素长度)
// 基数排序相当于通过循环进行了多次桶排序
void RadixSort(std::vector <std::string> &v, int n) {
	int Max = 0;
	for(auto s : v) if(s.size() > Max) Max = s.size();
	std::vector <std::string> tmp_v(n);
	
	// 如果要对序列进行排序，k 应该从个位开始枚举
	for(int k = Max - 1; k >= 0; --k) {
		// 进行计数排序 
		std::vector <int> c(128, 0); // 统计所有字符串的第k位
		for(int i = 0; i < n; ++i) {
			int x = '0'; // 先假设需要补 0 
			if(k < v[i].size()) x = v[i][k]; // 判断一下字符是否有 k 位 
			c[x]++;
		}
		for(int i = 1; i < c.size(); ++i) c[i] += c[i-1];
		// 倒序找到正确位置并输出，保证稳定性
		for(int i = n - 1; i >= 0; --i) {
			int x = '0';
			if(k < v[i].size()) x = v[i][k];
			tmp_v[c[x] - 1] = v[i];
			c[x]--;
		}
		v.swap(tmp_v);
	}
	print(v);
}


// 9.快排 O(nlogn)，最坏 O(n^2) 
// 算法描述: 选定Pivot中心轴，在原来的元素里根据这个枢纽分
// 将小于Pviot的元素放到Pivot的左边, 将大于Pviot的元素放到Pivot的右边
// 递归处理左右子序列 
void QuickSort(std::vector<int> &v, int l, int r) {
	if(l >= r) return;
	int first = l, last = r, pivot = v[l];
	while(first < last) {	 
		while(first < last && v[last] >= pivot) --last;//将小于piv的放到左边
		v[first] = v[last];
		while(first < last && v[first] <= pivot) ++first;//将大于piv的放到右边
		v[last] = v[first];
	}
	v[first] = pivot; // 更新pivot
	QuickSort(v, l, first);
	QuickSort(v, first + 1, r);
}

// 10.归并排序   O(nlogn)  稳定的排序算法，它不是原地排序算法
// 算法描述：将两个游标 i 和 j，分别指向 v[l, mid] 和 v[mid+1, r] 的第一个元素。比较这两个元素
// 如果 v[i]<v[j]，就把 v[i] 放到临时数组 tmp, 并且 i 后移一位，否则将 v[j] 放入 tmp，j后移一位 
template<class T>
void MergeSort(std::vector <T> &v, int l, int r) {
	if(l >= r) return;
	int mid = (l + r) >> 1;
	MergeSort(v, l, mid);	  // 对 [l, mid] 区间排序
	MergeSort(v, mid + 1, r);//  对 [mid+1, r] 区间排序
	// 双指针对把俩个数组合并成一个有序数组 
	T *tmp = new T[r-l+1];	  // 暂时存放合并出的数组 
	int i = l, j = mid + 1, c = 0;
	while(i <= mid && j <= r) {
		if(v[i] < v[j]) tmp[c++] = v[i++];
		else tmp[c++] = v[j++];
	}
	while(i <= mid) tmp[c++] = v[i++];
	while(j <= r) tmp[c++] = v[j++];
	for(int k = 0; k < c; ++k) v[l+k] = tmp[k];
	delete[] tmp;
}


int main() 
{
	std::vector <int> v = {19, 97, 9, 17, 1, 8};
//	BubbleSort(v, v.size());
//	SelectSort(v, v.size());
//	SelectSort(v, v.size());
//	HeapSort(v, v.size());
//	ShellSort(v, v.size());
	CountSort(v, v.size());

	std::vector <double> d = {3.14, 2.66, 15.33, 20.0, 0.33};
	BucketSort(d, d.size());


	std::vector <std::string> v_s = {"121", "321", "12", "544", "312", "4354"};
	// 如果要对序列排序，不要用字符串的，用数字更方便，同时也要对函数进行修改 
	// 这种对字符串排序方式， 不足Max位的字符串，在末尾补 '0' 
	std::vector <std::string> v_ss = {"banana","apple","orange","ape","he"};
	// 正确排序结果：ape apple banana he orange 
	RadixSort(v_ss, v_ss.size());

	// 这俩函数是递归实现的，无法调用print,就放在最后了 
//	QuickSort(v, 0, v.size() - 1);
//	print(v);
//	MergeSort(v, 0, v.size() - 1);
//	print(v);
	return 0;
}