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

1、學號2014-2015學年第2學期高級語言程序設計課程設計報告題目：排序算法專業(yè)：班級：姓名：指導教師：成績：計算機與信息工程系2015年3月26日引言0需求分析0第一章程序內容及要求01.1 冒泡排序01.2 選擇排序11.3 插入排序2第二章概要設計32.1 冒泡排序32.2 選擇排序42.3 插入排序5第三章程序的比較及其應用63.1 時間復雜度63.2 空間復雜度63.3 穩(wěn)定程度63.4 應用及其改進7第四章程序設計結果8附錄8參考文獻12引言伴隨著社會的發(fā)展，數據也變得越來越龐大。如何將龐大的數據進行很好的排序，使用戶更加方便的查找資料，成了一件越來越重要的問題。對于程序員來說，這

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

3、短。由于使用的調試軟件及操作系統(tǒng)不一樣。因此個別程序在不同的軟件上可能會報錯。本課程軟件運行的的操作系統(tǒng)為Windows764位操作系統(tǒng)。所使用的軟件為MicrosoftVisualC+6.0以及TurboC2.0第一章程序內容及要求1.1 冒泡排序冒泡排序（BubbleSort,臺灣譯為：泡沫排序或氣泡排序）是一種簡單的排序算法。它重復地走訪過要排序的數列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。走訪數列的工作是重復地進行直到沒有再需要交換，也就是說該數列已經排序完成。這個算法的名字由來是因為越大的元素會經由交換慢慢“浮”到數列的頂端，故名。冒泡排序（BubbleSort）的基

4、本概念是：依次比較相鄰的兩個數，將小數放在前面，大數放在后面。即在第一趟：首先比較第1個和第2個數，將小數放前，大數放后。然后比較第2個數和第3個數，將小數放前，大數放后，如此繼續(xù)，直至比較最后兩個數，將小數放前，大數放后。至此第一趟結束，將最大的數放到了最后。在第二趟：仍從第一對數開始比較（因為可能由于第2個數和第3個數的交換，使得第1個數不再小于第2個數），將小數放前，大數放后，一直比較到倒數第二個數（倒數第一的位置上已經是最大的），第二趟結束，在倒數第二的位置上得到一個新的最大數（其實在整個數列中是第二大的數）。如此下去，重復以上過程，直至最終完成排序。用二重循環(huán)實現，外循環(huán)變量設為i,

5、內循環(huán)變量設為jo假如有10個數需要進行排序，則外循環(huán)重復9次，內循環(huán)依次重復9,8,，1次。每次進行比較的兩個元素都是與內循環(huán)j有關的，它們可以分別用aj和aj+1標識，i的值依次為1,2,9,對于每一個i,j的值依次為1,2,10-io冒泡排序算法的性能1.2 選擇排序每一趟從待排序的數據元素中選出最?。ɑ蜃畲螅┑囊粋€元素，順序放在已排好序的數列的最后,直到全部待排序的數據元素排完。選擇排序是不穩(wěn)定的排序方法?；舅枷耄簄個記錄的文件的直接選擇排序可經過n-1趟直接選擇排序得到有序結果：初始狀態(tài)：無序區(qū)為R1.n,有序區(qū)為空。第1趟排序在無序區(qū)R1.n中選出關鍵字最小的記錄Rk,將它與無序

6、區(qū)的第1個記錄R1交換，使R1.1和R2.n分別變?yōu)橛涗泜€數增加1個的新有序區(qū)和記錄個數減少1個的新無序區(qū)。第i趟排序第i趟排序開始時，當前有序區(qū)和無序區(qū)分別為R1.i-1和R（1<i<n-1）。該趟排序從當前無序區(qū)中選出關鍵字最小的記錄Rk,將它與無序區(qū)的第1個記錄R交換，使R1.i和R分別變?yōu)橛涗泜€數增加1個的新有序區(qū)和記錄個數減少1個的新無序區(qū)。這樣，n個記錄的文件的直接選擇排序可經過n-1趟直接選擇排序得到有序結果。選擇排序法的第一層循環(huán)從起始元素開始選到倒數第二個元素，主要是在每次進入的第二層循環(huán)之前，將外層循環(huán)的下標賦值給臨時變量，接下來的第二層循環(huán)中，如果發(fā)現有比這個

