c語言程序設(shè)計(排序算法)

1、學(xué)號2014-2015學(xué)年第2學(xué)期高級語言程序設(shè)計課程設(shè)計報告題目：排序算法指導(dǎo)教師:計算機與信息工程系2015年3月26日引言 1需求分析 1第一章程序內(nèi)容及要求 11.1 冒泡排序 11.2 選擇排序 21.3 插入排序 3第二章概要設(shè)計 42.1冒泡排序 42.2選擇排序 52.3插入排序 6第三章程序的比較及其應(yīng)用 73.1時間復(fù)雜度 73.2空間復(fù)雜度 73.3穩(wěn)定程度 73.4應(yīng)用及其改進 8第四章程序設(shè)計結(jié)果 9附錄 9參考文獻 13引言伴隨著社會的發(fā)展，數(shù)據(jù)也變得越來越龐大。如何將龐大的數(shù)據(jù)進行很好 的排序，使用戶更加方便的查找資料，成了一件越來越重要的問題。對于程序員 來說，

2、這將是一個挑戰(zhàn)。經(jīng)常查找資料的朋友都會知道，面對海量的資料，如果其查找資料沒有進 行排序，那么其查找資料將會是一家非常痛苦的事情。 針對這一問題，我們自此 通過一個課程設(shè)計來解決它。理論上排序算法有很多種，不過本課程設(shè)計只涉及到三種算法。這三種算 法包括：冒泡排序，選擇排序，直接插入排序。本課程設(shè)計通過對這三種算法的運行情況進行對比，選擇最優(yōu)秀的算法出來。希望通過我的努力能解決一些問題，帶來一些方便。需求分析本課程題目是排序算法的實現(xiàn)，由于各方面的原因，本科程設(shè)計一共需要 設(shè)計三種排序算法。這三種算法包括：冒泡排序，選擇排序，直接插入排序。三 種排序算法各有獨到之處，因此我們要通過各種調(diào)試分析

3、來比較其優(yōu)劣長短。由于使用的調(diào)試軟件及操作系統(tǒng)不一樣。因此個別程序在不同的軟件上可 能會報錯。本課程軟件運行的的操作系統(tǒng)為 Windows764位操作系統(tǒng)。所使用的軟件 為 Microsoft Visual C+6.0 以及 Turbo C2.0第一章 程序內(nèi)容及要求1.1冒泡排序冒泡排序（Bubble Sort，臺灣譯為：泡沫排序或氣泡排序）是一種簡單 的排序算法。它重復(fù)地走訪過要排序的數(shù)列，一次比較兩個元素，如果他們的順 序錯誤就把他們交換過來。走訪數(shù)列的工作是重復(fù)地進行直到?jīng)]有再需要交換， 也就是說該數(shù)列已經(jīng)排序完成。這個算法的名字由來是因為越大的元素會經(jīng)由交 換慢慢“浮”到數(shù)列的頂端，

4、故名。冒泡排序（BubbleSort ）的基本概念是：依次比較相鄰的兩個數(shù)，將小數(shù) 放在前面，大數(shù)放在后面。即在第一趟：首先比較第1個和第2個數(shù)，將小數(shù)放前，大數(shù)放后。然后比較第2個數(shù)和第3個數(shù)，將小數(shù)放前，大數(shù)放后，如此繼 續(xù)，直至比較最后兩個數(shù)，將小數(shù)放前，大數(shù)放后。至此第一趟結(jié)束，將最大的 數(shù)放到了最后。在第二趟：仍從第一對數(shù)開始比較（因為可能由于第2個數(shù)和第 3個數(shù)的交換，使得第1個數(shù)不再小于第2個數(shù)），將小數(shù)放前，大數(shù)放后，一 直比較到倒數(shù)第二個數(shù)（倒數(shù)第一的位置上已經(jīng)是最大的），第二趟結(jié)束，在倒 數(shù)第二的位置上得到一個新的最大數(shù)（其實在整個數(shù)列中是第二大的數(shù)）。如此 下去，重復(fù)以上

