# Top Ten Sorting Algorithm

**Repository Path**: zhang---xuan/top-ten-sorting-algorithm

## Basic Information

- **Project Name**: Top Ten Sorting Algorithm
- **Description**: 十大排序算法的模板实现 以及运行时间测试
- **Primary Language**: C++
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2024-03-13
- **Last Updated**: 2024-03-13

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# 十大排序算法



1. 冒泡排序（Bubble Sort）：比较相邻元素，将较大的元素往后移动，每次遍历将最大的元素移到末尾。时间复杂度为O(n^2)。

   ```c++
   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)。

   ```c++
   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)，在有序序列中表现良好。

   ```c++
   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)。

   ```c++
   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)，在大多数情况下表现良好。

   ```c++
   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)。

   ```c++
   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类型

测试用Int类

```c++
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;
}
```