《數(shù)據(jù)結構PPT演示課件》由會員分享，可在線閱讀，更多相關《數(shù)據(jù)結構PPT演示課件（63頁珍藏版）》請在裝配圖網(wǎng)上搜索。
第7章 排序,排序（sorting）是計算機程序設計的一個特別重要的技術，計算機的各個應用領域都有它的身影。如在處理學生考試成績和元素的查找等都涉及到了對數(shù)據(jù)的排序。排列有序的折半查找要比順序查找的效率要高許多。本章主要給大家介紹幾種常用的排序技術：插入排序、選擇排序、交換排序、歸并排序和基數(shù)排序。
本章重點和難點：
1、希爾排序
2、快速排序
3、堆排序
4、歸并排序
5、基數(shù)排序,7.1 基本概念,排序：把一個無序的元素序列按照元素的關鍵字遞增或遞減排列為有序的序列。
假設包含n個元素（記錄）的序列
(E1,E2,…,En)
其對應的關鍵字為
(k1,k2,…,kn)
需確定1,2,…,n的一種排列p1,p2,…,pn，使關鍵字滿足以下非遞減（或非遞增）關系：
kp1≤kp2≤…≤kpn
從而使元素構成一個非遞減（或非遞增）的序列：
(Ep1,Ep2,…,Epn)
這樣的一種操作被稱為排序。,,7.1 基本概念,穩(wěn)定排序和不穩(wěn)定排序：在待排序的記錄序列中，若存在兩個或兩個以上關鍵字想到呢個的記錄。假設ki=kj(1≤i≤n,1≤j≤n,i≠j)，且排序前的對應的記錄Ei領先于Ej（即i
6，所以需要先將22向后移動一個位置，然后將6插入到第一個位置，如圖7.2所示。其中，陰影部分表示無序集，白色部分表示有序集。
第2趟排序：將無序集的元素17從右到左依次與有序集中的元素比較，即先與22比較，因為176，所以將17放在第2個元素的位置，如圖7.3所示。,,,,7.2 插入排序,第3趟排序：將待排序集合中的元素8與已經(jīng)有序的元素集合從右到左依次比較，先與22比較。因為86，所以將8放在第2個位置，如圖7.4所示。,,7.2 插入排序,假設待排序元素有8個，分別是17、46、32、87、58、9、50、38。使用直接插入排序?qū)υ撛匦蛄械呐判蜻^程如圖7.5所示。,,7.2 插入排序,直接插入排序算法描述如下。
void InsertSort(SqList *L)
/*直接插入排序*/
{
int i,j;
DataType t;
for(i=1;ilength;i++) /*前i個元素已經(jīng)有序，從第i+1個元素開始與前i個有序的關鍵字比較*/
{
t=L->data[i+1]; /*取出第i+1個元素，即待排序的元素*/
j=i;
while(j>0 /*將當前元素插入合適的位置*/
}
},,7.2 插入排序,7.2.2 折半插入排序
折半插入排序算法是直接插入排序的改進。它的主要改進在于，在已經(jīng)有序的集合中使用折半查找法確定待排序元素的插入位置。在找到要插入的位置后，將待排序元素插入到相應的位置。
假設待排序元素有7個：67、53、73、21、34、98、12。使用折半插入排序?qū)υ撛匦蛄械谝惶伺判蜻^程如圖7.6所示。,,,7.2 插入排序,第2趟折半插入排序過程如圖7.7所示。,,,7.2 插入排序,void BinInsertSort(SqList *L)
/*折半插入排序*/
{
int i,j,mid,low,high;
DataType t;
for(i=1;ilength;i++)
{
t=L->data[i+1]; /*取出第i+1個元素，即待排序的元素*/
low=1,high=i;
while(lowdata[mid].key>t.key)
high=mid-1;
else
low=mid+1;
}
for(j=i;j>=low;j--) /*移動元素，空出要插入的位置*/
L->data[j+1]=L->data[j];
L->data[low]=t; /*將當前元素插入合適的位置*/
}
},,,7.2 插入排序,7.2.3 希爾排序
希爾排序（shell’s sort）也稱為縮小增量排序（diminishing increment sort），它也屬于插入排序類的算法，但時間效率比前幾種排序有較大改進。
設待排序元素為：48、26、66、57、32、85、55、19，使用希爾排序算法對該元素序列的排序過程如圖7.8所示。,,,,,7.2 插入排序,相應地，希爾排序的算法可描述如下。
void ShellInsert(SqList *L,int c)
/*對順序表L進行一次希爾排序，c是增量*/
{
int i,j;
DataType t;
for(i=c+1;ilength;i++) /*將距離為c的元素作為一個子序列進行排序*/
{
if(L->data[i].keydata[i-c].key) /*如果后者小于前者，則需要移動元素*/
{
t=L->data[i];
for(j=i-c;j>0/*依次將元素插入到正確的位置*/
}
}
},,,7.2 插入排序,void ShellInsertSort(SqList *L,int delta[],int m)
/*希爾排序，每次調(diào)用算法ShellInsert,delta是存放增量的數(shù)組*/
{
int i;
for(i=0;inext=NULL。指針p指向待排序的鏈表，若有序序列為空，將p指向的第一個結點插入到空鏈表L中。然后將有序鏈表即L指向的鏈表的每一個結點與p指向的結點比較，并將結點*p插入到L指向的鏈表的恰當位置。重復執(zhí)行上述操作，直到待排序鏈表為空。此時，L就是一個有序鏈表。,7.3 交換排序,7.3.1 冒泡排序
冒泡排序(bubble sort)是一種簡單的交換類排序算法，它是通過交換相鄰的兩個數(shù)據(jù)元素，逐步將待排序序列變成有序序列。它的基本算法思想描述如下：
假設待排序元素有n個，從第1個元素開始，依次交換相鄰的兩個逆序元素，直到最后一個元素為止。當?shù)?趟排序結束，就會將最大的元素移動到序列的末尾。然后按照以上方法進行第2趟排序，次大的元素將會被移動到序列的倒數(shù)第2個位置。依次類推，經(jīng)過n-1趟排序后，整個元素序列就成了一個有序的序列。每趟排序過程中，值小的元素向前移動，值大的元素向后移動，就像氣泡一樣向上升，因此將這種排序方法稱為冒泡排序。,,7.3 交換排序,例如，有5個待排序元素55、26、48、63和37。
第1趟排序：,,7.3 交換排序,第2趟排序：從第1個元素開始，依次比較第1個元素與第2個元素、第2個元素與第3個元素、第3個元素與第4個元素，如果前者大于后者，則交換之；否則不進行交換。第2趟排序過程如圖7.12所示。,,7.3 交換排序,第3趟排序：按照以上方法，依次比較兩個相鄰元素，交換逆序的元素。第3趟排序過程如圖7.13所示。
第4趟排序：此時，待排序元素只剩下26和37，只需要進行一次比較即可。因為26<37，所以不需要交換。第4趟排序過程如圖7.14所示。,,,,,7.3 交換排序,設待排序元素為56、72、44、31、99、21、69、80，使用冒泡排序?qū)υ撛匦蛄械呐判蜻^程如圖7.15所示。,,7.3 交換排序,冒泡排序的算法描述如下。
void BubbleSort(SqList *L,int n)
/*冒泡排序*/
{
int i,j,flag;
DataType t;
for(i=1;idata[j].key>L->data[j+1].key)
{
t=L->data[j];
L->data[j]=L->data[j+1];
L->data[j+1]=t;
flag=1;
}
}
},7.3 交換排序,快速排序的算法思想是：從待排序記錄序列中選取一個記錄（通常是第一個記錄）作為樞軸，其關鍵字設為key，然后將其余關鍵字小于key的記錄移至前面，而將關鍵字大于key的記錄移至后面，結果將待排序記錄序列分為兩個子表，最后將關鍵字key的記錄插入到其分界線的位置。我們將這個過程稱為一趟快速排序。通過這一趟劃分后，就以關鍵字為key的記錄為界，將待排序序列分為兩個子表，前面的子表所有記錄的關鍵字均不大于key，而后面子表的所有記錄的關鍵字均不小于key。繼續(xù)對分割后的子表進行上述劃分，直至所有子表的表長不超過1為止，此時的待排序記錄就成了一個有序序列。,,7.3 交換排序,【算法步驟】設待排序序列存放在數(shù)組a[1…n]中，n為元素個數(shù)，設置兩個指針i和j，初值分別為1和n，令a[1]作為樞軸元素賦給pivot，a[1]相當于空單元，然后執(zhí)行以下操作：
（1）j從右往左掃描，若a[j].keypivot.key，將a[i]移至a[j]中，并執(zhí)行一次j--操作；
（3）重復執(zhí)行（1）和（2），直到出現(xiàn)i≥j，則將元素pivot移動到a[i]中。此時整個元素序列在位置i被劃分成兩個部分，前一部分的元素關鍵字都小于a[i].key，后一部分元素的關鍵字都大于等于a[i].key。即完成了一趟快速排序。,,,,,7.3 交換排序,例如，一組待排序元素序列為55,22,44,67,35,77,18,69，依據(jù)快速排序的算法思想，得到第1趟排序的過程如圖7.16所示。,,,7.3 交換排序,設待排序元素為55、22、44、67、35、77、18、69，用快速排序算法對該元素序列的排序過程如圖7.17所示。,,,,7.3 交換排序,進行一趟快速排序，即將元素序列進行一次劃分的算法描述如下所示。
int Partition(SqList *L,int low,int high)
/*對順序表L.r[low..high]的元素進行一趟排序，使樞軸前面的元素關鍵字小于
樞軸元素的關鍵字，樞軸后面的元素關鍵字大于等于樞軸元素的關鍵字，并返回樞軸位置*/
{
DataType t;
KeyType pivotkey;
pivotkey=(*L).data[low].key;/*將表的第一個元素作為樞軸元素*/
t=(*L).data[low];
while(low=pivotkey)/*從表的末端向前掃描*/
high--;
if(lowdata[i];
L->data[i]=L->data[j];
L->data[j]=t;
}
}
},7.4 選擇排序,,,7.4 選擇排序,一組元素的關鍵字序列為(76,31,19,20,6,83,60,52)，簡單選擇排序的過程如圖7.19所示。,,7.4.2 堆排序
1．什么是堆和堆排序
堆排序(heap sort) 主要是利用了二叉樹的樹形結構，按照完全二叉樹的編號次序，將元素序列的關鍵字依次存放在相應的結點。然后從葉子結點開始，從互為兄弟的兩個結點中（沒有兄弟結點除外），選擇一個較大（或較小）者與其雙親結點比較，如果該結點大于（或小于）雙親結點，則將兩者進行交換，使較大（或較?。┱叱蔀殡p親結點。將所有的結點都做類似操作，直到根結點為止。這時，根結點的元素值的關鍵字最大（或最?。?7.4 選擇排序,,這樣就構成了堆，堆中的每一個結點都大于（或小于）其孩子結點。堆的數(shù)學形式定義為：假設存在n個元素，其關鍵字序列為(k1,k2,…,ki,…,kn)，如果有：
則稱此元素序列構成了一個堆。如果將這些元素的關鍵字存放在一維數(shù)組中，將此一維數(shù)組中的元素與完全二叉樹一一對應起來，則完全二叉樹中的每個非葉子結點的值都不小于（或不大于）孩子結點的值。,7.4 選擇排序,,,,在堆中，堆的根結點元素值一定是所有結點元素值的最大值或最小值。例如，序列（89,77,65,62,32,55,60,48）和（18,37,29,48,50,43,33,69,77,60）都是堆，相應的完全二叉樹表示如圖7.20所示。,7.4 選擇排序,,,,如果將堆中的根結點（堆頂）輸出之后，然后將剩余的n-1個結點的元素值重新建立一個堆，則新堆的堆頂元素值是次大（或次?。┲担瑢⒃摱秧斣剌敵?。然后將剩余的n-2個結點的元素值重新建立一個堆，反復執(zhí)行以上操作，直到堆中沒有結點，就構成了一個有序序列，這樣的重復建堆并輸出堆頂元素的過程稱為堆排序。,7.4 選擇排序,2．建堆
堆排序的過程就是建立堆和不斷調(diào)整使剩余結點構成新堆的過程。假設將待排序的元素的關鍵字存放在數(shù)組a中，第1個元素的關鍵字a[1]表示二叉樹的根結點，剩下的元素的關鍵字a a[2…n]分別與二叉樹中的結點按照層次從左到右一一對應。例如，a[1]的左孩子結點存放在a[2]中，右孩子結點存放在a[3]中，a[i]的左孩子結點存放在a[2*i]中，右孩子結點存放在a[2*i+1]中。,7.4 選擇排序,,,例如，給定一組元素序列(27,58,42,53,42,69,50,62)，建立大頂堆的過程如圖7.21所示。,7.4 選擇排序,,,,相應地，建立大頂堆的算法描述如下所示。
void CreateHeap(SqList *H,int n)
/*建立大頂堆*/
{
int i;
for(i=n/2;i>=1;i--) /*從序號n/2開始建立大頂堆*/
AdjustHeap(H,i,n);
},7.4 選擇排序,,void AdjustHeap(SqList *H,int s,int m)
/*調(diào)整H.data[s...m]的關鍵字，使其成為一個大頂堆*/
{
DataType t;
int j;
t=(*H).data[s]; /*將根結點暫時保存在t中*/
for(j=2*s;j(*H).data[j].key) /*如果孩子結點的值小于根結點的值，則不進行交換*/
break;
(*H).data[s]=(*H).data[j];
s=j;
}
(*H).data[s]=t; /*將根結點插入到正確位置*/
},7.4 選擇排序,,,,3．調(diào)整堆
具體實現(xiàn)：當堆頂元素輸出后，可以將堆頂元素放在堆的最后，即將第1個元素與最后一個元素交換a[1]a[n]，則需要調(diào)整的元素序列就是a[1…n-1]。從根結點開始，如果其左、右子樹結點元素值大于根結點元素值，選擇較大的一個進行交換。即如果a[2]>a[3]，則將a[1]與a[2]比較，如果a[1]>a[2]，則將a[1]與a[2]交換，否則不交換。如果a[2]a[3]，則將a[1]與a[3]交換，否則不交換。重復執(zhí)行此操作，直到葉子結點不存在，就完成了堆的調(diào)整，構成了一個新堆。,7.4 選擇排序,,7.4 選擇排序,例如，一個大頂堆的關鍵字序列為(69,62,50,58,42,42,27,53)，當輸出69后，調(diào)整剩余的元素序列為大頂堆的過程如圖7.22所示。,,,,7.4 選擇排序,調(diào)整堆的算法實現(xiàn)如下。
void HeapSort(SqList *H)
/*對順序表H進行堆排序*/
{
DataType t;
int i;
CreateHeap(H,H->length); /*創(chuàng)建堆*/
for(i=(*H).length;i>1;i--) /*將堆頂元素與最后一個元素交換，重新調(diào)整堆*/
{
t=(*H).data[1];
(*H).data[1]=(*H).data[i];
(*H).data[i]=t;
AdjustHeap(H,1,i-1); /*將(*H).data[1..i-1]調(diào)整為大頂堆*/
}
},,,7.4 選擇排序,例如，一個大頂堆的元素的關鍵字序列為(69,62,50,58,42,42,27,53)，其相應的完整的堆排序過程如圖7.23所示。,,,7.4 選擇排序,7.4.3 選擇排序應用舉例
【例7_4】編寫算法，利用簡單選擇排序和堆排序算法對一組關鍵字序列 (69,62,50,58,42,42,27,53)進行排序，要求輸出每趟排序的結果。
【分析】簡單選擇排序和堆排序都是一種不穩(wěn)定的排序方法。它們的主要思想：每次從待排序元素中選擇關鍵字最小（或最大）的元素，經(jīng)過不斷交換，重復執(zhí)行以上操作，最后形成一個有序的序列。,7.4 選擇排序,【例7_5】編寫算法，對關鍵字序列(76,20,99,32,60,53,11,8,42)進行選擇排序，要求使用鏈表實現(xiàn)。
【分析】主要考察選擇排序的算法思想和鏈表的操作。具體實現(xiàn)時，設置兩個指針p和q，分別指向已排序鏈表和未排序鏈表。初始時，先創(chuàng)建一個鏈表，q指向該鏈表，p指向的鏈表為空。然后從q指向的鏈表中找到一個元素值最小的結點，將其取出并插入到p指向的鏈表中。重復執(zhí)行以上操作直到q指向的鏈表為空，此時p指向的鏈表就是一個有序鏈表。,,,7.5 歸并排序,7.5.1 2路歸并排序算法
主要思想是：假設元素的個數(shù)是n，將每個元素作為一個有序的子序列，然后將相鄰的兩個子序列兩兩歸并，得到個長度為2的有序子序列。然后將相鄰的兩個有序子序列兩兩歸并，得到個長度為4的有序子序列。如此重復，直至得到一個長度為n的有序序列為止。
關鍵字序列(50,22,61,35,87,12,19,75)的2路歸并排序的過程如圖7.26所示。,,,7.5 歸并排序,void Merge(DataType s[],DataType t[],int low,int mid,int high)
/*將有序的s[low...mid]和s[mid+1..high]歸并為有序的t[low..high]*/
{
int i,j,k;
i=low,j=mid+1,k=low;
while(i<=mid
},,,,,7.5 歸并排序,void MergeSort(DataType s[],DataType t[],int low, int high)
/*2路歸并排序，將s[low...high]歸并排序并存儲到t[low...high]中*/
{
int mid;
DataType t2[MaxSize];
if(low==high)
t[low]=s[low];
else
{
mid=(low+high)/2; /*將s[low...high]分為s[low...mid]和s[mid+1...high]*/
MergeSort(s,t2,low,mid); /*將s[low...mid]歸并為有序的t2[low...mid]*/
MergeSort(s,t2,mid+1,high); /*將s[mid+1...high]歸并為有序的t2[mid+1...high]*/
Merge(t2,t,low,mid,high); /*將t2[low...mid]和t2[mid+1..high]歸并到t[low...high]*/
}
},,7.5 歸并排序,7.5.2 歸并排序應用舉例
【例7_6】編寫算法，請使用2路歸并排序?qū)σ唤M關鍵字 (50,22,61,35,87,12,19,75)進行排序。,7.6 基數(shù)排序,7.6.1 基數(shù)排序算法
基數(shù)排序正是借助這種思想，對不同類的元素進行分類，然后對同一類中的元素進行排序，通過這樣的一種過程，完成對元素序列的排序。在基數(shù)排序中，通常將對不同元素的分類稱為分配，排序的過程稱為收集。
具體算法思想：假設第i個元素ai的關鍵字keyi，keyi是由d位十進制組成，即keyi=kidkid-1…ki1，其中ki1為最低位，kid為最高位。關鍵字的每一位數(shù)字都可作為一個子關鍵字。首先將元素序列按照最低的關鍵字進行排序，然后從低位到高位直到最高位依次進行排序，這樣就完成了排序過程。,,7.6 基數(shù)排序,例如，一組元素的關鍵字序列為(236,128,34,567,321,793,317,106)。
對最低位進行分配和收集的過程如圖7.28所示。其中，數(shù)組f[i]保存第i個鏈表的頭指針，數(shù)組r[i]保存第i個鏈表的尾指針。,,,,,7.6 基數(shù)排序,對十位數(shù)字分配和收集的過程如圖7.29所示。
對百位數(shù)字分配和收集的過程如圖7.30所示。,,,,,,,,7.6 基數(shù)排序,基數(shù)排序的算法主要包括分配和收集。靜態(tài)鏈表類型定義描述如下：
#define MaxNumKey 6 /*關鍵字項數(shù)的最大值*/
#define Radix 10 /*關鍵字基數(shù)，此時是十進制整數(shù)的基數(shù)*/
#define MaxSize 1000
typedef int KeyType;
typedef struct
{
KeyType key[MaxNumKey]; /*關鍵字*/
int next;
}SListCell; /*靜態(tài)鏈表的結點類型*/
typedef struct
{
SListCell data[MaxSize]; /*存儲元素，data[0]為頭結點*/
int keynum; /*每個元素的當前關鍵字個數(shù)*/
int length; /*靜態(tài)鏈表的當前長度*/
}SList; /*靜態(tài)鏈表類型*/
typedef int addr[Radix]; /*指針數(shù)組類型*/,,,,7.6 基數(shù)排序,基數(shù)排序的分配算法實現(xiàn)如下所示。
void Distribute(SListCell data[],int i,addr f,addr r)
/*為data中的第i個關鍵字key[i]建立Radix個子表，使同一子表中元素的key[i]相同*/
/*f[0..Radix-1]和r[0..Radix-1]分別指向各個子表中第一個和最后一個元素*/
{
int j,p;
for(j=0;j
下載提示(請認真閱讀)
- 1.請仔細閱讀文檔，確保文檔完整性，對于不預覽、不比對內(nèi)容而直接下載帶來的問題本站不予受理。
- 2.下載的文檔，不會出現(xiàn)我們的網(wǎng)址水印。
- 3、該文檔所得收入（下載+內(nèi)容+預覽）歸上傳者、原創(chuàng)作者；如果您是本文檔原作者，請點此認領！既往收益都歸您。
文檔包含非法信息？點此舉報后獲取現(xiàn)金獎勵！
下載文檔到電腦，查找使用更方便
5
積分
- 配套講稿：
如PPT文件的首頁顯示word圖標，表示該PPT已包含配套word講稿。雙擊word圖標可打開word文檔。
- 特殊限制：
部分文檔作品中含有的國旗、國徽等圖片，僅作為作品整體效果示例展示，禁止商用。設計者僅對作品中獨創(chuàng)性部分享有著作權。
- 關 鍵 詞：
-
數(shù)據(jù)結構
PPT
演示
課件
- 溫馨提示:
1: 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2: 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
3.本站RAR壓縮包中若帶圖紙，網(wǎng)頁內(nèi)容里面會有圖紙預覽，若沒有圖紙預覽就沒有圖紙。
4. 未經(jīng)權益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 裝配圖網(wǎng)僅提供信息存儲空間，僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理，對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對任何下載內(nèi)容負責。
6. 下載文件中如有侵權或不適當內(nèi)容，請與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
裝配圖網(wǎng)所有資源均是用戶自行上傳分享，僅供網(wǎng)友學習交流，未經(jīng)上傳用戶書面授權，請勿作他用。
數(shù)據(jù)結構PPT演示課件
鏈接地址：http://italysoccerbets.com/p-249659.html