5、過程，直至最終完成排序。用二重循環(huán)實現(xiàn)，外循環(huán)變量設(shè)為i， 內(nèi)循環(huán)變量設(shè)為j。假如有10個數(shù)需要進行排序，則外循環(huán)重復(fù) 9次，內(nèi)循環(huán) 依次重復(fù)9，8，. ，1次。每次進行比較的兩個元素都是與內(nèi)循環(huán)j有關(guān)的，它們可以分別用aj和aj+1標識，i的值依次為1,2,.,9，對于每一個i,j的值依次為1,2,.10-i。冒泡排序算法的性能1.2選擇排序每一趟從待排序的數(shù)據(jù)元素中選出最小（或最大）的一個元素，順序放 在已排好序的數(shù)列的最后，直到全部待排序的數(shù)據(jù)元素排完。選擇排序是不穩(wěn)定的排序方法?；舅枷耄簄個記錄的文件的直接選擇排序可經(jīng)過n-1趟直接選擇排序得到有序結(jié)果： 初始狀態(tài)：無序區(qū)為R仁n，有

6、序區(qū)為空。 第1趟排序 在無序區(qū)R仁n中選出關(guān)鍵字最小的記錄 Rk，將它與無序區(qū) 的第1個記錄R1交換，使R1.1和R2.n分別變?yōu)橛涗泜€數(shù)增加1個的新有序區(qū)和記錄個數(shù)減少1 個的新無序區(qū)。第i趟排序 第i趟排序開始時，當前有序區(qū)和無序區(qū)分別為R1.i-1和R（1< i < n-1）。該趟排序從當前無序區(qū)中選出關(guān)鍵字最小的記錄Rk，將它與無序區(qū)的第1個記錄R交換，使R1.i和R分別變?yōu)橛涗泜€數(shù)增加1個的新有序區(qū)和記錄個數(shù)減少1個的新 無序區(qū)。這樣，n個記錄的文件的直接選擇排序可經(jīng)過 n-1趟直接選擇排序得到有序結(jié)果。選擇排序法的第一層循環(huán)從起始元素開始選到倒數(shù)第二個元素，主要是在每

7、次進 入的第二層循環(huán)之前，將外層循環(huán)的下標賦值給臨時變量，接下來的第二層循環(huán)中，如果發(fā)現(xiàn)有比這個 最小位置處的元素更小的元素,則將那個更小的元素的下標賦給臨時變量，最后,在二層循環(huán)退出后，如果 臨時變量改變，則說明，有比當前外層循環(huán)位置更小的元素，需要將這兩個元素交換1.3 插入排序有一個已經(jīng)有序的數(shù)據(jù)序列，要求在這個已經(jīng)排好的數(shù)據(jù)序列中插入一 個數(shù)，但要求插入后此數(shù)據(jù)序列仍然有序，這個時候就要用到一種新的排序方法-插入排序法，插入排序的基本操作就是將一個數(shù)據(jù)插入到已經(jīng)排好序的有序數(shù) 據(jù)中，從而得到一個新的、個數(shù)加一的有序數(shù)據(jù)，算法適用于少量數(shù)據(jù)的排序， 時間復(fù)雜度為0（nA2）。是穩(wěn)定的排序

8、方法。插入算法把要排序的 數(shù)組分成兩部 分：第一部分包含了這個數(shù)組的所有元素，但將最后一個元素除外（讓數(shù)組多一個 空間才有插入的位置），而第二部分就只包含這一個元素（即待插入元素）。在第 一部分排序完成后，再將這個最后元素插入到已排好序的第一部分中。插入排序的基本思想是：每步將一個待排序的紀錄，按其關(guān)鍵碼值的大小插入前面已經(jīng)排 序的文件中適當位置上，直到全部插入完為止。1從有序數(shù)列和無序數(shù)列a2,a3，an開始進行排序；2.處理第i個元素時（i=2,3，n），數(shù)列a1,a2，ai-1是已有序 的，而數(shù)列ai,ai+1 ，an是無序的。用ai與ai-1 ，a i-2，al進行比 較，找出合適的位

