问答文章1 问答文章501 问答文章1001 问答文章1501 问答文章2001 问答文章2501 问答文章3001 问答文章3501 问答文章4001 问答文章4501 问答文章5001 问答文章5501 问答文章6001 问答文章6501 问答文章7001 问答文章7501 问答文章8001 问答文章8501 问答文章9001 问答文章9501

利用插入排序,希尔排序,起泡排序,快速排序,选择排序,堆排序,归并排序排 ...

发布网友 发布时间：2022-04-30 05:34

我来回答

共1个回答

热心网友 时间：2022-04-18 21:33

#include"stdio.h"
#include "stdlib.h"
#include <windows.h>
#include<algorithm>
#include"time.h"
#include<iostream>
using namespace std;

void InsertSort(int* pDataArray, int iDataNum)
{
for (int i = 1; i < iDataNum; i++) //从第2个数据开始插入
{
int j = 0;
while (j < i && pDataArray[j] <= pDataArray[i]) //寻找插入的位置
j++;

if (j < i) //i位置之前，有比pDataArray[i]大的数，则进行挪动和插入
{
int k = i;
int temp = pDataArray[i];
while (k > j) //挪动位置
{
pDataArray[k] = pDataArray[k-1];
k--;
}
pDataArray[k] = temp; //插入
}
}
}
//交换data1和data2所指向的整形
void DataSwap(int* data1, int* data2)
{
int temp = *data1;
*data1 = *data2;
*data2 = temp;
}

/********************************************************
*函数名称：SelectionSort
*参数说明：pDataArray 无序数组；
* iDataNum为无序数据个数
*说明： 选择排序
*********************************************************/
void SelectionSort(int* pDataArray, int iDataNum)
{
for (int i = 0; i < iDataNum - 1; i++) //从第一个位置开始
{
int index = i;
for (int j = i + 1; j < iDataNum; j++) //寻找最小的数据索引
if (pDataArray[j] < pDataArray[index])
index = j;

if (index != i) //如果最小数位置变化则交换
DataSwap(&pDataArray[index], &pDataArray[i]);
}
}
/********************************************************
*函数名称：ShellInsert
*参数说明：pDataArray 无序数组；
* d 增量大小
* iDataNum为无序数据个数
*说明： 希尔按增量d的插入排序
*********************************************************/
void ShellInsert(int* pDataArray, int d, int iDataNum)
{
for (int i = d; i < iDataNum; i += 1) //从第2个数据开始插入
{
int j = i - d;
int temp = pDataArray[i]; //记录要插入的数据
while (j >= 0 && pDataArray[j] > temp) //从后向前，找到比其小的数的位置
{
pDataArray[j+d] = pDataArray[j]; //向后挪动
j -= d;
}

if (j != i - d) //存在比其小的数
pDataArray[j+d] = temp;
}
}

/********************************************************
*函数名称：ShellSort
*参数说明：pDataArray 无序数组；
* iDataNum为无序数据个数
*说明： 希尔排序
*********************************************************/
void ShellSort(int* pDataArray, int iDataNum)
{
int d = iDataNum / 2; //初始增量设为数组长度的一半
while(d >= 1)
{
ShellInsert(pDataArray, d, iDataNum);
d = d / 2; //每次增量变为上次的二分之一
}
}

/********************************************************
*函数名称：BubbleSort
*参数说明：pDataArray 无序数组；
* iDataNum为无序数据个数
*说明： 冒泡排序
*********************************************************/
void BubbleSort(int* pDataArray, int iDataNum)
{
for (int i = 0; i < iDataNum - 1; i++) //走iDataNum-1趟
for (int j = 0; j < iDataNum - i - 1; j++)
if (pDataArray[j] > pDataArray[j + 1])
DataSwap(&pDataArray[j], &pDataArray[j + 1]);
}
int partions(int l[],int low,int high)
{
int prvotkey=l[low];l[0]=l[low];
while (low<high)
{
while (low<high&&l[high]>=prvotkey)
--high;
l[low]=l[high];
while (low<high&&l[low]<=prvotkey)
++low;
l[high]=l[low];
}
l[low]=l[0];
return low;
}
void qsort(int l[],int low,int high)
{
int prvotloc;if(low<high)
{
prvotloc=partions(l,low,high);
//将第一次排序的结果作为枢轴
qsort(l,low,prvotloc-1);
//递归调用排序 由low 到prvotloc-1
qsort(l,prvotloc+1,high);
//递归调用排序 由 prvotloc+1到 high
}
}
void quicksort(int l[],int n)
{
qsort(l,1,n); //第一个作为枢轴 ，从第一个排到第n个
}

