1、排序深圳職業(yè)技術(shù)學(xué)院軟件系排序2基本概念排序： 將n個(gè)數(shù)字按一定順序排列（比如：升序，或者降序）班上有30個(gè)學(xué)生，按照學(xué)號(hào)進(jìn)行由小到大的排序排序3基本概念內(nèi)部排序 ：若整個(gè)排序過程不需要訪問外存便能完成，則稱此類排序問題為內(nèi)部排序 外部排序：若參加排序的記錄數(shù)量很大，整個(gè)序列的排序過程不可能在內(nèi)存中完成，則稱此類排序問題為外部排序排序4幾種常用的排序方法冒泡排序選擇排序快速排序插入排序希爾排序歸并排序排序5冒泡排序基本思想：對(duì)所有相鄰記錄的關(guān)鍵字值進(jìn)行比較，如果是逆序（ajaj+1），則將其交換，最終達(dá)到有序化 排序6冒泡排序?qū)嵗跏缄P(guān)鍵字序列： 51 33 62 96 87 17 28 51

2、第一趟排序結(jié)果： 33 51 62 87 17 28 51 96 第二趟排序結(jié)果： 33 51 62 17 28 51 87 96 第三趟排序結(jié)果： 33 51 17 28 51 62 87 96 第四趟排序結(jié)果： 33 17 28 51 51 62 87 96 第五趟排序結(jié)果： 17 28 33 51 51 62 87 96 第六趟排序結(jié)果： 17 28 33 51 51 62 87 96 51336296872817513351628717512896排序7 課堂練習(xí)與算法設(shè)計(jì)一組關(guān)鍵字（19,01,26,92,87,11,43,87,21），進(jìn)行冒泡排序，試列出每一趟排序后的關(guān)鍵字序列1

3、9,1,26,92,87,11,43,87,21i=1 1 19 26 87 11 43 87 21 92 i=2 1 19 26 11 43 87 21 87 92 i=3 1 19 11 26 43 21 87 87 92 i=4 1 11 19 26 21 43 87 87 92 i=5 1 11 19 21 26 43 87 87 92 i=6 1 11 19 21 26 43 87 87 92i=7 1 11 19 21 26 43 87 87 92i=8 1 11 19 21 26 43 87 87 92算法設(shè)計(jì)：for(int i=1;i=a.length-1;i+) for(j

4、=0;jaj+1) 交換aj和aj+1編程實(shí)現(xiàn)排序8選擇排序基本思想：依次從待排序記錄序列中選擇出關(guān)鍵字值最?。ɑ蜃畲螅┑挠涗?、關(guān)鍵字值次之的記錄、，并分別將它們定位到序列左側(cè)（或右側(cè)）的第1個(gè)位置、第2個(gè)位置、，從而使待排序的記錄序列成為按關(guān)鍵字值由小到大（或由大到小）排列的有序序列。 選擇排序種類：直接選擇排序和堆排序排序9直接選擇排序?qū)嵗跏缄P(guān)鍵字序列： 51 33 62 96 87 17 28 51 第一趟排序后： 17 33 62 96 87 51 28 51 第二趟排序后： 17 28 62 96 87 51 33 51 第三趟排序后： 17 28 33 96 87 51 62 5

5、1第四趟排序后： 17 28 33 51 87 96 62 51第五趟排序后： 17 28 33 51 51 96 62 87 第六趟排序后： 17 28 33 51 51 62 96 87 第七趟排序后： 17 28 33 51 51 62 87 96排序10 課堂練習(xí)與算法設(shè)計(jì)選擇排序過程： 34 12 45 21 87 26 3i=1 3 12 45 21 87 26 34i=2 3 12 45 21 87 26 34i=3 3 12 21 45 87 26 34i=4 3 12 21 26 87 45 34i=5 3 12 21 26 34 45 87i=6 3 12 21 26 34

6、 45 87算法設(shè)計(jì)：n=a.length;for(i=0,in-1;i+)從aian-1中找出最小的元素放到ai處 min=i; for( j=i-1jaj)min=j; if(min!=i) 交換amin和ai 排序11插入排序主要思想：不斷地將待排序的數(shù)值插入到有序序列中，使有序序列逐漸擴(kuò)大，直至所有數(shù)值都進(jìn)入有序序列中位置 插入排序種類：直接插入排序、折半插入排序、二路插入排序、表插入排序和希爾排序排序12直接插入排序基本思想：將記錄Ri插入到有序子序列R0.i-1中，使記錄的有序序列從R0.i-1變?yōu)镽0.i 排序13直接插入排序?qū)嵗跏缄P(guān)鍵字序列： 51 33 62 96 87 1

