C++排序算法实现
#include"sort.h"
void menu(){
cout << "**********************************************\n";
cout << "*****************1，冒泡排序******************\n";
cout << "*****************2，插入排序******************\n";
cout << "*****************3，希尔排序******************\n";
cout << "*****************4，选择排序******************\n";
cout << "***************5，快速排序算法****************\n";
cout << "*****************6，堆排序********************\n";
cout << "*****************7，归并排序******************\n";
cout << "*****************8，计数排序******************\n";
cout << "*****************9，基数排序******************\n";
cout << "*******************0，退出********************\n";
cout << "**********************************************\n";
cout << "请选择一种排序的算法： " << endl;
}1.冒泡排序
//1.冒泡排序
void BubbleSort(vector<int> &a ,size_t n){
int i, j;
int tmp;
for (int i = 0; i < n;++i){
for (int j = 0 ; j < n-1-i;++j){
if(a[j]>a[j+1]){
swap(a[j], a[j + 1]);
}
}
}
}2.插入排序
//2.插入排序
void InsertSort(vector<int>&a,size_t n){
int i, j;
for (i = 1; i < n;++i){
int key = a[i]; //保存无序区第一个元素为key
int j = i - 1;
while(!(j<0) && a[j]>key){
a[j + 1] = a[j];
--j;
}
a[j + 1] = key;
}
}3.希尔排序
//3.希尔排序
void SheelSort(vector<int>&a,size_t n){
int gap = n;
//当gap等于1的时候终止
while(gap = gap/2){
//增量
cout << "每列待排序元素:" << endl;
for (int i = gap; i < n;++i){
cout << i << " ";
int key = a[i]; //待排序元素
int j = i - gap;
for (; j + 1 > 0 && a[j] > key;j -= gap){
a[j + gap] = a[j];
}
a[j + gap] = key;
}
cout << endl;
cout << "增量" << gap << "的排序结果：" << endl;
if(gap!=1){
for (int i = 0; i < n;++i){
cout << " " << a[i];
}
cout << endl;
}
}
}4.选择排序
void SelectSort(vector<int>&a ,size_t n){
int index, tmp;
for (int i = 0; i < n; ++i)
{
//每次遍历一遍寻找最小元素放在头部 下次遍历到的最小元素放在头部的下一个位置
index = i;
for (int j = i + 1; j < n;++j){
if(a[j]<a[index]){
index = j;
}
}
if(index != i){
swap(a[i], a[index]);
}
}
}5.快速选择排序
void QuickSort(vector<int>&a,size_t low,size_t high){
if(low<high){
int i = low - 1;
int j = low;
int key = a[high];
for (int j = low; j <= high; ++j)
{
if(a[j] <= key){
++i;
swap(a[i], a[j]);
}
}
QuickSort(a, low, i - 1);
QuickSort(a, i + 1, high);
}
}6.堆排序
void Heap(vector<int>&a,int node,int n){
for (int i = 2 * node + 1; i < n;++i){
if(i+1 <n && a[i+1]>a[i]){
++i;
//找到子节点中较大的一个和根节点交换
}
if(a[i]>a[node]){
swap(a[i], a[node]);
}
}
}
void HeapSort(vector<int>&a ,int n){
for (int node = n / 2 - 1; node >= 0;--node){
//构建大顶堆 node向下取整
Heap(a, node, n);
}
//堆顶元素和堆底元素交换 剩余元素继续构建大顶堆
for (int i = n - 1; i > 0;--i){
swap(a[0], a[i]);
Heap(a, 0, i);
}
}7.归并排序(自顶向下)
void _merge(vector<int>&a,int l,int q,int r){
int n = r - l + 1; //临时数组合并后的有序序列
vector<int> tmp(n,0);
int i = 0;
int left = l;
int right = q + 1; //分割的第二个数组的首元素位置
while(left<=q && right<=r){
//两个数组依次遍历比较 将较小元素放入输出数组
tmp[i++] = a[left] <= a[right] ? a[left++] : a[right++];
}
//当其中一个数组遍历完成 则依次按顺序输出另一个数组元素
while(left<=q){
tmp[i++] = a[left++];
}
while(right<=r){
tmp[i++] = a[right++];
}
//重新赋值原数组
for (int j = 0; j < n;++j){
a[l + j] = tmp[j];
}
}
void MergeSort(vector<int>&a,int l,int r){
if(l==r){
return;
}
int q = l + (r - l) / 2;
MergeSort(a, l, q);
MergeSort(a, q + 1, r);
_merge(a, l, q, r);
}
8.计数排序
void CountSort(vector<int> &a ,size_t n){
int i, j, k;
vector<int> C(n, 0);
int maxres = 0;
for (int i = 0; i < n; ++i)
{
cout << "a[i]:" << a[i] << endl;
C[a[i]]++;
maxres = max(maxres, a[i]);
}
k = 0;
cout << "maxres:" << maxres << endl;
for (j = 0; j <= maxres; j++)
{
for (i = 1; i <= C[j];i++){
//从0开始递增 如果遇到的元素的计数大于等于1 则加入数组
a[k++] = j;
cout <<"j:"<<j<<" "<<"k:" << k << endl;
}
}
}计数排序：
当增加随机数组元素个数的时候 ，会出现错误提示
munmap_chunk(): invalid pointer需要改进。
附加信息：
‘sort.h’ 头文件
#pragma once
#include<iostream>
using namespace std;
#include<time.h>
#include<assert.h>
#include<stack>
#include<vector>
#define M 1 //执行次数
#define N 50 //数组大小
void menu(); //菜单函数
void BubbleSort(vector<int> &a, size_t n); //1.冒泡排序
void InsertSort(vector<int> &a, size_t n); // 2.插入排序
void SheelSort(vector<int> &a, size_t n); // 3.希尔排序
void SelectSort(vector<int> &a, size_t n); // 4.选择排序
void QuickSort(vector<int> &a, size_t left,size_t right); // 5.快速排序
void HeapSort(vector<int> &a, int n); // 6.堆排序
void MergeSort(vector<int> &a, int l,int r); // 7.归并排序
void CountSort(vector<int> &a, size_t n); // 8.计数排序
void LSDSort(vector<int> &a, size_t n); //9.基数排序
void QuickSort2(vector<int> &a, size_t low, size_t high); // 10.快速排序
计时设计
#include"sort.h"
template<typename T >
void displayFunction(T &input){
for (auto iterator = input.begin(); iterator != input.end();++iterator)
cout << *iterator << " " ;
cout << endl;
}
void datanum(vector<int>&a){
for (int j = 0; j < M; j++)
{
for (int i = 0; i < N; ++i){
a[i] = rand()%100;
}
}
}
int main(){
vector<int> a(N);
int i, j, p;
menu();
datanum(a);
displayFunction(a);
do
{
cin >> p;
double start, finish; //定义开始和结束时间
start = (double)clock();
switch (p) {
case 1:
BubbleSort(a, N);
break;
case 2:
InsertSort(a, N);
break;
case 3:
SheelSort(a, N);
break;
case 4:
SelectSort(a, N);
break;
case 5:
QuickSort(a,0,N-1);
break;
case 6:
HeapSort(a, N);
break;
case 7:
MergeSort(a,0,N);
break;
case 8:
CountSort(a, N);
break;
case 0:
break;
default :
break;
}
displayFunction(a);
finish = (double)clock();
printf("%.4fms\n", (finish - start));
} while (p != 0);
return 0;
}
