2021-11-08_大数据系统

基于C++标准容器Vector实现的十大经典排序方法

简介
代码
输出

简介

其他博客中关于十大排序算法的方法以及非常全面，我这里就不再赘述。目前其他博客中大多是利用c语法的数组类型来实现排序的操作，有些代码仍旧会出现一些边界问题。这里总结的代码使用C++17标准，利用vector标准容器来实现十大算法。由于vector自身复制和分配仍旧需要一定开销，因此部分理论上能达到O(nlogn)的算法在使用辅助容器排序时将产生额外的开销，如归并排序。原地算法的效果就比使用了辅助容器的算法效果好很多。

代码

#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
class Solution {
public:
	//排序方法
	static void selectSort(vector& nums);	//选择排序
	static void insertSort(vector& nums);	//插入排序
	static void bubbleSort(vector& nums);	//冒泡排序
	static void shellSort(vector& nums);	//希尔排序
	static void mergeSort(vector& nums);	//归并排序
	static void heapSort(vector& nums);	//堆排序
	static void quickSort(vector& nums);	//快速排序
	static void countingSort(vector& nums);	//计数排序
	static void bucketSort(vector& nums);	//桶排序
	static void radixSort(vector& nums);	//基数排序
	//辅助方法
	static void merge(vector& nums, int left, int mid, int right);
	static void mergeRecursion(vector& nums, int left, int right);
	static void mergeIteration(vector& nums);
	static void heapAdjust(vector& nums, int parent, int len);
	static void quickRecursion(vector& nums, int left, int right);
	
};
void Solution::selectSort(vector& nums) {
	//选择排序
	int len = nums.size();
	for (int i = 0; i < len - 1; ++i) {
		int minIndex = i;
		for (int j = i + 1; j < len; ++j) {
			if (nums[j] < nums[minIndex])
				minIndex = j;
		}
		swap(nums[i], nums[minIndex]);
	}
}
void Solution::insertSort(vector& nums) {
	//插入排序
	int len = nums.size();
	for (int i = 1; i < len; ++i) {
		int temp = nums[i], j = i - 1;
		while (j >= 0 && nums[j] > temp) {
			nums[j + 1] = nums[j];
			j--;
		}
		nums[j + 1] = temp;
	}
}
void Solution::bubbleSort(vector& nums) {
	//冒泡排序
	int len = nums.size();
	for (int i = len - 1; i > 0; --i) {
		for (int j = 0; j < i; ++j) {
			if (nums[j] > nums[j + 1])
				swap(nums[j], nums[j + 1]);
		}
	}
}

void Solution::shellSort(vector& nums) {
	//希尔排序
	int len = nums.size();
	auto insert = [&len](vector& nums, int interval, int i) {
		int temp = nums[i];
		int k = i - interval;
		while (k >= 0 && temp < nums[k]) {
			nums[k + interval] = nums[k];
			k -= interval;
		}
		nums[k + interval] = temp;
	};
	for(int interval = len / 2; interval > 0; interval /= 2){
		for (int i = interval; i < len; ++i) {
			//这里指的是从第2个interval到数组最后都要与前面的分组进行比较并执行插入。
			insert(nums, interval, i);
		}
	}
}

void Solution::mergeSort(vector& nums) {
	//归并排序
	Solution::mergeRecursion(nums, 0, nums.size() - 1); //递归法
	//Solution::mergeIteration(nums); //递归法
}

void Solution::mergeIteration(vector& nums) {
	//归并排序，迭代法
	int len = nums.size();
	for (int interval = 1; interval < len; interval <<= 1) {
		int left = 0;
		int mid = left + interval - 1;
		int right = mid + interval;
		while (right < len) {
			Solution::merge(nums, left, mid, right);
			left = right + 1;
			mid = left + interval - 1;
			right = mid + interval;
		}
		// 合并遗留的数组
		if (left < len && mid < len) {
			Solution::merge(nums, left, mid, len - 1);
		}
	}
}

void Solution::mergeRecursion(vector& nums, int left, int right) {
	//归并排序，递归法
	if (left >= right)
		return;
	int mid = left + (right - left) / 2;
	Solution::mergeRecursion(nums, left, mid);
	Solution::mergeRecursion(nums, mid+1, right);
	Solution::merge(nums, left, mid, right);
}

