如果有一個隨機排列的整數表，怎樣將它排序呢？這是生活中也經常碰到的問題。比如給一組牌排序，我們通常會怎樣做呢？

不斷從原序列中取出元素來排成一個新序列，在新序列形成的時候保證它有序，這就是插入排序的辦法。插入排序需要有空間存放和操作新序列，這可以在原序列的空間中滿足。插入排序需要大量的比較和移動，量級是O(n*n)。我們也可以每次從現有元素中取出最小元素，這樣新序列排下來自然是有序的，這就是選擇排序的辦法。選擇排序需要O(n*n)的比較，最壞最好情況下都一樣。這是一個缺點，和與之對稱的插入排序比較，選擇排序對原序列的情況缺乏適應性，冒泡排序是對此的改進。冒泡排序也基本使用原序列的空間，每次在現有元素中進行比較以尋找最小元素，并通過交換逐步把它移到相應位置。冒泡排序在原序列的基礎上逐步調整得到新序列，它可以更加適應原序列的情況，在最好情況下時間為O(n)。這三種排序是最基本的，其它方法都是從各種角度對它們進行改進。

三種基本排序都著眼于從原序列形成新序列的過程。這是最基本的，但還可以把整個過程用分治或漸進的思想來處理。具體的改進方法有多種，希爾排序，快速排序，歸并排序等等，我們現在可以欣賞它們的思想，但是當初每種方法的發現都是重要的成果，需要對排序問題有扎實的認識，也需要創造的靈感。

希爾排序把原序列分組，每一組進行插入排序，從較小的分組開始逐漸擴大，直到整個序列作為一組。分組元素是間隔選取的，較小的分組排序完成后，整個序列就在一個較大的尺度上有序了，隨著分組的擴大，序列在越來越小的尺度上有序，直到完全有序。希爾排序利用插入排序對樂觀情況的適應性，自頂向下漸進處理，避免了直接在小尺度上進行處理的盲目性。

歸并排序反映出一種自底向上的分治思想，其時間為O(n*log(n))。

快速排序采用了自頂向下的分治思想，其做法和歸并排序有某種對稱性。

基數排序也是自頂向下的分治思想，它從關鍵字本身衡量問題的解決程度。