数据结构排序算法程序求解惑

Question

A数组中存储500个2000以内的随机整数，完成以下操作：
（1）对A数组中的元素进行直接插入排序，显示排序所用时间；
（2）对A数组中的元素进行希尔排序，显示排序所用时间；
（3）对A数组中的元素进行起泡排序，显示排序所用时间；
（4）对A数组中的元素进行快速排序，显示排序所用时间。

Answer 1

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;
}