void Solution::merge(vector& nums, int left, int mid, int right) {
	//归并排序融合
	if (left >= right)
		return;
	vector helper;
	helper.assign(nums.begin() + mid + 1, nums.begin() + right + 1);
	int ln = mid - left + 1;
	int rn = right - mid;
	int k = right, i = mid, j = rn - 1;
	while (i >= left && j >= 0) {
		nums[k--] = nums[i] > helper[j] ? nums[i--] : helper[j--];
	}
	while (i >= left)
		nums[k--] = nums[i--];
	while (j >= 0)
		nums[k--] = helper[j--];
}

void Solution::heapSort(vector& nums) {
	//堆排序
	//首先构造大根堆
	int len = nums.size();
	for (int i = len / 2 - 1; i >= 0; --i)
		Solution::heapAdjust(nums, i, len);
	for (int k = len - 1; k > 0; --k) {
		//构造好大根堆后，将大根堆顶与末尾节点swap，修正len，同时以新的堆顶开始进行新一轮的下沉操作
		swap(nums[0], nums[k]);
		Solution::heapAdjust(nums, 0, --len);
	}
}
void Solution::heapAdjust(vector& nums, int parent, int len) {
	//堆调整，其目的是使得当前较小的父节点下沉到子节点，优先下沉到右子节点
	int leftChild = 2 * parent + 1;
	int rightChild = 2 * parent + 2;
	int largerOne = parent;
	if (leftChild < len && nums[largerOne] < nums[leftChild])
		largerOne = leftChild;
	if (rightChild < len && nums[largerOne] < nums[rightChild])
		largerOne = rightChild;
	if (largerOne != parent) {
		//此时发现父节点相比于子节点值更小，则进行下沉操作
		//即交换父子节点，同时对交换后节点进行递归
		swap(nums[parent], nums[largerOne]);
		Solution::heapAdjust(nums, largerOne, len);
	}

}

void Solution::quickSort(vector& nums) {
	//快速排序
	quickRecursion(nums, 0, nums.size() - 1);
}

void Solution::quickRecursion(vector& nums, int left, int right) {
	//快速排序递归形式
	if (left >= right)
		return;
	int pivot = nums[left];
	int i = left, j = right;
	while (i < j) {
		//先从右向左寻找一个小于pivot的值，将其赋值给i所在位置
		while (i < j && nums[j] >= pivot)
			j--;
		if (i < j)
			nums[i] = nums[j];
		//赋值后，j所在位置空闲出来了，那么再从左向右寻找一个大于pivot的值，将其赋值给j所在位置
		while (i < j && nums[i] <= pivot)
			i++;
		if (i < j)
			nums[j] = nums[i];
	}
	//在相遇时，将pivot放置在相遇位置
	nums[i] = pivot;
	quickRecursion(nums, left, i - 1);
	quickRecursion(nums, i + 1, right);
}

void Solution::countingSort(vector& nums) {
	//计数排序
	auto minmax = minmax_element(nums.begin(), nums.end());
	int maxVal = *minmax.second;
	int minVal = *minmax.first;
	vector coutingArr(maxVal - minVal + 1);
	for (auto& num : nums)
		++coutingArr[num - minVal];
	size_t i = 0, j = 0;
	while (i < nums.size()) {
		while (coutingArr[j] > 0) {
			nums[i++] = j + minVal;
			--coutingArr[j];
		}
		j++;
	}
}

void Solution::bucketSort(vector& nums) {
	//桶排序
	auto minmax = minmax_element(nums.begin(), nums.end());
	int bucketNum = 10;
	if(*minmax.second - *minmax.first < 10)
		bucketNum = *minmax.second - *minmax.first + 1;
	int interval = (*minmax.second - *minmax.first + 1) / bucketNum;
	vector> buckets(bucketNum);
	for (auto& num : nums) {
		int bucket = (num - *minmax.first) / interval;
		bucket = bucket > bucketNum - 1 ? bucketNum - 1 : bucket;
		buckets[bucket].emplace_back(num);
	}
	vector res;
	for (auto& bucket:buckets)
	{
		Solution::quickSort(bucket);
		res.insert(res.end(), bucket.begin(), bucket.end());
	}
	nums = res;
}

void Solution::radixSort(vector& nums) {
	//基数排序
	auto minmax = minmax_element(nums.begin(), nums.end());
	int minNum = *minmax.first;
	for (auto& num : nums)
		num = num - minNum;
	int maxNum = *minmax.second;
	int digitNum = 1;
	while (maxNum) {
		digitNum *= 10;
		maxNum /= 10;
	}
	vector temps = nums;
	for (int digit = 1; digit < digitNum; digit *= 10) {
		vector> buckets(10);
		for (auto& num : temps) {
			buckets[(num / digit) % 10].emplace_back(num);
		}
		temps.clear();
		for (auto& bucket : buckets)
			temps.insert(temps.end(), bucket.begin(), bucket.end());
	}
	for (auto& num : temps)
		num += minNum;
	nums = temps;
}

