数据结构排序算法程序求解惑
A数组中存储500个2000以内的随机整数，完成以下操作：
（1）对A数组中的元素进行直接插入排序，显示排序所用时间；
（2）对A数组中的元素进行希尔排序，显示排序所用时间；
（3）对A数组中的元素进行起泡排序，显示排序所用时间；
（4）对A数组中的元素进行快速排序，显示排序所用时间。
500个数据基本出来的都是0秒。
下面是5000个数据出来的结果：
代码：
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAXLEN 5000
//生成随机数组
void createSjArray(int a[])
{
for (int i = 0; i < MAXLEN; i++)
a[i] = rand() % 2000;
}
//冒泡排序
void Bubblesort(int* num, int n)
{
int i, j, t;
for (i = 0; i < n - 1; i++)
{
for (j = 0; j < n - 1 - i; j++)
{
if (num[j] > num[j + 1]) //从小到大，升序
{
t = num[j];
num[j] = num[j + 1];
num[j + 1] = t;
}
}
}
}
//选择排序，升序
void SelectSort(int* num, int n)
{
int i, j;
int minindex, tmp;
for (i = 0; i < n - 1; i++)
{
minindex = i;
//找出第i小的数所在的位置
for (j = i + 1; j < n; j++)
{
if (num[j] < num[minindex])
minindex = j;
}
//将第i小的数放在第i个位置
if (i != minindex)
{
tmp = num[i];
num[i] = num[minindex];
num[minindex] = tmp;
}
}
}
//插入排序
void InsertSort(int* nums, int numsSize)
{
int i, j, temp;
for (i = 1; i < numsSize; i++)
{
{
if (nums[i] < nums[i - 1])
{
temp = nums[i];
for (j = i - 1; j >= 0; j--)
{
if (nums[j] > temp)
nums[j + 1] = nums[j];
else
break;
}
nums[j + 1] = temp;
}
}
}
}
//希尔排序
void shellSort(int* a, int len)
{
int i, j, k, tmp, gap; // gap 为步长
for (gap = len / 2; gap > 0; gap /= 2) { // 步长初始化为数组长度的一半，每次遍历后步长减半,
for (i = 0; i < gap; ++i) { // 变量 i 为每次分组的第一个元素下标
for (j = i + gap; j < len; j += gap) { //对步长为gap的元素进行直插排序，当gap为1时，就是直插排序
tmp = a[j]; // 备份a[j]的值
k = j - gap; // j初始化为i的前一个元素（与i相差gap长度）
while (k >= 0 && a[k] > tmp) {
a[k + gap] = a[k]; // 将在a[i]前且比tmp的值大的元素向后移动一位
k -= gap;
}
a[k + gap] = tmp;
}
}
}
}
//显示数组
void showArray(int* num, int n)
{
for (int i = 0; i < n; i++)
{
if ((i + 1) % 10 == 0)
printf("%d\n", num[i]);
else
printf("%d ", num[i]);
}
printf("\n");
}
//快速排序
void QuickSort(int nums[], int L, int R) {
int i, j = L, temp, k = nums[R];
if (L < R) {
for (i = L; i < R; i++) {
if (nums[i] < k) {
temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
j++;
}
}
temp = nums[R];
nums[R] = nums[j];
nums[j] = temp;
QuickSort(nums, L, j - 1);
QuickSort(nums, j + 1, R);
}
return;
}
//归并排序
void merge(int* nums, int L, int M, int R) {
int LEFT_SIZE = M - L;
int RIGHT_SIZE = R - M + 1;
int* left = (int*)malloc(LEFT_SIZE * sizeof(int));
int* right = (int*)malloc(RIGHT_SIZE * sizeof(int));
int i, j, k;
for (i = L; i < M; i++) left[i - L] = nums[i];
for (i = M; i <= R; i++) right[i - M] = nums[i];
i = 0, j = 0, k = L;
while (i < LEFT_SIZE && j < RIGHT_SIZE) {
if (left[i] < right[j]) {
nums[k] = left[i];
i++;
k++;
}
else {
nums[k] = right[j];
j++;
k++;
}
}
while (i < LEFT_SIZE) {
nums[k] = left[i];
k++;
i++;
}
while (j < RIGHT_SIZE) {
nums[k] = right[j];
k++;
j++;
}
}
void mergesort(int* nums, int L, int R) {
//L为数组的开始下表，R为数组的结束下标，以[1,2,3,4]为例，L=0，R=3
if (L == R)return;
else {
int M = (R + L) / 2;
mergesort(nums, L, M);
mergesort(nums, M + 1, R);
merge(nums, L, M + 1, R);
}
}
//堆排序 // 从小到大排序
void swap(int array[], int x, int y) {
int key = array[x];
array[x] = array[y];
array[y] = key;
}
void Down(int array[], int i, int n) { // 最后结果就是大顶堆
int parent = i; // 父节点下标
int child = 2 * i + 1; // 子节点下标
while (child < n) {
if (child + 1 < n && array[child] < array[child + 1]) { // 判断子节点那个大，大的与父节点比较
child++;
}
if (array[parent] < array[child]) { // 判断父节点是否小于子节点
swap(array, parent, child); // 交换父节点和子节点
parent = child; // 子节点下标 赋给 父节点下标
}
child = child * 2 + 1; // 换行，比较下面的父节点和子节点
}
}
void BuildHeap(int array[], int size) {
for (int i = size / 2 - 1; i >= 0; i--) { // 倒数第二排开始, 创建大顶堆，必须从下往上比较
Down(array, i, size); // 否则有的不符合大顶堆定义
}
}
void HeapSort(int array[], int size) {
BuildHeap(array, size); // 初始化堆
for (int i = size - 1; i > 0; i--) {
swap(array, 0, i); // 交换顶点和第 i 个数据
// 因为只有array[0]改变，其它都符合大顶堆的定义，所以可以从上往下重新建立
Down(array, 0, i); // 重新建立大顶堆
}
}
//重置数组
void ResetArray(int dst[], int src[])
{
for (int i = 0; i < MAXLEN; i++)
dst[i] = src[i];
}
int main()
{
int a[MAXLEN], b[MAXLEN];
double tms[7] = { 0 }; //记录三种情况下，每种算法的时间
clock_t start, stop;
int i = 0, j;
const char* alth[] = { "选择排序","冒泡排序","插入排序","希尔排序","快速排序","归并排序","堆排序" };
srand((unsigned int)time(0)); //生成随机数种子
createSjArray(a);
//showArray(a, MAXLEN);
//统计每种算法的排序时间
ResetArray(b, a); //用b备份a
start = clock();
SelectSort(a, MAXLEN); //调用选择排序算法
stop = clock();
tms[0] = (double)(stop - start)/ CLOCKS_PER_SEC;
ResetArray(a, b); //还原a
start = clock();
Bubblesort(a, MAXLEN); //调用冒泡排序算法
stop = clock();
tms[1] = (double)(stop - start) / CLOCKS_PER_SEC;
ResetArray(a, b); //还原a
start = clock();
InsertSort(a, MAXLEN); //调用插入排序算法
stop = clock();
tms[2] = (double)(stop - start) / CLOCKS_PER_SEC;
ResetArray(a, b); //还原a
start = clock();
shellSort(a, MAXLEN); //调用希尔排序算法
stop = clock();
tms[3] = (double)(stop - start) / CLOCKS_PER_SEC;
ResetArray(a, b); //还原a
start = clock();
QuickSort(a, 0, MAXLEN - 1); //调用快速排序算法
stop = clock();
tms[4] = (double)(stop - start) / CLOCKS_PER_SEC;
ResetArray(a, b); //还原a
start = clock();
mergesort(a, 0, MAXLEN - 1); //调用归并排序算法
stop = clock();
tms[5] = (double)(stop - start) / CLOCKS_PER_SEC;
ResetArray(a, b); //还原a
start = clock();
HeapSort(a, MAXLEN); //调用堆排序算法
stop = clock();
tms[6] = (double)(stop - start) / CLOCKS_PER_SEC;
printf("耗时统计：\n\n");
for (i = 0; i < 7; i++)
{
if (i < 6)
printf("%8s ", alth[i]);
else
printf("%8s\n", alth[i]);
}
for (j = 0; j < 7; j++)
{
if (j < 6)
printf("%-8.4lf ", tms[j]);
else
printf("%-8.4lf\n", tms[j]);
}
system("pause");
return 0;
}
网上都有现成的排序，直接拿来用就行，前后加上时间。
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define n 500
void maopao(int *a){
clock_t start,stop;
int k;
start=clock();//起始时刻
for(int i=0;i<n-1;i++)
{
for(int j=0;j<n-i-1;j++)
{
if(a[j]>a[j+1]){
k=a[j];
a[j]=a[j+1];
a[j+1]=k;
}
}
}
stop=clock();//结束时间
printf("冒泡排序所需时间：%d s\n",stop-start);
}
int main()
{
int nums[n];
srand((unsigned)time(NULL));
for(int i=0;i<n;i++){
nums[i]=rand()%2000;
}
maopao(nums);
return 0;
}
PS：问答VIP年卡 【限时加赠：IT技术图书免费领】，了解详情>>> https://vip.csdn.net/askvip?utm_source=1146287632