《數(shù)據(jù)結(jié)構(gòu)(Java版)排序ppt課件.ppt》由會員分享，可在線閱讀，更多相關(guān)《數(shù)據(jù)結(jié)構(gòu)(Java版)排序ppt課件.ppt（20頁珍藏版）》請?jiān)趨R文網(wǎng)上搜索。

1、在整堂課的教學(xué)中，劉教師總是讓學(xué)生帶著問題來學(xué)習(xí)，而問題的設(shè)置具有一定的梯度，由淺入深，所提出的問題也很明確排序排序深圳職業(yè)技術(shù)學(xué)院軟件系在整堂課的教學(xué)中，劉教師總是讓學(xué)生帶著問題來學(xué)習(xí)，而問題的設(shè)置具有一定的梯度，由淺入深，所提出的問題也很明確排序2基本概念基本概念n排序：排序：將n個(gè)數(shù)字按一定順序排列（比如：升序，或者降序）n班上有30個(gè)學(xué)生，按照學(xué)號進(jìn)行由小到大的排序在整堂課的教學(xué)中，劉教師總是讓學(xué)生帶著問題來學(xué)習(xí)，而問題的設(shè)置具有一定的梯度，由淺入深，所提出的問題也很明確排序3基本概念基本概念n內(nèi)部排序內(nèi)部排序：若整個(gè)排序過程不需要訪問外：若整個(gè)排序過程不需要訪問外存便能完成，則稱此類

2、排序問題為內(nèi)部排存便能完成，則稱此類排序問題為內(nèi)部排序序 n外部排序外部排序：若參加排序的記錄數(shù)量很大，：若參加排序的記錄數(shù)量很大，整個(gè)序列的排序過程不可能在內(nèi)存中完成，整個(gè)序列的排序過程不可能在內(nèi)存中完成，則稱此類排序問題為外部排序則稱此類排序問題為外部排序在整堂課的教學(xué)中，劉教師總是讓學(xué)生帶著問題來學(xué)習(xí)，而問題的設(shè)置具有一定的梯度，由淺入深，所提出的問題也很明確排序4幾種常用的排序方法幾種常用的排序方法n冒泡排序n選擇排序n快速排序n插入排序n希爾排序n歸并排序在整堂課的教學(xué)中，劉教師總是讓學(xué)生帶著問題來學(xué)習(xí)，而問題的設(shè)置具有一定的梯度，由淺入深，所提出的問題也很明確排序5冒泡排序冒泡排序

3、n基本思想基本思想：對所有相鄰記錄的關(guān)鍵字值進(jìn)行比較，如果是逆序（ajaj+1），則將其交換，最終達(dá)到有序化 在整堂課的教學(xué)中，劉教師總是讓學(xué)生帶著問題來學(xué)習(xí)，而問題的設(shè)置具有一定的梯度，由淺入深，所提出的問題也很明確排序6冒泡排序?qū)嵗芭菖判驅(qū)嵗跏缄P(guān)鍵字序列：51 33 62 96 87 17 28 51第一趟排序結(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

4、51 51 62 87 96 第六趟排序結(jié)果：17 28 33 51 51 62 87 96 51336296872817513351628717512896在整堂課的教學(xué)中，劉教師總是讓學(xué)生帶著問題來學(xué)習(xí)，而問題的設(shè)置具有一定的梯度，由淺入深，所提出的問題也很明確排序7 課堂練習(xí)與算法設(shè)計(jì)課堂練習(xí)與算法設(shè)計(jì)n一組關(guān)鍵字一組關(guān)鍵字（19,01,26,92,87,11,43,87,21），進(jìn)行冒），進(jìn)行冒泡排序，試列出每一趟排序后的關(guān)鍵字序泡排序，試列出每一趟排序后的關(guān)鍵字序列列n19,1,26,92,87,11,43,87,21ni=1 1 19 26 87 11 43 87 21 92 ni

5、=2 1 19 26 11 43 87 21 87 92 ni=3 1 19 11 26 43 21 87 87 92 ni=4 1 11 19 26 21 43 87 87 92 ni=5 1 11 19 21 26 43 87 87 92 ni=6 1 11 19 21 26 43 87 87 92ni=7 1 11 19 21 26 43 87 87 92ni=8 1 11 19 21 26 43 87 87 92算法設(shè)計(jì)：for(int i=1;i=a.length-1;i+)for(j=0;jaj+1)交換aj和aj+1編程實(shí)現(xiàn)在整堂課的教學(xué)中，劉教師總是讓學(xué)生帶著問題來學(xué)習(xí)，而問題

6、的設(shè)置具有一定的梯度，由淺入深，所提出的問題也很明確排序8選擇排序選擇排序n基本思想基本思想：依次從待排序記錄序列中選擇出關(guān)鍵字值最?。ɑ蜃畲螅┑挠涗?、關(guān)鍵字值次之的記錄、，并分別將它們定位到序列左側(cè)（或右側(cè)）的第1個(gè)位置、第2個(gè)位置、，從而使待排序的記錄序列成為按關(guān)鍵字值由小到大（或由大到小）排列的有序序列。n選擇排序種類選擇排序種類：直接選擇排序和堆排序在整堂課的教學(xué)中，劉教師總是讓學(xué)生帶著問題來學(xué)習(xí)，而問題的設(shè)置具有一定的梯度，由淺入深，所提出的問題也很明確排序9直接選擇排序?qū)嵗苯舆x擇排序?qū)嵗跏缄P(guān)鍵字序列：51 33 62 96 87 17 28 51 第一趟排序后：17 33 62

