資源描述：
《【數據結構與算法】排序》由會員上傳分享，免費在線閱讀，更多相關內容在教育資源-天天文庫。
1、第十章內部排序10.1概述10.2插入排序10.2.1直接插入排序10.2.3shell排序10.3交換排序（快速排序）10.4選擇排序10.4.1簡單選擇排序10.4.3堆排序10.5歸并排序10.6基數排序10.7各種排序方法的比較討論10.1內部排序概述排序(Sorting):將數據元素(或記錄)的一個任意序列,重新排列成一個按關鍵字有序的序列。排序方法的穩(wěn)定性：對關鍵字相同的數據元素，排序前后它們的領先關系保持不變，則稱該排序方法是穩(wěn)定的。反之，稱該排序方法是不穩(wěn)定的。內部排序待排序記錄存放在計算機的內存中進行排序。外部排序待排序記錄的數量很大，以致內存一次不能容納全部記錄，
2、在排序過程中尚需對外存進行訪問的排序。排序的分類按排序過程依據的不同原則進行分類：插入排序、交換排序、選擇排序、歸并排序和基數排序按工作量分類，可以分為三類：(1)簡單的排序方法,其時間復雜度為O(n2);(2)先進的排序方法,其時間復雜度為O(nlog2n);(3)基數排序，其時間復雜度為O(dn);排序的基本操作和 記錄的存儲方式排序過程中需要的兩種基本操作：（1）比較關鍵字的大??；（2）將記錄從一個位置移至另一個位置。待排序記錄序列可有下列三種存儲方式：（1）記錄存放在一組連續(xù)的存儲單元中；類似于線性表的順序存儲結構，記錄次序由存儲位置決定，實現排序需移動記錄。（2）記錄存放在
3、靜態(tài)鏈表中；記錄次序由指針指示，實現排序不需移動記錄，僅需修改指針。---鏈排序（3）記錄本身存放在一組連續(xù)的存儲單元中，同時另設指示各個記錄存儲位置的地址向量，排序過程中不移動記錄本身，而移動地址向量中相應記錄的地址。排序結束后再根據地址調整記錄的存儲位置。---地址排序待排序記錄的數據類型#defineMAXSIZE20typedefintKeyType;typedefstruct{KeyTypekey;InfoTypeotherinfo;}RcdType;typedefstruct{RedTyper[MAXSIZE+1];intlength;}SqList;10.2插入排序 1
4、0.2.1直接插入排序例：序列為{49，38，65，97，76，13，27，49}{(49)，38，65，97，76，13，27，49}(38){(38，49)，65，97，76，13，27，49}(65){(38，49，65)，97，76，13，27，49}(97){(38，49，65，97)，76，13，27，49}(76){(38，49，65，76，97)，13，27，49}(13){(13，38，49，65，76，97)，27，49}(27){(13，27，38，49，65，76，97)，49}(49){(13，27，38，49，49，65，76，97)}直接插入排序算法vo
5、idInsertSort(SqList&L){for(i=2;i<=L.length;++i)if(LT(L.r[i].key,L.r[i-1].key)){L.r[0]=L.r[i];//復制為哨兵for(j=i-1;LT(L.r[0].key,L.r[j].key);--j)L.r[j+1]=L.r[j];//記錄后移L.r[j+1]=L.r[0];}}//InsertSort時間：最壞情形判斷與移動各接近n(n+1)/2;最好情形判斷n次，無移動；故時間復雜度：O(n2)空間：一個輔助空間10.2.2Shell排序算法基本思想：先將整個待排序記錄序列分割成若干子序列分別進行直接
6、插入排序，待整個序列“基本有序”時，再對全體記錄進行一次直接插入排序。算法復雜度：O(n3/2)Shell排序舉例（非穩(wěn)定的）二趟結果{13，04，49，38，27，49，55，65，97，76}增量取1：13，04，49，38，27，49，55，65，97，76三趟結果{04，13，27，38，49，49，55，65，76，97}一趟結果{13，27，49，55，04，49，38，65，97，76}增量取3：13553876270465494997例：{49，38，65，97，76，13，27，49，55，04}增量取5：4913382765499755760410.3交換排序 1
7、.冒泡排序（其時間復雜度O(n2)）初始關鍵字第一趟排序后第二趟排序后第三趟排序后第四趟排序后第五趟排序后第六趟排序后例：49383838381313384949491327276565651327383897761327494976132749491327496527497649972.快速排序 -----對冒泡排序的一種改進基本思想：通過一趟排序將待排序記錄分割成獨立的兩部分，其中一部分的關鍵字均比另一部分的關鍵字小，則可分別對這兩部分記錄繼續(xù)分別進行
