C++：11种排序方法

// ConsoleApplication1.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
/*
排序算法（升序）：
1、插入排序
1）01 √ 插入
查找插入位置
2）02 √ 折半插入
快速查找插入位置
3）03 √ 希尔
不同步长分部排序
2、交换排序
1）04 √ 冒泡
每次确定一个极数的位置
2）05 √ 快速
每次确定一个选择的数的位置
3、选择排序
1）06 √ 选择
找到最小值交换位置
2）07 √ 堆排序
建大根堆，取堆顶后调整堆
4、其他排序
1）08 √ 归并排序
分治合并
2）09 √ 基数排序
从小位到大位分桶
3）10 √ 计数排序
单一值存桶
4）11 √ 桶排序
区间值存桶
*/
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
void printArr(vector<int>& arr) {
cout << std::right << setfill('0');
for (auto i : arr) {
cout << setw(2) << i << ' ';
}
cout << endl;
cout << setfill(' ');
}
void printName(string s) {
cout << endl << std::left << setw(20) << s;
}
void generate(vector<int>& arr, int n) {
printName("generate");
while (n--)
{
//arr.push_back(rand() % 100);
arr.push_back(rand());
}
}
//=======================================================================
void insertSort(vector<int> arr) {
printName("insertSort");
int n = arr.size();
for (int i = 1; i < n; i++)
{
int idx = i - 1;
int cur_val = arr[i];
while (idx >= 0 and arr[idx] > cur_val)
{
arr[idx + 1] = arr[idx];
idx--;
}
arr[idx + 1] = cur_val;
}
printArr(arr);
}
void halfInsertSort(vector<int> arr) {
printName("halfInsertSort");
int n = arr.size();
for (int i = 1; i < n; i++)
{
int curVal = arr[i];
//查找
int left = 0, right = i - 1;
while (left <= right)
{
int mid = (left + right) >> 1;
//跳出时保证right对应的值一定小于curVal
if (arr[mid] < curVal)
{
left = mid + 1;
}
else
{
right = mid - 1;
}
}
int j = i;
//移动
while (j > right + 1)
{
arr[j] = arr[j - 1];
j--;
}
arr[right + 1] = curVal;
}
printArr(arr);
}
void shellInsertSort(vector<int> arr) {
printName("shellInsertSort");
int n = arr.size();
for (int gap = n >> 1; gap > 0; gap /= 2)
{
for (int i = gap; i < n; i += gap)
{
int idx = i - gap;
int cur_val = arr[i];
while (idx >= 0 and arr[idx] > cur_val)
{
arr[idx + gap] = arr[idx];
idx -= gap;
}
arr[idx + gap] = cur_val;
}
}
printArr(arr);
}
//=======================================================================
void bubbleSort(vector<int> arr) {
printName("bubbleSort");
int n = arr.size();
for (int i = n - 1; i > 0; i--)
{
for (int j = 1; j <= i; j++)
{
if (arr[j] < arr[j - 1])
{
swap(arr[j], arr[j - 1]);
}
}
}
printArr(arr);
}
int partition(vector<int>& arr, int left, int right) {
int i = left;
int j = right;
int bound = arr[left];
while (i < j)
{
// j 对应的值小于bound
while (i < j and arr[j] >= bound) j--;
// i 对应的值大于bound
while (i < j and arr[i] <= bound) i++;
//跳出时，保证i对应的值比bound小
if (i < j)
{
swap(arr[i], arr[j]);
}
}
swap(arr[left], arr[i]);
return i;
}
void quick(vector<int>& arr, int left, int right) {
if (left <= right)
{
int pivot = partition(arr, left, right);
quick(arr, pivot + 1, right);
quick(arr, left, pivot - 1);
}
}
void quickSort(vector<int> arr) {
printName("quickSort");
int n = arr.size();
quick(arr, 0, n - 1);
printArr(arr);
}
//=======================================================================
void selectSort(vector<int> arr) {
printName("selectSort");
int n = arr.size();
int min_idx;
for (int i = 0; i < n - 1; i++)
{
min_idx = i;
for (int j = i + 1; j < n; j++)
{
if (arr[j] < arr[min_idx]) {
min_idx = j;
}
}
swap(arr[i], arr[min_idx]);
}
printArr(arr);
}
void adjustHeap(vector<int>& arr, int idx, int size) {
int n = size;
int curVal = arr[idx];//取当前元素
//从上往下调整
for (int i = idx * 2 + 1; i < n; i = i * 2 + 1)//i为左子节点
{
if (i + 1 < n and arr[i] < arr[i + 1]) {
i++;
//i指向右子节点
}
//如果子节点的值比父节点大，则调换位置
if (arr[i] > curVal)
{
//父子节点交换，再看孙节点
arr[idx] = arr[i];
idx = i;
}
else
{
break;
}
}
arr[idx] = curVal;
}
void buildMaxHeap(vector<int>& arr) {
int n = arr.size();
for (int i = n / 2 - 1; i >= 0; i--)
{
adjustHeap(arr, i, n);
}
}
void heapSort(vector<int> arr) {
printName("heapSort");
int n = arr.size();
//构造大根堆
buildMaxHeap(arr);
//进行排序
for (int i = n - 1; i > 0; i--)
{
//头尾调换，再从root重新调整堆
swap(arr[0], arr[i]);
adjustHeap(arr, 0, i);
//printArr(arr);
}
printArr(arr);
}
//================================================================================
void merge(vector<int>& arr, vector<int>& temp, int left, int mid, int right) {
int i, j, k;
for (i = left; i <= right; i++)
{
temp[i] = arr[i];
}
for (i = left, j = mid + 1, k = left; i <= mid and j <= right; k++)
{
if (temp[i] < temp[j])
{
arr[k] = temp[i++];
}
else
{
arr[k] = temp[j++];
}
}
while (i <= mid)
{
arr[k++] = temp[i++];
}
while (j <= right)
{
arr[k++] = temp[j++];
}
}
void dfs(vector<int>& arr, vector<int>& temp, int left, int right) {
if (left >= right)
{
return;
}
int mid = (left + right) / 2;
dfs(arr, temp, left, mid);
dfs(arr, temp, mid + 1, right);
merge(arr, temp, left, mid, right);
}
void mergeSort(vector<int> arr) {
printName("mergeSort");
int n = arr.size();
vector<int> temp(n, 0);
dfs(arr, temp, 0, n - 1);
printArr(arr);
}
//=========================================================================
void radixSort(vector<int> arr) {
printName("radixSort");
int max = *max_element(arr.begin(), arr.end());
int radix = 0;
while (max)
{
max /= 10;
radix++;
}
int R = radix;
radix = 0;
vector<vector<int>> store(10, vector<int>());
while (radix++ <= R)
{
for (int i = 0; i < 10; i++)
{
store[i].clear();
}
int s = pow(10, radix);
for (auto i : arr)
{
store[i / s % 10].emplace_back(i);
}
int idx = 0;
for (int i = 0; i < 10; i++)
{
while (!store[i].empty())
{
arr[idx++] = store[i].front();
store[i].erase(store[i].begin());
}
}
}
printArr(arr);
}
//================================================================================
void countingSort(vector<int> arr) {
printName("countingSort");
int max = *max_element(arr.begin(), arr.end());
vector<int> bucket(max + 1, 0);
int n = arr.size();
for (int i = 0; i < n; i++)
{
bucket[arr[i]]++;
}
int idx = 0;
for (int i = 0; i < max + 1; i++)
{
while (bucket[i]) {
arr[idx++] = i;
bucket[i]--;
}
}
printArr(arr);
}
//================================================================================
void bucketSort(vector<int> arr) {
printName("bucketSort");
int n = arr.size();
int minVal = *min_element(arr.begin(), arr.end());
int maxVal = *max_element(arr.begin(), arr.end());
int bucketSize = (maxVal - minVal) / 10 + 1;
vector<vector<int>> store(bucketSize, vector<int>());
for (int i = 0; i < n; i++)
{
store[(arr[i] - minVal) / 10].emplace_back(arr[i]);
}
for (int i = 0; i < bucketSize; i++)
{
sort(store[i].begin(), store[i].end());
}
int idx = 0;
for (int i = 0; i < bucketSize; i++)
{
if (!store[i].empty()) {
arr[idx++] = store[i].front();
store[i].erase(store[i].begin());
}
}
printArr(arr);
}
//================================================================================
//主函数
int main(void) {
vector<int> arr;
generate(arr, 16);
printArr(arr);
insertSort(arr);
halfInsertSort(arr);
shellInsertSort(arr);
bubbleSort(arr);
quickSort(arr);
heapSort(arr);
selectSort(arr);
mergeSort(arr);
radixSort(arr);
countingSort(arr);
bucketSort(arr);
return 0;
}

最后

以上就是凶狠月亮为你收集整理的C++：11种排序方法的全部内容，希望文章能够帮你解决C++：11种排序方法所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。