十大排序算法

项目地址：https://gitee.com/zhang—xuan/top-ten-sorting-algorithm

1.冒泡排序（Bubble Sort）

比较相邻元素，将较大的元素往后移动，每次遍历将最大的元素移到末尾。时间复杂度为O(n^2)。

template<class _TY>
void Bubble_Sort(_TY* A, int left, int right) {//冒泡排序
	for (int i = left; i <= right; i++) {
		for (int j = left; j < right; j++) {
			if (A[j] > A[j + 1]) {
				std::swap(A[j], A[j + 1]);
			}
		}
	}
}

2.选择排序（Selection Sort）

每次从未排序的部分选择最小（或最大）的元素放到已排序部分的末尾。时间复杂度为O(n^2)。

template<class _TY>
Selection_Sort(_TY*A,int left,int right){
	for(int i=left;i<right;i++){
		for(int j=i+1;j<=right;j++){
			if(A[j]<A[i])swap(A[i],A[j]);
		}
	}
}

3.插入排序（Insertion Sort）

将未排序的元素逐个插入已排序部分的合适位置。时间复杂度为O(n^2)，在有序序列中表现良好。

template<class _TY>
Insert_Sort(_TY*A,int left,int right){
	for(int i=left+1;i<=right;i++){
		int k=i;
		while(A[k]<A[k-1]){
			swap(A[k],A[k-1]);
			k--;
			if(k==left)break;
		}
	}
}

4. 希尔排序（Shell Sort）

插入排序的改进版，通过将数组分成多个子序列进行排序，逐渐缩小子序列的长度，最终实现整体有序。时间复杂度为O(n log n)。

5. 归并排序（Merge Sort）

采用分治法的思想，将数组分成两个子数组，分别进行排序，然后合并两个有序子数组。时间复杂度为O(n log n)。

template<class _TY>
void Merge(_TY* A, int left, int right) {//合并
	int middle = (left + right) / 2;
	int L_Size = middle - left + 1;
	int R_Size = right - middle;
	_TY* L = new _TY[L_Size];
	_TY* R = new _TY[R_Size];
	for (int k = 0; k < L_Size; k++) {
		L[k] = A[left + k];
	}
	for (int k = 0; k < R_Size; k++) {
		R[k] = A[middle + k + 1];
	}
	int i = 0;
	int j = 0;
	for (int k = 0; k < right - left + 1; k++) {
		A[left + k] = [&]()->_TY {
			if (i >= L_Size)return R[j++];
			if (j >= R_Size)return L[i++];
			if (L[i] <= R[j])return L[i++];
			if (L[i] > R[j])return R[j++];
			return _TY{};
			}();
	}
}
template <class _TY>
void Merge_Sort(_TY* A, int left, int right) {//归并排序
	if (left >= right)return;
	Merge_Sort(A, left, (left + right) / 2);
	Merge_Sort(A, (left + right) / 2 + 1, right);
	Merge(A, left, right);
}

6. 快速排序（Quick Sort）：

选择一个基准元素，将比它小的元素放在左边，比它大的元素放在右边，然后对左右两边分别递归地进行快速排序。时间复杂度为O(n log n)，在大多数情况下表现良好。

template<class _TY>
int partition(_TY* A, int left, int right) {//数组划分
	srand(time(NULL));
	int n = rand() % (right - left+1) + left;
	swap(A[n], A[right]);
	int i = left - 1;
	for (int j = left; j < right; j++) {
		if (A[j] < A[right]) {
			swap(A[++i], A[j]);
		}
	}
	swap(A[++i], A[right]);
	return i;
}
template<class _TY>
void Quity_Sort(_TY* A, int left, int right) {//快速排序
	if (left >= right)return;
	int h = partition(A, left, right);
	Quity_Sort(A, left, h - 1);
	Quity_Sort(A, h + 1, right);
}

7. 堆排序（Heap Sort）

将数组构建成一个最大（或最小）堆，然后依次取出堆顶元素并调整堆的结构。时间复杂度为O(n log n)。

template <class_TY>
Heap_Maintenance(_TY*A,int i,int right){
	_TY X(A[i]);
	if(2*i<=right && A[2*i]>X)X=A[2*i];
	if(2*i+1<=right&&A[2*i+1]>X)X=A[2*i+1];
	if(X!=A[i]){
		if(X==A[2*i])swap(A[i],A[2*i]);
		else swap(A[i],A[2*i]);
		Heap_Maintenance(A,i,right);
	}
}
template <class _TY>
Heap_Create(_TY*A,int left,int right){
	int mid=(right+left)/2;
	for(int i=mid;i>=left;i--){
		Heap_Maintenance(A,i,left,right);
	}
}
template<class _TY>
Heap_Sort(_TY*A,int left,int right){
	Heap_Create(A,left,right);
	for(int i=right;i>=left;i--){
		swap(A[right],A[left]);
		right--;
		Heap_Maintenance(A,left,right);
	}
}

8. 计数排序（Counting Sort）

统计小于每个元素的个数，然后根据统计结果进行排序。时间复杂度为O(n+k)，其中k是数据范围。

9. 桶排序（Bucket Sort）

将元素根据大小分配到不同的桶中，再对每个桶进行排序，最后合并所有桶的结果。时间复杂度取决于桶的数量和桶内排序的算法。

10. 基数排序（Radix Sort）

按照元素的位数进行排序，先按个位排序，再按十位排序，以此类推。时间复杂度为O(d*(n+k))，其中d是最大元素的位数，k是基数。

附录：测试用Int类型

class Int {
private:
	int val;
public:
	Int(int x=0) :val(x) {}
	~Int() {}
	Int(Int& p):val(p.val) {}
	Int(Int&&p):val(p.val){}
	Int operator+(Int &p)const {
		return Int(val + p.val);
	}
	Int operator-(Int& p) const{
		return Int(val - p.val);
	}
	Int& operator=(const Int& p){
		if (this != &p) {
			val = p.val;
		}
		return *this;
	}
	Int& operator=(int x) {
		val = x;
		return *this;
	}
	Int& operator+=(const Int& p) {
		val += p.val;
		return *this;
	}
	Int& operator-=(const Int& p) {
		val -= p.val;
		return *this;
	}
	bool operator>(const Int&p)const{
		return val > p.val;
	}
	bool operator<(const Int& p)const {
		return val < p.val;
	}
	bool operator<=(const Int& p)const {
		return !(val > p.val);
	}
	bool operator>=(const Int& p)const {
		return !(val < p.val);
	}
	Int operator*(const Int& p) const{
		return Int(val * p.val);
	}
	Int operator/(const Int& p) const{
		return Int(val / p.val);
	}
	Int& operator++() {
		++val;
		return *this;
	}
	Int operator++(int i) {
		Int S(val);
		val++;
		return S;
	}
	friend ostream& operator<<(ostream& out, const Int& p);
	friend istream& operator>>(istream& in, Int& p);
};
ostream& operator<<(ostream& out, const Int& p) {
	out << p.val;
	return out;
}
istream& operator>>(istream& in, Int& p) {
	in >> p.val;
	return in;
}