冒泡排序、選擇排序、堆排序算法課程設(shè)計(jì)

1、日 年 6 月 日排序是計(jì)算機(jī)程序設(shè)計(jì)的一種重要操作，它的功能是將一組任意順序的數(shù)據(jù)元素，根據(jù)一個或幾個關(guān)鍵字按照一定的順序重新排列成為有序的序列。.如何進(jìn)行排序，特別是高效地處理進(jìn)行排序是計(jì)算機(jī)應(yīng)用中的主要課題之一。由于待排序的記錄數(shù)量不同，使得排序過程中能涉及的存儲器不同，可將排序方法分為兩大類：一類是內(nèi)部排序，指的是待排序的記錄存放在計(jì)算機(jī)隨機(jī)存儲器中進(jìn)行的排序過程；另一類是外部排序，指的是待排序的記錄數(shù)量很大，以致內(nèi)存不能一次容納全部記錄，在排序過程中尚需要對外存進(jìn)行訪問的排序過程。本次課程設(shè)計(jì)就是研究內(nèi)部排序中的三個常用的排序方法：直接插入排序、冒泡排序、堆排序。分析排序的實(shí)質(zhì)，排序

2、的應(yīng)用。應(yīng)用 Java 語言采用數(shù)組存儲結(jié)構(gòu)實(shí)現(xiàn)了算法的時間復(fù)雜度分析結(jié)果及其分析方法，以便在實(shí)際應(yīng)用中，根據(jù)實(shí)際問題要求，選用合適的排序方法。本次課程設(shè)計(jì)目的是通過程序語言設(shè)計(jì)并實(shí)現(xiàn)三種排序算法，直接插入排序、冒泡排序、堆排序的綜合系統(tǒng)。通過對不同的數(shù)據(jù)計(jì)量進(jìn)行實(shí)際排序?qū)Y(jié)構(gòu)進(jìn)行分析，找出它們之間的優(yōu)勢和劣勢，并結(jié)合理論總結(jié)在實(shí)際運(yùn)用排序算法過程中需要注意的問題。1排序，輸出排序后的數(shù)據(jù)、數(shù)據(jù)的個數(shù)和排序所花費(fèi)的時間。分析在相同數(shù)據(jù)下，采用不同算法所耗時間的差別。1.2.1 選擇排序方法模塊21.3.3 堆排序堆的關(guān)系。堆排序大體分為兩步來處理。初建堆，從堆的定義出發(fā)，當(dāng) i=1、2、2/n

3、時應(yīng)該滿足 ki,=k2i+1。所以先取 i=n/2（它一定是第n i 結(jié)點(diǎn)為根的子書調(diào)整為堆，然后令 i=i-1。此時可能會反復(fù)調(diào)整某些結(jié)點(diǎn)，知道 i=1為止，堆初步建成。頂位置，然后恢復(fù)堆。因?yàn)榻?jīng)過第一步輸出堆頂元素的操作后，往往破壞了堆關(guān)系，所以要恢復(fù)堆；重復(fù)執(zhí)行輸出堆頂元素、堆尾元素上移和恢復(fù)的步驟。3排序綜合系統(tǒng)圖4開始生成界面輸出數(shù)據(jù)5假設(shè)待排序的記錄存放在數(shù)組 Rn中，排序過程的某一中間時刻，R 被劃分為兩個子區(qū)間R1,Ri-1和Ri,Rn-1，其中：前一個子區(qū)間是已經(jīng)排好序的有序區(qū)；后一個子區(qū)間則是當(dāng)前未排序的部分，不妨稱其未無序區(qū).直接插入排序的基本操作是將當(dāng)前無序區(qū)的第一個

4、記錄 Ri插入到有序區(qū)中適當(dāng)位置，使得 R1到 Ri變?yōu)樾碌挠行騾^(qū). Ri(i=2,3,n-1)入后仍保證該區(qū)間記錄是按關(guān)鍵字有序的.顯然，最簡單的方法是：首先，在當(dāng)前有序區(qū) R1到 Ri-1中查找 Ri的正確插入位置 k(1=k=0&listkcurrentElement;k-)設(shè)想排序的記錄數(shù)組 R0到 Rn-1 Ri看作是重量為 Ri的氣泡. R則的輕氣泡，就使其向上“漂浮”，如此反復(fù)進(jìn)行，直到最后任何兩個氣泡大神輕者在上，重者在下為止.初始時，R0到 Rn-1泡的重量，若發(fā)現(xiàn)輕者在下，重者在上，則交換兩者的位置.本掃描完畢時，最輕的氣泡就漂浮到頂上面，即關(guān)鍵字最小的記錄被放在最高位置

