【正文】 還可以通過HTML5 可視化設(shè)計(jì)器設(shè)計(jì)令人難以置信的用戶界面。2排序算法(1) 基本原理假設(shè)待排序的n個(gè)記錄{L0，L1，…，Ln}順序存放在數(shù)組中，直接插入法在插入記錄Li(i=1，2，…，n1)時(shí)，記錄被劃分為兩個(gè)區(qū)間[L0,Li1]和[Li+1,Ln1],其中，前一個(gè)子區(qū)間已經(jīng)排好序，后一個(gè)子區(qū)間是當(dāng)前未排序的部分，將關(guān)鍵碼Ki與Ki1Ki2，…，K0依次比較，找出應(yīng)該插入的位置，將記錄Li插，然后將剩下的i1個(gè)元素按關(guān)鍵詞大小依次插入該有序序列，沒插入一個(gè)元素后依然保持該序列有序，經(jīng)過i1趟排序后即成為有序序列。 直接插入排序示例(2) 算法描述對(duì)字符串順序鏈表src作直接插入排序,返回值為空。 i 。 src[i] = src[i 1]。 for (。 j) { src[j + 1] = src[j]。 } } }(3) 時(shí)間復(fù)雜度分析直接插入排序算法必須進(jìn)行n1趟。因此最好情況下的時(shí)間復(fù)雜度就是O(n)。(1) 基本思想 是對(duì)直接插入排序算法的一種改進(jìn)，由于排序算法過程中，就是不斷的依次將元素插入前面已排好序的序列中。(2) 算法描述對(duì)字符串順序鏈表src作折半插入排序,返回值為空。 i 。 int low = 1, high = i 1。 if (src[0].pareTo(src[m]) 0) {// high = m 1。 } } // 記錄后移 for (int j = i 1。 j) { src[j + 1] = src[j]。 } }(3)時(shí)間空間復(fù)雜度 折半插入排序算法是一種穩(wěn)定的排序算法，比直接插入算法明顯減少了關(guān)鍵字之間比較的次數(shù)，因此速度比直接插入排序算法快，但記錄移動(dòng)的次數(shù)沒有變，所以折半插入排序算法的時(shí)間復(fù)雜度仍然為O(n^2)，與直接插入排序算法相同。(1) 基本原理 對(duì)起泡排序的一種改進(jìn)。假設(shè)待排序的序列為{ [s],[s+1],...,[t]},首先任意選取一個(gè)記錄（通常選第一個(gè)）作為支點(diǎn)，然后按下述原則重新排列其余記錄：將所有關(guān)鍵字比它小的記錄都安置在它的位置之前，將所有關(guān)鍵字較它打的記錄都安置在它的位置之后。這個(gè)過程稱一趟快速排序[11]。public int partition(String[] l,int low,int high) { //用字表的第一個(gè)記錄軸的記錄 l[0] = l[low]。 //從表的兩端交替向中間掃描 while(low high) { //將比軸記錄小的記錄移到低端 while(low high amp。 l[high].pareTo(pivotkey) = 0) { high。 while(lowhighamp。l[low].pareTo(pivotkey)= 0) { ++low。 } //軸記錄到位 l[low] = l[0]。 }(3) 時(shí)間復(fù)雜度分析如果每一次分劃操作后，左、右兩個(gè)子序列的長度基本相等，則快速排序的效率最高，其最好情況時(shí)間復(fù)雜度為O(nlog2n)；反之，如果每次分劃操作所產(chǎn)生的兩個(gè)子序列，其中之一為空序列，此時(shí)，快速排序效率最低，其最壞情況時(shí)間復(fù)雜度為O(n2)?？焖倥判虻钠骄闆r時(shí)間復(fù)雜度為O(nlog2n)。 選擇排序示例(2)算法描述對(duì)字符串順序鏈表src作選擇排序，返回值為空。 i 。 if (j != i) { String temp = src[i]。 src[j] = temp。不論初始排列如何，該算法都必須執(zhí)行n1趟，每趟執(zhí)行ni1次關(guān)鍵字的比較，這樣總的比較次數(shù)為：所以，簡(jiǎn)單選擇排序的最好、最壞和平均情況的時(shí)間復(fù)雜度都為O(n2)。利用歸并思想實(shí)現(xiàn)排序，假設(shè)初始序列含有n/2個(gè)長度為2或1的有序子列表；再兩兩歸并，......，如此重復(fù)直到得到長度為n的有序列表為止；。 //臨時(shí)數(shù)據(jù)存儲(chǔ) int i=s, k = 0,j = m+1。i=m amp。 j = t。 i++。 j++。i = m。 k++。j = t。 k++。 }(3) 時(shí)間復(fù)雜度分析一趟歸并排序的操作是，調(diào)用n/2h次算法merge將sr[1...n]中前后相鄰且長度為h的有序段進(jìn)行兩兩歸并得到前后相鄰，長度為2h的有序段并存放在Tr[1 ... n]中整個(gè)歸并排序需進(jìn)行l(wèi)og2n趟，可見需要和待排序等數(shù)量的輔助空間，其時(shí)間復(fù)雜度為O(nlogn)(1) 基本原理設(shè)數(shù)組中下標(biāo)為0的分量為表頭結(jié)點(diǎn)，并令表頭結(jié)點(diǎn)記錄的關(guān)鍵字取最大整數(shù)MAX，則表的插入過程描述如下：首先將靜態(tài)鏈表中的數(shù)組下標(biāo)為1的分量和表頭結(jié)點(diǎn)構(gòu)成一個(gè)循環(huán)鏈表，然后依次將下標(biāo)為2至n的分量按記錄關(guān)鍵字非遞減有序插入到循環(huán)鏈表中[1]。 private void updateNext(Node[] nodes) { for (int i = 2。 i++) { int q = 0。 while (nodes[i].getValue().pareTo(nodes[p].getValue()) 0) { q = p。 } nodes[q].setNext(i)。 } }(3) 時(shí)間復(fù)雜度分析 和直接插入排序相比，不同之處僅是以修改2n次指針值代替移動(dòng)記錄，排序過程中所需進(jìn)行的關(guān)鍵字間的比較次數(shù)相同，因此，表插入排序的時(shí)間復(fù)雜度仍是O(n2)；(1) 基本原理 堆含義表明，所有非終點(diǎn)結(jié)點(diǎn)的值均不大于（或不小于）其左右孩子結(jié)點(diǎn)；若輸出堆頂?shù)淖钚≈抵?，使得剩余n1個(gè)元素的序列重又建成一個(gè)堆，則得到n個(gè)元素中的次小值，如此反復(fù)執(zhí)行，便得到一個(gè)有序序列；堆排序解決2個(gè)問題：；，調(diào)整剩余元素成為一個(gè)新的堆；。public void adjustHeap(String[] num, int s, int t) { int i = s。 j = t。amp。// 找出較大者把較大者給num[i] if (num[i].pareTo(num[j])0) break。 num[i] = num[j]。 i = j。堆排序的最壞時(shí)間復(fù)雜度為O(nlogn)。由于建初始堆所需的比較次數(shù)較多，所以堆排序不適宜于記錄數(shù)較少的文件。（MSD）(1) 基本原理是一種借助多關(guān)鍵字排序的思想對(duì)單邏輯關(guān)鍵字進(jìn)行排序的方法；MSD：先對(duì)最主要位關(guān)鍵字K0進(jìn)行排序，將序列分成若干子序列，每個(gè)子序列中的記錄都具有相同的K0值，然后分別就每個(gè)子序列對(duì)關(guān)鍵字K1進(jìn)行排序，按K1值得不同再分成若干更小的子序列，依次重復(fù)直至每個(gè)子序列中都有相同的關(guān)鍵字[1]。public void msd(String[] data, int power) { String[][] temp = new String[26][]。 int pos = 0。 if (power 0) return。 i 。 if (power data[i].length()) { pos = (int) data[i].charAt(power) 97。 } temp[pos][order[pos]] = data[i]。 } ++power。 i 26。amp。 msd(temp[i], power)。 i 26。 j 。// regain the sorted numbers } } } }(3) 時(shí)間復(fù)雜度分析對(duì)于n個(gè)記錄（假設(shè)每個(gè)記錄含d個(gè)關(guān)鍵字，每個(gè)關(guān)鍵字的取值范圍為rd個(gè)值），時(shí)間復(fù)雜度為O(d(n+rd)),其中每一趟分配的時(shí)間復(fù)雜度為O(n),輔助存儲(chǔ)O(rd)。排序算法動(dòng)態(tài)演示系統(tǒng)鏈
表
插
入
排
序直
接
插
入
排
序折
半
插
入
排
序交
換
排
序選
擇
排
序歸
并
排
序堆
排
序基
數(shù)
排
序 系統(tǒng)模塊結(jié)構(gòu)圖 模塊算法流程圖(1) 直接插入排序。 折半插入排序算法流程圖(3) 選擇排序。 快速排序算法流程圖(5) 歸并排序。 堆排序算法流程圖(7) 鏈表插入排序。 基數(shù)MSD排序算法流程圖4實(shí)現(xiàn) 直接插入排序?qū)⒆址當(dāng)?shù)組封裝為VectorUnit，同時(shí)利用GUI在ContentPanel（中間JPanel）中繪制數(shù)據(jù)；()切入到排序代碼中，完成數(shù)組拷貝與賦值。().setSelectIndexs(new int[]{})。實(shí)現(xiàn)代碼如下：public void insertSortToShow(String[] src, int index) { units = (src)。 if ((src[index]).pareTo(HanziToPinyin. getPingYin(src[index 1])) 0) { src[0] = src[index]。 int j = index 2。 (src[0]).pareTo(HanziToPinyin. getPingYin(src[j])) 0。 //src[0]插入到插入位置 } repaintUnit(500)。AccessoryPanel（右邊JPanel）中加入JList，(int[] i)完成代碼跟隨。該方法切入到排序代碼完成排序算法每一步實(shí)現(xiàn)效果。 // 獲取顯示數(shù)據(jù) ().setUnits(units)。 //數(shù)組拷貝及代碼跟隨 int low = 1, high = index 1。 // 在src[low...high]中折半查找 (units)。 // 延遲time后重繪 repaintUnit(1000)。 // 記錄后移 for (int j = index 1。 j) { ......記錄后移 } ......將src[0]插入到指定位置 }將字符串?dāng)?shù)組封裝為VectorUnit，同時(shí)利用GUI在ContentPanel（中間JPanel）中繪制數(shù)據(jù)；()切入到排序代碼中，完成數(shù)組拷貝與賦值。().setSelectIndexs(new int[]{})。實(shí)現(xiàn)代碼如下：public void selectSortToShow(String[] src, int index) throws SortPlayingException { units = (src)。 //代碼跟隨 ().setSelectIndexs(new int[]{1})。 if (j != index) { String temp = src[index]。 src[j] = temp。 changeUnit(units, index, j)。AccessoryPanel（右邊JPanel）中加入JList，(int[] i)完成代碼跟隨。該方法切入到排序代碼完成排序算法每一步實(shí)現(xiàn)效果。 //用字表的第一個(gè)記錄軸的記錄 l[0] = l[low]。 (units,(low),(0))。 //代碼跟隨 ().setSelectIndexs(new int[]{2})。 }將字符串?dāng)?shù)組封裝為VectorUnit，同時(shí)利用GUI在ContentPanel（中間JPanel）中繪制數(shù)據(jù)；將movingUnit()完成數(shù)組的移動(dòng)與交換。().setSelectIndexs(new int[]{})。實(shí)現(xiàn)代碼如下：private void mergeToShow(String[] sr,int s,int m,int t) { String[] tmp = new String[t s +1]。 int curx = (s).getPoint().x。 //代碼跟隨 ().setSelectIndexs(new int[]{2})。i=m amp。 j = t。 //代碼跟隨 ().setSelectIndexs(new int[]{20})。 }將字符串?dāng)?shù)組封裝為LinkData，同時(shí)利用GUI在ContentPanel（中間JPanel）中繪制數(shù)據(jù)。AccessoryPanel（右邊JPanel）中加入JList，(int[]i)完成代碼跟隨。該方法切入到排序代碼完成排序算法每一步實(shí)現(xiàn)效果。 flashNext(linkData, q)。 ()[q].setValue(i + )。 flashNext(linkData, i)。 ()[i].setValue(p + )。()切入到排序代碼中，完成數(shù)組拷貝與賦值。().setSelectIndexs(new int[]{})。實(shí)現(xiàn)代碼如下： public void adjustHeapToShow(String[] num, int s, int t) {