7、最小位置處的元素更小的元素，則將那個更小的元素的下標賦給臨時變量，最后,在二層循環(huán)退出后，如果臨時變量改變，則說明，有比當前外層循環(huán)位置更小的元素，需要將這兩個元素交換1.3插入排序有一個已經有序的數據序列，要求在這個已經排好的數據序列中插入一個數，但要求插入后此數據序列仍然有序，這個時候就要用到一種新的排序方法-插入排序法，插入排序的基本操作就是將一個數據插入到已經排好序的有序數據中，從而得到一個新的、個數加一的有序數據，算法適用于少量數據的排序，時間復雜度為0mA2）。是穩(wěn)定的排序方法。插入算法把要排序的數組分成兩部分：第一部分包含了這個數組的所有元素，但將最后一個元素除外（讓數組多一個空

8、間才有插入的位置），而第二部分就只包含這一個元素（即待插入元素）。在第一部分排序完成后,再將這個最后元素插入到已排好序的第一部分中。插入排序的基本思想是：每步將一個待排序的紀錄，按其關鍵碼值的大小插入前面已經排序的文件中適當位置上，直到全部插入完為止。L從有序數列和無序數列a2,a3,an開始進行排序；2 .處理第i個元素時（i=2,3，n）,數列a1,a2，,ai-1是已有序的，而數列ai,ai+1,，an是無序的。用ai與ai-1,ai-2,，al進行比較，找出合適的位置將ai插入；3 .重復第二步，共進行n-i次插入處理，數列全部有序。第二章概要設計2.1 冒泡排序在要排序的一組數中，對

