#include<iostream>
#include<ctime>
#include<math.h>
#define N 100001
using namespace std;
long long sum[5][10][3];
int randNum[N];
int randNum1[N - 1];
//显示数组
void show(int randNum[N]) {
for (int i = 1; i < N; i++)
printf("%6d", randNum[i]);
cout << endl;
}
//产生随机数
void proRandNum(int *randNum) {
randNum[0] = 0;
srand((unsigned)clock());
for (int i = 1; i < N; i++)
randNum[i] = rand();
}
//产生正序
void proPosiNum(int *posiNum) {
posiNum[0] = 0;
for (int i = 1; i < N; i++)
posiNum[i] = i;
}
//产生逆序
void proNegaNum(int *negaNum) {
negaNum[0] = 0;
for (int i = 1; i < N; i++)
negaNum[i] = N- i;
}
//前一半有序,后一半随机
void proPosiRandNum(int *posiRand) {
posiRand[0] = 0;
for (int i = 1; i < N / 2 + 1; i++)
posiRand[i] = i;
srand((unsigned)time(NULL));
for (int i = N / 2 + 1; i < N; i++)
posiRand[i] = rand();
}
//前一半随机,后一半有序
void proRandPosiNum(int *randPosi) {
randPosi[0] = 0;
srand((unsigned)time(NULL));
for (int i = 1; i < N / 2 + 1; i++)
randPosi[i] = rand();
for (int i = N / 2 + 1; i < N; i++)
randPosi[i] = i;
}
//输入结果
void resultPrint(int num, int num2) {
cout << " 比较次数 移动次数 运行时间(ms)\n";
switch (num2) {
case 0:
if (num + 1 == 11) {
for (int i = 0; i < 10; i++) {
switch (i + 1) {
case 1:cout << "直接插入排序:"; break;
case 2:cout << " 希尔排序 :"; break;
case 3:cout << " 冒泡排序 :"; break;
case 4:cout << " 快速排序 :"; break;
case 5:cout << "简单选择排序:"; break;
case 6:cout << " 堆排序 :"; break;
case 7:cout << " 归并排序 :"; break;
case 8:cout << " 基数排序 :"; break;
case 9:cout << "折半插入排序:"; break;
case 10:cout << "2路插入排序:"; break;
default:
break;
}
printf("%12lld", (sum[0][i][0] + sum[1][i][0] + sum[2][i][0] + sum[3][i][0] + sum[4][i][0]) / 5);
printf("%12lld", (sum[0][i][1] + sum[1][i][1] + sum[2][i][1] + sum[3][i][1] + sum[4][i][1]) / 5);
printf("%12lld", (sum[0][i][2] + sum[1][i][2] + sum[2][i][2] + sum[3][i][2] + sum[4][i][2]) / 5);
cout << endl;
}
break;
}
for (int i = 0; i < 5; i++) {
cout << "数据" << i + 1 << ": ";
printf("%12lld", sum[i][num][0]);
printf("%12lld", sum[i][num][1]);
printf("%12lld", sum[i][num][2]);
cout << endl;
}
cout << "均值: ";
printf("%12lld", (sum[0][num][0] + sum[1][num][0] + sum[2][num][0] + sum[3][num][0] + sum[4][num][0]) / 5);
printf("%12lld", (sum[0][num][1] + sum[1][num][1] + sum[2][num][1] + sum[3][num][1] + sum[4][num][1]) / 5);
printf("%12lld", (sum[0][num][2] + sum[1][num][2] + sum[2][num][2] + sum[3][num][2] + sum[4][num][2]) / 5);
cout << endl;
break;
case 1:
case 2:
case 3:
case 4:
if (num + 1 == 11) {
for (int i = 0; i < 10; i++) {
switch (i + 1) {
case 1:cout << "直接插入排序:"; break;
case 2:cout << " 希尔排序 :"; break;
case 3:cout << " 冒泡排序 :"; break;
case 4:cout << " 快速排序 :"; break;
case 5:cout << "简单选择排序:"; break;
case 6:cout << " 堆排序 :"; break;
case 7:cout << " 归并排序 :"; break;
case 8:cout << " 基数排序 :"; break;
case 9:cout << "折半插入排序:"; break;
case 10:cout << "2路插入排序:"; break;
default:
break;
}
printf("%12lld", sum[4][i][0]);
printf("%12lld", sum[4][i][1]);
printf("%12lld", sum[4][i][2]);
cout << endl;
}
break;
}
cout << "数据"<< ": ";
printf("%12lld", sum[4][num][0]);
printf("%12lld", sum[4][num][1]);
printf("%12lld", sum[4][num][2]);
cout << endl;
break;
}
//清零
for (int i = 0; i < 5; i++)
for (int j = 0; j < 10; j++)
for (int k = 0; k < 3; k++)
sum[i][j][k] = 0;
}
//1.直接插入排序
void straightInsertSort(int *randNum, int n) {
int i, j;
for (i = 2; i < N;++i)
if (sum[n][0][0]++,randNum[i] < randNum[i - 1]) {
randNum[0] = randNum[i];
randNum[i] = randNum[i - 1]; sum[n][0][1] += 2;
for (j = i - 2; sum[n][0][0]++, randNum[0] < randNum[j]; --j)
{
randNum[j + 1] = randNum[j]; sum[n][0][1]++;
}
randNum[j + 1] = randNum[0]; sum[n][0][1]++;
}
}
//2.希尔排序
void shellSort(int randNum[N], int n) {
int dlta[17];
int j;
for (int k = 0; k <= 16; k++) {
dlta[k] = pow(2, 16 - k) + 1;
}
for (int k = 0; k <= 16; k++) {
for (int i = dlta[k] + 1; i < N; i++) {
if (sum[n][1][0]++, randNum[i] < randNum[i - dlta[k]]) {
sum[n][1][1]++; randNum[0] = randNum[i];
for (j = i - dlta[k]; sum[n][1][0]++, j > 0 && randNum[0] < randNum[j]; j -= dlta[k])
{
sum[n][1][1]++; randNum[j + dlta[k]] = randNum[j];
}
sum[n][1][1]++; randNum[j + dlta[k]] = randNum[0];
}
}
}
//show(randNum);
}
//3.冒泡排序
void bubbleSort(int randNum[N], int n) {
int i, j;
long long t;
for (i = 1; i<N-1; i++)
for (j = 1; j<N - i; j++)
{
if (sum[n][2][0]++, randNum[j]>randNum[j + 1])
{
t = randNum[j];
randNum[j] = randNum[j + 1];
randNum[j + 1] = t;
sum[n][2][1] += 3;
}
}
//show(randNum);
}
//4.快速排序
//取待排序序列中low、mid、high三个位置上数据,选取他们中间的那个数据作为枢轴
int SelectPivotMedianOfThree(int arr[], int low, int high)
{
int mid = low + (high - low) / 2;
if (arr[mid] > arr[high])
swap(arr[mid], arr[high]);
if (arr[low] > arr[high])
swap(arr[low], arr[high]);
if (arr[mid] > arr[low])
swap(arr[mid], arr[low]);
return arr[low];
}
int partition(int *randNum, int low, int high, int n) {
randNum[0] = randNum[low];
int pivotkey = SelectPivotMedianOfThree(randNum, low, high);
while (low < high) {
while (low < high&&randNum[high] >= pivotkey) {
--high; sum[n][3][0]++;
}
randNum[low] = randNum[high]; sum[n][3][1]++;
while (low < high&&randNum[low] <= pivotkey) {
++low; sum[n][3][0]++;
}
randNum[high] = randNum[low]; sum[n][3][1]++;
}
randNum[low] = randNum[0];
return low;
}
void QSort(int *randNum, int low, int high, int n) {
if (low < high) {
int pivotloc = partition(randNum, low, high, n);
if (pivotloc - 1 - low <= high - pivotloc - 1) {
if(pivotloc!=low)
QSort(randNum, low, pivotloc - 1, n);
if(pivotloc != high)
QSort(randNum, pivotloc + 1, high, n);
}
else {
if (pivotloc != high)
QSort(randNum, pivotloc + 1, high, n);
if (pivotloc != low)
QSort(randNum, low, pivotloc - 1, n);
}
}
}
void quickSort(int *randNum, int n) {
QSort(randNum, 1, N - 1, n);
//show(randNum);
}
//5.简单选择排序
void simpleSelectionSort(int randNum[N], int n) {
int i, j, min, ex;
for (i = 1; i < N-1; i++) {
min = i;
for (j = i+1; j < N; j++) {
if (sum[n][4][0]++, randNum[min] > randNum[j])
min = j;
}
if (min != i) {
ex = randNum[i];
randNum[i] = randNum[min];
randNum[min] = ex;
sum[n][4][1] += 3;
}
}
//show(randNum);
}
//6.堆排序
void heapAdjust(int *randNum, int s, int m, int n) {
int rc = randNum[s];
for (int j = 2 * s; j <= m; j *= 2) {
if (sum[n][5][0]++, j < m&&randNum[j] < randNum[j + 1]) ++j;
if (rc >= randNum[j]) break;
randNum[s] = randNum[j]; s = j; sum[n][5][1]++;
}
randNum[s] = rc; sum[n][5][1]++;
}
void heapSort(int *randNum, int n) {
int i,ex;
for (i = (N - 1) / 2; i > 0; --i)
heapAdjust(randNum, i, N - 1, n);
for (i = N - 1; i > 1; --i) {
swap(randNum[i], randNum[1]);
heapAdjust(randNum, 1, i - 1, n);
}
//show(randNum);
}
//7.归并排序
void mergingSort(int *randNum, int n) {
//MSort(randNum, randNum, 1, N - 1, n);
int i, left_min, left_max, right_min, right_max, next;
int *tmp = (int*)malloc(sizeof(int) * (N-1));
if (tmp == NULL)
{
fputs("Error: out of memory\n", stderr);
abort();
}
for (i = 1; i < N-1; i *= 2) // i为步长,1,2,4,8……
{
for (left_min = 1; left_m

LilWing
- 粉丝: 3720
最新资源
- C#.NET框架程序设计习题和答案公开课获奖课件.pptx
- 逐飞科技基于英飞凌TC264的智能车BLDC开源项目-大学生程序设计竞赛资源
- 2023年电子商务概论的国内外现状及应用前景.doc
- EXCEL-函数-宏-VBA-入门知识.ppt
- 大数据发展脉络.ppt
- 第三章顾客网络购买分析.ppt
- 毕业设计单片机相关外文文献翻译人工修订精确版.doc
- 毕业论文设计基于51单片机的电阻测量-精品.doc
- 毕业设计仓库管理系统JAVA源代码设计说明.doc
- PLM和ERP系统集成技术的研究和实施应用.docx
- 传送带及机械手PLC控制设计范本.docx
- 单片机课程设计任务书.doc
- 2023年专业技术人员公共危机管理网络考试参考题库.docx
- 财税实务网络平台代收代付是否具有增值税义务.doc
- 2023年哈工大人工智能导论实验报告.docx
- ASQ--项目管理、工业工程、物流工程专业基础与综合考试笔试指南(DOC13).doc
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈


