排序算法

#pragma once
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

//冒泡
void bubbleSort(vector<int>& arr)
{
	int n = arr.size();
	if (n <= 1) return;
	int temp;
	for (int i = 0; i < n - 1; ++i)
	{
		for (int j = 0; j < n - 1 - i; ++j)
		{ 
			if (arr[j] > arr[j + 1])
			{
				temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
			}
		}
	}
}

//快排
void quickSort(vector<int> &q, int l, int r) {
	if (l >= r)
		return;
	int i = l - 1, j = r + 1, x = q[l + rand() % (r - l + 1)];
	while (i < j) {
		do j--; while (q[j] > x);
		do i++; while (q[i] < x);
		if (i < j)
			swap(q[i], q[j]);
		else {
			quickSort(q, l, j);
			quickSort(q, j + 1, r);
		}
	}
}


//选择
void selectionSort(vector<int> &q) {
	for (int i = 0; i < q.size(); i++) {
		for (int j = i + 1; j < q.size(); j++) {
			if (q[i] > q[j])
				swap(q[i], q[j]);
		}
	}
}

//归并
void mergeSort(vector<int> &q, int l, int r) {
	if (l >= r)
		return;
	int mid = l + r >> 1;
	mergeSort(q, l, mid);
	mergeSort(q, mid + 1, r);
	static vector<int> w;
	w.clear();
	int i = l, j = mid + 1;
	while (i <= mid && j <= r) {
		if (q[i] > q[j])
			w.push_back(q[j++]);
		else
			w.push_back(q[i++]);
	}
	while (i <= mid)
		w.push_back(q[i++]);
	while (j <= mid)
		w.push_back(q[j++]);
	for (int i : w)
		q[l++] = i;
}

//希尔
void shellSort(vector<int> &q) {
	int gap = q.size() / 2;
	while (gap) {
		for (int i = gap; i < q.size(); i += gap) {
			int t = q[i], j;
			for (j = i - gap; j >= 0; j -= gap) {
				if (q[j] > t)
					q[j + gap] = q[j];
				else
					break;
			}
			q[j + gap] = t;
		}
		gap /= 2;
	}
}


//桶排
void push_down(vector<int>& heap, int size, int u) {
	int t = u, left = u * 2, right = u * 2 + 1;
	if (left <= size && heap[left] > heap[t])
		t = left;
	if (right <= size && heap[right] > heap[t])
		t = right;
	if (u != t) {
		swap(heap[u], heap[t]);
		push_down(heap, size, t);
	}
}

void push_up(vector<int>& heap, int u) {
	while (u / 2 && heap[u / 2] < heap[u]) {
		swap(heap[u / 2], heap[u]);
		u /= 2;
	}
}

void heapSort(vector<int> &q, int n) {
	int size = n;
	for (int i = 1; i <= n; i++)
		push_up(q, i);
	for (int i = 1; i <= n; i++) {
		swap(q[1], q[size]);
		size--;
		push_down(q, size, 1);
	}
}


//计数
void countingSort(vector<int> &q, int n) {
	vector<int> cnt(101, 0);
	for (int i = 0; i < n; i++)
		cnt[q[i]]++;
	for (int i = 0, k = 0; i <= 100; i++) {
		while (cnt[i]) {
			q[k++] = i;
			cnt[i]--;
		}
	}
}



//基数
//这里设所有待排序的数都不超过三位数，也就是说不超过999。

int get(int x, int i) {
	while (i--)
		x /= 10;
	return x % 10;
}

void radixSort(vector<int> &q, int n) {
	vector<vector<int>> cnt(10);
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 10; j++)
			cnt[j].clear();
		for (int j = 0; j < n; j++)
			cnt[get(q[j], i)].push_back(q[j]);
		for (int j = 0, k = 0; j < 10; j++) {
			for (int x : cnt[j])
				q[k++] = x;
		}
	}
}