c語(yǔ)言課程設(shè)計(jì)---各種排序算法的設(shè)計(jì)和分析-文庫(kù)吧
2025-05-16 10:01 本頁(yè)面
【正文】 （ 6）堆排序：在堆排序的算法中先建一個(gè)大頂堆，既先選得一個(gè)關(guān)鍵字作為最大的記錄并與序列中最后一個(gè)記錄交換，然后對(duì)序列中前 N1 記錄進(jìn)行選擇，重新將它調(diào)整成一個(gè)大頂堆，如此反復(fù)直到排序結(jié)束。 （ 7）基數(shù)排序：按最低位優(yōu)先法先對(duì)低位關(guān)鍵字進(jìn)行排序，直到對(duì)最高位關(guān)鍵字排序?yàn)橹?，?jīng)過若干次分配和收集來實(shí)現(xiàn)排序 4 （二）時(shí)間復(fù)雜度分析 排序算法 最差時(shí)間 時(shí)間復(fù)雜度 是否穩(wěn)定？ 插入排序 O(n2) O(n2) 穩(wěn)定 冒泡排序 O(n2) O(n2) 穩(wěn)定 快速排序 O(n2) O(n*log2n) 不穩(wěn)定 選擇排序 O(n2) O(n2) 穩(wěn)定 堆排序 O(n*log2n) O(n*log2n) 不穩(wěn)定 基數(shù)排序 O(n*log2n) O(n2) 穩(wěn)定 4000 個(gè)數(shù)據(jù)的時(shí)間比較： 算法名稱 用時(shí) 直接插入排序 折半插入排序 起泡排序 快速排序 選擇排序 堆排序 基數(shù)排序 （ 三 ） 源代碼 ： 代碼如下： include include include 5 define N 4000 void InsertSort() //第一個(gè)插入排序 { int i,j,t。 int a[N]。 for(i=0。iN。i++) { a[i]=(int)rand()。 printf(%d ,a[i])。 } printf(\n)。 for(i=1。iN。i++) { t=a[i]。 for(j=i1。j=0amp。amp。ta[t]。j) { a[j+1]=a[j]。 a[j+1]=t。 } } for(i=0。iN。i++) { printf(插入排序的程序： %d\n,a[i])。 } } void BInsertSort()//第二個(gè)，折半插入排序 { int i=0,j=0,low=0,high=0,m=0。 for(i=0。iN。i++) { a[i]=(int)rand()。 printf(%d ,a[i])。 } printf(\n)。 for(i=2。i=N。++i) { L[0]=L[i]。 low=1。high=i1。 while(low=high){ m=(low+high)/2。 if(L[0]L[m]) high=m1。 else low=m+1。 } for(j=i1。L[0]L[j]。j) L[j+1]=L[j]。 //記錄后移 L[high+1]=L[0]。 //插入 } } 6 void BubbleSort()//第三個(gè)，冒泡排序 { int i,j,l。 int a[N]。 for(i=0。iN。i++) { a[i]=(int)rand()。 printf(%d ,a[i])。 } printf(\n)。 for(i=0。iN。i++) { for(j=0。jNi。
畢業(yè)設(shè)計(jì)相關(guān)推薦
鄂ICP備17016276號(hào)-1