算法之排序之穩定性

選擇排序（Selection sort）是一種簡單直覺的排序算法。它的工作原理是每一次從待排序的資料元素中選出最小（或最大）的一個元素，存放在序列的起始位置，直到全部待排序的資料元素排完。 選擇排序是不穩定的排序方法（比如序列[5， 5， 3]第一次就将第一個[5]與[3]交換，導緻第一個5挪動到第二個5後面）。

快速排序（Quicksort）是對冒泡排序的一種改進。

快速排序由C. A. R. Hoare在1962年提出。它的基本思想是：通過一趟排序将要排序的資料分割成獨立的兩部分，其中一部分的所有資料都比另外一部分的所有資料都要小，然後再按此方法對這兩部分資料分别進行快速排序，整個排序過程可以遞歸進行，以此達到整個資料變成有序序列。

希爾排序(Shell Sort)是插入排序的一種。也稱縮小增量排序，是直接插入排序算法的一種更高效的改進版本。希爾排序是非穩定排序算法。該方法因DL．Shell于1959年提出而得名。

希爾排序是把記錄按下标的一定增量分組，對每組使用直接插入排序算法排序；随着增量逐漸減少，每組包含的關鍵詞越來越多，當增量減至1時，整個檔案恰被分成一組，算法便終止。

堆排序(Heapsort)是指利用堆積樹（堆）這種資料結構所設計的一種排序算法，它是選擇排序的一種。可以利用數組的特點快速定位指定索引的元素。堆分為大根堆和小根堆，是完全二叉樹。大根堆的要求是每個節點的值都不大于其父節點的值，即A[PARENT[i]] >= A[i]。在數組的非降序排序中，需要使用的就是大根堆，因為根據大根堆的要求可知，最大的值一定在堆頂。

冒泡排序（Bubble Sort），是一種計算機科學領域的較簡單的排序算法。

它重複地走訪過要排序的數列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。走訪數列的工作是重複地進行直到沒有再需要交換，也就是說該數列已經排序完成。

這個算法的名字由來是因為越大的元素會經由交換慢慢“浮”到數列的頂端，故名。

插入排序:有一個已經有序的資料序列，要求在這個已經排好的資料序列中插入一個數，但要求插入後此資料序列仍然有序，這個時候就要用到一種新的排序方法——插入排序法,插入排序的基本操作就是将一個資料插入到已經排好序的有序資料中，進而得到一個新的、個數加一的有序資料，算法适用于少量資料的排序，時間複雜度為O(n^2)。是穩定的排序方法。插入算法把要排序的數組分成兩部分：第一部分包含了這個數組的所有元素，但将最後一個元素除外（讓數組多一個空間才有插入的位置），而第二部分就隻包含這一個元素（即待插入元素）。在第一部分排序完成後，再将這個最後元素插入到已排好序的第一部分中。

插入排序的基本思想是：每步将一個待排序的紀錄，按其關鍵碼值的大小插入前面已經排序的檔案中适當位置上，直到全部插入完為止。

歸并排序是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法（Divide and Conquer）的一個非常典型的應用。将已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若将兩個有序表合并成一個有序表，稱為二路歸并。

歸并過程為：比較a[i]和a[j]的大小，若a[i]≤a[j]，則将第一個有序表中的元素a[i]複制到r[k]中，并令i和k分别加上1；否則将第二個有序表中的元素a[j]複制到r[k]中，并令j和k分别加上1，如此循環下去，直到其中一個有序表取完，然後再将另一個有序表中剩餘的元素複制到r中從下标k到下标t的單元。歸并排序的算法我們通常用遞歸實作，先把待排序區間[s,t]以中點二分，接着把左邊子區間排序，再把右邊子區間排序，最後把左區間和右區間用一次歸并操作合并成有序的區間[s,t]。

基數排序（radix sort）屬于“配置設定式排序”（distribution sort），又稱“桶子法”（bucket sort）或bin sort，顧名思義，它是透過鍵值的部份資訊，将要排序的元素配置設定至某些“桶”中，藉以達到排序的作用，基數排序法是屬于穩定性的排序，其時間複雜度為O (nlog(r)m)，其中r為所采取的基數，而m為堆數，在某些時候，基數排序法的效率高于其它的穩定性排序法。

關于排序：

選擇排序、快速排序、希爾排序、堆排序不是穩定的排序算法，而冒泡排序、插入排序、歸并排序和基數排序是穩定的排序算法。