資料結構課程設計

課程設計說明書

課程名稱：資料結構和演算法

設計題目多種排序

院系：電腦科學與資訊工程學院

學生姓名

學號專業班級：計科嵌入式（12-1）

指導教師

年月日課程設計任務書

多種排序

摘要：排序是演算法中最基礎的問題之一，經典的排序演算法是前人不斷總結得到的，基於比較的方法是比較直觀的方式，主要存在插入法排序、堆排序、希爾排序、歸併排序、快速排序，每一種排序演算法都有自己的優缺點，比如插入法排序適用於那些長度短的排序，要是長的話，有些愛莫能助啦，堆排序主要是依據了二叉堆的特性，但是建立堆的過程也是乙個複雜的問題，希爾排序的過程是乙個不斷精確的過程，但是目前也只是乙個經驗方式。歸併排序是乙個遞迴的問題，採用分治的思想實現，但是這種演算法需要額外的儲存空間，快速排序雖然是實踐中比較常用的演算法，但是對於有序的陣列採用快速排序就是災難。

比較型演算法的時間複雜度最優也只能到達o(nlogn)。

關鍵詞：

歸併排序快排排序選擇排序氣泡排序

插入排序堆排序希爾排序內部排序

5. 演算法複雜度以及穩定性分析 18

1. 設計背景

1.1問題描述

利用隨機函式產生n個隨機整數（10000以上），對這些數進行多種方法進行排序。包括：插入排序、希爾排序、起泡排序、快速排序、選擇排序、堆排序、歸併排序。

1.2 問題分析

經典的排序演算法是前人不斷總結得到的，基於比較的方法是比較直觀的方式，主要存在插入法排序、堆排序、希爾排序、歸併排序、快速排序，每一種排序演算法都有自己的優缺點。

2.設計方案

2.1 演算法設計

（1）選擇排序

在待排序的一組資料元素中，選出最小的乙個資料元素與第乙個位置的資料元素交換；然後在剩下的資料元素當中再找最小的與第二個位置的資料元素交換，迴圈到只剩下最後乙個資料元素為止。

（2）氣泡排序

相鄰的兩個元素進行比較，將小的調到前面，大的調到後面。

（3）插入排序

待排序的記錄放在陣列r[0n-1]中排序過程中某一時刻，r被劃分成兩個子區間r[0,i-1] (有序和)r[in-1](無序)。直接插入的基本操作是將當前無序區的乙個記錄r[i]插入到有序區r[0i-1]中適當的位置

（4）快速排序

在待排序的陣列的n個元素中取乙個元素(一般取第乙個)，將其移動到這樣的位置：在其之前的元素的值都小於它，在其之後的元素都大於它，這樣是一趟快速排序；然後對陣列的兩個部分進行同樣的操作，直到每部分只有乙個記錄為止；總之，每趟使表的第乙個元素放在適當位置，將表兩分，再對兩子表進行同樣的遞迴劃分，直至劃分的子表長度為1。

（5）堆排序

堆排序中 heap 演算法的時間複雜度與堆所對應的完全二叉樹的樹高度 log2n 相關。而 heapsort 中對 heap 的呼叫數量級為n，所以堆排序的整個時間複雜度為o(nlog2n) 。並且堆排序是不穩定的。

堆排序利用了大根堆(或小根堆)堆頂記錄的關鍵字最大(或最小)這一特徵，使得在當前無序區中選取最大(或最小)關鍵字的記錄變得簡單。

（6）歸併排序

將兩個或兩個以上的有序表組成乙個新的有序表。

（7）希爾排序

將無序陣列分割為若干個子串行，子串行不是逐段分割的，而是相隔特定的增量的子串行，對各個子串行進行插入排序；然後再選擇乙個更小的增量，再將陣列分割為多個子串行進行排序......最後選擇增量為1，即使用直接插入排序，使最終陣列成為有序。增量的選擇：

在每趟的排序過程都有乙個增量，至少滿足乙個規則增量關係 d[1] > d[2] > d[3] >..> d[t] = 1 (t趟排序)；根據增量序列的選取其時間複雜度也會有變化，這個不少**進行了研究，在此處就不再深究；本文採用首選增量為n/2,以此遞推，每次增量為原先的1/2，直到增量為1。

2.2 功能模組分析

1.資料輸入：採取隨機函式實現輸入資料表。

int input_num()

}2.資料輸出：for迴圈輸出即可。

int outnew0()

其中增加了輸出空格與換行區別。

3.主介面實現：

printf("date:may twenty 2014\n");

printf("address: 604 ayit\r\n\n\n");

printfn");

printf("——————各種排序比較n");

printf("預設從大到小輸出，可以選擇9進行切換\n");

printfn");

printf520n");

printf歡迎n");

printf使用n");

printfn");

printf("歡迎再次使用!!!\n\r\n");

printfn");

4.人機互動介面：

printf("\nn");

printf("——————請輸入指令n");

printfn");

printf("————$ 1.快速排序n");

printf("————$ 2.歸併排序n");

printf("————$ 3.堆排序n");

printf("————$ 4.希爾排序n");

資料結構課程設計

資料結構課程設計

資料結構課程設計

資料結構課程設計

相關推薦