[数据结构与算法]排序算法-C++

1.冒泡排序

#include <iostream>
#include <vector>
using namespace std;

void bubbleSort(vector<int> &data) {
	int n = data.size();
	if (n < 2) {
		return;
	}
	for (int i = n - 1; i > 0; i--) {
		for (int j = 0; j < i; j++) {
			if (data[j] > data[j + 1]) {
				swap(data[j], data[j + 1]);
			}
		}
	}
}

int main() {
	vector<int> data = { 9, 4, 2, 7, 0, 1, 6, 5, 8, 3 };
	bubbleSort(data);

	for (auto &item : data) {
		cout << item << " ";
	}
	system("pause");
	return 0;
}

2.选择排序

#include <iostream>
#include <vector>
using namespace std;

void selectSort(vector<int> &data) {
	int n = data.size();
	if (n < 2) return;

	for (int i = 0; i < n - 1; i++) {
		int minIndex = i;
		for (int j = i + 1; j < n; j++) {
			if (data[j] < data[minIndex]) minIndex = j;
		}
		swap(data[minIndex], data[i]);
	}
}

int main() {
	vector<int> data = { 9, 4, 2, 7, 0, 1, 6, 5, 8, 3 };
	selectSort(data);

	for (auto &item : data) {
		cout << item << " ";
	}
	system("pause");
	return 0;
}

3.插入排序

#include <iostream>
#include <vector>
using namespace std;

void insertSort(vector<int> &data) {
	int n = data.size();
	if (n < 2) return;
	for (int i = 1; i < n; i++) {
		for (int j = i - 1; j >= 0 && data[j] > data[j + 1]; j--) {
			swap(data[j], data[j + 1]);
		}
	}
}

int main() {
	vector<int> data = { 9, 4, 2, 7, 0, 1, 6, 5, 8, 3 };
	insertSort(data);

	for (auto &item : data) {
		cout << item << " ";
	}
	system("pause");
	return 0;
}

4.快速排序

#include <iostream>
#include <vector>
using namespace std;

int partation(vector<int> &data, int left, int right) {
	int key = data[right];
	int less = left - 1;
	int more = right;
	int index = left;
	while (index < more)
	{
		if (data[index] > key) {
			swap(data[index], data[--more]);
		}
		else if (data[index] < key) {
			swap(data[index++], data[++less]);
		}
		else {
			index++;
		}
	}
	swap(data[right], data[index]);
	return index;
}

void quick(vector<int> &data, int left, int right) {
	if (left < right) {
		int s = partation(data, left, right);
		quick(data, left, s - 1);
		quick(data, s + 1, right);
	}
}

void quickSort(vector<int> &data) {
	int n = data.size();
	if (n < 2) return;
	quick(data, 0, n - 1);
}

int main() {
	vector<int> data = { 9, 4, 2, 7, 0, 1, 6, 5, 8, 3 };
	quickSort(data);

	for (auto &item : data) {
		cout << item << " ";
	}
	system("pause");
	return 0;
}

5.归并排序

#include <iostream>
#include <vector>
using namespace std;

void merge(vector<int> &data, int left, int mid, int right) {
	vector<int> tool;
	int p = left;
	int q = mid + 1;
	while (p <= mid && q <= right) {
		if (data[p] <= data[q]) tool.emplace_back(data[p++]);
		else {
			tool.emplace_back(data[q++]);
		}
	}
	while (p <= mid)
	{
		tool.emplace_back(data[p++]);
	}
	while (q <= right) {
		tool.emplace_back(data[q++]);
	}
	for (auto &item : tool) {
		data[left++] = item;
	}
}

void progress(vector<int> &data, int left, int right) {
	if (left >= right) return;

	int mid = left + (right - left) / 2;
	progress(data, left, mid);
	progress(data, mid + 1, right);
	merge(data, left, mid, right);
}

void mergeSort(vector<int> &data) {
	int n = data.size();
	if (n < 2) return;
	progress(data, 0, n - 1);
}

int main() {
	vector<int> data = { 9, 4, 2, 7, 0, 1, 6, 5, 8, 3 };
	mergeSort(data);

	for (auto &item : data) {
		cout << item << " ";
	}
	system("pause");
	return 0;
}

6.堆排序

#include <iostream>
#include <vector>
using namespace std;

void heapInsert(vector<int> &heap, int index) {
	while (heap[(index - 1) / 2] < heap[index]) {
		swap(heap[index], heap[(index - 1) / 2]);
		index = (index - 1) / 2;
	}
}

void heapIfy(vector<int> &heap, int index, int heapSize) {
	int left = 2 * index + 1;
	while (left < heapSize)
	{
		int largest = left + 1 < heapSize && heap[left + 1] > heap[left] ? left + 1 : left;
		largest = heap[largest] > heap[index] ? largest : index;
		if (largest == index) break;
		swap(heap[largest], heap[index]);
		index = largest;
		left = 2 * largest + 1;
	}
}

void heapSort(vector<int> &data) {
	int n = data.size();
	if (n < 2) return;
	for (int i = 0; i < n; i++) {
		heapInsert(data, i);
	}
	swap(data[0], data[--n]);
	while (n > 0) {
		heapIfy(data, 0, n);
		swap(data[0], data[--n]);
	}
}

int main() {
	vector<int> data = { 9, 4, 2, 7, 0, 1, 6, 5, 8, 3 };
	heapSort(data);

	for (auto &item : data) {
		cout << item << " ";
	}
	system("pause");
	return 0;
}

7.希尔排序

#include <iostream>
#include <vector>
using namespace std;

void shellSort(vector<int> &data) {
	int n = data.size();
	for (int gap = n / 2; gap > 0; gap /= 2) {
		for (int i = gap; i < n; i++) {
			int j = i;
			while (j - gap >= 0 && data[j] < data[j - gap]) {
				swap(data[j], data[j - gap]);
				j -= gap;
			}
		}
	}
}

int main() {
	vector<int> data = { 9, 4, 2, 7, 0, 1, 6, 5, 8, 3 };
	shellSort(data);

	for (auto &item : data) {
		cout << item << " ";
	}
	system("pause");
	return 0;
}