9、置將ai插入；3重復(fù)第二步，共進行n-i次插入處理，數(shù)列全部有序。第二章概要設(shè)計2.1冒泡排序在要排序的一組數(shù)中，對當前還未排好序的范圍內(nèi)的全部數(shù)，自上而下對 相鄰的兩個數(shù)依次進行比較和調(diào)整，讓較大的數(shù)往下沉，較小的往上冒。即：每 當兩相鄰的數(shù)比較后發(fā)現(xiàn)它們的排序與排序要求相反時，就將它們互換。for(i=0;i<10;i+)第一輪循環(huán)，輸入十個數(shù)據(jù)。scanf( “%d，&ai);printf( “n ” );for(j=0;j<9;j+)挨個判斷輸入的書的大小，第二輪循環(huán)for(i=0;i<9-j;i+)if(ai>ai+1t=ai;進行數(shù)的調(diào)換，把大的數(shù)據(jù)

10、調(diào)到后面。ai=ai+1;ai+1=t;2.2選擇排序簡單選擇排序，每趟循環(huán)只能確定一個元素排序后的定位。我們可以考慮改進為每趟循環(huán)確定兩個元素（當前趟最大和最小記錄）的位置，從而減少排序所需的循環(huán)次數(shù)。改進后對 n個數(shù)據(jù)進行排序，最多只需進行n/2趟循環(huán)即i=lpn=lO;t e m戸=列j) alj)-a(i) aflj-tamp min >0ji+-為數(shù)組a的元素個數(shù)void select_sort(i nt a,i nt n)/n/進行N-1輪選擇for(i nt i=0; i<n-1; i+) int min_in dex = i;/ 找出第i小的數(shù)所在的位置for(i

11、nt j=i+1; j< n; j+)if(aj < amin_in dex)min_i ndex = j;/ 將第i小的數(shù)，放在第i個位置；如果剛好，就不用交換if( i != min_i ndex)int temp = ai;ai = amin_in dex;amin_i ndex = temp;2.3插入排序?qū)⒁粋€記錄插入到已排序好的有序表中，從而得到一個新，記錄數(shù)增1的有序表。即：先將序列的第1個記錄看成是一個有序的子序列，然后從第 2個記錄逐個進行插入，直至整個序列有序為止3A-r34>3AJ5從數(shù)組中的第二個元素開始int temp;for (i nt i = 1

12、; i < len gth; +i) /temp = arri; /記錄當前的元素int j = i - 1;while (j >= 0 && temp < arrj) /將當前元素與之前的已經(jīng)排序好的序列元素進行挨個比較arrj + 1 = arrj; /已經(jīng)排序好的序列整體向后移動T；arrj + 1 = temp; /插入當前的元素第三章程序的比較及其應(yīng)用3.1時間復(fù)雜度冒泡排序算法的最差時間復(fù)雜度為 0(n2)，平均時間復(fù)雜度為0(n2)。選 擇排序算法的最差時間復(fù)雜度為 0(n2)，平均時間復(fù)雜度為0(n2)。插入排序算法 的最差時間復(fù)雜度為0(n2

13、)，平均時間復(fù)雜度為0(n2)。冒泡排序和插入排序時間 復(fù)雜度最好的情況下是 0(n),而選擇排序時間復(fù)雜度最好的情況下是0(n2)。從時間復(fù)雜度比較來看。選擇排序的時間復(fù)雜度在以下情況下是沒有冒泡排序和插 入排序的好。3.2空間復(fù)雜度冒泡排序，選擇排序，以及插入排序是空間復(fù)雜度都是0(1)。從空間復(fù)雜度來看，三者也沒有什么可以區(qū)分開來的。并不能直觀的看出優(yōu)劣。3.3穩(wěn)定程度冒泡排序和插入排序的穩(wěn)定程度都是比較穩(wěn)定的，只有選擇排序是不穩(wěn) 定的。那么綜合上面的比較來看，選擇排序是最不好的，而冒泡排序以及插入排 序是比較好的。冒泡排序是最慢的，但是也是最容易懂得。插入排序是比較快的， 但是對于自身

