資料結構中什麼是排序演算法的穩定性

2021-07-12 17:37:40 字數 3408 閱讀 7187

1樓:幻想v飛翔

比如說 5 2 3 5# 1 排序後可能是 5 5# 3 2 1 也可能是5# 5 3 2 1,前者是穩定的,後者是不穩定的。冒泡,選擇有穩定性,快拍沒有

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

2樓:匿名使用者

冒泡。 複雜度n平方。適用於陣列

插入排序。複雜度n平方。適用於連結串列

快排。複雜度nlog(n)。

希爾排序。這是一種插入排序,但是從統計角度看,比插入排序要快。

資料結構排序演算法有哪些常用的

3樓:銷

最常用的是快速排序,基數排序,計數排序,歸併排序,堆排序,(偶爾還有插入排序)

都有各自的應用,快排就是單純的快,但是特殊資料下複雜度會退化

基數排序可以配合一些特定的演算法,譬如字尾陣列的構建

計數排序簡單且常用,通常排序值域小但是資料量大的情況

歸併直接用來排序並不多,但是可以用來求解一些其他問題,本身的思想也非常重要,有很多拓展的演算法(不是排序演算法)

堆排序勝在穩定,不論資料如何最壞都是o(nlogn),一般情況比快速排序慢些,但是極端情況下表現十分優秀,常用來配合快速排序,優化其穩定性

插入排序適合極少量資料的排序(幾個到十幾個),速度要比這些高階演算法快一些

4樓:匿名使用者

簡單選擇排序的基本思想:比較+交換。

從待排序序列中,找到關鍵字最小的元素;

如果最小元素不是待排序序列的第一個元素,將其和第一個元素互換;

從餘下的 n - 1 個元素中,找出關鍵字最小的元素,重複(1)、(2)步,直到排序結束。

因此我們可以發現,簡單選擇排序也是通過兩層迴圈實現。

第一層迴圈:依次遍歷序列當中的每一個元素

第二層迴圈:將遍歷得到的當前元素依次與餘下的元素進行比較,符合最小元素的條件,則交換。

排序演算法效能比較(資料結構)c語言程式

5樓:匿名使用者

#include

#include

#include

#define l 8 //排序元素個數

#define false 0

#define true 1

typedef struct

rectype;

typedef rectype seqlist[l+1];

int num; //定義排序趟數的全域性變數

seqlist r;

//直接插入排序

void insertsort()

getchar();

printf("\n");

for(i=2;i<=l;i++)

else }

} gap=gap/2;

m++;

printf("\t\t第%d趟排序結果為(按回車鍵開始排序):\n\t\t",m);

for(k=1;k<=l;k++)

getchar();

printf("\n");

} printf("\n\t\t排序的最終結果是:\n\t\t");

for(i=1;i<=l;i++)

printf("\n");

} //氣泡排序

void bubblesort()

getchar();

printf("\n");

for(i=1;i=i+1;j--)

if(i=r[j].key)

else }

r[j/2].key=temp;

}//堆排序

void heapsort()

for(i=l-1,k=1;i>=1;i--,k++)

getchar();

printf("\n");

} }void heap()

getchar();

printf("\n");

heapsort();

printf("\n\t\t排序的最終結果是:\n\t\t");

for(i=1;i<=l;i++)

printf("\n");

} main()

printf("\n\t\t排序資料已經輸入完畢!");

ch1='y';

while(ch1=='y'||ch1=='y')

switch(ch2)

printf("\n\t\t排序資料已經輸入完畢!");

break;

case '2':

insertsort();

break;

case '3':

shellsort();

break;

case '4':

bubblesort();

break;

case '5':

printf("\n\t\t原始資料為(按回車鍵開始排序):\n\t\t");

for(k=1;k<=l;k++)

getchar();

printf("\n");

num=0;

quicksort(1,l);

printf("\n\t\t排序的最終結果是:\n\t\t");

for(k=1;k<=l;k++)

printf("\n");

break;

case '6':

selectsort();

break;

case '7':

mergesort();

break;

case '8':

heap();

break;

case '0':

ch1='n';

break;

default:

system("cls");

printf("\n\t\t 對不起,您的輸入有誤,請重新輸入!\n");

break;

} if(ch2!='0') }

} }}

6樓:夢想的影子

這題你只要把每個演算法的程式**看一下,在計算下就行

氣泡排序:兩個迴圈,從1加到n,(1+n)n/2 = 500500,最壞交換情況是每次判斷都要交換,既500500*3次

選擇排序:也是兩個迴圈,比較次數跟氣泡排序一樣500500,但是這個只要底層迴圈交換,既只需1000*3 = 3000次賦值。

插入排序:迴圈次數一樣500500,但是這個最壞情況是每比較一次就賦值一次,既需500500次賦值

希爾排序:時間複雜度是n^1.3倍,比較次數和賦值應該是1000^1.3次方。

歸併排序和快速排序,你去查查它的時間複雜度是怎麼算,o(lgn*n),好像有係數,演算法導論那本書上有,現在不記得是多少了。

希望能幫到你,

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

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

資料結構中,什麼時候用,資料結構中,什麼時候用

這個是取bai地址的作du 用。一般定義一個普通變數,zhi若要dao將其在指標中呼叫就專要用 如int a 要將屬a在函式void hanshu int t 中呼叫的話,那麼就應該寫成hanshu a 另外在鍵盤輸入資料的時候也要用到,比如scanf d a 這個符號,主要用在這兩個地方。在資料結...

求用C語言或C 編寫的資料結構中的快速排序 麻煩寫出大概的設計過程,語句的含義 謝謝啦

include include define size 20 typedef structrecord void initrecord record h,int a int qkpass record r,int low,int high while i r ele i i if iele j r ...