5、R0上.第二趟掃描時，只需掃視 R1到 Rn-1 R1的位置上. i 趟掃描時，R0到 Ri-1和 Ri到 Rn-1分別為當(dāng)前的有序區(qū)和無序區(qū)，掃描仍是從無序區(qū) RiR0到 Ri變?yōu)樾碌挠行騾^(qū).因?yàn)槊恳惶伺判蚨际褂行騾^(qū)增加了一個氣泡，在經(jīng)過n-1 趟排序之后，有序區(qū)中就有 n-1 個氣泡，而無序區(qū)中氣泡的重量總是大于等于有序區(qū)中的氣泡的重量，所以，整個冒泡排序過程至多需要進(jìn)行 n-1 趟排序.但是，若在某一趟排序中未發(fā)現(xiàn)氣泡位置的交換，則說明待排序的無序區(qū)中所有氣泡均滿足輕者在上，重者在下的原則，因此，冒泡排序過程可在此趟排序后終止.圖 1.1 中，在第四趟（圖中第六列）排序過程中就沒有氣泡交

6、換位置，此時整個文件已達(dá)到有序狀態(tài).744 11 11 11 11 11 11 11 1133 44 22 22 22 22 22 22 2266 33 44 33 33 33 33 33 3377 66 33 44 44 44 44 44 4488 77 66 66 66 55 55 55 5511 88 77 77 77 66 66 66 6622 22 88 88 88 77 77 77 7755 55 55 55 55 88 88 88 88圖 3.1 從下往上的冒泡排序public static void bubbleSor(double list)boolean needNextP

7、ass=true;for(int i=0;ilisti+1)double temp=listi;3.2.3 堆排序初建堆，從堆的定義出發(fā)，當(dāng) i=1、2、2/n時應(yīng)該滿足 ki,string=ta1.getText();/獲取輸入的數(shù)據(jù)string=InsertionSort.insertionSort(string);string=BubbleSort.bubbleSort(string);/如果rd3被選中，則執(zhí)行直接插入排序算法if(rd3.isSelected()string=HeapSort.heapSort(string);Scanner scan1=new Scanner(str

8、ing);Scanner scan2=new Scanner(string);/從排序算法返回字符串string中提取排序后的數(shù)據(jù)for(int j=0;j=0&listkcurrentElement;k-)for(;scan.hasNext();)d=scan.nextDouble();n=n+1;double list=new doublen;Scanner scanner=new Scanner(string);for(int i=0;scanner.hasNext();i+)returnString=returnString+time;return returnString;publi

9、c static void bubbleSor(double list)boolean needNextPass=true;for(int i=0;ilisti+1)double temp=listi;for(;scan.hasNext();)d=scan.nextDouble();n=n+1;double list=new doublen;Scanner scanner=new Scanner(string);for(int i=0;scanner.hasNext();i+)long startTime=System.nanoTime();bubbleSor(list);long endTi

10、me=System.nanoTime();long time=endTime-startTime;for(int j=0;jlist.length;j+)returnString+=listj+;returnString=returnString+time;return returnString;import java.util.Scanner;/*Heap sort method*/for(;scan.hasNext();)d=scan.nextDouble();n=n+1;double list=new doublen;Scanner scanner=new Scanner(string)

11、;for(int i=0;scanner.hasNext();i+)long startTime=System.nanoTime();heapSor(li);long endTime=System.nanoTime();long time=endTime-startTime;for(int j=0;j0)Etemp=list.get(currentIndex);list.set(currentIndex,list.get(parentIndex);list.set(parentIndex,temp);currentIndex=parentIndex;/*Remove the root from the heap*/EremovedObject=list.get(0);list.set(0, list.get(list.size()-1