六、排序
     1.直接插入排序
     直接插入排序的基本思想是把表中元素依次插入一個(gè)已排好序的表中，就像人們打撲克摸牌時(shí)把牌插入手中的若干張牌里一樣。表中n個(gè)元素依次插入的比較次數(shù)為1+2+3+…+（n-1）=n（n-1）/2。在插入時(shí)，元素的移動(dòng)次數(shù)最多為1+2+3+…+（n-1）=n（n-1）/2。如果表中元素已排好序，則只需比較n-1次，而移動(dòng)次數(shù)為0。
     2.直接選擇排序
     直接選擇排序的基本思想是在表的n個(gè)元素中，經(jīng)過n-1次比較得到其值（或最小值，下同），這就排好了第一個(gè)元素;再經(jīng)過n-2次比較得到余下元素中的值，這就排好了第二個(gè)元素…直到比較1次后排好第n-1個(gè)元素，第n個(gè)元素的位置也就自然確定了。所需的比較次數(shù)為（n-1）+（n-2）++1=n（n-1）/2。所需移動(dòng)次數(shù)最多也為n（n-1）/2。如果表中元素排好序，也需要比較n（n-1）/2次，而移動(dòng)次數(shù)為0。
     3.冒泡排序
     冒泡排序的基本思想是將表中元素兩個(gè)相鄰元素依次比較，若不符合排序要求，則交換位置，這樣經(jīng)過n-1次比較后，將確定出（或最?。┰氐奈恢?，這稱為一趟掃描。經(jīng)過n-1次掃描后，就完成了整個(gè)表的排序。第一趟掃描的比較次數(shù)是n-1，第二趟掃描的比較次數(shù)是n-2……，總的比較次數(shù)是（n-1）+（n-2）+……+1=n（n-1）/2。如果恰好表中元素按反序排列，則需要移動(dòng)的次數(shù)為3×n（n-1）/2。如果表中元素已排好序，并采用交換標(biāo)志來表示并未發(fā)生過交換，則只需一趟掃描，只比較n-1次，就夠了;當(dāng)然，移動(dòng)次數(shù)也是0。
     4.歸并排序
     歸并排序的基本思想是表中元素兩兩比較排序，使表中的n個(gè)元素變成n/2個(gè)已排序的組，再兩兩組比較，而變成n/4個(gè)已排序的組……，直到表中只含有一個(gè)已排序的組，即完成排序。所需要的比較次數(shù)為nlog 2 n，移動(dòng)次數(shù)為n。若表已排好序，則比較次數(shù)仍為nlog 2 n，但移動(dòng)次數(shù)為0。
     5.快速排序
     快速排序的基本思想是把表中某元素作為基準(zhǔn)，將表劃分為大于該值和小于該值的兩部分，然后用遞歸的方法處理這兩個(gè)子表，直到完成整個(gè)表的排序?？焖倥判虻谋容^次數(shù)為（n-1）+（n-2）+…+1=n（n-1）/2，移動(dòng)次數(shù)最多也是n（n-1）/2。如果每次的基準(zhǔn)元素剛好是表的中值，使表分為大小相等的兩個(gè)子表，則比較次數(shù)為nlog 2 n;如果表已排好序，則移動(dòng)次數(shù)為0。
     6.常用排序方法的性能比較如下表所示:
     常用排序方法的性能比較
     排序方法 平均時(shí)間 最壞情況的時(shí)間 輔助存儲
     冒泡法、直接選擇法、直接插入法 O（n2 ） O（n2 ） O（1）
     快速排序 O（nlog2 n） O（n2 ） O（log2 n）
     堆排序 O（nlog2n） O（nlog2 n） O（1）
     歸并排序 O（nlog2 n） O（nlog2 n） O（n）
     注:在上表中，我們將n（n-1）/2也記為O（n2 ）。如果在待排序的表中含有多個(gè)碼值相同的記錄，經(jīng)過排序后，這些記錄的相對次序不變，則稱這種排序方法是穩(wěn)定的，否則是不穩(wěn)定的。根據(jù)上述說法，可以看出直接插入法、歸并法是穩(wěn)定的;而直接選擇法、冒泡法、快速排序法、堆排序法是不穩(wěn)定的。