void sortPrint(vector nums, function& )> sortMethod, string_view name) {
	auto start = chrono::steady_clock::now();
	sortMethod(nums);
	auto end = chrono::steady_clock::now();
	auto diff = end - start;
	cout << "Sort method: " << name <(diff).count() << "ms" << endl;
	
}

int main() {
	vector input{-1, 2, 1, 9, 8, 7, 99, 66, 333, 128, 17, 1, 4, 0, -6, -12, -88, 4, 32, 99, 111, 72, 67, 89, 111, 34, 33, -15, 164, -72 };
	sortPrint(input, Solution::selectSort, "selectSort");
	sortPrint(input, Solution::insertSort, "insertSort");
	sortPrint(input, Solution::bubbleSort, "bubbleSort");
	sortPrint(input, Solution::shellSort, "shellSort");
	sortPrint(input, Solution::mergeSort, "mergeSort");
	sortPrint(input, Solution::heapSort, "heapSort");
	sortPrint(input, Solution::quickSort, "quickSort");
	sortPrint(input, Solution::countingSort, "countingSort");
	sortPrint(input, Solution::bucketSort, "bucketSort");
	sortPrint(input, Solution::radixSort, "radixSort");
	return 0;
}

输出

Sort method: selectSort
-88 -72 -15 -12 -6 -1 0 1 1 2 4 4 7 8 9 17 32 33 34 66 67 72 89 99 99 111 111 128 164 333
                Execution time: 0.0352 ms
Sort method: insertSort
-88 -72 -15 -12 -6 -1 0 1 1 2 4 4 7 8 9 17 32 33 34 66 67 72 89 99 99 111 111 128 164 333
                Execution time: 0.0312 ms
Sort method: bubbleSort
-88 -72 -15 -12 -6 -1 0 1 1 2 4 4 7 8 9 17 32 33 34 66 67 72 89 99 99 111 111 128 164 333
                Execution time: 0.0436 ms
Sort method: shellSort
-88 -72 -15 -12 -6 -1 0 1 1 2 4 4 7 8 9 17 32 33 34 66 67 72 89 99 99 111 111 128 164 333
                Execution time: 0.0125 ms
Sort method: mergeSort
-88 -72 -15 -12 -6 -1 0 1 1 2 4 4 7 8 9 17 32 33 34 66 67 72 89 99 99 111 111 128 164 333
                Execution time: 0.1807 ms
Sort method: heapSort
-88 -72 -15 -12 -6 -1 0 1 1 2 4 4 7 8 9 17 32 33 34 66 67 72 89 99 99 111 111 128 164 333
                Execution time: 0.0675 ms
Sort method: quickSort
-88 -72 -15 -12 -6 -1 0 1 1 2 4 4 7 8 9 17 32 33 34 66 67 72 89 99 99 111 111 128 164 333
                Execution time: 0.0265 ms
Sort method: countingSort
-88 -72 -15 -12 -6 -1 0 1 1 2 4 4 7 8 9 17 32 33 34 66 67 72 89 99 99 111 111 128 164 333
                Execution time: 0.031 ms
Sort method: bucketSort
-88 -72 -15 -12 -6 -1 0 1 1 2 4 4 7 8 9 17 32 33 34 66 67 72 89 99 99 111 111 128 164 333
                Execution time: 0.1153 ms
Sort method: radixSort
-88 -72 -15 -12 -6 -1 0 1 1 2 4 4 7 8 9 17 32 33 34 66 67 72 89 99 99 111 111 128 164 333
                Execution time: 0.2315 ms

少量数据可能效果不明显，整了个包含50000个数值的大数据，因为数据太长只显示排序方法和执行时长。

Sort method: selectSort
                Execution time: 60383.1 ms
Sort method: insertSort
                Execution time: 45004.1 ms
Sort method: bubbleSort
                Execution time: 168150 ms
Sort method: shellSort
                Execution time: 197.473 ms
Sort method: mergeSort
                Execution time: 407.789 ms
Sort method: heapSort
                Execution time: 196.435 ms
Sort method: quickSort
                Execution time: 56.1361 ms
Sort method: countingSort
                Execution time: 10.1593 ms
Sort method: bucketSort
                Execution time: 64.6273 ms
Sort method: radixSort
                Execution time: 87.2654 ms

2021-11-08

大数据系统相关栏目本月热门文章