演算法設計復雜度排序

A. 排序演算法的時間復雜度如何

排序演算法的時間復雜度是若文件的初始狀態是正序的，一趟掃描即可完成排序。

比較是相鄰的兩個元素比較，交換也發生在這兩個元素之間。所以，如果兩個元素相等，是不會再交換的；如果兩個相等的元素沒有相鄰，那麼即使通過前面的兩兩交換把兩個相鄰起來，這時候也不會交換，所以相同元素的前後順序並沒有改變，所以冒泡排序是一種穩定排序演算法。

次線性時間

對於一個演算法，若其匹配T(n) = o(n)，則其時間復雜度為次線性時間（sub-linear time或sublinear time）。實際上除了匹配以上定義的演算法，其他一些演算法也擁有次線性時間的時間復雜度。例如有O(n)葛羅佛搜索演算法。

常見的非合次線性時間演算法都採用了諸如平行處理（就像NC1matrix行列式計算那樣）、非古典處理（如同葛羅佛搜索那樣），又或者選擇性地對有保證的輸入結構作出假設（如冪對數時間的二分搜索）。

不過，一些情況，例如在頭 log(n) 比特中每個字元串有一個比特作為索引的字元串組就可能依賴於輸入的每個比特，但又匹配次線性時間的條件。

「次線性時間演算法」通常指那些不匹配前一段的描述的演算法。它們通常運行於傳統計算機架構系列並且不容許任何對輸入的事先假設。但是它們可以是隨機化演算法，而且必須是真隨機演算法除了特殊情況。

B. 設計一個排序演算法，並分析其時間復雜度

可以直接採用冒泡排序，按升序排列就好。
public void bubbleSort(int arr[]) {
boolean didSwap;
for(int i = 0, len = arr.length; i < len - 1; i++) {
didSwap = false;
for(int j = 0; j < len - i - 1; j++) {
if(arr[j + 1] < arr[j]) {
int temp;
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
didSwap = true;
}
}
if(didSwap == false)
return;
}
}

最佳情況為O（n），最壞的情況為O（n2){註：n的平方}。

C. 常見的排序演算法以及時間復雜度

在常見的排序演算法中，冒泡排序，選擇排序和直接插入排序都是O（N平方）的。快速排序，歸並排序，2叉排序樹排序。都是O（NLogN）的。小學生排序則是O（N）的。

D. 排序演算法的時間復雜度計算

你這個問題是自己想出來的吧？
第一，你指的時間復雜度是大O表示法的復雜度，也就是一個上界，但不是上確界，所以就算你以一種方式中斷排序過程，時間復雜度還是O(N*logN)，假設排序過程還能執行的話。
第二，達到O(N*logN)的排序演算法，以快速排序為例，快速排序不知道你看過沒有，它不像選擇排序或者冒泡排序那樣，每一趟可以確定一直最大或者最小值，對於快速排序，每一趟排序後如果你刪掉最後一個元素將導致整個演算法失效。如果你要用這種刪除元素方法的話，只能採用冒泡排序或者選擇排序，時間復雜度是O(N^2)
所以，我猜想你是不是想做類似於在N個元素中尋找前K個最大者之類的事情（K=N-L）
如果是這樣的話，有復雜度是O(N*logK)的演算法，利用快速排序中的partition操作
經過partition後，pivot左邊的序列sa都大於pivot右邊的序列sb；
如果|sa|==K或者|sa|==K-1，則數組的前K個元素就是最大的前K個元素，演算法終止;
如果|sa|<K-1，則從sb中尋找前K-|sa|-1大的元素;
如果|sa|>K，則從sa中尋找前K大的元素。
一次partition(arr,begin,end)操作的復雜度為end-begin，也就是O(N)，最壞情況下一次partition操作只找到第1大的那個元素，則需要進行K次partition操作，總的復雜度為O(N*K)。平均情況下每次partition都把序列均分兩半，需要logK次partition操作，總的復雜度為O(N*logK)。
由於K的上界是N，所以以N表示的總復雜度還是O(N*logN)

E. 排序演算法的時間復雜度是什麼

排序演算法的時間復雜度是若文件的初始狀態是正序的，一趟掃描即可完成排序。

比較是相鄰的兩個元素比較，交換也發生在這兩個元素之間。所以，如果兩個元素相等，是不會再交換的；如果兩個相等的元素沒有相鄰，那麼即使通過前面的兩兩交換把兩個相鄰起來，這時候也不會交換，所以相同元素的前後順序並沒有改變，所以冒泡排序是一種穩定排序演算法。

冒泡排序演算法的原理如下：

1、比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。

2、對每一對相鄰元素做同樣的工作，從開始第一對到結尾的最後一對。

3、針對所有的元素重復以上的步驟，除了最後一個。

4、持續每次對越來越少的元素重復上面的步驟，直到沒有任何一對數字需要比較。