c++实现7种常见排序算法并测试

c++实现7种常用排序算法

1. 快速排序；
2. 选择排序；
3. 冒泡排序；
4. 插入排序；
5. 希尔排序；
6. 归并排序；
7. 堆排序；

#include <iostream>
#include <vector>
#include <limits.h>
#include <algorithm>
using namespace std;
// 1.快速排序
void quick_sort(vector<int>& nums, int left, int right)
{
if (left >= right) return;
// 选择基准
int i = left;
int j = right;
int base = nums[left];
// 从右向左搜索第一个比base小的
while (i < j) {
while (nums[j] >= base && i < j) {
--j;
}
// 从左向右搜索第一个比base大的数
while (nums[i] <= base && i < j) {
++i;
}
swap(nums[i], nums[j]);
}
swap(nums[left], nums[j]); // 交换base与中间位置的数
quick_sort(nums, left, i - 1);
quick_sort(nums, i + 1, right);
}
// 2.选择排序
void select_sort(vector<int>& nums, int start)
{
for (int i = 0; i < nums.size(); ++i) {
int minv = i;
for (int j = i; j < nums.size(); ++j) {
if (nums[j] < nums[minv]) {
minv = j;
}
}
swap(nums[minv], nums[i]);
}
}
// 3.冒泡排序
void bubble_sort(vector<int>& nums)
{
int n = nums.size();
bool sorted = false;
for (int i = n - 1; i >= 0 && (!sorted); --i) {
sorted = true;
for (int j = 0; j < i; ++j) {
if (nums[j + 1] < nums[j]) {
sorted = false;
swap(nums[j], nums[j + 1]);
}
}
}
}
// 4. 插入排序
void insert_sort(vector<int>& nums)
{
for (int i = 1; i < nums.size(); ++i) {
for (int j = i - 1; j >= 0 && nums[j] > nums[j + 1]; --j) {
swap(nums[j], nums[j + 1]);
}
}
}
// 5. 希尔排序
void shell_sort(vector<int>& nums)
{
// h 为最大间隔，从满足（h<N/3）的最大值开始递减（h = h/3）,知道h=1为止，序列全有序
int h = 1;
int N = nums.size();
while (h < N / 3) {
h = h * 3 + 1;
}
while (h >= 1) {
for (int i = h; i < N; ++i) { // 从最大间隔处，到数组末尾依次遍历
// 对于分组后的每一组都实行插入排序
for (int j = i; (j - h) >= 0 && (nums[j] < nums[j - h]); j -= h) {
swap(nums[j], nums[j - h]);
}
}
h = h / 3;
}
}
// 6. 归并排序
class MergeSort
{
public:
// 1.自顶向下归并排序
void up2downMergeSort(vector<int>& nums) {
sort(nums, 0, nums.size() - 1);
}
void sort(vector<int>& nums, int l, int h) {
if (l >= h) return;
int mid = l + ((h - l) >> 1);
sort(nums, l, mid);
sort(nums, mid + 1, h);
merge(nums, l, mid, h);
}
// 2. 自低向上归并排序
void down2upMergeSort(vector<int>& nums) {
int N = nums.size();
for (int sz = 1; sz < N; sz += sz) {
for (int lo = 0; lo < N - sz; lo += sz + sz) { // 每次以sz为中心分为两个区间 [lo, sz+sz-1] 和 [lo+sz+sz-1, N-1]
merge(nums, lo, lo + sz - 1, min(lo + sz + sz - 1, N - 1));
}
}
}
void merge(vector<int>& nums, int l, int m, int h)
{
int i = l, j = m + 1;
vector<int> aux = nums; // 创建辅助数组
for (int k = l; k <= h; ++k) {
if (i > m) {
nums[k] = aux[j++]; // 数组前一半全部排序完成
}
else if (j > h) {
nums[k] = aux[i++]; // 数组后一半全部排序完成
}
else if (aux[i] <= aux[j]) {
// 把较小的排到前面
nums[k] = aux[i++];
}
else if (aux[i] > aux[j]) {
nums[k] = aux[j++];
}
}
}
};
// 7. 堆排序
class heapSort
{
public:
// 堆排序
void sort(vector<int> &arr, int size)
{
// 构建大根堆（从最后一个非叶子节点向上）
for (int i = size / 2 - 1; i >= 0; i--)
{
adjust(arr, size, i);
}
// 调整大根堆
for (int i = size - 1; i >= 1; i--)
{
swap(arr[0], arr[i]);
// 将当前最大的放置到数组末尾
adjust(arr, i, 0);
// 将未完成排序的部分继续进行堆排序
}
}
// 递归方式构建大根堆(len是arr的长度，index是第一个非叶子节点的下标)
void adjust(vector<int> &arr, int len, int index)
{
int left = 2 * index + 1; // index的左子节点
int right = 2 * index + 2;// index的右子节点
int maxIdx = index;
if (left<len && arr[left] > arr[maxIdx])
maxIdx = left;
if (right<len && arr[right] > arr[maxIdx])
maxIdx = right;
if (maxIdx != index)
{
swap(arr[maxIdx], arr[index]);
adjust(arr, len, maxIdx);
}
}
};
void printVec(const vector<int>& nums) {
for (int i : nums) {
printf("%d ", i);
}
printf("n");
}
void test01()
{
vector<int> nums = { 5,3,6,1,0,7,4,8,2,9 };
quick_sort(nums, 0, nums.size() - 1);
printVec(nums);
}
void test02()
{
vector<int> nums = { 5,3,6,1,0,7,4,8,2,9 };
select_sort(nums, 0);
printVec(nums);
}
void test03()
{
vector<int> nums = { 5,3,6,1,0,7,4,8,2,9 };
bubble_sort(nums);
printVec(nums);
}
void test04()
{
vector<int> nums = { 5,3,6,1,0,7,4,8,2,9 };
insert_sort(nums);
printVec(nums);
}
void test05()
{
vector<int> nums = { 5,3,6,1,0,7,4,8,2,9 };
shell_sort(nums);
printVec(nums);
}
void test06()
{
vector<int> nums = { 5,3,6,1,0,7,4,8,2,9 };
vector<int> nums2 = { 5,3,6,1,0,7,4,8,2,9 };
MergeSort mgsort;
mgsort.up2downMergeSort(nums);
mgsort.down2upMergeSort(nums2);
printf("up2downMergeSort: ");
printVec(nums);
printf("down2upMergeSort: ");
printVec(nums2);
}
void test07()
{
vector<int> arr = { 8, 1, 14, 3, 21, 5, 7, 10 };
heapSort hs;
hs.sort(arr, arr.size());
for (int i = 0; i < arr.size(); i++)
{
cout << arr[i] << " ";
}
cout << endl;
}
int main()
{
test01();
test02();
test03();
test04();
test05();
test06();
test07();
system("pause");
return 0;
}

最后

以上就是着急蜜蜂为你收集整理的c++实现7种常见排序算法并测试的全部内容，希望文章能够帮你解决c++实现7种常见排序算法并测试所遇到的程序开发问题。

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