c語(yǔ)言程序設(shè)計(jì)排序算法

-.z.---.可修編.**202014-2015學(xué)年第2學(xué)期《高級(jí)語(yǔ)言程序設(shè)計(jì)》課程設(shè)計(jì)報(bào)告題目：排序算法專(zhuān)業(yè)：班級(jí)：：指導(dǎo)教師：成績(jī)：計(jì)算機(jī)與信息工程系2015年3月26日-.z.-.可修編.目錄TOC\o"1-3"\h\u30引言 111217需求分析 116740第一章程序容及要求 1142331.1冒泡排序 1280011.2選擇排序 228811.3插入排序 36821第二章概要設(shè)計(jì) 4320992.1冒泡排序 4324122.2選擇排序5107562.3插入排序622595第三章程序的比較及其應(yīng)用 7171743.1時(shí)間復(fù)雜度 7197373.2空間復(fù)雜度735943.3穩(wěn)定程度7130503.4應(yīng)用及其改進(jìn)816079第四章程序設(shè)計(jì)結(jié)果 821906附錄99205參考文獻(xiàn) 12-.z.引言伴隨著社會(huì)的發(fā)展，數(shù)據(jù)也變得越來(lái)越龐大。如何將龐大的數(shù)據(jù)進(jìn)行很好的排序，使用戶(hù)更加方便的查找資料，成了一件越來(lái)越重要的問(wèn)題。對(duì)于程序員來(lái)說(shuō)，這將是一個(gè)挑戰(zhàn)。經(jīng)常查找資料的朋友都會(huì)知道，面對(duì)海量的資料，如果其查找資料沒(méi)有進(jìn)行排序，則其查找資料將會(huì)是一家非常痛苦的事情。針對(duì)這一問(wèn)題，我們自此通過(guò)一個(gè)課程設(shè)計(jì)來(lái)解決它。理論上排序算法有很多種，不過(guò)本課程設(shè)計(jì)只涉及到三種算法。這三種算法包括：冒泡排序，選擇排序，直接插入排序。本課程設(shè)計(jì)通過(guò)對(duì)這三種算法的運(yùn)行情況進(jìn)行對(duì)比，選擇最優(yōu)秀的算法出來(lái)。希望通過(guò)我的努力能解決一些問(wèn)題，帶來(lái)一些方便。需求分析本課程題目是排序算法的實(shí)現(xiàn)，由于各方面的原因，本科程設(shè)計(jì)一共需要設(shè)計(jì)三種排序算法。這三種算法包括：冒泡排序，選擇排序，直接插入排序。三種排序算法各有獨(dú)到之處，因此我們要通過(guò)各種調(diào)試分析來(lái)比較其優(yōu)劣長(zhǎng)短。由于使用的調(diào)試軟件及操作系統(tǒng)不一樣。因此個(gè)別程序在不同的軟件上可能會(huì)報(bào)錯(cuò)。本課程軟件運(yùn)行的的操作系統(tǒng)為Windows764位操作系統(tǒng)。所使用的軟件為MicrosoftVisualC++6.0以及TurboC2.0第一章程序容及要求1.1冒泡排序冒泡排序（BubbleSort，譯為：泡沫排序或氣泡排序）是一種簡(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ù)列的頂端，故名。冒泡排序（BubbleSort）的基本概念是：依次比較相鄰的兩個(gè)數(shù)，將小數(shù)放在前面，大數(shù)放在后面。即在第一趟：首先比較第1個(gè)和第2個(gè)數(shù)，將小數(shù)放前，大數(shù)放后。然后比較第2個(gè)數(shù)和第3個(gè)數(shù)，將小數(shù)放前，大數(shù)放后，如此繼續(xù)，直至比較最后兩個(gè)數(shù)，將小數(shù)放前，大數(shù)放后。至此第一趟結(jié)束，將最大的數(shù)放到了最后。在第二趟：仍從第一對(duì)數(shù)開(kāi)始比較（因?yàn)榭赡苡捎诘?個(gè)數(shù)和第3個(gè)數(shù)的交換，使得第1個(gè)數(shù)不再小于第2個(gè)數(shù)），將小數(shù)放前，大數(shù)放后，一直比較到倒數(shù)第二個(gè)數(shù)（倒數(shù)第一的位置上已經(jīng)是最大的），第二趟結(jié)束，在倒數(shù)第二的位置上得到一個(gè)新的最大數(shù)（其實(shí)在整個(gè)數(shù)列中是第二大的數(shù)）。如此下去，重復(fù)以上過(guò)程，直至最終完成排序。用二重循環(huán)實(shí)現(xiàn)，外循環(huán)變量設(shè)為i，循環(huán)變量設(shè)為j。假如有10個(gè)數(shù)需要進(jìn)行排序，則外循環(huán)重復(fù)9次，循環(huán)依次重復(fù)9，8，...，1次。每次進(jìn)行比較的兩個(gè)元素都是與循環(huán)j有關(guān)的，它們可以分別用a[j]和a[j+1]標(biāo)識(shí)，i的值依次為1,2,...,9，對(duì)于每一個(gè)i,j的值依次為1,2,...10-i。冒泡排序算法的性能1.2選擇排序每一趟從待排序的數(shù)據(jù)元素中選出最?。ɑ蜃畲螅┑囊粋€(gè)元素，順序放在已排好序的數(shù)列的最后，直到全部待排序的數(shù)據(jù)元素排完。選擇排序是不穩(wěn)定的排序方法?；舅枷?

