綜合實(shí)踐課程《創(chuàng)新思維-程序設(shè)計(jì)（高級(jí)班）》（論文）排序算法

1、綜合實(shí)踐課程創(chuàng)新思維-程序設(shè)計(jì)（高級(jí)班）（論文）排序算法摘 要排序是計(jì)算機(jī)內(nèi)經(jīng)常進(jìn)行的一種操作，其目的是將一組“無(wú)序”的記錄序列調(diào)整為“有序”的記錄序列。將雜亂無(wú)章的數(shù)據(jù)元素，通過(guò)一定的方法按關(guān)鍵字順序排列的過(guò)程叫做排序。假定在待排序的記錄序列中，存在多個(gè)具有相同的關(guān)鍵字的記錄，若經(jīng)過(guò)排序，這些記錄的相對(duì)次序保持不變，即在原序列中，ri=rj，且ri在rj之前，而在排序后的序列中，ri仍在rj之前，則稱這種排序算法是穩(wěn)定的；否則稱為不穩(wěn)定的。 很多題目，當(dāng)獲取信息后，需要將信息進(jìn)行排序處理，這樣才便于對(duì)這些信息的利用，所以，也可以說(shuō)，排好序是處理好一個(gè)題目第一步的關(guān)鍵。關(guān)鍵詞：穩(wěn)定排序；不穩(wěn)定

2、排序；快速排序；時(shí)間復(fù)雜度.目錄常見(jiàn)的排序算法排序的分類常見(jiàn)排序冒泡排序快速排序桶排序排序算法的應(yīng)用例1.例2.優(yōu)缺點(diǎn)總結(jié)致謝參考文獻(xiàn)一、常見(jiàn)的排序算法1.排序的分類 （1）分類 穩(wěn)定排序：假設(shè)在待排序的文件中，存在兩個(gè)或兩個(gè)以上的記錄具有相同的關(guān)鍵字，在用某種排序法排序后，若這些相同關(guān)鍵字的元素的相對(duì)次序仍然不變，則這種排序方法是穩(wěn)定的。其中冒泡，插入，基數(shù)，歸并屬于穩(wěn)定排序，選擇，快速，希爾，堆屬于不穩(wěn)定排序。就地排序：若排序算法所需的輔助空間并不依賴于問(wèn)題的規(guī)模n，即輔助空間為O（1）,則稱為就地排序。 （2）常見(jiàn)排序 不穩(wěn)定排序算法：快速排序、希爾排序、選擇排序 穩(wěn)定排序算法：冒泡排序

3、、直接插入排序、歸并排序2.常見(jiàn)排序（1）冒泡排序 簡(jiǎn)介：冒泡排序是一種較簡(jiǎn)單的排序算法。它重復(fù)地走訪過(guò)要排序的數(shù)列，一次比較兩個(gè)元素，如果他們的順序錯(cuò)誤就把他們交換過(guò)來(lái)。走訪數(shù)列的工作是重復(fù)地進(jìn)行直到?jīng)]有再需要交換，也就是說(shuō)該數(shù)列已經(jīng)排序完成。這個(gè)算法的名字由來(lái)是因?yàn)樵酱蟮脑貢?huì)經(jīng)由交換慢慢“浮”到數(shù)列的頂端，故名。 冒泡排序十分穩(wěn)定，但速度慢，時(shí)間復(fù)雜度為O（n2）。Pascal 代碼框架： for i: =1 to n-1 do begin k:=ifor j:=i+1 to n do if ajai then begin tmp:=ai; ai:=aj; aj:=tmp; end； e

4、nd; （2）快速排序 簡(jiǎn)介：快速排序是對(duì)冒泡排序的一種改進(jìn)。它的基本思想是：通過(guò)一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個(gè)排序過(guò)程可以遞歸進(jìn)行，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列。 快速排序是已知排序中，速度最快的一種，二分的思想，能讓大部分時(shí)間節(jié)省，時(shí)間復(fù)雜度最快達(dá)O（nlog2n），但如果遇到最壞情況，就會(huì)退化成冒泡。但你的運(yùn)氣不可能那么好，所以，我個(gè)人推薦使用快排。Pascal 代碼框架： procedureqs(l,r:integer);vari,j,m,t:integer;begini:

