排序量表的類型和其各自的優(yōu)缺點(diǎn)？

一、冒泡排序 已知一組無(wú)序數(shù)據(jù)a[1]、a[2]、……a[n]，需將其按升序排列。首先比較a[1]與 a[2]的值，若a[1]大于a[2]則交換 兩者的值，否則不變。再比較a[2]與a[3]的值，若a[2]大于a[3]則交換兩者的值，否則不變。再比 較a[3]與a[4]，以此 類推，最后比較a[n-1]與a[n]的值。這樣處理一輪后，a[n]的值一定是這組數(shù)據(jù)中最大的。再對(duì)a[1]~a[n- 1]以相同方法 處理一輪，則a[n-1]的值一定是a[1]~a[n-1]中最大的。再對(duì)a[1]~a[n-2]以相同方法處理一輪，以此類推。共處理 n-1 輪 后a[1]、a[2]、……a[n]就以升序排列了。 優(yōu)點(diǎn)：穩(wěn)定； 缺點(diǎn)：慢，每次只能移動(dòng)相鄰兩個(gè)數(shù)據(jù)。 二、選擇排序 每一趟從待排序的數(shù)據(jù)元素中選出最小（或最大）的一個(gè)元素，順序放在已排好序的數(shù)列的最后，直到全部待排序的數(shù) 據(jù)元素排完。 選擇排序是不穩(wěn)定的排序方法。 n 個(gè)記錄的文件的直接選擇排序可經(jīng)過(guò)n-1 趟直接選擇排序得到有序結(jié)果： ①初始狀態(tài)：無(wú)序區(qū)為R[1..n]，有序區(qū)為空。 ②第1 趟排序 在無(wú)序區(qū)R[1..n]中選出關(guān)鍵字最小的記錄R[k]，將它與無(wú)序區(qū)的第1 個(gè)記錄R[1]交換，使R[1..1]和R[2..n]分別變 為記錄個(gè)數(shù)增加1 個(gè)的新有序區(qū)和記錄個(gè)數(shù)減少1 個(gè)的新無(wú)序區(qū)。 ③第i 趟排序 第i 趟排序開(kāi)始時(shí)，當(dāng)前有序區(qū)和無(wú)序區(qū)分別為R[1..i-1]和R(1≤i≤n-1)。該趟 排序從當(dāng)前無(wú)序區(qū)中選出關(guān)鍵字最 小的記錄 R[k]，將它與無(wú)序區(qū)的第1 個(gè)記錄R 交換，使R[1..i]和R 分別變?yōu)橛涗泜€(gè)數(shù)增加1 個(gè)的新有序區(qū)和記錄個(gè)數(shù)減少 1 個(gè)的新無(wú)序區(qū)。 這樣，n 個(gè)記錄的文件的直接選擇排序可經(jīng)過(guò)n-1 趟直接選擇排序得到有序結(jié)果。 優(yōu)點(diǎn)：移動(dòng)數(shù)據(jù)的次數(shù)已知（n-1 次）； 缺點(diǎn)：比較次數(shù)多。 三、插入排序 已知一組升序排列數(shù)據(jù)a[1]、a[2]、……a[n]，一組無(wú)序數(shù)據(jù)b[1]、 b[2]、……b[m]，需將二者合并成一個(gè)升序數(shù)列。 首先比較b[1]與a[1]的值，若b[1]大于a[1]，則跳過(guò)，比較b[1]與a[2]的值， 若b[1]仍然大于a[2]，則繼續(xù)跳過(guò)，直 到b[1]小于a 數(shù)組中某一數(shù)據(jù)a[x]，則將a[x]~a[n]分別向后移動(dòng)一位，將b[1]插入到原來(lái) a[x]的位置這就完成了b[1] 的插入。b[2]~b[m]用相同方法插入。（若無(wú)數(shù)組a，可將b[1]當(dāng)作n=1 的數(shù)組a） 優(yōu)點(diǎn)：穩(wěn)定，快； 缺點(diǎn)：比較次數(shù)不一定，比較次數(shù)越少，插入點(diǎn)后的數(shù)據(jù)移動(dòng)越多，特別是當(dāng)數(shù)據(jù)總量龐大的時(shí)候，但用鏈表可以解決 這個(gè)問(wèn)題。 四、縮小增量排序 由希爾在1959 年提出，又稱希爾排序(shell 排序)。 已知一組無(wú)序數(shù)據(jù)a[1]、a[2]、……a[n]，需將其按升序排列。發(fā)現(xiàn)當(dāng)n 不大時(shí)，插入 排序的效果很好。首先取一增 量d(d