7、7 28 51i=1(33) 33 51 62 96 87 17 28 51i=2(62) 33 51 62 96 87 17 28 51i=3(96) 33 51 62 96 87 17 28 51i=4(87) 33 51 62 87 96 17 28 51i=5(17) 17 33 51 62 87 96 28 51i=6(28) 17 28 33 51 62 87 96 51i=7(51) 17 28 33 51 51 62 87 96 排序14一組關(guān)鍵字（19, 1,26,92,87,11,43,87,21），進(jìn)行插入 排序，試列出每一趟排序后的關(guān)鍵字序列19, 1,26,92,87

8、,11,43,87,21i=1 1,19,26,92,87,11,43,87,21i=2 1,19,26,92,87,11,43,87,21i=3 1,19,26,92,87,11,43,87,21i=4 1,19,26, 87,92,11,43,87,21i=5 1, 11,19,26, 87,92,43,87,21i=6 1, 11,19,26, 43,87,92,87,21i=7 1, 11,19,26, 43,87,87,92,21i=81, 11,19,21,26, 43,87,87,92算法設(shè)計(jì)：void insertSort(int a)n=a.length;for(i=1;in

9、;i+) 將ai插入到a0ai-1中,保持原來的排序 1 在a0ai-1中找到插入的位置j 2 把a(bǔ)jai-1逐個(gè)后移一個(gè)位置 (ai-1移到ai,aj移到aj+1) 3 把a(bǔ)i放到aj處 課堂練習(xí)與算法設(shè)計(jì)排序15快速排序基本思想：首先將待排序記錄序列中的所有記錄作為當(dāng)前待排序區(qū)域，從中任選取一個(gè)記錄（通?？蛇x第一個(gè)記錄），以它的關(guān)鍵字作為樞軸（或支點(diǎn)）（pivot），凡其關(guān)鍵字小于樞軸的記錄均移動(dòng)至該記錄之前，反之，凡關(guān)鍵字大于樞軸的記錄均移動(dòng)至該記錄之后 排序16快速排序一趟排序過程 初始關(guān)鍵字序列： 51 33 62 96 87 17 28 51R0=51 i j第一次交換之后： 28

10、 33 62 96 87 17 28 51 i j第二次交換之后： 28 33 62 96 87 17 62 51 i j第三次交換之后： 28 33 17 96 87 17 62 51 i j 第四次交換之后： 28 33 17 96 87 96 62 51 i j 完成一趟排序： 28 33 17 51 87 96 62 51排序17快速排序結(jié)果初始關(guān)鍵字序列： 51 33 62 96 87 17 28 51一趟排序之后： 28 33 17 51 87 96 62 51分別進(jìn)行快速排序：17 28 33 51 62 87 96 51 62 有序序列： 17 28 33 51 51 62 8

11、7 96排序18課堂練習(xí)與算法設(shè)計(jì)給出一組關(guān)鍵字 ，快速排序的每一趟的排序結(jié)果：46,58,15,45,90,18,10,62,87,23t=46 23,58,15,45,90,18,10,62,87,23 i jt=46 23,58,15,45,90,18,10,62,87,58 i jt=46 23,10,15,45,90,18,10,62,87,58 i jt=46 23,10,15,45,90,18,90,62,87,58 i jt=46 23,10,15,45,46,18,90,62,87,58 i j算法設(shè)計(jì)：void quickSort(int a ,int s,int t) if(st) k=partion(a,s,t); quickSort (a,s,k-1) quickSort (a,k+1,t) int partion(int a,int l,int r) temp=al;j=r;i=l; while(ij) 從j位置逐個(gè)比較temp和aj,把比temp小的元素調(diào)到ai處； 從i位置逐個(gè)比較temp和ai,把比temp大的元素調(diào)到aj處； return j; 排序19排序方式比較排序方法平均時(shí)間最壞情況輔助空間直接插入排序O(n2)O(n2)O(1)冒泡排序O(n2)O(