插入排序在VS上特别快,已调release

Question

1 2 3 4 5 6 7 8 9 10 11

template<typename T> void insertionSort(T arr[], int n) {     for (int i = 1; i < n; i++) {         T e  = arr[i];         int j;         for (j = i; j > 0 && arr[j] < arr[j - 1]; j--)                  arr[j] = arr[j - 1];         arr[j] = e;     }   }

1 2 3 4 5 6 7 8 9 10 11 12 13

int main() {     const int n = 10000;     int *arr1 = SortTestHeiper::generateRandomArray(n, 0, n);     int *arr2 = SortTestHeiper::copyIntArray(arr1, n);     SortTestHeiper::TestSort("Insertion Sort", Sort::insertionSort, arr1, n);     SortTestHeiper::TestSort("Selection Sort", Sort::selectionSort, arr2, n);       delete[] arr1;     delete[] arr2;     return 0; } 10000的数量级

1000000的数量,selection sort 太慢了,注释了

为什么会这样呢

Answer 1

liuyubobobo 2018-02-15 11:06:44

O(n^2)的排序就是这么慢哦。但是如果换成O(nlogn)的排序，100万的数据是小case，这就是算法的力量：）

• 提问者 纸女神 #1

  重点是插入排序太快了吧O(n^2)百万数量级可以在0.002秒完成?

• 提问者 纸女神 #2

  已解决,谢谢