當記錄序列基本有序時，哪種排序方法效率高?簡單選擇排序與起泡排序兩者在什么情況下執(zhí)行效率差別較大？序列基本順序是指正序，直接插入、冒泡或隨機快速排序是合適的這兩種算法效率都很低，一般我們用一個與數(shù)據(jù)大

當記錄序列基本有序時，哪種排序方法效率高?簡單選擇排序與起泡排序兩者在什么情況下執(zhí)行效率差別較大？

序列基本順序是指正序，直接插入、冒泡或隨機快速排序是合適的

這兩種算法效率都很低，一般我們用一個與數(shù)據(jù)大小相關(guān)的時間漸近函數(shù)來評價算法的時間效率，這就是所謂的算法時間復(fù)雜度。這兩種算法的時間復(fù)雜度均為O（n^2），基于比較的排序算法的時間復(fù)雜度最好，為O（nlogn）。堆排序、合并排序和快速排序的預(yù)期復(fù)雜度可以達到o（nlogn）。堆排序和合并排序的最壞情況復(fù)雜度仍然是o（nlogn）]~]，這主要是在每一輪的交換方式上的不同，最大或最小的元素被過濾掉并放在相應(yīng)的位置。這是相同的，但對于每一輪，例如，在第一輪中，1~n中的最大元素放在n的位置。冒泡方法每次比較和移動兩個相鄰的項，并選擇排序，每次交換當前項和第n項。我將為您編寫代碼：冒泡：對于I:=1到n-1 do if（a[I]>A[I 1]），然后交換（I，I，1）選擇：對于I:=1到n-1 do if（a[I]>A[n]），然后交換（I，n）（交換意味著交換）一般來說，這兩種類型的比較時間是相同的，但交換時間較少。雖然這兩種排序的時間復(fù)雜度都是O（n^2），但一般來說，選擇排序的速度更快

我現(xiàn)在想了解這個問題。事實上，這個比較排名的下界（注意下界是最好的情況）一定是對的。但有一個條件，即在排序過程中，附加的信息或條件不能用來比較排序的下限。

1. 氣泡排序，它利用了上次掃描中沒有發(fā)生交換的附加條件。

2. 插入排序，它利用了大量有序元素的額外信息。

3. 快速排序，如果采用三向切分法，可以將其分為與pivot相同、大于pivot和小于pivot，然后利用含有大量重復(fù)元素的額外信息來突破nlogn。因此，比較排名或下界的最佳情況是nlogn，它不考慮任何附加條件和附加信息。如果你對數(shù)據(jù)做額外的假設(shè)，你就可以突破這個下限。