5、=l;j:=r;m:=a(l+r)div2;repeatwhileaimdodec(j);ifij;ifljthenqs(l,j);ifi0do begin write(i:6); ai:=ai-1; end;排序算法的應(yīng)用例1： 明明的隨機(jī)數(shù)【問(wèn)題描述】明明想在學(xué)校中請(qǐng)一些同學(xué)一起做一項(xiàng)問(wèn)卷調(diào)查，為了實(shí)驗(yàn)的客觀性，他先用計(jì)算機(jī)生成了N個(gè)1到1000之間的隨機(jī)整數(shù)（N100），對(duì)于其中重復(fù)的數(shù)字，只保留一個(gè)，把其余相同的數(shù)去掉，不同的數(shù)對(duì)應(yīng)著不同的學(xué)生的學(xué)號(hào)。然后再把這些數(shù)從小到大排序，按照排好的順序去找同學(xué)做調(diào)查。請(qǐng)你協(xié)助明明完成“去重”與“排序”的工作。輸入：第1行為1個(gè)正整數(shù)，表示所生成

6、的隨機(jī)數(shù)的個(gè)數(shù)：N；第2行有N個(gè)用空格隔開(kāi)的正整數(shù)，為所產(chǎn)生的隨機(jī)數(shù)。輸出：也是2行，第1行為1個(gè)正整數(shù)M，表示不相同的隨機(jī)數(shù)的個(gè)數(shù)。第2行為M個(gè)用空格隔開(kāi)的正整數(shù)，為從小到大排好序的不相同的隨機(jī)數(shù)。 【輸入樣例】 1020 40 32 67 40 20 89 300 400 15 【輸出樣例】 815 20 32 40 67 89 300 400解析：因?yàn)榇祟}數(shù)據(jù)范圍并不大（ai1000），所以此題可用桶排序來(lái)解決，將會(huì)比冒泡排序時(shí)間效率高。 代碼： var a:array1.100 of integer; b:array1.1000 of integer; s,i,n:integer; b

7、egin readln(n); for i:=1 to n do read(ai); readln; for i:=1 to n do inc（bai） s:=0; for i:=1 to 1000 do if bi=1 then inc(s); writeln(s); for i:=1 to 1000 do if bi1 then write(i, ); writeln; end. 例2：分?jǐn)?shù)的眾數(shù) 【問(wèn)題描述】 期末考試結(jié)束了，老師們改完了試卷，將他們將改好的分?jǐn)?shù)排完名，發(fā)現(xiàn)有很多分?jǐn)?shù)相同，請(qǐng)你找出相同次數(shù)最多的分?jǐn)?shù)（滿分一百分，分?jǐn)?shù)保留一位小數(shù)），若有多個(gè)相同次數(shù)相同的分?jǐn)?shù)，按分?jǐn)?shù)從小到

8、大輸出。 輸入：第一行為一個(gè)正整數(shù)n(n)，表示有n個(gè)成績(jī)；第二行有n個(gè)數(shù)為每一個(gè)成績(jī)。輸出： 只有一行，相同次數(shù)最多的分?jǐn)?shù)。 【輸入樣例】 5 95.2 98.7 98.7 95.2 93.6 【輸出樣例】 95.2 98.7解析：這一題n的數(shù)值很大，很明顯得用桶排，可這里的分?jǐn)?shù)中含有小數(shù)，不少同學(xué)在此處無(wú)從下手，其實(shí)，只要將分?jǐn)?shù)乘10保存就可以了。例3： 車廂重組【問(wèn)題描述】在一個(gè)舊式的火車站旁邊有一座橋，其橋面可以繞河中心的橋墩水平旋轉(zhuǎn)。一個(gè)車站的職工發(fā)現(xiàn)橋的長(zhǎng)度最多能容納兩節(jié)車廂，如果將橋旋轉(zhuǎn)180度，則可以把相鄰兩節(jié)車廂的位置交換，用這種方法可以重新排列車廂的順序。于是他就負(fù)責(zé)用這座

9、橋?qū)⑦M(jìn)站的車廂按車廂號(hào)從小到大排列。他退休后，火車站決定將這一工作自動(dòng)化，其中一項(xiàng)重要的工作是編一個(gè)程序，輸入初始的車廂順序，計(jì)算最少用多少步就能將車廂排序。輸入：輸入文件有兩行，第一行是車廂總數(shù)N（不大于1000），第二行是N個(gè)不同的數(shù)表示初始的車廂順序。輸出：一個(gè)數(shù)據(jù)，是最少的旋轉(zhuǎn)次數(shù)。 【輸入樣例】44 3 2 1 【輸出樣例】6 代碼：var a:array1.maxint of integer; i,j,k,n,m,c:longint; begin readln(n); for i:=1 to n do read(ai); for i:=1 to n do for j:=1 to n do begin if i=aj then begin c:=j; while ic do begin c:=c-1;m:=m+1; k:=ac; ac:=ac+1; ac+1:=k; end; end; end; writ