內部排序演算法比較
Ⅰ 關於排序演算法比較的問題
樓上的說法不準確吧，不能說比較和交換的次數不是一個級別的，交換也不是最多隻有n次。比如一個逆序的數組進行升序的冒泡排序，交換就遠遠超過n次。
但是假設比較次數為P(n)，交換次數為Q(n)，那麼因為交換發生在比較之後（基本上排序演算法都是這樣，樓主可以自己想想），必然有Q(n)<=P(n)。如果時間復雜度為T(n)，那麼顯然根據時間復雜度的定義（極限定義），用大O表示法可以忽略Q(n)項（或用P(n)代替Q(n)），僅用P對T進行表示。
因為大O表示法是對時間復雜度上限的一個估計，而這種每比較一次就需要交換的情況確實存在（最差情況），所以在T(n)中使用P(n)對Q(n)進行替換並不會擴大對上限估計，而只是乘以了系數2，在大O表示法中常數項是不寫入的。
這些數學分析一般在國內的演算法教材中都不寫入的，MIT的《ITA》注重這方面的敘述。
關於總結其實樓主可以自己去搜，上來問這行為太懶了。不過我也幫你找來吧。
冒泡法：
這是最原始，也是眾所周知的最慢的演算法了。他的名字的由來因為它的工作看來象是冒泡： 復雜度為O(n*n)。當數據為正序，將不會有交換。復雜度為O(0)。
直接插入排序：O(n*n)
選擇排序：O(n*n)
快速排序：平均時間復雜度log2(n)*n，所有內部排序方法中最高好的，大多數情況下總是最好的。
歸並排序：log2(n)*n
堆排序：log2(n)*n
希爾排序：演算法的復雜度為n的1.2次冪
Ⅱ 為什麼python內置的sort比自己寫的快速排序快100倍
主要原因，內置函數用C寫的。在Python語言內無論如何造不出內置函數的輪子。這也是通常C跟C++語言用戶更喜歡造基礎演算法的輪了的原因。因為C/C++用戶真有條件寫出匹敵標准庫的演算法，但很多高級語言不行，不是程序員技術差，是客觀條件就根本做不到。
你比如說Java語言沒人造字元串的輪子，C++光一個字元串類就有無數多的實現。是因為C+用戶更喜歡寫字元串類嗎？顯然不是，一方面是因為Java語言內沒法造出匹敵Java內置標准庫演算法的輪子，而C++真的可以，另外一個比較慘的原因是C++標准庫的字元串功能太弱了，大多數高級語言的字元串類功能都比C+標准庫字元串類功能更強。
Cpp內置的排序是快排和堆排的結合，最壞時間復雜度為nlogn，而快排最壞是n2。至於python內部的排序，我認為是一個道理，不會簡簡單單是一個快排，舉個簡單例子，當你數據已經是有序的時候，再傳入快排肯定就不合適。那你設置排序函數的時候，是不是預先將他打亂，再進行快排會更好呢。當然具體不會這么簡單，只是我認為官方給的介面都是很精妙的，很值得學習。
一方面Python中sort函數是用C語言寫的，C++內部的sort是由快排，直接插入和堆排序混合的，當數據量比較大的時候先用的快排，當數據量小的時候用直接插入，因為當數據量變小時，快排中的每個部分基本有序，接近直接插入的最好情況的時間復雜度O（n），就比快排要好一點了。
另外一方面這個的底層實現就是歸並排序。，只是使用了Python無法編寫的底層實現，從而避免了Python本身附加的大量開銷，速度比我們自己寫的歸並排序要快很多，所以說我們一般排序都盡量使用sorted和sort。
Ⅲ 幾種排序演算法的比較
一、八大排序演算法的總體比較
4.3、堆的插入：
每次插入都是將新數據放在數組最後。可以發現從這個新數據的父結點到根結點必然為一個有序的數列，然後將這個新數據插入到這個有序數據中
（1）用大根堆排序的基本思想
先將初始數組建成一個大根堆，此對為初始的無序區；
再將最大的元素和無序區的最後一個記錄交換，由此得到新的無序區和有序區，且滿足<=的值；
由於交換後新的根可能違反堆性質，故將當前無序區調整為堆。然後再次將其中最大的元素和該區間的最後一個記錄交換，由此得到新的無序區和有序區，且仍滿足關系的值<=的值，同樣要將其調整為堆；
..........
直到無序區只有一個元素為止；
4.4：應用
尋找M個數中的前K個最小的數並保持有序；
時間復雜度：O(K)[創建K個元素最大堆的時間復雜度] +（M-K）*log(K)[對剩餘M-K個數據進行比較並每次對最大堆進行從新最大堆化]
5.希爾排序
（1）基本思想
先將整個待排序元素序列分割成若乾子序列（由相隔某個「增量」的元素組成的）分別進行直接插入排序，然後依次縮減增量再進行排序，待整個序列中的元素基本有序（增量足夠小）時，再對全體元素進行一次直接插入排序（因為直接插入排序在元素基本有序的情況下，效率很高）；
（2）適用場景
比較在希爾排序中是最主要的操作，而不是交換。用已知最好的步長序列的希爾排序比直接插入排序要快，甚至在小數組中比快速排序和堆排序還快，但在涉及大量數據時希爾排序還是不如快排；
6.歸並排序
（1）基本思想
首先將初始序列的n個記錄看成是n個有序的子序列，每個子序列的長度為1，然後兩兩歸並，得到n/2個長度為2的有序子序列，在此基礎上，再對長度為2的有序子序列進行兩兩歸並，得到若干個長度為4的有序子序列，以此類推，直到得到一個長度為n的有序序列為止；
（2）適用場景
若n較大，並且要求排序穩定，則可以選擇歸並排序；
7.簡單選擇排序
（1）基本思想
第一趟：從第一個記錄開始，將後面n-1個記錄進行比較，找到其中最小的記錄和第一個記錄進行交換；
第二趟：從第二個記錄開始，將後面n-2個記錄進行比較，找到其中最小的記錄和第2個記錄進行交換；
...........
第i趟：從第i個記錄開始，將後面n-i個記錄進行比較，找到其中最小的記錄和第i個記錄進行交換；
以此類推，經過n-1趟比較，將n-1個記錄排到位，剩下一個最大記錄直接排在最後；
Ⅳ 幾種經典排序演算法優劣比較的C++程序實現
一、低級排序演算法
1.選擇排序
（1）排序過程
給定一個數值集合，循環遍歷集合，每次遍歷從集合中選擇出最小或最大的放入集合的開頭或結尾的位置，下次循環從剩餘的元素集合中遍歷找出最小的並如上操作，最後直至所有原集合元素都遍歷完畢，排序結束。
（2）實現代碼
//選擇排序法
template
void Sort：：SelectSort（T* array， int size）
{
int minIndex；
for（int i = 0； i < size； i++）
{
minIndex = i；
for（int j = i + 1； j < size； j++）
{
if（array[minIndex] > array[j]）
{
minIndex = j；
}
}
if（minIndex ！= i）
{
Swap（array， i， minIndex）；
}
}
}
（3）分析總結
選擇排序時間復雜度比較高，達到了O（n^2），每次選擇都要遍歷一遍無序區間。選擇排序對一類重要的元素序列具有較好的效率，就是元素規模很大，而排序碼卻比較小的序列。另外要說明的是選擇排序是一種不穩定的排序方法。
2.冒泡排序
（1）排序過程
冒泡排序的過程形如其名，就是依次比較相鄰兩個元素，優先順序高（或大或小）的元素向後移動，直至到達序列末尾，無序區間就會相應地縮小。下一次再從無序區間進行冒泡操作，依此循環直至無序區間為1，排序結束。
（2）實現代碼
//冒泡排序法
template
void Sort：：BubbleSort（T* array， int size）
{
for（int i = 0； i < size； i++）
{
for（int j = 1； j < size - i； j++）
{
if（array[j] < array[j - 1]）
{
Swap（array， j， j - 1）；
}
}
}
}
（3）分析總結
冒泡排序的時間復雜度也比較高，達到O（n^2），每次遍歷無序區間都將優先順序高的元素移動到無序區間的末尾。冒泡排序是一種穩定的排序方式。
二、高級排序演算法
（1）排序過程
歸並排序的原理比較簡單，也是基於分治思想的。它將待排序的元素序列分成兩個長度相等的子序列，然後為每一個子序列排序，然後再將它們合並成一個序列。
（2）實現代碼
//歸並排序
template
void Sort：：MergeSort（T* array， int left， int right）
{
if（left < right）
{
int mid = （left + right） / 2；
MergeSort（array， left， mid）；
MergeSort（array， mid + 1， right）；
Merge（array， left， mid， right）；
}
}
//合並兩個已排好序的子鏈
template
void Sort：：Merge（T* array， int left， int mid， int right）
{
T* temp = new T[right - left + 1]；
int i = left， j = mid + 1， m = 0；
while（i <= mid && j <= right）
{
if（array[i] < array[j]）
{
temp[m++] = array[i++]；
}
else
{
temp[m++] = array[j++]；
}
}
while（i <= mid）
{
temp[m++] = array[i++]；
}
while（j <= right）
{
temp[m++] = array[j++]；
}
for（int n = left， m = 0； n <= right； n++， m++）
{
array[n] = temp[m]；
}
delete temp；
}
（3）分析總結
歸並排序最好、最差和平均時間復雜度都是O（nlogn），是一種穩定的排序演算法。
Ⅳ 常見的幾種排序演算法總結
對於非科班生的我來說，演算法似乎對我來說是個難點，查閱了一些資料，趁此來了解一下幾種排序演算法。
首先了解一下，什麼是程序
關於排序演算法通常我們所說的往往指的是內部排序演算法，即數據記錄在內存中進行排序。
排序演算法大體可分為兩種：
一種是比較排序，時間復雜度O(nlogn) ~ O(n^2)，主要有：冒泡排序，選擇排序，插入排序，歸並排序，堆排序，快速排序等。
另一種是非比較排序，時間復雜度可以達到O(n)，主要有：計數排序，基數排序，桶排序等
冒泡排序它重復地走訪過要排序的元素，一次比較相鄰兩個元素，如果他們的順序錯誤就把他們調換過來，直到沒有元素再需要交換，排序完成。這個演算法的名字由來是因為越小(或越大)的元素會經由交換慢慢「浮」到數列的頂端。
選擇排序類似於冒泡排序，只不過選擇排序是首先在未排序的序列中找到最小值（最大值），放到序列的起始位置，然後再從剩餘未排序元素中繼續尋找最小（大）元素，放到已排序序列的末尾，以此類推，直到所有元素均排序完畢。
插入排序比冒泡排序和選擇排序更有效率，插入排序類似於生活中抓撲克牌來。
插入排序具體演算法描述，以數組[3, 2, 4, 5, 1]為例。
前面三種排序演算法只有教學價值，因為效率低，很少實際使用。歸並排序（Merge sort）則是一種被廣泛使用的排序方法。
它的基本思想是，將兩個已經排序的數組合並，要比從頭開始排序所有元素來得快。因此，可以將數組拆開，分成n個只有一個元素的數組，然後不斷地兩兩合並，直到全部排序完成。
以對數組[3, 2, 4, 5, 1] 進行從小到大排序為例，步驟如下：
有了merge函數，就可以對任意數組排序了。基本方法是將數組不斷地拆成兩半，直到每一半隻包含零個元素或一個元素為止，然後就用merge函數，將拆成兩半的數組不斷合並，直到合並成一整個排序完成的數組。
快速排序（quick sort）是公認最快的排序演算法之一，有著廣泛的應用。
快速排序演算法步驟
參考：
常用排序演算法總結(一)
阮一峰-演算法總結
Ⅵ 幾種排序演算法的比較
1.穩定性比較
插入排序、冒泡排序、二叉樹排序、二路歸並排序及其他線形排序是穩定的
選擇排序、希爾排序、快速排序、堆排序是不穩定的
2.時間復雜性比較
插入排序、冒泡排序、選擇排序的時間復雜性為O(n2)
其它非線形排序的時間復雜性為O(nlog2n)
線形排序的時間復雜性為O(n);
3.輔助空間的比較
線形排序、二路歸並排序的輔助空間為O(n),其它排序的輔助空間為O(1);
4.其它比較
插入、冒泡排序的速度較慢，但參加排序的序列局部或整體有序時，這種排序能達到較快的速度。
反而在這種情況下，快速排序反而慢了。
當n較小時，對穩定性不作要求時宜用選擇排序，對穩定性有要求時宜用插入或冒泡排序。
若待排序的記錄的關鍵字在一個明顯有限范圍內時,且空間允許是用桶排序。
當n較大時，關鍵字元素比較隨機，對穩定性沒要求宜用快速排序。
當n較大時，關鍵字元素可能出現本身是有序的，對穩定性有要求時，空間允許的情況下。
宜用歸並排序。
當n較大時，關鍵字元素可能出現本身是有序的，對穩定性沒有要求時宜用堆排序。