數(shù)組排序的最少時間復雜度O(nlog2n)怎么計算的？二分法的基本思想如下：假設數(shù)據(jù)按升序排序。對于給定的值x，從序列的中間位置開始。如果當前位置值等于x，則搜索成功；如果x小于當前位置值，則搜索在序

數(shù)組排序的最少時間復雜度O(nlog2n)怎么計算的？

二分法的基本思想如下：假設數(shù)據(jù)按升序排序。對于給定的值x，從序列的中間位置開始。如果當前位置值等于x，則搜索成功；如果x小于當前位置值，則搜索在序列的前半部分；如果x大于當前位置值，則搜索在序列的后半部分繼續(xù)，直到找到為止。因為數(shù)組是預先排序的，所以我們可以使用半查詢的方法，每次都丟棄一半要查詢的部分。這樣，長度為n的數(shù)組只需要log2n查詢，2是對數(shù)的基。例如，長度為7的數(shù)組最多只能找到三次。O（log2n）只表示與log2n的數(shù)量級相同，因為存在舍入問題，在查詢過程中也有可能找到它（即半個查詢點就是要查詢的數(shù)據(jù)），所以o（log2n）是一個上限

冒泡排序算法的時間復雜度是o（n^2））冒泡排序是通過將所有要排序的數(shù)字放入工作列表來實現(xiàn)的。

從列表中的第一個數(shù)字到倒數(shù)第二個數(shù)字，逐一檢查：如果某個位上的數(shù)字大于下一個數(shù)字，則會與其下一個數(shù)字交換。

重復步驟2，直到無法再更換。

冒泡排序的平均時間復雜度與插入排序的平均時間復雜度相同，也是平方級，但也很容易實現(xiàn)。

選擇排序選擇排序實現(xiàn)如下：在數(shù)組內存中設置n個要排序的數(shù)字，數(shù)組下標從1開始，到n結束。

從數(shù)組的第I個元素到第n個元素，I=1，找到最小的元素。

將上一步中找到的最小元素與第i個元素交換。

如果I=n-1，則算法結束，否則，排序的平均時間復雜度為O（n^2）。