【C++】几个常见的简单排序算法

先给结论,随机出10000个0-100000的数字后,各算法的消耗如下(swap_counts表示交换或拷贝次数, compare_counts表示比较次数)

Function swap_counts compare_counts
bubbleSort(冒泡排序) 24952888 49993404
insertSort(直插排序) 24962888 24962883
heapSort(堆排序) 17886448 24100914
quickSort(快速排序) 69039 173996
mergeSort(归并排序) 267232 120493
bucketSort(桶排序) 80640 132267

sort_helper.h

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


enum INIT_MODE
{
	INIT_MODE_RAND = 1,//随机
	INIT_MODE_SORT = 2,//已排序
	INIT_MODE_REVERSE = 3,//逆排序

};
class SortHelper
{
public:
	void InitData();
	SortHelper(int iInitMode, int iInitNum = 50, int iNumMin = 0, int iNumMax = 100, uint32_t iRandSeed = 0):
		m_initmode(iInitMode), m_initnum(iInitNum), m_inummin(iNumMin), m_inummax(iNumMax), m_randseed(iRandSeed)
	{
		InitData();
	};
	void print(std::string name);
public:
	void bubbleSort();
	void insertSort();
	void heapSort();
	void quickSort();
	void mergeSort();
	void bucketSort();


private:
	void swap(int& a, int& b);
	void copy(int& a, const int& val);
	void push(std::vector<int> &a, const int& val);
	void adjust(int loc, int n);
	void QuickSortFunc(std::vector<int> &arr, int low, int high);
	int Partition(std::vector<int> &arr, int low, int high);
	void MergeSortFunc(std::vector<int> &arr, int low, int high);
	void MergeSortArr(std::vector<int> &arr, int low, int mid, int high);

private:
	int m_swapcounts;//交换次数
	int m_compcounts;//比较次数
	std::vector<int> m_arr;//待排序数组
	int m_initmode;
	int m_initnum;
	int m_inummin;
	int m_inummax;
	uint32_t m_randseed;
};

sort_helper.cpp

#include "sort_helper.h"
#include <algorithm>
#include <string>

void SortHelper::InitData()
{
	m_swapcounts = 0;
	m_compcounts = 0;
	m_arr.clear();
	srand(m_randseed);
	for (int i = 0; i < m_initnum; ++i)
	{
		int val = rand() % (m_inummax - m_inummin) + m_inummin;
		m_arr.push_back(val);
	}
	switch (m_initmode)
	{
	case INIT_MODE_SORT: sort(m_arr.begin(), m_arr.end()); break;
	case INIT_MODE_REVERSE: sort(m_arr.begin(), m_arr.end()); reverse(m_arr.begin(), m_arr.end()); break;
	default:break;
	}
}
void SortHelper::print(std::string name)
{ 
	int N = m_arr.size();

	for (int i = 0; i < N; ++i) 
	{
		if (N < 20 || i % (N / 20) == 0)
			std::cout << m_arr [i]<< " ";
	}
	std::cout << std::endl;
	std::cout << name << ": swap_counts = " << m_swapcounts << ", compare_counts = " << m_compcounts << std::endl;
}

void SortHelper::swap(int& a, int& b)
{
	int tmp = a;
	a = b;
	b = tmp;
	m_swapcounts++;
}
void SortHelper::copy(int& a, const int& val)
{
	a = val;
	m_swapcounts++;
}
void SortHelper::push(std::vector<int> &a, const int& val)
{
	a.push_back(val);
	m_swapcounts++;
}
void SortHelper::adjust(int loc, int n)
{
	int left = loc * 2 + 1;
	int right = (loc + 1) * 2;
	m_compcounts += (left < n) ? 1 : 0;
	if (left < n && m_arr[loc] < m_arr[left])
	{
		swap(m_arr[left], m_arr[loc]);
		adjust(left, n);
	}
	m_compcounts += (right < n) ? 1 : 0;
	if (right < n && m_arr[loc] < m_arr[right])
	{
		swap(m_arr[right], m_arr[loc]);
		adjust(right, n);
	}
}
int SortHelper::Partition(std::vector<int> &arr, int low, int high)
{
	int val = arr[low];
	while (low < high)
	{
		while (low < high && arr[high] >= val)
		{
			--high; m_compcounts++;
		}
		copy(arr[low], arr[high]);
		while (low < high && arr[low] <= val)
		{
			++low; m_compcounts++;
		}
		copy(arr[high], arr[low]);
	}
	copy(arr[low], val);
	return low;

}
void SortHelper::QuickSortFunc(std::vector<int> &arr, int low, int high)
{
	if (low < high && high < m_arr.size())
	{
		int pivot = Partition(arr, low, high);
		QuickSortFunc(arr, pivot + 1, high);
		QuickSortFunc(arr, low, pivot - 1);
	}
}
void SortHelper::MergeSortArr(std::vector<int> &arr, int low, int mid, int high)
{
	std::vector<int> tmp;
	int idx1 = low;
	int idx2 = mid + 1;
	while (idx1 <= mid && idx2 <= high)
	{
		int val = arr[idx1] < arr[idx2] ? arr[idx1++] : arr[idx2++];
		push(tmp, val);
		m_compcounts++;
	}
	while (idx1 <= mid)
	{
		push(tmp, arr[idx1++]);
	}
	while (idx2 <= high)
	{
		push(tmp, arr[idx2++]);
	}
	for (int i = 0; i < tmp.size(); ++i, low++)
	{
		copy(arr[low], tmp[i]);
	}
}
void SortHelper::MergeSortFunc(std::vector<int> &arr, int low, int high)
{
	if (low < high && high < m_arr.size())
	{
		int mid = (low + high) / 2;
		MergeSortFunc(arr, low, mid);
		MergeSortFunc(arr, mid + 1, high);
		MergeSortArr(arr, low, mid, high);
	}
}



