程序員的藝術：排序算法舞蹈

1.冒泡排序

冒泡排序（BubbleSort）的基本概念是：依次比較相鄰的兩個數，將小數放在前面，大數放在后面。即在第一趟：首先比較第 1 個和第 2 個數，將小數放前，大數放后。然后比較第 2 個數和第 3 個數，將小數放前，大數放后，如此繼續，直至比較最后兩個數，將小數放前，大數放后。至此第一趟結束，將最大的數放到了最后。在第二趟：仍從第一對數開始比較（因為可能由于第 2 個數和第 3 個數的交換，使得第 1 個數不再小于第 2 個數），將小數放前，大數放后，一直比較到倒數第二個數（倒數第一的位置上已經是最大的），第二趟結束，在倒數第二的位置上得到一個新的最大數（其實在整個數列中是第二大的數）。如此下去，重復以上過程，直至最終完成排序。

由于在排序過程中總是小數往前放，大數往后放，相當于氣泡往上升，所以稱作冒泡排序。

2.希爾排序

先取一個小于n的整數 d1 作為第一個增量，把文件的全部記錄分成（n除以 d1）個組。所有距離為 d1 的倍數的記錄放在同一個組中。先在各組內進行直接插入排序；然后，取第二個增量 d2<d1重復上述的分組和排序，直至所取的增量 dt=1(dt<dt-l<…<d2<d1)，即所有記錄放在同一組中進行直接插入排序為止。

該方法實質上是一種分組插入方法。

3.選擇排序

每一趟從待排序的數據元素中選出最小（或最大）的一個元素，順序放在已排好序的數列的最后，直到全部待排序的數據元素排完。 選擇排序是不穩定的排序方法。

4.插入排序

有一個已經有序的數據序列，要求在這個已經排好的數據序列中插入一個數，但要求插入后此數據序列仍然有序，這個時候就要用到一種新的排序方法——插入排序法,插入排序的基本操作就是將一個數據插入到已經排好序的有序數據中，從而得到一個新的、個數加一的有序數據，算法適用于少量數據的排序，時間復雜度為O(n^2)。是穩定的排序方法。插入算法把要排序的數組分成兩部分：第一部分包含了這個數組的所有元素，但將最后一個元素除外，而第二部分就只包含這一個元素。在第一部分排序后，再把這個最后元素插入到此刻已是有序的第一部分里的位置

5.快速排序

快速排序（Quicksort）是對冒泡排序的一種改進。由C. A. R. Hoare 在 1962 年提出。它的基本思想是：通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然后再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。

6.歸并排序

歸并（Merge）排序法是將兩個（或兩個以上）有序表合并成一個新的有序表，即把待排序序列分為若干個子序列，每個子序列是有序的。然后再把有序子序列合并為整體有序序列。