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

Question

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

	}

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

  已解决,谢谢