void HeapAdjust(int *a,int i,int size) //调整堆
{
int lchild=2*i; //i的左孩子节点序号
int rchild=2*i+1; //i的右孩子节点序号
int max=i; //临时变量
if(i<=size/2) //如果i是叶节点就不用进行调整
{
if(lchild<=size&&a[lchild]>a[max])
{
max=lchild;
}
if(rchild<=size&&a[rchild]>a[max])
{
max=rchild;
}
if(max!=i)
{
swap(a[i],a[max]);
HeapAdjust(a,max,size); //避免调整之后以max为父节点的子树不是堆
}
}
}
void BuildHeap(int *a,int size) //建立堆
{
int i;
for(i=size/2;i>=1;i--) //非叶节点最大序号值为size/2
{
HeapAdjust(a,i,size);
}
}
void HeapSort(int *a,int size) //堆排序
{
int i;
BuildHeap(a,size);
for(i=size;i>=1;i--)
{
//cout<<a[1]<<" ";
swap(a[1],a[i]);
//交换堆顶和最后一个元素，即每次将剩余元素中的最大者放到最后面
//BuildHeap(a,i-1);
//将余下元素重新建立为大顶堆
HeapAdjust(a,1,i-1);
//重新调整堆顶节点成为大顶堆
}
}
void mergearray(int a[], int first, int mid, int last, int temp[])
{
int i = first, j = mid + 1;
int m = mid, n = last;
int k = 0;

while (i <= m && j <= n)
{
if (a[i] <= a[j])
temp[k++] = a[i++];
else
temp[k++] = a[j++];
}

while (i <= m)
temp[k++] = a[i++];

while (j <= n)
temp[k++] = a[j++];

for (i = 0; i < k; i++)
a[first + i] = temp[i];
}
void mergesort(int a[], int first, int last, int temp[])
{
if (first < last)
{
int mid = (first + last) / 2;
mergesort(a, first, mid, temp); //左边有序
mergesort(a, mid + 1, last, temp); //右边有序
mergearray(a, first, mid, last, temp); //再将二个有序数列合并
}
}