9、當前還未排好序的范圍內的全部數，自上而下對相鄰的兩個數依次進行比較和調整，讓較大的數往下沉，較小的往上冒。即：每當兩相鄰的數比較后發(fā)現它們的排序與排序要求相反時，就將它們互換。for(i=0;i<10;i+)第一輪循環(huán)，輸入十個數據。scanf("d,&ai);printf("n”);挨個判斷輸入的書的大小，第二輪循環(huán)for(j=0;j<9;j+)for(i=0;i<9-j;i+)if(ai>ai+1t=ai;進行數的調換，把大的數據調到后面ai=ai+1；ai+1=t;2.2 選擇排序簡單選擇排序，每趟循環(huán)只能確定一個元素排序后的定位。我們

10、可以考慮改進為每趟循環(huán)確定兩個元素(當前趟最大和最小記錄)的位置，從而減少排序所需的循環(huán)次數。改進后對n個數據進行排序，最多只需進行n/2趟循環(huán)即可。?“時庫排外法開始1-I'三口11M1gIm加7i1j=i4工i|卜,JIXs否V：1m»n>a(jI_»*-*"J¥1temp=a(j)a(j«s(i)(i)-tempmin-a(i)1 H結束/”_jpvoidselect_sort(inta口,intn)/n為數組a的元素個數/進行N-1輪選擇for(inti=0;i<n-1;i+)intmin_index=i;/找出第i

11、小的數所在的位置for(intj=i+1;j<n;j+)if(aj<amin_index)min_index=j;/將第i小的數，放在第i個位置；如果剛好，就不用交換if(i!=min_index)inttemp=ai;ai=amin_index;amin_index=temp;2.3 插入排序將一個記錄插入到已排序好的有序表中，從而得到一個新，記錄數增1的有序表。即：先將序列的第1個記錄看成是一個有序的子序列，然后從第 2個記錄逐個進行插入，直至整個序列有序為止inttemp;從數組中的第二個元素開始for(inti=1;i<length;+i)/temp=arri;/記錄

12、當前的元素intj=i-1;while(j>=0&&temp<arrj)/將當前元素與之前的已經排序好的序列元素進行挨個比較arrj+1=arr用;已經排序好的序列整體向后移動-j;arrj+1=temp;/插入當前的元素第三章程序的比較及其應用3.1 時間復雜度冒泡排序算法的最差時間復雜度為O(n2),平均時間復雜度為O(n2)。選擇排序算法的最差時間復雜度為O(n2),平均時間復雜度為O(n2)。插入排序算法的最差時間復雜度為O(n2),平均時間復雜度為O(n2)。冒泡排序和插入排序時間復雜度最好的情況下是O(n),而選擇排序時間復雜度最好的情況下是O(n2)。

13、從時間復雜度比較來看。選擇排序的時間復雜度在以下情況下是沒有冒泡排序和插入排序的好。3.2 空間復雜度冒泡排序，選擇排序，以及插入排序是空間復雜度都是。(1)。從空間復雜度來看，三者也沒有什么可以區(qū)分開來的。并不能直觀的看出優(yōu)劣。3.3 穩(wěn)定程度冒泡排序和插入排序的穩(wěn)定程度都是比較穩(wěn)定的,只有選擇排序是不穩(wěn)定的。那么綜合上面的比較來看，選擇排序是最不好的，而冒泡排序以及插入排序是比較好的。冒泡排序是最慢的，但是也是最容易懂得。插入排序是比較快的，但是對于自身的能力有一定的要求。當然，這只是相對而言。3.4 應用及其改進三種排序算法都可以應用于一些簡單排列數據的程序。也可以作為C語言初學者的練手

14、的課題。對于我們學習C語言也是一個不小的幫助。同時可以加深我們對于循環(huán)和數組的理解及其應用。同時我們可以對冒泡排序進行一點點的改進，使其更加的完善。冒泡算法的改進，當排序的數據比較多時排序的時間會明顯延長。改進方法：快速排序：具體做法：任意選取某一記錄（通常取第一個記錄），比較其關鍵字與所有記錄的關鍵字，并將關鍵字比它小的記錄全部放在它的前面，將比它大的記錄均存放在它的后面，這樣，經過一次排序之后，可將所有記錄以該記錄所在的分界點分為兩部分，然后分別對這兩部分進行快速排序，直至排序完。在冒泡排序中，一趟掃描有可能無數據交換，也有可能有一次或多次數據交換，在傳統(tǒng)的冒泡排序算法及近年來的一些改進的

15、算法中，只記錄一趟掃描有無數據交換的信息，對數據交換發(fā)生的位置信息則不予處理。為了充分利用這一信息，可以在一趟全局掃描中，對每一反序數據對進行局部冒泡排序處理，稱之為局部冒泡排序。局部冒泡排序與冒泡排序算法具有相同的時間復雜度，并且在正序和逆序的情況下，所需的關鍵字的比較次數和移動次數完全相同。由于局部冒泡排序和冒泡排序的數據移動次數總是相同的，而局部冒泡排序所需關鍵字的比較次數常少于冒泡排序,這意味著局部冒泡排序很可能在平均比較次數上對冒泡排序有所改進，當比較次數較少的優(yōu)點不足以抵消其程序復雜度所帶來的額外開銷，而當數據量較大時，局部冒泡排序的時間性能則明顯優(yōu)于冒泡排序。第四章程序設計結果插

16、入排序算法的結果選擇排序算法的結果冒泡排序算法的結果附錄冒泡排序：#include<stdio.h>voidmain()Inti,j,t;printf(“input10numbers: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(ai>ai+1t=ai;ai=ai+1;ai+1=t;printf(“thesortednumbers:n”);printf(“%d”,ai);printf(“n”);選擇排序：#include<st

17、dio.h>#include<stdlib.h>#defineN8voidselect_sort(inta,intn);/選擇排序實現voidselect_sort(inta,intn)/n為數組a的元素個數/進行N-1輪選擇for(inti=0;i<n-1;i+)intmin_index=i;/找出第i小的數所在的位置for(intj=i+1;j<n;j+)if(aj<amin_index)min_index=j;/將第i小的數，放在第i個位置；如果剛好，就不用交換if(i!=min_index)inttemp=ai;ai=amin_index;amin_

18、index=temp;intmain()intnumN=89,38,11,78,96,44,19,25;select_sort(num,N);for(inti=0;i<N;i+)printf("%d",numi);printf("n");system("pause");return0;插入排序：#include<iostream>usingnamespacestd;voidInsertSort(intarr,intlength)inttemp;for(inti=1;i<length;+i)/從數組中的第二個元素開始temp=arri;/記錄當前的元素intj=i-1;while(j>=0&&temp<arrj)/將當前元素與之前的已