數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計(jì)王麗蘋20sorting

1、10/21/2021數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計(jì) 1數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計(jì)(20) (20) 王麗蘋10/21/2021數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計(jì) 2chapter 8 sorting 排序n什么是排序？什么是排序？n設(shè)有設(shè)有n個(gè)結(jié)點(diǎn)的一個(gè)序列個(gè)結(jié)點(diǎn)的一個(gè)序列r1，r2，rn，它們對(duì)應(yīng)，它們對(duì)應(yīng)的關(guān)鍵字值序列為的關(guān)鍵字值序列為k1，k2，kn，排序就是要確，排序就是要確定出這定出這n個(gè)結(jié)點(diǎn)的一個(gè)新的序列個(gè)結(jié)點(diǎn)的一個(gè)新的序列rq1,rq2, rqn，這，這個(gè)新序列中結(jié)點(diǎn)的關(guān)鍵字個(gè)新序列中結(jié)點(diǎn)的關(guān)鍵字kq1，kq2，kqn滿足遞滿足遞增或遞減的關(guān)系，即增或遞減的關(guān)系，即kq1kq2kqn; 或或kq1

2、kq2kqn；10/21/2021數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計(jì) 3排序方法的穩(wěn)定性n排序的過程中，如果具有相同關(guān)鍵字的那些結(jié)點(diǎn)排序前后它們?cè)诮Y(jié)點(diǎn)序列中的先后相對(duì)次序保持不變，則稱這種排序方法是穩(wěn)定的；否則，稱這種排序方法是不穩(wěn)定的。例如：一組數(shù) 5，2，6，3， 2 ，用一種排序方法排序后，這組數(shù)成為：2， 2 ，3，5，6n則這種排序方法是穩(wěn)定的。n而用另一種排序方法排序后，這組數(shù)成為：n 2 ， 2 ，3，5，6n則這種排序方法是不穩(wěn)定的。10/21/2021數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計(jì) 4sortable_listn本章排序算法主要是針對(duì)本章排序算法主要是針對(duì) list，list的的元素內(nèi)容為元素內(nèi)容為re

3、cord。nrecord類型在第七章定義，包括類型在第七章定義，包括key和和other兩個(gè)數(shù)據(jù)成員。兩個(gè)數(shù)據(jù)成員。nlist類型在第六章定義。關(guān)于順序列表和類型在第六章定義。關(guān)于順序列表和鏈表的排序問題在本章都將有討論。鏈表的排序問題在本章都將有討論。n目錄目錄sortable_list下例程下例程,需要你來補(bǔ)充。需要你來補(bǔ)充。10/21/2021數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計(jì) 5sortable_listn#include list.cppn#include record.hnclass sortable_list: public list npublic: / add prototypes for

4、sorting methods here.nvoid insertion_sort( ); /插入排序插入排序n/for selection_sort. /選擇排序選擇排序nvoid swap(int low, int high);nint max_key(int low, int high);nvoid selection_sort( );n/for shell_sort. 希爾排序希爾排序nvoid sort_interval(int start, int increment);nvoid shell_sort();nprivate: / add prototypes for auxili

5、ary functions here.n;10/21/2021數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計(jì) 6插入排序n有序表插入方法的回顧10/21/2021數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計(jì) 7插入排序（排序過程）10/21/2021數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計(jì) 8插入排序n插入步驟如下插入步驟如下: :n 對(duì)對(duì)n n個(gè)等待排序的結(jié)點(diǎn)序列個(gè)等待排序的結(jié)點(diǎn)序列d0,d1,.dn-1,d0,d1,.dn-1,已有已有s s個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)d0,d2,.ds-1d0,d2,.ds-1排好序排好序, ,所以存在不等式所以存在不等式d0=d1=.=ds-1d0=d1=.=ds-1，對(duì)下一個(gè)要插入的結(jié)點(diǎn)，對(duì)下一個(gè)要插入的結(jié)點(diǎn)ds,ds,首首先將先將dsds

