排序算法的分析與總結

【摘要】排序的功能是將一組“無序”的記錄序列按照一定的方法調整成為“有序”的序列，這是計算機內進行的一種常見操作，也是一種重要的操作。若是按照在排序中涉及的存儲器的不同，來對排序進行劃分，可以分內部排序和外部排序。本文是就常見的幾種內部排序的方法進行分析與比較。

【關鍵詞】時間復雜度；關鍵字

排序（sorting）又稱分類，是計算機程序設計中的一個重要操作，即把一批任意序列的數據元素（或記錄），重新排列成一個按關鍵字有序的序列。通過排序可以提高數據表的直觀性，并為以后查詢提供方便，提高查找效率。

排序（sorting）又稱分類，是計算機程序設計中的一個極其重要的操作，應用極其廣泛，如電話簿、病歷、檔案等等。排序就是把任意序列的數據元素，重新排列成一個按某種關鍵字形成有序的序列。排序之后可以提高數據表的直觀性，方便查詢，并提高查找效率。

一、插入排序

1、直接插入排序

直接插入排序（straight insertion sort）是一種最簡單的排序方式。這種排序的操作就是將一個記錄或數據元素插入到一個長度為n的有序表中，使表仍保持有序，會得到一個新的長度為n+1的有序表。

算法思路：設有一組關鍵字{k1，k2，…，kn}；在這里k1是一個有序的序列；讓k2插入這個只有1個記錄的的序列中，使之成為一個有2個記錄的有序序列；以此類推，最后讓kn插入到表長為n-1的有序序列中，得到一個表長為n的有序序列。

2、折半插入排序

當用直接插入排序進行到某一趟比較時，對于r[i].key來講，前邊i-1個記錄已經按關鍵字排序。……