6排序數據結構6排序6排序主要內容排序的基本概念簡單排序方法★選擇排序★插入排序★起泡排序◆先進排序方法★快速排序★歸并排序★基數排序61排序的基本概念排序是計算機內經常進行的一種操作,其目的是將一組“無序”的記錄序列調整為“有序”的記錄序列。例如:將下列關鍵字序列52,49,80,36,14358,61,23,97,75調整為1423,36,49,52,58,61,75,80,97定義假設含n個記錄的序列為{R1,R2…,Rn}其相應的關鍵字序列為{K1K2…,K這些關鍵字相互之間可以進行比較,即在它們之間存在著這樣按此固有關系將上式記錄序列重新排列為Rony的操作稱作排序。主要內容排序的基本概念簡單排序方法★選擇排序★插入排序★起泡排序◆先進排序方法★快速排序★歸并排序★基數排序61排序的基本概念排序是計算機內經常進行的一種操作,其目的是將一組“無序”的記錄序列調整為“有序”的記錄序列。例如:將下列關鍵字序列52,49,80,36,14358,61,23,97,75調整為1423,36,49,52,58,61,75,80,97定義假設含n個記錄的序列為{R1,R2…,Rn}其相應的關鍵字序列為{K1K2…,K這些關鍵字相互之間可以進行比較,即在它們之間存在著這樣按此固有關系將上式記錄序列重新排列為Rony的操作稱作排序。61排序的基本概念typedefintKeyType;∥關健字類型為整數typedefstructtKeyTypekey;∥關鍵字項infoTypeOtherlnfo;∥其它信息IRetYpe;∥記錄類型61排序的基本概念★排序分類按待排序記錄所在位置●內部排序:待排序記錄存放在內存●外部排序:排序過程中需對外存進行訪問的排序按排序依據原則●插入排序:直接插入排序、折半插入排序、希爾排序●交換排序:冒泡排序、快速排序●選擇排序:簡單選擇排序、堆排序●歸并排序:2-路歸并排序●基數排序排序穩定性61排序的基本概念★按排序所需工排序算法的思想:簡單的排序將待排序列看成是看成是有有序序列和>先進的排序無序序列組成,每次排序都會按照某種基數排序:原則將無序序列中的某個元素取出,放★排序基太操作在有序序列中,這樣經n1次操作就會將內部排序的過程是一個逐步擴大記錄的有序序列長度的過程。有序序列R1…i無序序列R[i+1,n61排序的基本概念基于不同的“擴大”有序序列長度的方法,內部排序方法大致可分下列幾種類型:插入類交換類選擇類歸并類其它方法61排序的基本概念◆插入類排序★將無序子序列中的一個或幾個記錄“插入”到有序序列中,從而增加記錄的有序子序列的長度。◆交換類排序★通過“交換”無序序列中的記錄從而得到其中關鍵字最小或最大的記錄,并將它加入到有序子序列中,以此方法增加記錄的有序子序列的長度。◆選擇類排序★從記錄的無序子序列中“選擇”關鍵字最小或最大的記錄,并將它加入到有序子序列中,以此方法增加記錄的有序子序列的長度。◆歸并類排序★通過“歸并”兩個或兩個以上的記錄有序子序列,逐步增加記錄有序序列的長度。◆其它類排序62插入排序◆6.21直接插入排序◆622二分(折半)插入排序◆623希爾排序621直接插入排序☆插入排序過程:★整個排序過程為n-1趟插入,即先將序列中第1個記