6、的值送到一個(gè)臨時(shí)的變量的值送到一個(gè)臨時(shí)的變量t,t,然后用然后用t t值依次與排好值依次與排好序的結(jié)點(diǎn)序列中的序的結(jié)點(diǎn)序列中的ds-1,ds-2.d0ds-1,ds-2.d0進(jìn)行比較進(jìn)行比較, ,并且將比并且將比t t大的結(jié)點(diǎn)依次右移一個(gè)位置大的結(jié)點(diǎn)依次右移一個(gè)位置. .如果存在某個(gè)如果存在某個(gè)dm(0=m=s-dm(0=m=dmt=dm, ,則把則把t t送到送到dm+1;dm+1;如果這樣的如果這樣的dmdm不存在不存在, ,那那么在比較過程中么在比較過程中,ds-1,ds-2,.d0,ds-1,ds-2,.d0都依次后移了一個(gè)都依次后移了一個(gè)位置位置, ,最后在最后在d0d0中放置中放置

7、t t。10/21/2021數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計(jì) 9插入排序（穩(wěn)定的）10/21/2021數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計(jì) 10sortable_list p322nvoid sortable_list : insertion_sort( )n/* post: the entries of the sortable list have been rearranged so that the keys in allnthe entries are sorted into nondecreasing order.nuses: methods for the class record ; the contiguou

8、s list implementation of chapter 6 */nnint first_unsorted; / position of first unsorted entrynint position; / searches sorted part of listnrecord current; / holds the entry temporarily removed from listnfor (first_unsorted = 1; first_unsorted count; first_unsorted+)nif (entryfirst_unsorted 0 & entry

9、position - 1 current);nentryposition = current;nn 10/21/2021數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計(jì) 11效率分析n順序表插入排序的效率：n每插入一個(gè)值，平均需要比較的次數(shù)為：i/2i為已經(jīng)排序的元素個(gè)數(shù)。比較的總次數(shù)約為：1/2+2/2+(n-1)/21/4n2移動(dòng)次數(shù)與比較次數(shù)相同。n請(qǐng)考慮：n插入排序的最好情況是什么？n插入排序的最壞情況是什么？10/21/2021數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計(jì) 12選擇排序選擇排序 n選擇排序的方法是：每次從待排序結(jié)點(diǎn)序列中選選擇排序的方法是：每次從待排序結(jié)點(diǎn)序列中選出結(jié)點(diǎn)值出結(jié)點(diǎn)值最小或最大最小或最大的，然后將它放在已排好序

10、的，然后將它放在已排好序的結(jié)點(diǎn)序列的的結(jié)點(diǎn)序列的尾部或前部尾部或前部，直到待排序序列已無，直到待排序序列已無任何結(jié)點(diǎn)。任何結(jié)點(diǎn)。n一種算法是：對(duì)一種算法是：對(duì)n n個(gè)待排序結(jié)點(diǎn)做個(gè)待排序結(jié)點(diǎn)做n-1n-1次的掃描，第一次掃次的掃描，第一次掃描找出整個(gè)結(jié)點(diǎn)序列中結(jié)點(diǎn)值最小的，并且將它與第一個(gè)描找出整個(gè)結(jié)點(diǎn)序列中結(jié)點(diǎn)值最小的，并且將它與第一個(gè)結(jié)點(diǎn)交換位置。第二次掃描從第二個(gè)結(jié)點(diǎn)開始，找出剩余結(jié)點(diǎn)交換位置。第二次掃描從第二個(gè)結(jié)點(diǎn)開始，找出剩余的的n-1n-1個(gè)結(jié)點(diǎn)中結(jié)點(diǎn)值最小的，并把它與第二個(gè)結(jié)點(diǎn)交換個(gè)結(jié)點(diǎn)中結(jié)點(diǎn)值最小的，并把它與第二個(gè)結(jié)點(diǎn)交換位置位置，如此重復(fù)至，如此重復(fù)至n-1n-1次。則整個(gè)結(jié)

11、點(diǎn)序列已是排好序。次。則整個(gè)結(jié)點(diǎn)序列已是排好序。 10/21/2021數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計(jì) 13選擇排序執(zhí)行過程選擇排序執(zhí)行過程(不不穩(wěn)定的) 10/21/2021數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計(jì) 14sortable_listnvoid sortable_list : selection_sort( )n/* post: the entries of the sortable list have been rearranged so that the keys in all the entries are sorted into nondecreasing order.nuses: max_key ,swa

12、p . */nnfor (int position = 0; position count-1; position+) nint min = min_key(position, count-1);nswap(min, position);n n10/21/2021數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計(jì) 15sortable_listnint sortable_list : min_key(int low, int high)nnint min, current;nmin = low;nfor (current = low + 1; current entrycurrent)nmin = current;nretu

13、rn min;n10/21/2021數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計(jì) 16sortable_listnvoid sortable_list : swap(int low, int high)n/* pre: low and high are valid positions in the sortable list .npost: the entry at position low is swapped with the entry at position high .nuses: the contiguous list implementation of chapter 6. */nnrecord temp

14、;ntemp = entrylow;nentrylow = entryhigh;nentryhigh = temp;n10/21/2021數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計(jì) 17sortable_listnvoid sortable_list : selection_sort( )n/* post: the entries of the sortable list have been rearranged so that the keys in all the entries are sorted into nondecreasing order.nuses: max_key ,swap . */nnfor

15、(int position = count - 1; position 0; position-) nint max = max_key(0, position);nswap(max, position);n n10/21/2021數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計(jì) 18sortable_listnint sortable_list : max_key(int low, int high)n/* pre: low and high are valid positions in the sortable list and low = high .npost: the position of the entry

16、between low and high with the largest key is returned.nuses: the class record . the contiguous list implementation of chapter 6. */nnint largest, current;nlargest = low;nfor (current = low + 1; current = high; current+)nif (entrylargest entrycurrent)nlargest = current;nreturn largest;n10/21/2021數(shù)據(jù)結(jié)構(gòu)

17、與程序設(shè)計(jì) 19選擇排序分析n特點(diǎn)： 選擇排序的最壞情況和最好情況下的實(shí)際沒有太大區(qū)別。即選擇排序?qū)τ谠加涗浀捻樞虿幻舾小選擇排序的比較次數(shù)分析： n每一次的比較次數(shù)求和：n(n-1)+(n-2)+.+11/2n2n總移動(dòng)次數(shù)為：3(n-1)10/21/2021數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計(jì) 20選擇和插入排序?qū)Ρ?0/21/2021數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計(jì) 21shell sortn在插入排序中，比較結(jié)點(diǎn)的值時(shí)，每次至多把結(jié)點(diǎn)移動(dòng)一個(gè)位置（當(dāng)tdm時(shí)，才把dm向“后” 移動(dòng)一位）。希爾排序的想法是：如果能夠把相對(duì)位置較遠(yuǎn)的結(jié)點(diǎn)進(jìn)行比較，使得結(jié)點(diǎn)在比較后能夠一次移動(dòng)較大的距離。這樣處理可以把值較小的結(jié)點(diǎn)盡快

