資料結構中排序方法有多少種,資料結構中常見的排序方式都有哪些?比如氣泡排序,快速排序等。每種排序具體是怎麼排的?

2021-05-12 16:55:50 字數 5397 閱讀 5349

1樓:匿名使用者

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)。

資料結構中常見的排序方式都有哪些?比如氣泡排序,快速排序等。每種排序具體是怎麼排的?

2樓:匿名使用者

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、快速排序:要採用分劃控制。比較複雜。

資料結構中幾種常見的排序演算法之比較

3樓:

實話實說,關於資料結構中幾種常見的排序演算法(例如:氣泡排序、shell排序、歸併排序、快速排序等)的效能好壞,還不只是學好了資料結構這門課程就能夠解決的問題,還必須要學習好、且精通掌握計算機軟體專業的另外一門非常重要的課程,才能夠解決這個問題。即:

計算機演算法複雜性理論。

只有同時把這門課程學好了,那麼才能夠真正掌握資料結構中的各種排序演算法、以及各種查詢演算法中所有涉及到的:比較次數、以及交換次數,最終才能夠根據具體的開發軟體規模的不同,選擇出一個適合開發該軟體的最佳演算法。

資料結構中幾種常見內部排序方法的比較

4樓:百度文庫精選

內容來自使用者: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....

5樓:張幾何

這些全是內排,有什麼問題你再問我

資料結構的排序方法有哪些?

6樓:百度文庫精選

內容來自使用者: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....

7樓:

題目似乎不是很完整。

先回答:(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

8樓:果典熊經賦

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)。

9樓:春曉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)

寫類,實現棧這種資料結構,要求底層資料使用A

棧的特點的就是後進先出,那麼你就linkedlist,如果要新增一個元素,就把他存到最後一個位置,要取一個元素,也從最後開始取就可以實現了,只有linkedlist才有存,取,刪最後一個元素這個方法,所以要要用linkedlist 如下 public class studytestpublic vo...

C語言資料結構求解,c語言常見的資料結構有哪些

如上圖,把k位置的資料刪除後,需要把k後面的元素逐個向前移動一次。一共是n個元素,k前面 包括k 一共是k個元素,剩下需要移動的就是n k個元素。答案選a 需要移動k 1 k 2。一直到n的元素,所以次數是n k 1 1 c語言常見的資料結構有哪些?1 線性資料結構 元素之間一般存在元素之間存在一對...

什麼是資料結構和演算法,資料結構和演算法有什麼關係?資料結構就是演算法嗎?

程式 資料結構 演算法 資料結構是相互之間存在的一種或多種特定關係的資料元素的集合。包括4類基本的結構 集合 線形結構 樹形結構 圖狀或網狀結構。通俗點就是資料的邏輯結構,比方說這些資料在記憶體中以什麼樣的結構存放。演算法實際是程式設計過程中完成一件事採用的方法,比方說現實生活中做數學題時兩個人都將...