void SortHelper::bubbleSort()
{
	InitData();
	int N = m_arr.size();
	for (int i = 0; i < N; ++i)
	{
		int flag = 0;
		int tmp = m_arr[i];
		for (int j = N - 1; j > i; --j)
		{
			m_compcounts++;
			if (m_arr[j] < m_arr[j - 1])
			{
				flag = 1;
				swap(m_arr[j], m_arr[j - 1]);
			}
		}
		if (flag == 0)
			break;
	}
	print("bubbleSort");
}

void SortHelper::insertSort()
{
	InitData();
	int N = m_arr.size();
	for (int i = 0, j = 0; i < N; ++i)
	{
		int tmp = m_arr[i];
		for (j = i - 1; j >= 0; --j)
		{
			m_compcounts++;
			if (tmp < m_arr[j])
				copy(m_arr[j + 1], m_arr[j]);
			else
				break;
		}
		copy(m_arr[j + 1], tmp);
	}
	print("insertSort");
}

void SortHelper::heapSort()
{
	InitData();
	int N = m_arr.size();
	for (int i = N / 2 - 1; i >= 0; --i)
	{
		adjust(i, N);
	}
	for (int i = N - 1; i >= 0; --i)
	{
		swap(m_arr[i], m_arr[0]);
		adjust(0, i);
	}
	print("heapSort");
}


void SortHelper::quickSort()
{
	InitData();
	int low = 0;
	int high = m_arr.size();
	QuickSortFunc(m_arr, low, high - 1);
	print("quickSort");
}
void SortHelper::mergeSort()
{
	InitData();
	int low = 0;
	int high = m_arr.size();
	MergeSortFunc(m_arr, low, high - 1);
	print("mergeSort");
}
void SortHelper::bucketSort()
{
	InitData();

	std::vector<std::vector<int> > bucket;
	int bucket_num = 10;//10个桶
	int bais = (m_inummax - m_inummin) / bucket_num;//区间段
	for (int i = 0; i < bucket_num; ++i)
	{
		bucket.push_back({});
	}
	for (int i = 0; i < m_arr.size(); ++i)
	{
		int val = m_arr[i];
		int bucketID = (val - m_inummin) / bais;//看看在第几个区间段
		push(bucket[bucketID], val);
	}
	for (int i = 0, k = 0; i < bucket_num; ++i)
	{
		QuickSortFunc(bucket[i], 0, bucket[i].size() - 1);
		if (bucket[i].size() > 0)
		{
			for (int j = 0; j < bucket[i].size(); ++j)
			{
				copy(m_arr[k++], bucket[i][j]);
			}
		}
	}
	print("bucketSort");
}

main.cpp

#include<iostream>
#include<memory>
#include <algorithm>
#include<vector>
#include "sort_helper.h"

using namespace std;

int main(int argc, char **argv) {

	int model = INIT_MODE_RAND;

	SortHelper ss(model, 30, 0, 100, 1);
	ss.print("Init");

	ss.bubbleSort();
	ss.insertSort();
	ss.heapSort();
	ss.quickSort();
	ss.mergeSort();
	ss.bucketSort();

	return 0;
}

发布者

VC-Robot

游戏爱好者,动漫迷,C++修炼中,编程菜鸟,随性

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据