18、往前移，值較大的結(jié)點(diǎn)盡快往后移，希望以此提高排序的效率。 n算法如下：n首先將整個(gè)待排序結(jié)點(diǎn)序列分割成若干個(gè)子序列，然后對(duì)各個(gè)子序列分別執(zhí)行插入排序；當(dāng)各個(gè)子序列排好序后，整個(gè)文件就有序了些；多次重復(fù)上述過程，最終實(shí)現(xiàn)全部結(jié)點(diǎn)的排序。10/21/2021數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計(jì) 22shell sortn第一步，increment=510/21/2021數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計(jì) 23shell sortn第二步，increment=3 第三步，increment=110/21/2021數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計(jì) 24shell sortnbook p334 figure 8.7n取不同的增量序列，會(huì)有不同的比較次

19、數(shù)。另外，至今沒有一種最好的增量序列。但是肯定的是，無論哪種增量序列，最后一個(gè)增量值必須為。n大量實(shí)例表明：希爾排序的速度要比插入排序快得多。另外，希爾排序是不穩(wěn)定的。10/21/2021數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計(jì) 25shell sortnvoid sortable_list : shell_sort( )n/* post: the entries of thesortable list have been rearranged so that the keys in allnthe entries are sorted into nondecreasing order.nuses: sort_in

20、terval */nnint increment, / spacing of entries in sublistn start; / starting point of sublistnincrement = count;ndo nincrement = increment/3 + 1;nfor (start = 0; start 1);n 10/21/2021數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計(jì) 26shell sort (compare with p322)void sortable_list : sort_interval(int start, int increment)int first_unsor

21、ted; / position of first unsorted entryint position; / searches sorted part of listrecord current; / holds the entry temporarily removed from listfor (first_unsorted = start + increment; first_unsorted count; first_unsorted += increment ) if (entryfirst_unsorted start & entryposition - increment cur

22、rent);entryposition = current;/上述算法和插入排序的區(qū)別上述算法和插入排序的區(qū)別10/21/2021數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計(jì) 27mainnvoid main()nsortable_list mylist;nfor(int i=0; i10; i+) mylist.insert(i,record(10-i,10);ncoutthe list is: endl;nmylist.traverse(print);nncoutendluse insertion_sort method:endl;nmylist.insertion_sort();nmylist.traverse(

23、print);ncoutendluse selection_sort method:endl;nmylist.selection_sort();nmylist.traverse(print);nncoutendluse shell_sort method:endl;nmylist.shell_sort();nmylist.traverse(print);ncin.get();n10/21/2021數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計(jì) 28linked_sortable_listn上機(jī)：上機(jī)： n（1）請(qǐng)上機(jī)完成鏈表的插入排序操作，）請(qǐng)上機(jī)完成鏈表的插入排序操作，參考目錄參考目錄linked_sortable_l

24、ist下例程下例程nbook p325 figure 8.410/21/2021數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計(jì) 29linked_sortable_list(book p324)void sortable_list : insertion_sort( ) node *first_unsorted, / the first unsorted node to be inserted*last_sorted, / tail of the sorted sublist*current, / used to traverse the sorted sublist*trailing; / one position behindcurrent if (head != null) / otherwise, the empty list is already sorted.last_sorted = head; / the first node alone makes a sorted sublist.while (last_sorted-next != null) first_unsorted = last_sorted-next;if (first_unsorted-entry entry) / insert *first_unso