7、 96 87 51 28 51 第二趟排序后：17 28 62 96 87 51 33 51 第三趟排序后：17 28 33 96 87 51 62 51第四趟排序后：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在整堂課的教學(xué)中，劉教師總是讓學(xué)生帶著問題來學(xué)習(xí)，而問題的設(shè)置具有一定的梯度，由淺入深，所提出的問題也很明確排序10 課堂練習(xí)與算法設(shè)計(jì)課堂練習(xí)與算法設(shè)計(jì)選擇排序過程：34 12 45 21 87 26

8、 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 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 在整堂課的教學(xué)中，劉教師總是讓學(xué)生帶著問題來學(xué)習(xí)，而問題的設(shè)置具有一定的梯度，由淺入深，所提出的問題也很明確排序11插入排序

9、插入排序n主要思想主要思想：不斷地將待排序的數(shù)值插入到：不斷地將待排序的數(shù)值插入到有序序列中，使有序序列逐漸擴(kuò)大，直至有序序列中，使有序序列逐漸擴(kuò)大，直至所有數(shù)值都進(jìn)入有序序列中位置所有數(shù)值都進(jìn)入有序序列中位置 n插入排序種類插入排序種類：直接插入排序、折半插入直接插入排序、折半插入排序、二路插入排序、表插入排序和希爾排序、二路插入排序、表插入排序和希爾排序排序在整堂課的教學(xué)中，劉教師總是讓學(xué)生帶著問題來學(xué)習(xí)，而問題的設(shè)置具有一定的梯度，由淺入深，所提出的問題也很明確排序12直接插入排序直接插入排序n基本思想基本思想：將記錄Ri插入到有序子序列R0.i-1中，使記錄的有序序列從R0.i-1變?yōu)?/p>

10、R0.i 在整堂課的教學(xué)中，劉教師總是讓學(xué)生帶著問題來學(xué)習(xí)，而問題的設(shè)置具有一定的梯度，由淺入深，所提出的問題也很明確排序13直接插入排序?qū)嵗苯硬迦肱判驅(qū)嵗跏缄P(guān)鍵字序列：51 33 62 96 87 17 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

11、28 33 51 51 62 87 96 在整堂課的教學(xué)中，劉教師總是讓學(xué)生帶著問題來學(xué)習(xí)，而問題的設(shè)置具有一定的梯度，由淺入深，所提出的問題也很明確排序14n一組關(guān)鍵字一組關(guān)鍵字（19,1,26,92,87,11,43,87,21），進(jìn)行插），進(jìn)行插入入 排序，試列出每一趟排序后的關(guān)排序，試列出每一趟排序后的關(guān)鍵字序列鍵字序列n19,1,26,92,87,11,43,87,21ni=1 1,19,26,92,87,11,43,87,21ni=2 1,19,26,92,87,11,43,87,21ni=3 1,19,26,92,87,11,43,87,21ni=4 1,19,26,87,92,

