【C++】几个常见的简单排序算法
251 Views
先给结论,随机出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;
}
《【C++】几个常见的简单排序算法》有1条留言