书签 分享 收藏 举报 版权申诉 / 59
上传文档赚钱

类型把一堆或者记录根据某一个键值由小到大或由大而小汇总课件.ppt

  • 上传人(卖家):晟晟文业
  • 文档编号:5214411
  • 上传时间:2023-02-17
  • 格式:PPT
  • 页数:59
  • 大小:880.08KB
  • 【下载声明】
    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

    17、ompression&Multimedia Communication Lab.1/2/202328合併兩個已經排序好的數列 A=()B=(8,9,10)C=(1,2,3,5,6)當 A 與 B 有一個已經空了,將沒空的一個直接接到C 的後面。NCKUEE Data Compression&Multimedia Communication Lab.1/2/202329合併排序法 8,3,13,6,2,14,5,9,10,1,7,12,48,3,13,6,2,14,59,10,1,7,12,48,3,13,6 2,14,58,3 13,68 313 62,14 52 149,10,17,12,4

    18、9,10 19 107,124712NCKUEE Data Compression&Multimedia Communication Lab.1/2/202330合併排序法 3,8 6,133,6,8,138 313 62,142,5,142,3,5,6,8,13,1452 149,101,9,1019 107,124,7,121,4,7,9,10,121,2,3,4,5,6,7,8,9,10,12,13,144712NCKUEE Data Compression&Multimedia Communication Lab.1/2/202331合併排序法 23 5 25 4 3 5+29 1 3

    19、0 17 5 23 4 25 3 5+1 29 17 30 4 5 23 25 1 3 5+29 17 30 1 3 4 5 5+23 25 29 17 30 1 3 4 5 5+17 23 25 29 30 NCKUEE Data Compression&Multimedia Communication Lab.1/2/202332合併排序法void merge(int data,int workspace,int front,int mid,int rear)int input=front;int input1=mid+1;int output=front;while(input=mid&

    20、input1=rear)/*將兩序列中較小的放入暫存中*/if(datainput=datainput1)workspaceoutput+=datainput+;else workspaceoutput+=datainput1+;while(input=mid)/*將未比對完的放入暫存中*/workspaceoutput+=datainput+;while(input1=rear)workspaceoutput+=datainput1+;NCKUEE Data Compression&Multimedia Communication Lab.1/2/202333合併排序法 void merge

    21、sort(int data,int workspace,int front,int rear)int mid,i;if(front rear)mid=(front+rear)/2;/*將資料分為兩段*/mergesort(data,workspace,front,mid);/*排序左半段 */mergesort(data,workspace,mid+1,rear);/*排序右半段 */merge(data,workspace,front,mid,rear);/*將資料合在一起*/for(i=front;i=rear;i+)datai=workspacei;/*把暫存資料搬回原來的的陣列*/NC

    22、KUEE S.C.Tai 1/2/202334合併排序法 穩 定 度 最 佳 狀 況 平 均 狀 況 最 差 狀 況 額 外 空 間 使 用 時 機 穩 定 O(nlogn)O(nlogn)O(nlogn)O(n)20n NCKUEE S.C.Tai 1/2/202335堆積排序法(Heap Sort)假設現在我有10筆資料10,66,30,52,61,21,3,27,55,10+組成最小堆積樹 1.先將其放入二元樹中 2.然後調整成為最小堆積樹3.重複地”從樹的頂端彈出最小的元素,以及重新調整剩下的二元樹使其再度成為最小堆積樹”這兩個步驟,NCKUEE Data Compression&Mu

    23、ltimedia Communication Lab.1/2/202336堆積排序法先將其放入二元樹中 1052306632161552710+NCKUEE S.C.Tai 1/2/202337堆積排序法然後調整成為如下的最小堆積樹 調整堆積樹的方法請閱讀第五章 3271010+302161555266NCKUEE S.C.Tai 1/2/202338堆積排序法從樹的頂端彈出最小的元素,以及重新調整剩下的二元樹使其再度成為最小堆積樹 10+5210273021615566彈出3之後之最小堆積樹。已排序好之數列=3.1052212730556166彈出10+之後之最小堆積樹。已排序好之數列=3,

    24、10+.NCKUEE Data Compression&Multimedia Communication Lab.1/2/202339堆積排序法21523027665561彈出10之後之最小堆積樹。已排序好之數列=3,10+,10.NCKUEE S.C.Tai 1/2/202340堆積排序法void adjust(int x,int root,int item,int boundary)/*修正heap*/int father,son;int done;father=root;/*父節點的位置*/son=2*father;/*子節點的位置*/done=FALSE;while(son=bound

    25、ary&!done)/*是否有子節點*/if(sonxson)/*大的節點用來調整*/son+;if(item=1;i-)/*將資料從中間開始加入,並調整heap*/adjust(x,i,xi,n);for(index=n;index=2;index-)/*一個一個移除heap中的元素,*/temp=x1;/*將最大的元素放到陣列最後 */adjust(x,1,xindex,index-1);xindex=temp;NCKUEE Data Compression&Multimedia Communication Lab.1/2/202342堆積排序法穩 定 度 最 佳 狀 況 平 均 狀 況

    26、最 差 狀 況 額 外 空 間 使 用 時 機 不 穩 定 O(nlogn)O(nlogn)O(nlogn)O(n)20n NCKUEE S.C.Tai 1/2/202343基數排序法(Radix Sort)多鍵值排序法Key花色:Key點數:A K Q J 10 9 8 7 6 5 4 3 2 2,A,2,A NCKUEE S.C.Tai NCKUEE Data Compression&Multimedia Communication Lab.1/2/202344基數排序法 MSD優先優先 1.分配將含有相同鍵值的資料置於同一箱中;2.排序將各個箱子中的資料分別排序;3.合併將各箱中的資料用

    27、插入排序法合成一串 NCKUEE Data Compression&Multimedia Communication Lab.1/2/202345基數排序法-MSD優先優先 80,44,324,44+,3,94,221,8,25,210做排序 步驟步驟1:最高位數為百位數,用百位數當鍵值,將數字分別放在不同的箱子中 0 80 44 44+3 94 8 25 1 2 221 210 3 324 4 5 6 7 8 9 NCKUEE S.C.Tai 1/2/202346基數排序法-MSD優先優先 步驟步驟2:分別將各箱子裡的數值做排序 0 3 8 25 44 44+80 94 2 210 221

    28、3 324 NCKUEE S.C.Tai 1/2/202347基數排序法-MSD優先優先 步驟步驟3:合併各箱子裡的資料成一份 3,8,25,44,44+,80,94,210,221,324 NCKUEE S.C.Tai 1/2/202348基數排序法-LSD優先優先 分配從最右邊的位數開始比較,將含有相同鍵值的資料置於同一箱中 重複以上動作,直到到達最大的數的最高位數為止,若最大的數是P位數,則需比較P次 合併將各箱中的資料用插入排序合成一串 NCKUEE S.C.Tai 1/2/202349基數排序法-LSD優先優先 80,44,324,44+,3,94,221,8,25,210 步驟步驟

    29、1:步驟1-1:以個位數做比較分配 0 80 210 1 221 2 3 3 4 44 324 44+94 5 25 6 7 8 8 9 NCKUEE S.C.Tai 1/2/202350基數排序法-LSD優先優先 步驟1-2:以十位數做比較分配 0 3 8 1 210 2 221 324 25 3 4 44 44+5 6 7 8 80 9 94 NCKUEE S.C.Tai 1/2/202351基數排序法-LSD優先優先步驟1-3:以百位數做比較分配 0 3 8 25 44 44+80 94 1 2 210 221 3 324 4 5 6 7 8 9 NCKUEE S.C.Tai 1/2/2

    30、02352基數排序法-LSD優先優先合併各箱子裡的資料成一份 3,8,25,44,44+,80,94,210,221,324 NCKUEE Data Compression&Multimedia Communication Lab.1/2/202353基數排序法-LSD優先優先/*最無效優先法的基數排序*/void radixsort(int data,int n)index i;建立暫存鍵結串列的結構;/*資料中,最大的數為幾位數就要做幾次排序*/for(i從1到最高位數為止)每次依照第i位分類,若資料的第i位為k就放入第k個暫存鍵結串列中;依鍵值將各個暫存鍵結串列中的資料由小到大放入陣列中

    31、;NCKUEE Data Compression&Multimedia Communication Lab.1/2/202354基數排序法穩 定 度 最 佳 狀 況 平 均 狀 況 最 差 狀 況 額 外 空 間 使 用 時 機 穩 定 O(nlogn)O(nlogn)O(n2)O(n)20n NCKUEE Data Compression&Multimedia Communication Lab.1/2/202355外部排序法 當資料量太大時,我們無法將其一次全部放在主記憶體中做處理 因此需要對外部儲存裝置中的資料做排序 外部排序最常用的方法是合併排序法 先將檔案分段 每一段檔案用內部排序法

    32、加以排序之後再將它們寫出到外部儲存裝置 NCKUEE S.C.Tai 1/2/202356外部排序法 排序過後的各段資料稱為行程(runs)將各行程利用合併排序法逐漸合併 直到最後只剩下一個行程為止 如果我們使用二路合併,以m個行程來說,需要log2m處理次,如果採用k路合併,則需要logkm次當然,k越大,需要的處理次數就越少NCKUEE S.C.Tai 1/2/202357外部排序法 但是由於每處理一個行程就得寫入記憶體及寫出到外部儲存裝置一次所以當k的數目太大時,反而會讓系統的整體表現變差 NCKUEE Data Compression&Multimedia Communication Lab.1/2/202358外部排序法 R1R2R3R4R5R1_R2R3_R4R1_R2_R3_R4R1_R2_R3_R4_R5二 路合併NCKUEE S.C.Tai NCKUEE Data Compression&Multimedia Communication Lab.1/2/202359

    展开阅读全文
    提示  163文库所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
    关于本文
    本文标题:把一堆或者记录根据某一个键值由小到大或由大而小汇总课件.ppt
    链接地址:https://www.163wenku.com/p-5214411.html

    Copyright@ 2017-2037 Www.163WenKu.Com  网站版权所有  |  资源地图   
    IPC备案号:蜀ICP备2021032737号  | 川公网安备 51099002000191号


    侵权投诉QQ:3464097650  资料上传QQ:3464097650
       


    【声明】本站为“文档C2C交易模式”,即用户上传的文档直接卖给(下载)用户,本站只是网络空间服务平台,本站所有原创文档下载所得归上传人所有,如您发现上传作品侵犯了您的版权,请立刻联系我们并提供证据,我们将在3个工作日内予以改正。

    163文库