姓名：周燕學號：1204012032 班級：12計本（2）班
這個學期在老師的帶領下我們學習了資料結構與演算法這門課程。在本次資料結構與演算法的學習中最令我深刻的是關於幾種排序演算法的學習，所以在這裡我想對我本學期所學習的這幾種排序演算法做乙個比較詳細的總結。
首先我們要對排序有乙個了解，排序是將乙個資料元素或記錄的任意序列，重新排列成乙個按關鍵字有序的序列。排序按照不同的分類方式可以劃分為不同的種類。按照穩定性劃分，可以劃分為穩定排序和不穩定排序。
穩定排序在待排序的檔案中，若存在多個關鍵字相同的記錄，經過排序後這些具有相同關鍵字的記錄之間的相對次序保持不變，該排序方法是穩定的；若具有相同關鍵字的記錄之間的相對次序發生改變，則稱這種排序方法是不穩定的。即所有相等的數經過某種排序方法後，仍能保持它們在排序之前的相對次序，則說這種排序演算法是穩定的，反之，就是不穩定的。
穩定的排序演算法如下表所示：
不穩定的排序演算法如下表所示：
一、插入排序
插入排序的基本思想是每步將乙個待排序的記錄按其排序碼值的大小，插到前面已經排好的檔案中的適當位置，直到全部插入完為止。插入排序方法主要有直接插入排序和希爾排序。
直接插入排序具體演算法描述如下：
1. 從第乙個元素開始，該元素可以認為已經被排序
2. 取出下乙個元素，在已經排序的元素序列中從後向前掃瞄
3. 如果該元素（已排序）大於新元素，將該元素移到下一位置
4. 重複步驟3，直到找到已排序的元素小於或者等於新元素的位置
5. 將新元素插入到下一位置。
二、希爾排序
希爾(shell)排序的基本思想是：先取乙個小於n的整數d1作為第乙個增量把檔案的全部記錄分成d1個組。所有距離為d1的倍數的記錄放在同乙個組中。
先在各組內進行直接插入排序；然後，取得第二個增量d2
三、氣泡排序
氣泡排序（bubblesort）的基本概念是：依次比較相鄰的兩個數，將小數放在前面，大數放在後面。即在第一趟：
首先比較第1個和第2個數，將小數放前，大數放後。然後比較第2個數和第3個數，將小數放前，大數放後，如此繼續，直至比較最後兩個數，將小數放前，大數放後。至此第一趟結束，將最大的數放到了最後。
在第二趟：仍從第一對數開始比較（因為可能由於第2個數和第3個數的交換，使得第1個數不再小於第2個數），將小數放前，大數放後，一直比較到倒數第二個數（倒數第一的位置上已經是最大的），第二趟結束，在倒數第二的位置上得到乙個新的最大數（其實在整個數列中是第二大的數）。如此下去，重複以上過程，直至最終完成排序
四、歸併排序
歸併排序是將兩個或兩個以上的有序子表合併成乙個新的有序表。初始時，把含有n個結點的待排序序列看作由n個長度都為1的有序子表組成，將它們依次兩兩歸併得到長度為2的若干有序子表，再對它們兩兩合併。直到得到長度為n的有序表，排序結束。
歸併操作的工作原理如下：
1、申請空間，使其大小為兩個已經排序序列之和，該空間用來存放合併後的序列
2、設定兩個指標，最初位置分別為兩個已經排序序列的起始位置
3、比較兩個指標所指向的元素，選擇相對小的元素放入到合併空間，並移動指標到下一位置
4、重複步驟3直到某一指標達到序列尾
5、將另一串行剩下的所有元素直接複製到合併序列尾。
五、選擇排序
選擇排序的基本思想是每一趟從待排序的資料元素中選出最小（或最大）的乙個元素，順序放在已排好序的數列的最後，直到全部待排序的資料元素排完。選擇排序中主要使用直接選擇排序和堆排序。
直接選擇排序的過程是：首先在所有記錄中選出序碼最小的記錄，把它與第1個記錄交換，然後在其餘的記錄內選出排序碼最小的記錄，與第2個記錄交換......依次類推，直到所有記錄排完為止。
6、快速排序
快速排序採用了一種分治的策略，通常稱其為分治法，其基本思想是：將原問題分解為若干個規模更小但結構與原問題相似的子問題。遞迴地解這些子問題，然後將這些子問題的解組合為原問題的解。
快速排序的具體過程如下：
第一步，在待排序的n個記錄中任取乙個記錄，以該記錄的排序碼為準，將所有記錄分成兩組，第1組各記錄的排序碼都小於等於該排序碼，第2組各記錄的排序碼都大於該排序碼，並把該記錄排在這兩組中間。
第二步，採用同樣的方法，對左邊的組和右邊的組進行排序，直到所有記錄都排到相應的位置為止
七、堆排序
堆的定義：n個關鍵字序列kl，k2，…，kn稱為(heap)，當且僅當該序列滿足如下性質(簡稱為堆性質)：
(1) ki≤k2i 且 ki≤k2i+1或
(2)ki≥k2i 且 ki≥k2i+1(1≤i≤ n)
若將此序列所儲存的向量r[1..n]看作是一棵完全二叉樹的儲存結構，則堆實質上是滿足如下性質的完全二叉樹：樹中任一非葉結點的關鍵字均不大於(或不小於)其左右孩子(若存在)結點的關鍵字。
根結點(堆頂)的關鍵字是堆裡所有結點關鍵字中最小者，稱為小根堆；根結點的關鍵字是堆裡所有結點關鍵字中最大者，稱為大根堆。
用大根堆排序的基本思想如下：
1、先將初始檔案r[1..n]建成乙個大根堆,此堆為初始的無序區
2、再將關鍵字最大的記錄r[1](即堆頂)和無序區的最後乙個記錄r[n]交換，由此得到新的無序區r[1..n-1]和有序區r[n]，且滿足r[1..n-1].
keys≤r[n].key
3、由於交換後新的根r[1]可能違反堆性質，故應將當前無序區r[1..n-1]調整為堆。然後再次將r[1..
n-1]中關鍵字最大的記錄r[1]和該區間的最後乙個記錄r[n-1]交換，由此得到新的無序區r[1..n-2]和有序區r[n-1..n]，且仍滿足關係r[1..
n-2].keys≤r[n-1..n].
keys，同樣要將r[1..n-2]調整為堆。直到無序區只有乙個元素為止。
八、二叉樹排序
二叉排序樹（binary sort tree）又稱二叉查詢樹。它或者是一棵空樹；或者是具有下列性質的二叉樹：
（1）若左子樹不空，則左子樹上所有結點的值均小於它的根結點的值；
（2）若右子樹不空，則右子樹上所有結點的值均大於它的根結點的值；
（3）左、右子樹也分別為二叉排序樹；
我的理解是：二叉樹排序，即先建乙個二叉排序樹，然後中序遍歷，即得到乙個從小到大的排序結果。
九，拓撲排序
拓撲排序是對有向無環圖的一種排序，表示了定點按邊的方向出現的先後順序。如果有還就無法表示兩個頂點的先後順序。
拓撲排序的基本演算法：
輸入aov網路，令定點數為n。
（1）在aov網路中選乙個沒有直接前驅的頂點，並輸出。
（2）從圖中刪除這個頂點，同時刪去所有他發出的有向邊。
（3）重複以上步驟，知道所有的頂點都已經輸出，則拓撲序列形成。
二．學習感悟
以上就是我對於本學期所學的各種排序演算法的總結，在學習的過程中遇到過很多的問題，包括是對概念認識的不清晰，還有運用不靈活等。在學習這門課程之前，我們學習過c語言，但由於我對c語言的掌握並不夠紮實，導致我對這門課程沒有什麼信心。但在學完了這門課程後， 我對資料結構與演算法有一定的了解，也加深了對c語言的理解，我感覺所以的致死框架都建立在基礎概念之上。
但是對於這門課程的學習，絕不是那種死記硬背，只有結合思考與運用才能夠加以理解和掌握。
我們都知道，了解了在程式設計過程中採用好的演算法可以降低程式的時間和空間複雜度。對作業系統、編譯原理、資料庫管理系統、軟體工程、人工智慧等的學習都是很有益的，而且所有的計算機系統軟體和應用軟體都要用到各種型別的資料結構。再次溫習這本書，增加了對資料結構與演算法的理解，對資料結構的構建也有更深層次的體會。
演算法的每一次改進和提高，都凝聚著人類的智慧型和辛勤勞動，每一次創新都給人類帶來了巨大的進步。剛開始學習的時候就感覺這學期課好多，而且好難，每天都感覺很累很累。到學期中的時候，都有點鼓不起來幹勁了，每天就是「快點下課快點下課」。
重新調整好狀態，發現落下不少，又努力的彌補。不管開心還是鬱悶，這門課就要結束了，學會了很多，沒學會的也多。胡老師是乙個很細緻的人，書上的每個知識點幾乎都講到了，也經常督促我們做課後習題，因為到了大學，大家都喜歡跳躍式前進，卻經常顧此失彼，我更加傾向於一步一步的學習。
在這裡感謝胡老師乙個學期的教導，也希望我能在接下來的考試中獲得好成績。
資料結構中排序演算法
include define maxlen 20 typedef int keytype typedef char infotype 10 typedef structrectype void insersort rectype r,int n r j 1 temp 在j 1處插入iprintf i...
Merge sort等各種資料結構排序演算法
資料局結構 排序演算法 一 複習要點 排序是使用最頻繁的一類演算法。排序分內排序與外排序。內排序演算法主要分5大類，有12個演算法。在插入排序類中討論了直接插入排序 二分法插入排序 表插入排序和shell排序演算法 在交換排序類中討論了起泡排序和快速排序演算法 在選擇排序類中討論了簡單選擇排序 錦標...
資料結構實驗 排序
排序實驗 常用排序方法實現 實驗目的 1 熟悉常用的內部排序方法 插入排序 選擇排序 交換排序 基數排序和歸併排序 2 通過實驗，掌握排序的思路和方法，並能分析常用的排序方法的時間複雜度和穩定性。實驗要求 1 在vc 或tc環境下實現基本功能 2 先完成基本功能，基本功能為必做內容，有多餘時間的同學...