bool MergeSort(int a[], int n)
{
int *p = new int[n];
if (p == NULL)
return false;
mergesort(a, 0, n - 1, p);
delete[] p;
return true;
}
int main(int argc, char* argv[])
{
LARGE_INTEGER start;
LARGE_INTEGER end;
LARGE_INTEGER freq;
long n=30000;
int aa[30000];
srand(time(NULL));
for(long j=0;j<n;j++)
{
int t=100000*(rand()*0.1/RAND_MAX);
aa[j]=100000+t;//取随机数m

}
QueryPerformanceFrequency(&freq);
QueryPerformanceCounter(&start);
InsertSort(aa,30000);
QueryPerformanceCounter(&end);
double e=(double)(end.QuadPart-start.QuadPart)/ (double)freq.QuadPart;
printf("插入排序%.10f seconds\n",e);

QueryPerformanceFrequency(&freq);
QueryPerformanceCounter(&start);
SelectionSort(aa,30000);
QueryPerformanceCounter(&end);
e=(double)(end.QuadPart-start.QuadPart)/ (double)freq.QuadPart;
printf("选择排序%.10f seconds\n",e);

QueryPerformanceFrequency(&freq);
QueryPerformanceCounter(&start);
ShellSort(aa,30000);
QueryPerformanceCounter(&end);
e=(double)(end.QuadPart-start.QuadPart)/ (double)freq.QuadPart;
printf("希尔排序%.10f seconds\n",e);

QueryPerformanceFrequency(&freq);
QueryPerformanceCounter(&start);
BubbleSort(aa,30000);
QueryPerformanceCounter(&end);
e=(double)(end.QuadPart-start.QuadPart)/ (double)freq.QuadPart;
printf("起泡排序%.10f seconds\n",e);

QueryPerformanceFrequency(&freq);
QueryPerformanceCounter(&start);
quicksort(aa,30000);
QueryPerformanceCounter(&end);
e=(double)(end.QuadPart-start.QuadPart)/ (double)freq.QuadPart;
printf("快速排序%.10f seconds\n",e);

QueryPerformanceFrequency(&freq);
QueryPerformanceCounter(&start);
HeapSort(aa,30000);
QueryPerformanceCounter(&end);
e=(double)(end.QuadPart-start.QuadPart)/ (double)freq.QuadPart;
printf("堆排序%.10f seconds\n",e);

QueryPerformanceFrequency(&freq);
QueryPerformanceCounter(&start);
MergeSort(aa,30000);
QueryPerformanceCounter(&end);
e=(double)(end.QuadPart-start.QuadPart)/ (double)freq.QuadPart;
printf("归并排序%.10f seconds\n",e);

return 0;
}
我弄了很久才出来，请采纳吧！拜托了！
还有若是结果中停止程序，是因为你的数据太多太大，只要重新运行一遍就可以了！
声明声明：本网页内容为用户发布，旨在传播知识，不代表本网认同其观点，若有侵权等问题请及时与本网联系，我们将在第一时间删除处理。E-MAIL:11247931@qq.com
玉米仁子饭产自哪里 中国期货交易所的交易品种有哪些? 历史要怎么读,有啥诀窍 高中历史诀窍 年终会活动策划方案 深度解析:第一财经回放,探索财经新风向 逆水寒手游庄园怎么邀请好友同住 逆水寒手游 逆水寒不同区可以一起组队吗? 逆水寒手游 逆水寒怎么进入好友世界? 逆水寒手游 逆水寒怎么去别人的庄园? SOS!!要军训了,怎样防晒啊? 冒泡排序、插入排序、希尔排序 快速排序 归并排序 堆排序 选择排序中... 军训期间要怎麽防晒 大学军训如何防晒? 在插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序中,平均... 什么防晒才能挡住军训时的紫外线? 编写程序实现直接插入排序、希尔排序（d=5)、直接选择排序、快速排序和二路归并排序算法。 西南科技大学oj 军训期间如何防晒 ...Shell排序、快速排序、堆排序、二路归并排序等6种排序算法。 要求... 关于军训,你有什么防晒黑的好办法吗? 冒泡排序,快速排序,选择排序,归并排序,希尔排序,堆排序,插入排序 这些... 军训怕晒黑吃苹果有防晒的作用吗? 什么时候执业药师考试时间表? 美的电热水器出现e5维修要多少钱 求一个照片，照片里有爱因斯坦，普朗克，洛仑兹，居里夫人等著名的科学家。求大神们帮忙，感激不尽！ 执业药师考试一般要多久? 四季酒店都是用什么洗浴备品的呢? 首创量子论的人是谁? 2019执业药师考试时间是哪天? 美的热水器么风压故障维修下多少钱 军训防晒 比较直接插入排序，简单选择排序，快速排序，堆排序，归并排序，希尔排序和基数排序的时空性能稳定性和情 写出你所知道的3种常用的排序方法,并用其中一种方法设计出程序为数组a... 军训怎么防晒 应用javascript做输入年月日,计算出星期几。 军训怎样防晒 军训如何防晒 课题31：给出一组实验来比较下列排序算法的时间性能： 快速排序、堆排序、希尔排序、冒泡排序、归并排 军训如何防晒? 几种排序算法的效率比较 军训如何防晒伤?? 请问两种排序算法有什么区别? 大一军训,如何防晒? 偷电进拘留所五天会有案底吗?对小孩以后上学当兵有影响吗? 淋巴是在脖子的什么地方? 窃电会不会被拘留,会不会留案底~!对以后考公务员有没有影响~! 偷东西被拘留有案底吗 一般的行政拘留 会留案底吗? 脖子上的淋巴结是在下颚吗? 行政拘留会不会永远留下案底
懂视IT 51dongshi.com 版权所有
Copyright © 2019-2024