C语言自带快速排序对比插入排序

#include <stdio.h>

#include <stdlib.h>

#include <time.h>

void getRandomArr (int arr[], int n);

void printArr (int arr[], int n);

void swap (int arr[], int i, int j);

void insertSort (int arr[], int n);

int compare(const int *a, const int *b);

int main () {

    int max = 40000; // 数组长度

    int sortArr1[max]; // 待排序数组

    int sortArr2[max]; // 待排序数组

    clock_t start, stop;

    double duration1;

    double duration2;

    printf("待排数据共 %d 个\n", max);

    getRandomArr(sortArr1, max); // 为待排序数组, 赋值

    start = clock(); /* 开始计时 */

    insertSort(sortArr1, max);

    stop = clock(); /* 停止计时 */

    duration1 = ((double)(stop - start)) / CLK_TCK; /* 计算运行时间 */

    printf("插入排序用时: %.4f秒\n", duration1);

    getRandomArr(sortArr2, max); // 为待排序数组, 赋值

    start = clock(); /* 开始计时 */

    qsort(sortArr2, max, sizeof(int), compare);

    stop = clock(); /* 停止计时 */

    duration2 = ((double)(stop - start)) / CLK_TCK; /* 计算运行时间 */

    printf("快速排序用时: %.4f秒\n", duration2);

    printf("快速排序是插入排序的 %d 倍\n", (int)(duration1 / duration2));

    return 0;

}

// 函数功能: 对主程序中的数组进行, 随机数赋值

// 参数: arr[] 主程序数组名称, n 数组大小

void getRandomArr (int arr[], int n) {

    int i;

    arr[0] = 0; // 默认0号下标, 值为0

    srand(time(0)); // 随机数种子

    for (i=1; i<n; i++) {

        arr[i] = rand() % 20000 + 1; // 范围[1, 20000]

    }

}

// 函数功能: 打印数组

// 参数: arr[] 需要打印的数组, n 数组大小

void printArr (int arr[], int n) {

    int i;

    for (i=0; i<n; i++) {

        printf("arr[%d]: %d\n", i, arr[i]);

    }

    printf("\n");

}

// 函数功能: 交换数组i和j下标的2个元素

void swap (int arr[], int i, int j) {

    int tmp = arr[i];

    arr[i] = arr[j];

    arr[j] = tmp;

}

// 函数功能: 完成对arr[]的排序

// 参数: arr[] 待排序的数组, n该数组的长度

void insertSort (int arr[], int n) {

    int i;

    int j;

    for (i=2; i<n; i++) {

        // 如果刚开始i > i-1, 则该元素就是本次最大值, 不用移动

        if (arr[i] > arr[i-1]) {

            continue;

        }

        for (j=i-1; j>=1; j--) { // 遍历已经排好序的元素

            // 进行两两比较, 并交换

            if (arr[j+1] < arr[j]) {

                swap(arr, j, j+1);

            }

        }

        // printArr(arr, n);

    }

}

/*

    返回值: >0, 说明arg1 > arg2, 也就是arg1在arg2右边,

     从小到大排序

*/

int compare(const int *a, const int *b) {

    int res;

    int arg1 = *a;

    int arg2 = *b;

    if (arg1 < arg2) {

        res = -1;

    } else if (arg1 > arg2) {

        res = 1;

    } else {

        res = 0;

    }

    return res;

}

运行结果:

待排数据共 40000 个

插入排序用时: 3.8570秒

快速排序用时: 0.0080秒

快速排序是插入排序的 482 倍

Process returned 0 (0x0)   execution time : 3.983 s

Press any key to continue.

巴特西

C语言自带快速排序对比插入排序

最新文章

热门文章