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

Question

我用 C 实现了 3 个排序对数：冒泡排序、插入排序和快速排序。当我测试算法插入常数运行的时间时运行s 比冒泡排序快得多。 link 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

这可能是因为您的 BubbleSort 在排序列表时没有停止。您应该跟踪每次传递的更改次数。如果没有任何更改，则列表已排序。现在你强迫它总是有可能的最差性能。

for (x; x < size; x++){
    int changes = 0;
    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;
            changes++;
        }
    }
    if (changes == 0) {
        return;
    }
}

Answer 2

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

O(...) 只是给出了特定算法的时间与 n 的关系的一阶近似值。

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

Answer 3

渐近复杂性告诉您性能如何缩放与问题的大小。它不会告诉您关于同一任务的替代算法如何针对同一问题相对于彼此执行的任何信息。

插入排序是最快的 O(n²) 排序算法之一。尽管它的扩展方式与冒泡排序相同，但插入排序倾向于执行更少的比较和交换。减少多少取决于实施细节和输入。

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

Time Complexity between Bubble and Insertion

c

sorting

time-complexity