n個(gè)記錄的文件的直接選擇排序可經(jīng)過(guò)n-1趟直接選擇排序得到有序結(jié)果：

①初始狀態(tài)：無(wú)序區(qū)為R[1..n]，有序區(qū)為空。

②第1趟排序在無(wú)序區(qū)R[1..n]中選出關(guān)鍵字最小的記錄R[k]，將它與無(wú)序區(qū)的第1個(gè)記錄R[1]交換，

使R[1..1]和R[2..n]分別變?yōu)橛涗泜€(gè)數(shù)增加1個(gè)的新有序區(qū)和記錄個(gè)數(shù)減少1個(gè)的新無(wú)序區(qū)?！?/p>

第i趟排序第i趟排序開(kāi)始時(shí)，當(dāng)前有序區(qū)和無(wú)序區(qū)分別為R[1..i-1]和R(1≤i≤n-1)。

該趟排序從當(dāng)前無(wú)序區(qū)中選出關(guān)鍵字最小的記錄R[k]，將它與無(wú)序區(qū)的第1個(gè)記錄R交換，

使R[1..i]和R分別變?yōu)橛涗泜€(gè)數(shù)增加1個(gè)的新有序區(qū)和記錄個(gè)數(shù)減少1個(gè)的新無(wú)序區(qū)。

這樣，n個(gè)記錄的文件的直接選擇排序可經(jīng)過(guò)n-1趟直接選擇排序得到有序結(jié)果。

選擇排序法的第一層循環(huán)從起始元素開(kāi)始選到倒數(shù)第二個(gè)元素,主要是在每次進(jìn)入的第二層循環(huán)之前,

將外層循環(huán)的下標(biāo)賦值給臨時(shí)變量,接下來(lái)的第二層循環(huán)中,如果發(fā)現(xiàn)有比這個(gè)最小位置處的元素更小的

元素,則將那個(gè)更小的元素的下標(biāo)賦給臨時(shí)變量,最后,在二層循環(huán)退出后,如果臨時(shí)變量改變,則說(shuō)明,

