1樓：百度文庫精選
內容來自使用者:cngdzjl
資料結構各種排序方法的綜合比較
結論: 排序方法 平均時間 最壞時間 輔助儲存 簡單排序 o(n2) o(n2) o(1) 快速排序 o(nlogn) o(n2) o(logn) 堆排序 o(nlogn) o(nlogn) o(1) 歸併排序 o(nlogn) o(nlogn) o(n) 基數排序 o(d(n+rd)) o(d(n+rd)) o(rd)ps:直接插入排序、氣泡排序為簡單排序，希爾排序、堆排序、快速排序為不穩定排序
一、時間效能
按平均的時間效能來分，有三類排序方法：時間複雜度為o(nlogn)的方法有：快速排序、堆排序和歸併排序，其中以快速排序為最好；
時間複雜度為o(n2)的有：直接插入排序、起泡排序和簡單選擇排序，其中以直接插入為
最好，特別是對那些對關鍵字近似有序的記錄序列尤為如此；
時間複雜度為o(n)的排序方法只有，基數排序。
當待排記錄序列按關鍵字順序有序時，直接插入排序和起泡排序能達到o(n)的時間複雜度;而對於快速排序而言，這是最不好的情況，此時的時間效能蛻化為o(n2)，因此是應該儘量避免的情況。簡單選擇排序、堆排序和歸併排序的時間效能不隨記錄序列中關鍵字的分佈而改變。
二、空間效能
指的是排序過程中所需的輔助空間大小。
1.所有的簡單排序方法(包括：直接插入、起泡和簡單選擇3....
2樓：
題目似乎不是很完整。
先回答：（1）c，（2）a，（3）d，(4)b，(5)g
(1) c．插入排序 法從未排序的序列中依次取出元素，與已排序序列(初始時為空)中的元素作比較，將其放入已排序序列的正確位置上；
(2) a．選擇排序 法從未排序的序列中挑選元素， 並將其依次放入已排序序列(初始時為空)的一端；交換排序方法是對序列中的元素進行一系列比較， 當被比較的兩元素逆序時，進行交換；
(3) d．起泡排序 和 （4）b．快速排序 是基於這類方法的兩種排序方法；
(5) g．堆排序 法是基於選擇排序的一種排序方法，是完全二叉樹結構的一個重要應用。
原題應該是：
排序方法有許多種，（1）法從未排序的序列中依次取出元素，與已排序序列（初始時為空）中的元素作比較，將其放入已排序序列的正確位置上；（2）法從未排序的序列中挑選元素，並將其依次放入已排序序列（初始時為空）的一端； 交換排序方法是對序列中的元素進行一系列比較，當被比較的兩元素逆序時，進行交換；（3）和（4）是基於這類方法的兩種排序方法， 而（4）是比（3）效率更高的方法；（5）法是基於選擇排序的一種排序方法，是完全二叉樹結構的一個重要應用。 【北方交通大學 1999
一、3 （5分）】
（1）--（5）: a．選擇排序 b．快速排序 c．插入排序 d．起泡排序
e．歸併排序 f．shell排序 g．堆排序 h．基數排序
【解答】（1）c，（2）a，（3）d，(4)b，(5)g
3樓：果典熊經賦
1、插入排序（直接插入排序和希爾排序）
2、選擇排序（直接選擇排序和堆排序）
3、交換排序（氣泡排序和快速排序）
4、歸併排序
5、基數排序
直接插入排序：逐個將後一個數加到前面的排好的序中。在直接插入排序過程中，對其中一個記錄的插入排序稱為一次排序；直接插入排序是從第二個記錄開始進行的，因此，長度為n的記錄序列需要進行n-1次排序才能完成整個序列的排序。
時間複雜度為o(n2)。
希爾排序：希爾排序又稱縮小增量排序，增量di可以有各種不同的取法，但最後一次排序時的增量必須為1，最簡單可取di+1=di/2（取小）。時間複雜度為o(n(log2n)2)。
直接選擇排序
說明：每次將後面的最小的找出來插入前面的已排好的序中。同理，具有n個記錄的序列要做n-1次排序。
時間複雜度為o(n2)。
氣泡排序：兩個兩個比較，將大的往後移。通過第一次氣泡排序，使得待排序的n個記錄中關鍵字最大的記錄排到了序列的最後一個位置上。
然後對序列中前n-1個記錄進行第二次氣泡排序。。。對於n個記錄的序列，共需進行n次氣泡排序。時間複雜度為o(n2)。
快速排序：又叫分割槽交換排序，是對氣泡排序方法的一種改進。時間複雜度為o(nlog2n)。
歸併排序：將兩個或兩個以上的有序資料序列合併成一個有序資料序列的過程。時間複雜度為o(nlog2n)。
4樓：春曉sweet甜
穩定的氣泡排序（bubble sort） — o(n2)
雞尾酒排序 (cocktail sort, 雙向的氣泡排序) — o(n2)
插入排序 （insertion sort）— o(n2)
桶排序 （bucket sort）— o(n); 需要 o(k) 額外 記憶體
計數排序 (counting sort) — o(n+k); 需要 o(n+k) 額外 記憶體
歸併排序 （merge sort）— o(n log n); 需要 o(n) 額外記憶體
原地歸併排序 — o(n2)
二叉樹排序 （binary tree sort） — o(n log n); 需要 o(n) 額外記憶體
鴿巢排序 (pigeonhole sort) — o(n+k); 需要 o(k) 額外記憶體
基數排序 （radix sort）— o(n·k);
不穩定選擇排序 （selection sort）— o(n2)
希爾排序 （shell sort）— o(n log n)
堆排序 （heapsort）— o(n log n) smoothsort — o(n log n)
快速排序 （quicksort）— o(n log n)
資料結構中排序方法有多少種
5樓：匿名使用者
1、插入排序（直接插入排序和希爾排序）
2、選擇排序（直接選擇排序和堆排序）
3、交換排序（氣泡排序和快速排序）
4、歸併排序
5、基數排序
直接插入排序：逐個將後一個數加到前面的排好的序中。在直接插入排序過程中，對其中一個記錄的插入排序稱為一次排序；直接插入排序是從第二個記錄開始進行的，因此，長度為n的記錄序列需要進行n-1次排序才能完成整個序列的排序。
時間複雜度為o(n2)。
希爾排序：希爾排序又稱縮小增量排序，增量di可以有各種不同的取法，但最後一次排序時的增量必須為1，最簡單可取di+1=di/2（取小）。時間複雜度為o(n(log2n)2)。
直接選擇排序
說明：每次將後面的最小的找出來插入前面的已排好的序中。同理，具有n個記錄的序列要做n-1次排序。
時間複雜度為o(n2)。
氣泡排序：兩個兩個比較，將大的往後移。通過第一次氣泡排序，使得待排序的n個記錄中關鍵字最大的記錄排到了序列的最後一個位置上。
然後對序列中前n-1個記錄進行第二次氣泡排序。。。對於n個記錄的序列，共需進行n次氣泡排序。時間複雜度為o(n2)。
快速排序：又叫分割槽交換排序，是對氣泡排序方法的一種改進。時間複雜度為o(nlog2n)。
歸併排序：將兩個或兩個以上的有序資料序列合併成一個有序資料序列的過程。時間複雜度為o(nlog2n)。
資料結構中常見的排序方式都有哪些？比如氣泡排序，快速排序等。每種排序具體是怎麼排的？
6樓：匿名使用者
1.直接插入：就是有一個已經排好的子序列，它是有序的。
然後來一個插入一個仍是這個序列有序。比如a1本身就是有序的。a2來了，要和a1比較，a2大就插在a1之後，小就在a1之前，那麼a1、a2就是新的有序子序列，然後a3來了，又要插入進來，逐個與a2、a1比較插在它的適當位置再次形成子序列，就按這樣一步步進行，知道最後一個插入時，以前的都已經有序了。
2.希爾排序：由於有時候資料量大，用直接插入就不太合適。
於是把你的一組待排序資料按如8、4、2、1的一組增量數來分組，即第一次，a1和a9和a17甚至還有更多間隔為八的數分為一組進行直接插入排序，第二次則是新的a1和a5、a9、a13……依次知道最後比較資料之間的間隔數為1，每次都進行插入排序
3.直接選擇：n個數逐個比較，誰大的誰放最後（n的位置），比較範圍減一；然後又從n-1個數中找最大的，又放最後（n-1的位置），依次這樣進行就可以。
4.冒泡：比較的時候如果前者比後者大就要進行值的交換。那麼最大的每次都會沉到底下。比較範圍減一。
5、快速排序：要採用分劃控制。比較複雜。
資料結構中排序的方法中穩定的有那些，不穩定的有那些（如快速排序等）
7樓：黃家三爺爺
穩定的氣泡排序（bubble sort） — o(n2) 雞尾酒排序 (cocktail sort, 雙向的氣泡排序) — o(n2) 插入排序 （insertion sort）— o(n2) 桶排序 （bucket sort）— o(n); 需要 o(k) 額外 記憶體 計數排序 (counting sort) — o(n+k); 需要 o(n+k) 額外 記憶體 歸併排序 （merge sort）— o(n log n); 需要 o(n) 額外記憶體 原地歸併排序 — o(n2) 二叉樹排序 （binary tree sort） — o(n log n); 需要 o(n) 額外記憶體 鴿巢排序 (pigeonhole sort) — o(n+k); 需要 o(k) 額外記憶體 基數排序 （radix sort）— o(n·k); 需要 o(n) 額外記憶體 gnome sort — o(n2) library sort — o(n log n) with high probability, 需要 (1+ε)n 額外記憶體
不穩定選擇排序 （selection sort）— o(n2) 希爾排序 （shell sort）— o(n log n) 如果使用最佳的現在版本 comb sort — o(n log n) 堆排序 （heapsort）— o(n log n) smoothsort — o(n log n) 快速排序 （quicksort）— o(n log n) 期望時間, o(n2) 最壞情況; 對於大的、亂數串列一般相信是最快的已知排序 introsort — o(n log n) patience sorting — o(n log n + k) 最外情況時間, 需要 額外的 o(n + k) 空間, 也需要找到最長的遞增子序列（longest increasing subsequence）
資料結構中排序的方法中穩定的有那些，不穩定的有那些（如快速排序等）
穩定的氣泡排序 bubble sort o n2 雞尾酒排序 cocktail sort,雙向的氣泡排序 o n2 插入排序 insertion sort o n2 桶排序 bucket sort o n 需要 o k 額外 記憶體 計數排序 counting sort o n k 需要 o n k...
哪些資料結構與演算法需要學習,什麼是資料結構和演算法學演算法還需要去了解資料結構嗎
2談談面向bai物件,物件就是一種du資料結構zhi 什麼是資料結構和演算法?學演算法還需要去了解資料結構嗎?你這理解不完全正確。因為資料結構不只是記憶體中資料的排列,它是對資料的一種組織方式,就像圖書館要排書一樣,是為了便於操作,同時它本身也整合了對通用操作 比如查詢 比較等的支援。陣列不是一種資...
資料結構涉及到哪些數學知識，學習資料結構需要哪些數學知識？
好！我告訴你。我畢業兩年了，都是做c c 開發方面的 首先說一下 回資料結構和vc mfc以及資料結構的答應用，vc mfc主要是開發上位機軟體，即pc機上的軟體的。一般情況下做vc一般開發不需要掌握太多的資料結構知識。開發中不會用太多，瞭解就夠了。資料結構一般常用在嵌入式開發，譬如路由器開發裡常用...