請問:如何比較c語言中上述幾種排序方法在不同情況下的優(yōu)劣,從速度和所占存儲空間兩方面? 請給出驗證方法.
熱心網(wǎng)友
相關(guān)知識介紹（所有定義只為幫助讀者理解相關(guān)概念，并非嚴格定義）：1、穩(wěn)定排序和非穩(wěn)定排序 簡單地說就是所有相等的數(shù)經(jīng)過某種排序方法后，仍能保持它們在排序之前的相對次序，我們就說這種排序方法是穩(wěn)定的。反之，就是非穩(wěn)定的。 比如：一組數(shù)排序前是a1,a2,a3,a4,a5，其中a2=a4，經(jīng)過某種排序后為a1,a2,a4,a3,a5，則我們說這種排序是穩(wěn)定的，因為a2排序前在a4的前面，排序后它還是在a4的前面。假如變成a1,a4,a2,a3,a5就不是穩(wěn)定的了。2、內(nèi)排序和外排序 在排序過程中，所有需要排序的數(shù)都在內(nèi)存，并在內(nèi)存中調(diào)整它們的存儲順序，稱為內(nèi)排序； 在排序過程中，只有部分數(shù)被調(diào)入內(nèi)存，并借助內(nèi)存調(diào)整數(shù)在外存中的存放順序排序方法稱為外排序。3、算法的時間復(fù)雜度和空間復(fù)雜度 所謂算法的時間復(fù)雜度，是指執(zhí)行算法所需要的計算工作量。 一個算法的空間復(fù)雜度，一般是指執(zhí)行這個算法所需要的內(nèi)存空間。================================================================================*//*================================================ 功能：選擇排序 輸入：數(shù)組名稱（也就是數(shù)組首地址）、數(shù)組中元素個數(shù)================================================*//*====================================================算法思想簡單描述： 在要排序的一組數(shù)中，選出最小的一個數(shù)與第一個位置的數(shù)交換； 然后在剩下的數(shù)當中再找最小的與第二個位置的數(shù)交換，如此循環(huán) 到倒數(shù)第二個數(shù)和最后一個數(shù)比較為止。 選擇排序是不穩(wěn)定的。算法復(fù)雜度O(n2)--[n的平方]=====================================================*/void select_sort(int *x, int n){ int i, j, min, t; for (i=0; i=2] 個數(shù)已經(jīng)是排 好順序的，現(xiàn)在要把第n個數(shù)插到前面的有序數(shù)中，使得這n個數(shù) 也是排好順序的。如此反復(fù)循環(huán)，直到全部排好順序。 直接插入排序是穩(wěn)定的。算法時間復(fù)雜度O(n2)--[n的平方]=====================================================*/void insert_sort(int *x, int n){ int i, j, t; for (i=1; i=0 && t0; h=k) /*循環(huán)到?jīng)]有比較范圍*/ { for (j=0, k=0; j *(x+j+1)) /*大的放在后面，小的放到前面*/ { t = *(x+j); *(x+j) = *(x+j+1); *(x+j+1) = t; /*完成交換*/ k = j; /*保存最后下沉的位置。這樣k后面的都是排序排好了的。*/ } } }} /*================================================ 功能：希爾排序 輸入：數(shù)組名稱（也就是數(shù)組首地址）、數(shù)組中元素個數(shù)================================================*//*====================================================算法思想簡單描述： 在直接插入排序算法中，每次插入一個數(shù)，使有序序列只增加1個節(jié)點， 并且對插入下一個數(shù)沒有提供任何幫助。如果比較相隔較遠距離（稱為 增量）的數(shù)，使得數(shù)移動時能跨過多個元素，則進行一次比較就可能消除 多個元素交換。 ell于1959年在以他名字命名的排序算法中實現(xiàn) 了這一思想。算法先將要排序的一組數(shù)按某個增量d分成若干組，每組中 記錄的下標相差d。對每組中全部元素進行排序，然后再用一個較小的增量 對它進行，在每組中再進行排序。當增量減到1時，整個要排序的數(shù)被分成 一組，排序完成。 下面的函數(shù)是一個希爾排序算法的一個實現(xiàn)，初次取序列的一半為增量， 以后每次減半，直到增量為1。 希爾排序是不穩(wěn)定的。=====================================================*/void shell_sort(int *x, int n){ int h, j, k, t; for (h=n/2; h0; h=h/2) /*控制增量*/ { for (j=h; j=0 && tt) /*在右邊的只要比基準點大仍放在右邊*/ { j--; /*前移一個位置*/ } if (i=h2i,hi=2i+1）或（hi=0; i--) { sift(x,n,i); /*初始建堆*/ } for (k=n-1; k=1; k--) { t = *(x+0); /*堆頂放到最后*/ *(x+0) = *(x+k); *(x+k) = t; sift(x,k,0); /*剩下的數(shù)再建堆*/ }}void main(){ #define MAX 4 int *p, i, a[MAX]; /*錄入測試數(shù)據(jù)*/ p = a; printf("Input %d number for sorting :\n",MAX); for (i=0; i 唉，氣死我了，好容易打了半個鐘頭上千字，iASK 居然報出錯，全沒了，不打了！熱心網(wǎng)友