12、11,43,87,21ni=5 1,11,19,26,87,92,43,87,21ni=6 1,11,19,26,43,87,92,87,21ni=7 1,11,19,26,43,87,87,92,21ni=81,11,19,21,26,43,87,87,92算法設(shè)計(jì)：算法設(shè)計(jì)：void insertSort(int a)n=a.length;for(i=1;in;i+)將將ai插入到插入到a0ai-1中中,保持原來的排序保持原來的排序 1 在在a0ai-1中找到插入的位置中找到插入的位置j 2 把把a(bǔ)jai-1逐個(gè)后移一個(gè)位置逐個(gè)后移一個(gè)位置 (ai-1移到移到ai,aj移到移到aj+1)3

13、 把把a(bǔ)i放到放到aj處處 課堂練習(xí)與算法設(shè)計(jì)課堂練習(xí)與算法設(shè)計(jì)在整堂課的教學(xué)中，劉教師總是讓學(xué)生帶著問題來學(xué)習(xí)，而問題的設(shè)置具有一定的梯度，由淺入深，所提出的問題也很明確排序15快速排序快速排序n基本思想基本思想：首先將待排序記錄序列中的所有記錄作為當(dāng)前待排序區(qū)域，從中任選取一個(gè)記錄（通?？蛇x第一個(gè)記錄），以它的關(guān)鍵字作為樞軸樞軸（或支點(diǎn)）（pivot），凡其關(guān)鍵字小于樞軸的記錄均移動至該記錄之前，反之，凡關(guān)鍵字大于樞軸的記錄均移動至該記錄之后 在整堂課的教學(xué)中，劉教師總是讓學(xué)生帶著問題來學(xué)習(xí)，而問題的設(shè)置具有一定的梯度，由淺入深，所提出的問題也很明確排序16快速排序一趟排序過程快速排序一趟

14、排序過程 初始關(guān)鍵字序列初始關(guān)鍵字序列：51 33 62 96 87 17 28 51R0=51 i j第一次交換之后：第一次交換之后：28 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在整堂課的教學(xué)中，劉教師總是讓學(xué)生帶著問題來學(xué)習(xí)，而問題的設(shè)置具有一定的梯

15、度，由淺入深，所提出的問題也很明確排序17快速排序結(jié)果快速排序結(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 87 96在整堂課的教學(xué)中，劉教師總是讓學(xué)生帶著問題來學(xué)習(xí)，而問題的設(shè)置具有一定的梯度，由淺入深，所提出的問題也很明確排序18課堂練習(xí)與課堂練習(xí)與算法設(shè)計(jì)算法設(shè)計(jì)給出一組關(guān)鍵字給出一組關(guān)鍵字，快速排序的每一趟的，快速排序的每一趟的排序結(jié)果：排序結(jié)果：46,58,15,45,90,18

16、,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)i

17、nt 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;在整堂課的教學(xué)中，劉教師總是讓學(xué)生帶著問題來學(xué)習(xí)，而問題的設(shè)置具有一定的梯度，由淺入深，所提出的問題也很明確排序19排序方式比較排序方式比較排序方法平均時(shí)間最壞情況輔助空間直接插入排序直接插入排序O(n2)O(n2)O(1)冒泡排序冒泡排序O(n2)O(n2)O(1)直接選擇排序直接選擇排序O(n2)O(n2)O(1)希爾排序希爾排序O(n1.3)O(n1.3)O(1)快速排序快速排序O(nlog2n)O(n2)O(log2n)堆排序堆排序O(nlog2n)O(nlog2n)O(1)2路歸并排序路歸并排序O(nlog2n)O(nlog2n)O(n)在整堂課的教學(xué)中，劉教師總是讓學(xué)生帶著問題來學(xué)習(xí)，而問題的設(shè)置具有一定的梯度，由淺入深，所提出的問題也很明確排序20綜合項(xiàng)目實(shí)踐綜合項(xiàng)目實(shí)踐164頁實(shí)戰(zhàn)演練：設(shè)計(jì)一個(gè)項(xiàng)目可以對5000個(gè)數(shù)進(jìn)行排序，計(jì)算并比較各種排序的時(shí)間。運(yùn)行界面如下.