實際應用中最常用的排序是快速排序和堆排序。所謂堆排序，就是將最小的一個值放到堆棧的頂部，這樣就可以使最后出來的數完成排序。快速排序是不穩定的，堆排序是穩定的。所謂穩定，就是當兩個值相等時，排序后兩個值的順序和排序前相同。以上兩種排序使用的范圍和情況是不同的，一般對于自然生成序列排序使用快速排序效率比較高，而對于已經有一定順序的序列，使用堆排序比較合適，而且穩定的。

這里主要總結常用的5種排序，分別是快速排序，冒泡排序（也叫交換排序），選擇排序，shell排序，插入排序。

下邊分別介紹：

1快速排序，就是從一個序列中隨意取一個數，然后對剩下的數進行分類，小的放到左邊，大的放到右邊。如此進行下去知道最后。N(n-1)/2.空間復雜度是o（n）.

2冒泡排序，就是從第一個數開始和后一個數比較，然后依情況交換，然后再用第二個和第三個比較交換，如此反復，直到最后一個。一直進行n輪就可以完成排序。

3選擇排序，就是將一個序列中的最小的放到第一個，然后再將剩下的數據用相同的方式分別放到后一位。它的空間復雜度是O(1).

4shell排序，就是將有一定間隔的數進行排序，并且間隔變小，也就是開始是n/2,然后繼續變小，一般都是以一半為標準，直到最后間隔只有1，也就完成了排序。需要的空間復雜度是O(1).

5插入排序，就比如平時玩的撲克排，一般整理排的時候需要將排排序，當你拿到一張新排的時候，就要比較左邊和右邊，只有在左右中間的那個值的時候才說明排序成功。它需要的空間復雜度也是O(1).

Ps:空間復雜度就是需要另外占用的空間。

以上排序中，只有快速排序是O（n），其他都是O（1），因為只有快速排序需要另外再起存儲空間，而其他都是在原來空間中增加一個空間就可以。