14、的能力有一定的要求。當然，這只是相對而言3.4應(yīng)用及其改進三種排序算法都可以應(yīng)用于一些簡單排列數(shù)據(jù)的程序。也可以作為C語言初學(xué)者的練手的課題。對于我們學(xué)習(xí)C語言也是一個不小的幫助。同時可以 加深我們對于循環(huán)和數(shù)組的理解及其應(yīng)用。 同時我們可以對冒泡排序進行一點點 的改進，使其更加的完善。冒泡算法的改進，當排序的數(shù)據(jù)比較多時排序的時間會明顯延長。改進 方法：快速排序：具體做法：任意選取某一記錄（通常取第一個記錄），比較其 關(guān)鍵字與所有記錄的關(guān)鍵字，并將關(guān)鍵字比它小的記錄全部放在它的前面，將比它大的記錄均存放在它的后面，這樣，經(jīng)過一次排序之后，可將所有記錄以該記 錄所在的分界點分為兩部分，然后分別

15、對這兩部分進行快速排序，直至排序完。 在冒泡排序中，一趟掃描有可能無數(shù)據(jù)交換，也有可能有一次或多次數(shù)據(jù)交換， 在傳統(tǒng)的冒泡排序算法及近年來的一些改進的算法中，只記錄一趟掃描有無數(shù)據(jù) 交換的信息，對數(shù)據(jù)交換發(fā)生的位置信息則不予處理。為了充分利用這一信息， 可以在一趟全局掃描中，對每一反序數(shù)據(jù)對進行局部冒泡排序處理， 稱之為局部 冒泡排序。局部冒泡排序與冒泡排序算法具有相同的時間復(fù)雜度，并且在正序和逆序的情況下，所需的關(guān)鍵字的比較次數(shù)和移動次數(shù)完全相同。由于局部冒泡排序和冒泡排序的數(shù)據(jù)移動次數(shù)總是相同的， 而局部冒泡排序所需關(guān)鍵字的比較次 數(shù)常少于冒泡排序，這意味著局部冒泡排序很可能在平均比較次數(shù)

16、上對冒泡排序 有所改進，當比較次數(shù)較少的優(yōu)點不足以抵消其程序復(fù)雜度所帶來的額外開銷， 而當數(shù)據(jù)量較大時，局部冒泡排序的時間性能則明顯優(yōu)于冒泡排序。第四章 程序設(shè)計結(jié)果插入排序算法的結(jié)果選擇排序算法的結(jié)果冒泡排序算法的結(jié)果附錄冒泡排序：#i nclude<stdio.h>void mai n()int a10;Int i,j,t;printf( “ in put 10 nu mbers :n”);for(i=0;i<10;i+) scanf( “%d，&ai);printf(“n ”)；for(j=0;j<9;j+)for(i=0;i<9-j;i+)if(a

17、i>ai+1t=ai;ai=ai+1;ai+1=t;printf(“ the sorted nu mbers :n”printf(“%d ,ai);printf(“n ”)；選擇排序：#i nclude<stdio.h>#i nclude<stdlib.h>#defi ne N 8void select_sort(i nt a,i nt n);/選擇排序?qū)崿F(xiàn)為數(shù)組a的元素個數(shù)void select_sort(i nt a,i nt n)/n/ 進行N-1輪選擇for(i nt i=0; i<n-1; i+)int min_in dex = i;/ 找出第i小

18、的數(shù)所在的位置for(i nt j=i+1; j< n; j+)if(aj < amin_in dex)min_i ndex = j;/ 將第i小的數(shù)，放在第i個位置；如果剛好，就不用交換if( i != min_i ndex)int temp = ai;ai = amin_in dex;amin_i ndex = temp;int mai n()int numN = 89, 38, 11, 78, 96, 44, 19, 25;select_sort (num, N);for(i nt i=0; i<N; i+)prin tf("%d ", nu mi);prin tf("n&qu