把一堆或者记录根据某一个键值由小到大或由大而小汇总课件.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《把一堆或者记录根据某一个键值由小到大或由大而小汇总课件.ppt》由用户(晟晟文业)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 一堆 或者 记录 根据 某一个 键值 小到大 汇总 课件
- 资源描述:
-
1、排 序 6NCKUEE S.C.Tai NCKUEE Data Compression&Multimedia Communication Lab.1/2/20231排序 把一堆資料或者記錄根據某一個鍵值由小到大或由大而小來排列 內部排序 n在主記憶體中將資料依照某一個順序排列 外部排序 n要排序的資料是在檔案中 NCKUEE Data Compression&Multimedia Communication Lab.1/2/20232為什麼要排序?循序搜尋法 n一串未經排列的數列:5,96,21,67,55,87,12,30 n如果我們想找到21的話,我們就得比對3次n如果要找到12的話,就得
2、比對7次n如果是要確定25並不存在於此數列中則要比對9次n將整個數列比對完後的下一次才會發現已經沒有資料可以比對了欲搜尋數字的大小與比對的次數無關 NCKUEE S.C.Tai 1/2/20233為什麼要排序?如果我將整個數列先經過排序數列變成:5,12,21,30,55,67,87,96可以使用二元搜尋搜尋時間由O(n)降低為O(nlogn)NCKUEE S.C.Tai 1/2/20234穩定排序與不穩定排序 假設我們的原始資料中有兩筆或兩筆以上的資料具有相同的鍵值 當我們做完排序後,這兩筆資料仍然保持它們原先的順序而沒有互換時,就稱為穩定(stable)排序反之,則稱為不穩定(unstab
3、le)排序 NCKUEE Data Compression&Multimedia Communication Lab.1/2/20235穩定排序與不穩定排序原 始 資 料 4 5 7 5+排 序 後 4 5 5+7 穩 定 排 序 後 4 5+5 7 不 穩 定 5+表 示 資 料 為5,但 是 位 置 是 排 在 後 面 的5 NCKUEE Data Compression&Multimedia Communication Lab.1/2/20236泡沫法排序法(Bubble Sort)for(i從0到n-2)將第0個元素到第n-i-1個元素兩兩比較 if(前一個元素下一個元素)互相交換位置
4、;/*每執行一輪,最大值會出現在n-i-1中;*/NCKUEE Data Compression&Multimedia Communication Lab.1/2/20237泡沫法排序法原 始 資 料 5 7 4 5+3 第 一 次 掃 描 5 7 4 5+3 5 4 7 5+3 5 4 5+7 3 5 4 5+3 7 第 二 次 掃 描 4 5 5+3 7 4 5 5+3 7 4 5 3 5+7 第 三 次 掃 描 4 5 3 5+7 4 3 5 5+7 第 四 次 掃 描 3 4 5 5+7 結 果 3 4 5 5+7 四次比較 三次比較 二次比較 一次比較 NCKUEE Data Com
5、pression&Multimedia Communication Lab.1/2/20238泡沫法排序法穩 定 度 最 佳 狀 況 平 均 狀 況 最 差 狀 況 額 外 空 間 使 用 時 機 穩 定 O(n)O(n2)O(n2)O(1)n2 0 NCKUEE S.C.Tai 1/2/20239插入排序法(Insertion Sort)for(i從1到n-1)每次將datai中的元素當成欲加入的元素;從已排序完的陣列的最後 往前尋找可以加入的地方;將所有元素往後位移一格;/*每次排序好的陣列為data0到datai;*/NCKUEE S.C.Tai 1/2/202310插入排序法原 始 資
6、 料 5 7 4 5+3 第 一 次 排 列 5 7 4 5+3 第 二 次 排 列 5 7 4 5+3 第 三 次 排 列 5 4 7 5+3 4 5 7 5+3 第 四 次 排 列 4 5 5+7 3 第 五 次 排 列 4 5 5+3 7 4 5 3 5+7 4 3 5 5+7 3 4 5 5+7 NCKUEE Data Compression&Multimedia Communication Lab.1/2/202311插入排序法穩 定 度 最 佳 狀 況 平 均 狀 況 最 差 狀 況 額 外 空 間 使 用 時 機 穩 定 O(n)O(n2)O(n2)O(1)n20 NCKUEE
7、S.C.Tai 1/2/202312選擇排序法(Selection Sort)/*在data0datai中的數中,將最大的數放到datai中*/for(i從n-1到1)最大值=data0;for(j從1到i)if(dataj最大值)最大值=dataj;將dataj與datai的資料互換;NCKUEE Data Compression&Multimedia Communication Lab.1/2/202313選擇排序法原 始 資 料 5 7 4 5+3 第 一 次 排 列 3 7 4 5+5 第 二 次 排 列 3 4 7 5+5 第 三 次 排 列 3 4 5+7 5 第 四 次 排 列
8、3 4 5+5 7 NCKUEE S.C.Tai 1/2/202314選擇排序法穩 定 度 最 佳 狀 況 平 均 狀 況 最 差 狀 況 額 外 空 間 使 用 時 機 不 穩 定 O(n2)O(n2)O(n2)O(1)n20 NCKUEE S.C.Tai 1/2/202315快速排序法(Quick Sort)如果n=1,則return;令分隔點K為第一筆資料的值;由左向右找出一筆資料Qi,使得Qi K;由右向左找出一筆資料Qj,使得Qj K;若ij則將Qi與Qj交換,並跳到步驟(2);若ij則將K與Qj交換,並以j為基點將資料分割成左右兩半,然後分別針對左右兩半進行前面五個步驟 NCKUE
9、E Data Compression&Multimedia Communication Lab.1/2/202316快速排序法Q1 Q2 Q3 Q4 Q5 Q6 Q7 Q8 Q9 Q1 0 23 7 38 2 69 15 55 20 42 20+K i j 23 7 20+2 69 15 55 20 42 38 i j 23 7 20+2 20 15 55 69 42 38 j i 15 7 20+2 20 23 55 69 42 38 NCKUEE Data Compression&Multimedia Communication Lab.1/2/202317快速排序法Q1 Q2 Q3 Q4
10、 Q5 Q6 Q7 Q8 Q9 Q10 15 7 20+2 20 23 55 69 42 38 Kl i j Kr i j 15 7 2 20+20 23 55 38 42 69 j i j i 2 7 15 20+20 23 42 38 55 69 K,j i K,j i K i,j K,i,j 2 7 15 20+20 23 38 42 55 69 K,j i 2 7 15 20+20 23 38 42 55 69 完成 NCKUEE Data Compression&Multimedia Communication Lab.1/2/202318例子6 2 8 5 11 10 4 1 9
11、7 3使用 6 當分隔點28511104 1973 6針對左右兩半進行排序NCKUEE Data Compression&Multimedia Communication Lab.1/2/202319分隔點之選擇*最左元素隨機選擇前三個元素之中間值NCKUEE Data Compression&Multimedia Communication Lab.1/2/202320例子6 2 8 5 11 10 4 1 9 7 3ab28511104 1973 6左右兩份資料再遞迴地排序NCKUEE Data Compression&Multimedia Communication Lab.1/2/20
12、2321例子 另一種分割法6 2 8 5 11 10 4 1 9 7 3a6836 2 3 5 11 10 4 1 9 7 8a61116 2 3 5 1 10 4 11 9 7 8a610 46 2 3 5 1 4 10 11 9 7 8a6104大的值沒在小值的左邊,停止處理。將分隔值與大值交換。4 2 3 5 1 411 9 7 8a6 106NCKUEE S.C.Tai 1/2/202322分割法-separate x=inputfirst;current_separate=first;for(unknown=first+1;unknown=last;unknown+)if(input
13、unknown x)(current_separate)+;temp=inputcurrent_separate;/*交換current_separate及unknown的位置*/inputcurrent_separate=inputunknown;inputunknown=temp;temp=inputfirst;/*交換first及current_separate的位置*/inputfirst=inputcurrent_separate;inputcurrent_separate=temp;*separate_point=current_separate;NCKUEE S.C.Tai 1/
14、2/202323快速排序法-qsort(int input,int first,int last)if(first last)separate(input,first,last,&separate_point);if(separate_point-first last-separate_point)qsort(input,first,separate_point-1);qsort(input,separate_point+1,last);else qsort(input,separate_point+1,last);qsort(input,first,separate_point-1);NCK
15、UEE Data Compression&Multimedia Communication Lab.1/2/202324快速排序法穩 定 度 最 佳 狀 況 平 均 狀 況 最 差 狀 況 額 外 空 間 使 用 時 機 不 穩 定 O(n)O(nlogn)O(n2)O(n)20n NCKUEE S.C.Tai 1/2/202325合併排序法 將已經排序好的兩個數列合併為一個大的排序好的數列 1.將N個長度為1的數列,合併成N/2個長度為2的數列;2.將N/2個長度為2的數列,合併成N/4個長度為4的數列;3.繼續合併數列,直到形成一個長度為N的數列 NCKUEE Data Compressi
16、on&Multimedia Communication Lab.1/2/202326合併兩個已經排序好的數列 A=(2,5,6)B=(1,3,8,9,10)C=()比較 A 與 B 的最小元素並且將比較小的放入C.A=(2,5,6)B=(3,8,9,10)C=(1)NCKUEE Data Compression&Multimedia Communication Lab.1/2/202327合併兩個已經排序好的數列 A=(5,6)B=(3,8,9,10)C=(1,2)A=(5,6)B=(8,9,10)C=(1,2,3)A=(6)B=(8,9,10)C=(1,2,3,5)NCKUEE Data C
展开阅读全文