c - 冒泡和插入之间的时间复杂度

Question

我用 C 实现了 3 个对数排序:冒泡排序、插入排序和快速排序。当我测试算法的运行时间时，插入常量的运行速度比冒泡排序快得多。我被这个链接引导相信他们应该在同一时间 http://bigocheatsheet.com/
谁能解释一下为什么插入排序如此快？

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void insertSort(int arr[], int size){
    int temp, j, i;

    for (i = 1; i < size; i++){
        temp = arr[i];
        for (j = i; j > 0 && temp < arr[j - 1]; j--){
            arr[j] = arr[j - 1];
        }
        arr[j] = temp;
    }
}

void quicksort(int arr[], int first, int last){
    int pivot, j, temp, i;

    if (first < last){
        pivot = first;
        i = first;
        j = last;

        while (i < j){
            while (arr[i] <= arr[pivot] && i < last)
                i++;
            while (arr[j] > arr[pivot])
                j--;
            if (i < j){
                temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }

        temp = arr[pivot];
        arr[pivot] = arr[j];
        arr[j] = temp;
        quicksort(arr, first, j - 1);
        quicksort(arr, j + 1, last);
    }
}

void bubbleSort(int arr[], int size){
    int x = 0, y;

    for (x; x < size; x++){
        for (y = 0; y < size - 1; y++){
            if (arr[y] > arr[y + 1]){
                int temp = arr[y + 1];
                arr[y + 1] = arr[y];
                arr[y] = temp;
            }
        }
    }
}

void printArray(int arr[], int sizeArray){
    int i = 0;
    for (i; i < sizeArray; i++){
        printf("%i\n", arr[i]);
    }

    //  printf("\n");
    //  for (i = 0; i < number; i++){
    //      printf("bubbleNums[%d] = %d     ", i, *(bubbleNums + i));
    //      printf("insertNums[%d] = %d     ", i, *(insertNums + i));
    //      printf("quickNums[%d] = %d\n", i, *(quickNums + i));
    //  }
}

int main(){
    int *bubbleNums = (int *)malloc(100000 * sizeof(int)), *quickNums = (int *)malloc(100000 * sizeof(int)), *insertNums = (int *)malloc(100000 * sizeof(int));
    int number;
    int randNumber;
    int i = 0;

    printf("Enter a number: ");
    scanf(" %i", &number);

    printf("\n");
    srand(100);
    for (i; i < number; i++){
        randNumber = rand() % 100;
        bubbleNums[i] = randNumber;
        insertNums[i] = randNumber;
        quickNums[i] = randNumber;
        //      printf("bubbleNums[%d] = %d     ", i, *(bubbleNums + i));
        //      printf("insertNums[%d] = %d     ", i, *(insertNums + i));
        //      printf("quickNums[%d] = %d\n", i, *(quickNums + i));
    }

    printf("\n");
    clock_t t0 = clock();
    bubbleSort(bubbleNums, number);
    clock_t t1 = clock();
    printf("Time to sort bubblesort of %i elements: %d milliseconds\n", number, (t1 - t0));

    clock_t t2 = clock();
    insertSort(insertNums, number);
    clock_t t3 = clock();
    printf("Time to sort insertSort of %i elements: %d milliseconds\n", number, (t3 - t2));

    clock_t t4 = clock();
    quicksort(quickNums, 0, number - 1);
    clock_t t5 = clock();
    printf("Time to sort quicksort of %i elements: %d milliseconds\n", number, (t5 - t4));

        //printf("Bubble\n");
        //printArray(bubbleNums, number);
        //printf("Insert\n");
        //printArray(insertNums, number);
        //printf("Quick\n");
        //printArray(quickNums, number);

    getchar();
    getchar();

    return 0;
}

Answer 1

O(...) 不包括常数乘数或低阶项。因此，如果一种方法的时间为 2 x n^2，另一种方法的时间为 6 x n^2 + 12 x n + 18，则它们都被视为 O(n^2)，即使其中一种方法的速度比另一种方法快 3 倍多。其他。

O(...) 只是为您提供特定算法的时间与 n 关系的一阶近似值。

对于另一个问题，插入排序速度更快，因为它根据需要旋转数组的各个部分，而冒泡排序仅交换对。