課程設計5812483297

1、塔里木大學信息工程學院課程設計第1頁共9頁前言本次我的課程設計是關于數(shù)據(jù)排序的。至如今，排序方法越來越多，而關于排序的要求也越來越嚴格。首先，我介紹一下排序一個重要要求：排序算法的穩(wěn)定性。通俗地講就是能保證排序前2個相等的數(shù)其在序列的前后位置順序和排序后它們兩個的前后位置順序相同。在簡單形式化一下，如果Ai=AjAi原來在位置前，排序后Ai還是要在Aj位置前。排序算法如果是穩(wěn)定的，那么從一個鍵上排序，然后再從另一個鍵上排序，第一個鍵排序

2、的結果可以為第二個鍵排序所用。基數(shù)排序就是這樣，先按低位排序，逐次按高位排序，低位相同的元素其順序再高位也相同時是不會改變的。另外，如果排序算法穩(wěn)定，對基于比較的排序算法而言，元素交換的次數(shù)可能會少一些。其次，我們介紹一下現(xiàn)在的常用排序算法：選擇排序、快速排序、希爾排序、堆排序、冒泡排序、插入排序、歸并排序和基數(shù)排序等。選擇排序就是選擇排序是給每個位置選擇當前元素最小的，比如給第一個位置選擇最小的，在剩余元素里面給第二個元素選擇第二小的

3、，依次類推，直到第n1個元素。冒泡排序指冒泡排序就是把小的元素往前調(diào)或者把大的元素往后調(diào)。比較是相鄰的兩個元素比較，交換也發(fā)生在這兩個元素之間。插入排序指插入排序是在一個已經(jīng)有序的小序列的基礎上，一次插入一個元素。當然，剛開始這個有序的小序列只有1個元素，就是第一個元素。比較是從有序序列的末尾開始，也就是想要插入的元素和已經(jīng)有序的最大者開始比起，如果比它大則直接插入在其后面，否則一直往前找直到找到它該插入的位置。快速排序就是快速排序有兩

4、個方向，左邊的i下標一直往右走，當a[i]a[center_index]。如果i和j都走不動了，ij。交換a[j]和a[center_index]，完成一趟快速排序。在此，我就介紹這幾種排序其他排序就不一一介紹了。本次課設，我主要以直接插入排序為主。工程概況工程概況2.1項目所用的時間從這個項目開始到結束總共歷時7天。完成于2011年12月18日。塔里木大學信息工程學院課程設計第3頁共9頁牌的過程。插入排序的基本方法是：每步將一個待排序

5、的記錄按其關鍵字的大小插到前面已經(jīng)排序的序列中的適當位置，直到全部記錄插入完畢為止。注意，在直接插入排序中，需要一個哨兵。而對于哨兵有兩個作用：①進人查找(插入位置)循環(huán)之前，它保存了R[i]的副本，使不致于因記錄后移而丟失R[i]的內(nèi)容；②它的主要作用是：在查找循環(huán)中“監(jiān)視“下標變量j是否越界。一旦越界(即j=0)，因為R[0].key和自己比較，循環(huán)判定條件不成立使得查找循環(huán)結束，從而避免了在該循環(huán)內(nèi)的每一次均要檢測j是否越界(即省

6、略了循環(huán)判定條件“j=1“)。3.1.2折半插入排序折半插入排序是利用折半查找來實現(xiàn)的，它是插入排序的一種，它只是利用了折半查找減少了關鍵字的比較次數(shù)，而記錄的移動次數(shù)不變！其時間復雜度為O（nn）！3.1.32路插入排序在折半插入排序的基礎上在改進之，其目的是減少排序過程中移動記錄的次數(shù)，但為此需要n個記錄的輔助空間。具體做法是：另設一個和l.r同類型的數(shù)據(jù)d，首先將l.r[1]賦值個d[1]并將d[1]看成是在排號序的序列中處于中間

7、位置的記錄，然后在l.r中第二個記錄起依次插入到d[1]之前或之后的有序序列中。先將待插記錄的關鍵字和d[1]的關鍵字進行比較，若lr[i].kayright，然后再把第i個元素前1位與目標位置之間的所有元素后移，再把第i個元素放在目標位置上。二分法沒有排序，只有查找。所以當找到要插入的位置時。移動必須從最后一個記錄開始，向后移動一位，再移動倒數(shù)第2位，直到要插入的位置的記錄移后一位。3.1.5希爾排序希爾排序(ShellSt)是插入排