有比當(dāng)前外層循環(huán)位置更小的元素,需要將這兩個(gè)元素交換1.3插入排序有一個(gè)已經(jīng)有序的數(shù)據(jù)序列，要求在這個(gè)已經(jīng)排好的數(shù)據(jù)序列中插入一個(gè)數(shù)，但要求插入后此數(shù)據(jù)序列仍然有序，這個(gè)時(shí)候就要用到一種新的排序方法--插入排序法,插入排序的基本操作就是將一個(gè)數(shù)據(jù)插入到已經(jīng)排好序的有序數(shù)據(jù)中，從而得到一個(gè)新的、個(gè)數(shù)加一的有序數(shù)據(jù)，算法適用于少量數(shù)據(jù)的排序，時(shí)間復(fù)雜度為O(n^2)。是穩(wěn)定的排序方法。插入算法把要排序的數(shù)組分成兩部分:第一部分包含了這個(gè)數(shù)組的所有元素，但將最后一個(gè)元素除外(讓數(shù)組多一個(gè)空間才有插入的位置)，而第二部分就只包含這一個(gè)元素(即待插入元素)。在第一部分排序完成后，再將這個(gè)最后元素插入到已排好序的第一部分中。插入排序的基本思想是:每步將一個(gè)待排序的紀(jì)錄，按其關(guān)鍵碼值的大小插入前面已經(jīng)排序的文件中適當(dāng)位置上，直到全部插入完為止。⒈從有序數(shù)列和無(wú)序數(shù)列{a2,a3，…，an}開(kāi)始進(jìn)行排序；⒉處理第i個(gè)元素時(shí)（i=2,3，…，n），數(shù)列{a1,a2，…，ai-1}是已有序的，而數(shù)列{ai,ai+1，…，an}是無(wú)序的。用ai與ai-1，ai-2，…，a1進(jìn)行比較，找出合適的位置將ai插入；⒊重復(fù)第二步，共進(jìn)行n-i次插入處理，數(shù)列全部有序。第二章概要設(shè)計(jì)2.1冒泡排序在要排序的一組數(shù)中，對(duì)當(dāng)前還未排好序的圍的全部數(shù)，自上而下對(duì)相鄰的兩個(gè)數(shù)依次進(jìn)行比較和調(diào)整，讓較大的數(shù)往下沉，較小的往上冒。即：每當(dāng)兩相鄰的數(shù)比較后發(fā)現(xiàn)它們的排序與排序要求相反時(shí)，就將它們互換。for(i=0;i<10;i++)第一輪循環(huán)，輸入十個(gè)數(shù)據(jù)。scanf(“%d”,&a[i]);printf(“\n”);for(j=0;j<9;j++)挨個(gè)判斷輸入的書(shū)的大小，第二輪循環(huán)for(i=0;i<9-j;i++)if(a[i]>a[i+1]{t=a[i];進(jìn)行數(shù)的調(diào)換，把大的數(shù)據(jù)調(diào)到后面。a[i]=a[i+1];a[i+1]=t;2.2選擇排序簡(jiǎn)單選擇排序，每趟循環(huán)只能確定一個(gè)元素排序后的定位。我們可以考慮改進(jìn)為每趟循環(huán)確定兩個(gè)元素（當(dāng)前趟最大和最小記錄）的位置,從而減少排序所需的循環(huán)次數(shù)。改進(jìn)后對(duì)n個(gè)數(shù)據(jù)進(jìn)行排序，最多只需進(jìn)行[n/2]趟循環(huán)即可。voidselect_sort(inta[],intn)//n為數(shù)組a的元素個(gè)數(shù){//進(jìn)行N-1輪選擇for(inti=0;i<n-1;i++){intmin_inde*=i;//找出第i小的數(shù)所在的位置for(intj=i+1;j<n;j++){if(a[j]<a[min_inde*]){min_inde*=j;}}//將第i小的數(shù)，放在第i個(gè)位置；如果剛好，就不用交換if(i!=min_inde*){inttemp=a[i];a[i]=a[min_inde*];a[min_inde*]=temp;2.3插入排序?qū)⒁粋€(gè)記錄插入到已排序好的有序表中，從而得到一個(gè)新，記錄數(shù)增1的有序表。即：先將序列的第1個(gè)記錄看成是一個(gè)有序的子序列，然后從第2個(gè)記錄逐個(gè)進(jìn)行插入，直至整個(gè)序列有序?yàn)橹?。{inttemp;for(inti=1;i<length;++i)//從數(shù)組中的第二個(gè)元素開(kāi)始{temp=arr[i];//記錄當(dāng)前的元素intj=i-1;while(j>=0&&temp<arr[j])//將當(dāng)前元素與之前的已經(jīng)排序好的序列元素進(jìn)行挨個(gè)比較{arr[j+1]=arr[j];//已經(jīng)排序好的序列整體向后移動(dòng)--j;}arr[j+1]=temp;//插入當(dāng)前的元素程序的比較及其應(yīng)用3.1時(shí)間復(fù)雜度冒泡排序算法的最差時(shí)間復(fù)雜度為O(n2)，平均時(shí)間復(fù)雜度為O(n2)。選擇排序算法的最差時(shí)間復(fù)雜度為O(n2)，平均時(shí)間復(fù)雜度為O(n2)。插入排序算法的最差時(shí)間復(fù)雜度為O(n2)，平均時(shí)間復(fù)雜度為O(n2)。冒泡排序和插入排序時(shí)間復(fù)雜度最好的情況下是O(n)，而選擇排序時(shí)間復(fù)雜度最好的情況下是O(n2)。從時(shí)間復(fù)雜度比較來(lái)看。選擇排序的時(shí)間復(fù)雜度在以下情況下是沒(méi)有冒泡排序和插入排序的好。3.2空間復(fù)雜度冒泡排序，選擇排序，以及插入排序是空間復(fù)雜度都是O(1)。從空間復(fù)雜度來(lái)看，三者也沒(méi)有什么可以區(qū)分開(kāi)來(lái)的。并不能直觀的看出優(yōu)劣。3.3穩(wěn)定程度冒泡排序和插入排序的穩(wěn)定程度都是比較穩(wěn)定的，只有選擇排序是不穩(wěn)定的。則綜合上面的比較來(lái)看，選擇排序是最不好的，而冒泡排序以及插入排序是比較好的。冒泡排序是最慢的，但是也是最容易懂得。插入排序是比較快的，但是對(duì)于自身的能力有一定的要求。當(dāng)然，這只是相對(duì)而言。3.4應(yīng)用及其改進(jìn)三種排序算法都可以應(yīng)用于一些簡(jiǎn)單排列數(shù)據(jù)的程序。也可以作為C語(yǔ)言初學(xué)者的練手的課題。對(duì)于我們學(xué)習(xí)C語(yǔ)言也是一個(gè)不小的幫助。同時(shí)可以加深我們對(duì)于循環(huán)和數(shù)組的理解及其應(yīng)用。同時(shí)我們可以對(duì)冒泡排序進(jìn)行一點(diǎn)點(diǎn)的改進(jìn)，使其更加的完善。冒泡算法的改進(jìn)，當(dāng)排序的數(shù)據(jù)比較多時(shí)排序的時(shí)間會(huì)明顯延長(zhǎng)。改進(jìn)方法：快速排序：具體做法：任意選取*一記錄（通常取第一個(gè)記錄），比較其關(guān)鍵字與所有記錄的關(guān)鍵字，并將關(guān)鍵字比它小的記錄全部放在它的前面，將比它大的記錄均存放在它的后面，這樣，經(jīng)過(guò)一次排序之后，可將所有記錄以該記錄所在的分界點(diǎn)分為兩部分，然后分別對(duì)這兩部分進(jìn)行快速排序，直至排序完。在冒泡排序中，一趟掃描有可能無(wú)數(shù)據(jù)交換，也有可能有一次或多次數(shù)據(jù)交換，在傳統(tǒng)的冒泡排序算法及近年來(lái)的一些改進(jìn)的算法中，只記錄一趟掃描有無(wú)數(shù)據(jù)交換的信息，對(duì)數(shù)據(jù)交換發(fā)生的位置信息則不予處理。為了充分利用這一信息，可以在一趟全局掃描中，對(duì)每一反序數(shù)據(jù)對(duì)進(jìn)行局部冒泡排序處理，稱(chēng)之為局部冒泡排序。局部冒泡排序與冒泡排序算法具有相同的時(shí)間復(fù)雜度，并且在正序和逆序的情況下，所需的關(guān)鍵字的比較次數(shù)和移動(dòng)次數(shù)完全相同。由于局部冒泡排序和冒泡排序的數(shù)據(jù)移動(dòng)次數(shù)總是相同的，而局部冒泡排序所需關(guān)鍵字的比較次數(shù)常少于冒泡排序，這意味著局部冒泡排序很可能在平均比較次數(shù)上對(duì)冒泡排序有所改進(jìn)，當(dāng)比較次數(shù)較少的優(yōu)點(diǎn)不足以抵消其程序復(fù)雜度所帶來(lái)的額外開(kāi)銷(xiāo)，而當(dāng)數(shù)據(jù)量較大時(shí)，局部冒泡排序的時(shí)間性能則明顯優(yōu)于冒泡排序。程序設(shè)計(jì)結(jié)果插入排序算法的結(jié)果選擇排序算法的結(jié)果冒泡排序算法的結(jié)果附錄冒泡排序：*include<stdio.h>voidmain(){inta[10];Inti,j,t;printf(“input10numbers:\n”);for(i=0;i<10;i++)scanf(“%d”,&a[i]);printf(“\n”);for(j=0;j<9;j++)for(i=0;i<9-j;i++)if(a[i]>a[i+1]{t=a[i];a[i]=a[i+1];a[i+1]=t;}printf(“thesortednumbers:\n”);printf(“%d”,a[i]);printf(“\n”);}選擇排序：*include<stdio.h>*include<stdlib.h>*defineN8voidselect_sort(inta[],intn);//選擇排序?qū)崿F(xiàn)voidselect_sort(inta[],intn)//n為數(shù)組a的元素個(gè)數(shù){//進(jìn)行N-1輪選擇for(inti=0;i<n-1;i++){intmin_inde*=i;//找出第i小的數(shù)所在的位置for(intj=i+1;j<n;j++){if(a[j]<a[min_inde*]){min_inde*=j;}}//將第i小的數(shù)，放在第i個(gè)位置；如果剛好，就不用交換if(i!=min_inde*){inttemp=a[i];a[i]=a[min_inde*];a[min_inde*]=temp;}}}intmain(){intnum[N]={89,38,11,78,96,44,19,25};select_sort(num,N);for(inti=0;i<N;i++)printf("%d",num[i]);printf("\n");system("pause");ret