計算機軟件技術編程基礎 排序.ppt

(40頁)

本資源提供全文預覽，點擊全文預覽即可全文預覽,如果喜歡文檔就下載吧，查找使用更方便哦！

19.90 積分

基本排序技術排序是將一個無序序列整理成非遞減順序排列的有序序列。穩定排序：排序過程中，相同關鍵字的元素的相對次序不變。不穩定排序：排序過程中，相同關鍵字的元素的相對次序發生變化。例如：34，12，34`，08，96 08，12，34， 34`，96 穩定 08，12， 34`，34，96 不穩定一 交換排序比較兩個待排序紀錄的關鍵字，若為逆序則相互交換位置，否則，保持原來位置不變。冒泡排序、快速排序1 冒泡排序基本思想：從前往后掃描，逐個比較相鄰的兩個元素，發現倒序即交換——直到將第N-1個紀錄和第N個記錄交換為止。51731694286原序列517316942861 53 71 76 74 92 98 96 9關鍵字最大的安置到最后從后往前掃描，將第N-1個紀錄和前一個關鍵字進行比較，將小的放在前面，大的放在后面，依次類推，直到第2個記錄和第1個記錄交換為止。153167428696 82 42 71 31 52 6關鍵字最小的安置到最前面15316742869115326746893 52 54 76 7113256467894 64 52 3對剩余的線性表重復操作對線性表的每次來回操作都將最大的沉到表底，最小的像氣泡冒到表頭。1153267468911325646789112345667891531674286951731694286115326746891132564678911234566789012345678910void bub(int p[],int n){ int m,k,j,i; int d; k=0;m=n-1; //初始時子表表頭k和表尾m位置 while(k=j;i--) if(p[i-1]>p[i]) {d=p[i];p[i]=p[i-1];p[i-1]=d;k=i;} } return;}待排數組數組長度while(k掃描無交換，表尾置0 for(i=k;i掃描，子表p[m+1]沉底 if(p[i]>p[i+1]) {d=p[i];p[i]=p[i+1];p[i+1]=d;m=i;}//m為該趟冒泡后子表表尾的位置 j=k+1;k=0; //如果=j;i--) //從p[i]) {d=p[i];p[i]=p[i-1];p[i-1]=d;k=i;}//k為該趟冒泡后子表表頭的位置 }算法分析：穩定時間代價：需要進行比較的次數為２ 快速排序1) 從無序表中選取一個元素T，對線性表進行分割，大于T的元素放在前表中，小于T的元素放在后表中。此時，線性表分成前后兩個子表；2 )對分割的兩個子表再進一步分割，直到所有的子表為空為止；無序線性表≤T≥TT分割分割分割i為表頭位置； k 為表中位置； j為表尾位置比較大小，取中間值為分割元素t,該元素在表中的位置存放表頭元素，將表頭位置騰空；表尾位置前移(j--)；該元素放入表頭，表頭位置后移(i++)；P[j]>t從前往后掃描，p[i]P[i]<=t表頭位置后移(i++)；該元素放入表尾，表尾位置前移(j--) ；讀入表尾元素；在一趟快速排序中，整個過程交替地從后往前掃描關鍵字值小的記錄和從前往后掃描關鍵字值大的記錄并放置到對應端空出的位置中，又空出新的位置。當從兩個方向的掃描重合時，即i=j，就找到了基準記錄的存放位置。 按照快速排序的基本思想，在一趟快速排序之后，需要重復(1)，(2)，直到找到所有記錄的相應位置。快速排序是一個遞歸的過程。 快速排序算法是不穩定排序，對于有相同關鍵字的記錄，排序后有可能顛倒位置。51731694286012345678910i=0;j=10;k=5;1731694286217316948621316978621431t=59786i=2t=52746插入排序 插入排序的基本思想是：每次將一個待排序的記錄，按其關鍵字大小插入到前面已經排好序的子表中的適當位置，直到全部記錄插入完成為止。也就是說，將待序列表分成左右兩部分，左邊為有序表(有序序列)，右邊為無序表(無序序列)。整個排序過程就是將右邊無序表中的記錄逐個插入到左邊的有序表中，構成新的有序序列。根據不同的插入方法，插入排序算法主要包括：直接插入排序、折半插入排序、表插入排序和希爾排序等。本章重點介紹簡單插入排序、希爾排序。 簡單插入法：將一個記錄插入到已排好序的有序表中基本思想：將待排序表看成左右兩部分，左邊為有序區，右邊為無序區；整個排序過程就是將右邊無序區的元素插入到左邊有序區中。(插入時，有序子表從最后一個元素開始，逐個向前與待插入元素比較)數據表a={12，5，4，9，5}從小到大排序12549512495512551295412544512591294591251295void insort(T p[],int n){ int j,k; T t; for(j=1;j=0)&&(p[k]>t)) //如果有序子表的元素大于待排序元素 { p[k+1]=p[k];//有序子表的元素后移 k=k-1;//向前尋找有序子表的下一個比較元素 } p[k+1]=t;//待排序元素插入到有序子表 } return;}【例】假設有7個待排序的記錄，它們的關鍵字分別為23，4，15，8，19，24，15，用直接插入法進行排序。【解】簡單插入排序過程如圖所示。方括號[ ]中為已排好序的記錄的關鍵字，有兩個記錄的關鍵字都為15，為表示區別，將后一個15加下劃線。 簡單插入排序 for (j=1;jdata data >=b的父結點的值，*s插入到b的右子樹中80828575826871778875828085826871778856783445854536918478構造二叉排序樹34845685783645459178如何定義結點？struct bsnode{ int d; bsnode *lchild,*rchild;};bsnode *insert_bs_tree(bsnode *bt, int x)二叉排序樹的插入 insert_bs_tree( )傳入的形參：根結點，插入元素insert_bs_tree(bsnode *bt, int x)返回值：根結點bsnode *insert_bs_tree(bsnode *bt, int x){bsnode *p,*q;定義兩個結點構造一個新結點p=new(bsnode); p->d=x;p->lchild=NULL;p->rchild=NULL;建立一個搜索指針，從根結點開始搜索q=bt;如果二叉排序樹為空，將新結點作為根結點if(bt==NULL) bt=p;如果二叉排序樹不為空，將新結點插入到二叉樹中else {while((q->lchild!=p)&&(q->rchild!=p)) {判斷新結點是否插入到二叉樹中if(xd) { if(q->lchild!=NULL) q=q->lchild; else q->lchild=p; }如果插入值小于搜索結點q的值1搜索結點q的左子樹的結點已存在2搜索結點q的左子樹為空如果插入值大于搜索結點q的值1搜索結點q的右子樹的結點已存在2搜索結點q的右子樹為空else { if(q->rchild!=NULL) q=q->rchild; else q->rchild=p; } } } return bt;}返回根結點二叉排序樹的查找從二叉排序樹的根結點開始與被查值進行比較，若等于根結點，則查找結束根結點，到右子樹查找；void intrav(bsnode *bt){ if(bt!=NULL) { intrav(bt->lchild); cout

?天天文庫所有資源均是用戶自行上傳分享，僅供網友學習交流，未經上傳用戶書面授權，請勿作他用。

總結

以上是生活随笔為你收集整理的计算机软件编程应聘ppt,计算机软件技术编程基础 排序.ppt的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。