試題詳解

14. Consider an array of size n with perfectly inversely sorted order. Which of the following is correct about the running times to sort this array (deterministically)?
(A) Quicksort: O(n ign)； Merge Sort: O(n ign)； Insertion Sort: O(n²)
(B) Quicksort: 0(n²)； Merge Sort: O(n²)； Insertion Sort: 0(n²)
(C) Quicksort: O(n²)； Merge Sort: O(n lgn)； Insertion Sort: O(n lgn)
(D) Quicksort: 0(n²)； Merge Sort: O(n lgn)； Insertion Sort: O(n²)