第一篇：C++ 八種排序算法總結及實現
八種排序算法總結之C++版本
五種簡單排序算法
一、冒泡排序
【穩(wěn)定的】
void BubbleSort(int* a,int Count)//實現從小到大的最終結果 { int temp;for(int i=1;i for(int j=Count-1;j>=i;j--) if(a[j] < a[j-1]) { temp = a[j]; a[j] = a[j-1]; a[j-1] = temp; } } 現在注意，我們給出O方法的定義： 若存在一常量K和起點n0，使當n>=n0時，有f(n)<=K*g(n),則f(n)= O(g(n))。（呵呵，不要說沒學好數學呀，對于編程數學是非常重要的?。。?/p> 現在我們來看1/2*(n-1)*n，當K=1/2，n0=1，g(n)=n*n時，1/2*(n-1)*n<=1/2*n*n=K*g(n)。所以f(n)=O(g(n))=O(n*n)。所以我們程序循環(huán)的復雜度為O(n*n)。 二、交換排序 【穩(wěn)定的】 void ExchangeSort(int *a,int Count){ int temp;for(int i=0;i for(int j=i+1;j if(a[j] < a[i]) { temp = a[j]; a[j] = a[i]; a[i] = temp; } } 時間復雜度為O(n*n)。 三、選擇法 【不穩(wěn)定的】 void SelectSort(int *a,int Count){ int temp;//一個存儲值 int pos;//一個存儲下標 for(int i=0;i temp = a[i]; pos = i; for(int j=i+1;j if(a[j] < temp)//選擇排序法就是用第一個元素與最小的元素交換 { temp = a[j]; pos = j;//下標的交換賦值，記錄當前最小元素的下標位置 } a[pos] = a[i]; a[i] = temp;} } 遺憾的是算法需要的循環(huán)次數依然是1/2*(n-1)*n。所以算法復雜度為O(n*n)。 我們來看他的交換。由于每次外層循環(huán)只產生一次交換（只有一個最小值）。所以f(n)<=n 所以我們有f(n)=O(n)。所以，在數據較亂的時候，可以減少一定的交換次數。 四、插入法 【穩(wěn)定的】 void InsertSort(int *a,int Count){ int temp;//一個存儲值 int pos;//一個存儲下標 for(int i=1;i { temp = a[i];//當前要插入的元素 pos = i-1; while(pos>=0 && temp { a[pos+1] = a[pos];//將前一個元素后移一位 pos--; } a[pos+1] = temp;} } 其復雜度仍為O(n*n)。 最終，我個人認為，在簡單排序算法中，直接插入排序是最好的。 五、希爾排序法 【不穩(wěn)定的】 /* * 希爾排序，n為數組的個數 */ void ShellSort(int arr[], int n){ int temp,pos;int d = n;//增量初值 do{ d = d/3 + 1; for(int i= d;i { temp = arr[i]; pos = i-d; while(pos>=0 && temp < arr[pos]){ arr[ pos + d ] = arr[pos]; pos-= d; } arr[ pos + d ] = temp; } } while(d > 1);} //實現增量為d的插入排序 三種高級排序算法 一、快速排序 輔助空間復雜度為O（1） 【不穩(wěn)定的】 void QuickSort(int *a,int left, int right){ int i,j,middle,temp;i = left;j = right;middle = a[(left+right)/2 ];do { while(a[i] i++; while(a[j]>middle && j>left)//從右掃描小于中值的數 j--; if(i<=j)//找到了一對值 { temp = a[i]; a[i] = a[j]; } a[j] = temp; i++; j--;} } while(i 注意，在掃描過程中，對于給定參考值，對于向右(左)掃描，如果掃描值大(小)于或等于參考值，就需要進行交換。最終得到的結果是，j左邊的值都小于參考值，而i右邊的值都大于參考值，j和i之間的值都等于參考值。對j左邊和i右邊的分別使用遞歸，就可以完成最終的排序。 這里我沒有給出行為的分析，因為這個很簡單，我們直接來分析算法：首先我們考慮最理想的情況 1.數組的大小是2的冪，這樣分下去始終可以被2整除。假設為2的k次方，即k=log2(n)。 2.每次我們選擇的值剛好是中間值，這樣，數組才可以被等分。 第一層遞歸，循環(huán)n次，第二層循環(huán)2*(n/2)......所以共有n+2(n/2)+4(n/4)+...+n*(n/n)= n+n+n+...+n=k*n=log2(n)*n 所以算法復雜度為O(log2(n)*n) 其他的情況只會比這種情況差，最差的情況是每次選擇到的middle都是最小值或最大值，那么他將變 成交換法（由于使用了遞歸，情況更糟），但是糟糕的情況只會持續(xù)一個流程，到下一個流程的時候就很可能已經避開了該中間的最大和最小值，因為數組下標變化了，于是中間值不在是那個最大或者最小值。但是你認為這種情況發(fā)生的幾率有多大？？呵呵，你完全不必擔心這個問題。實踐證明，大多數的情況，快速排序總是最好的。 如果你擔心這個問題，你可以使用堆排序，這是一種穩(wěn)定的O(log2(n)*n)算法，但是通常情況下速度要慢 于快速排序（因為要重組堆）。 二、歸并排序（兩種實現方法均要掌握） 【穩(wěn)定的】 歸并排序是一種極好的外部排序方法，即針對數據保存在磁盤上而不是高速內存中的問題。 //以下程序參考數據結構課本P286頁的模板,為使用指針鏈表實現的 #include struct node{ //鏈表的節(jié)點數據 int value;node *next;}; node * divide_from(node * head){ node * position, * midpoint, * second_half;if((midpoint=head)== NULL)//List is empty return NULL;position = midpoint->next;while(position!= NULL)//Move position twice for midpoint's one move { position = position->next; if(position!= NULL) { midpoint = midpoint->next; position = position->next; } } second_half = midpoint->next;midpoint->next = NULL;//在這里將原鏈拆斷，分為兩段 return second_half;} node * merge(node * first, node * second){ node * last_sorted;//當前已經鏈接好的有序鏈中的最后一個節(jié)點 node combined;//啞節(jié)點 last_sorted = &combined;while(first!=NULL && second!=NULL){ if(first->value < second->value){ last_sorted->next = first; last_sorted = first; first = first->next; }else { last_sorted->next = second; last_sorted = second; second = second->next; } } if(first==NULL) last_sorted->next = second;else last_sorted->next = first;return combined.next;//返回啞節(jié)點的后繼指針，即為合并后的鏈表的頭指針 } //這里的參數必須是引用調用，需要這個指引去允許函數修改調用自變量 void MergeSort(node * &head){ if(head!= NULL && head->next!= NULL)//如果只有一個元素，則不需排序 { node * second_half = divide_from(head); MergeSort(head); MergeSort(second_half); head = merge(head, second_half);} } int main(){ node a,b,c,d;node *p1, *p2, *p3, *p4,*head;p1 = &a;p2 = &b;p3 = &c;p4 = &d;a.value = 2;b.value = 4;c.value = 3;d.value = 1;a.next = p2;b.next = p3;c.next = p4;d.next = NULL;//調用歸并排序前的結果 head = p1;while(head!= NULL){ cout< head = head->next;} cout< head = p1;while(head!= NULL){ cout< head = head->next;} cout< //以下程序為使用數組實現的歸并排序,輔助空間復雜度為O（n） #include void Merge(int data[], int left, int mid, int right){ int n1,n2,k,i,j;n1 = midmid;int *L = new int[n1];//兩個指針指向兩個動態(tài)數組的首地址 int *R = new int[n2];for(i=0,k=left;i L[i] = data[k];for(i=0,k=mid+1;i R[i] = data[k];for(k=left,i=0,j=0;i if(L[i] < R[j]){ //取小者放前面 data[k] = L[i]; i++; } else { data[k] = R[j]; j++; } } if(i for(j=i;j < n1;j++,k++) } /* * left:數組的開始下標，一般為0；right：數組的結束下標，一般為（n-1）*/ void MergeSort(int data[], int left, int right){ if(left < right){ int mid = left +(right-left)/ 2;//mid=(right+left)/2，防止溢出 MergeSort(data, left, mid); MergeSort(data , mid+1, right); Merge(data , left, mid , right);} } int main(){ int data[] = {9,8,7,2,5,6,3,55,1};//排序前的輸出 for(int i=0;i<9;i++) cout< for(int i=0;i<9;i++) cout< 三、堆排序 【不穩(wěn)定的】 /* * 向堆中插入current元素的函數 */ void insert_heap(int data[], const int ¤t, int low, int high) data[k] = L[j];else //if(j for(i=j;i data[k] = R[i];delete []L;//回收內存 delete []R;{ int large;//元素data[low]左右兒子中，大者的位置 large = 2*low + 1;while(large <= high){ if(large < high && data[large] < data[ large+1]) large++; if(current > data[ large ])//待插入元素的值比它的兩個兒子都大 break; else { data[ low ] = data[ large ];//將其左右兒子的大者上移 low = large; large = 2 * large + 1; } } data[ low ] = current;} /* * 建立堆函數，num為數組data的元素個數 * 只有一個結點的<2-樹>自動滿足堆的屬性，因此不必擔心樹中的任何樹葉，即 * 不必擔心表的后一半中的元素。如果從表的中間點開始并從后向前工作，就 * 能夠使用函數insert_heap去將每個元素插入到包含了所有后面元素的部分堆 * 中，從而創(chuàng)建完整的堆。*/ void build_heap(int data[], int num){ int current;for(int low = num/2-1;low>=0;low--){ current = data[ low ]; insert_heap(data, current, low, num-1);} } /* * 堆排序主函數,num為數組data的元素個數 */ void heap_sort(int data[], int num){ int current, last_sorted;build_heap(data, num);//建立堆 for(last_sorted = num-1;last_sorted>0;last_sorted--){ //逐個元素處理 current = data[ last_sorted ];//data[0]在整個數組排序結束前，存儲的是待排序元素中最大的元素 data[last_sorted] = data[0]; insert_heap(data, current, 0, last_sorted-1);} } int main(){ //用于排序算法的輸入輸出 int a[8] = {5,7,1,2,9,4,6,3,};for(int i=0;i< sizeof(a)/sizeof(int);i++) cout< for(int i=0;i< sizeof(a)/sizeof(int);i++) cout< 排序算法總結 所謂排序，就是要整理文件中的記錄，使之按關鍵字遞增(或遞減)次序排列起來。當待排序記錄的關鍵字都不相同時，排序結果是惟一的，否則排序結果不惟一。 在待排序的文件中，若存在多個關鍵字相同的記錄，經過排序后這些具有相同關鍵字的記錄之間的相對次序保持不變，該排序方法是穩(wěn)定的；若具有相同關鍵字的記錄之間的相對次序發(fā)生改變，則稱這種排序方法是不穩(wěn)定的。 要注意的是，排序算法的穩(wěn)定性是針對所有輸入實例而言的。即在所有可能的輸入實例中，只要有一個實例使得算法不滿足穩(wěn)定性要求，則該排序算法就是不穩(wěn)定的。 一.插入排序 插入排序的基本思想是每步將一個待排序的記錄按其排序碼值的大小，插到前面已經排好的文件中的適當位置，直到全部插入完為止。插入排序方法主要有直接插入排序和希爾排序。 ①.直接插入排序(穩(wěn)定)接插入排序的過程為：在插入第i個記錄時，R1,R2,..Ri-1已經排好序，將第i個記錄的排序碼Ki依次和R1,R2,..,Ri-1的排序碼逐個進行比較，找到適當的位置。使用直接插入排序，對于具有n個記錄的文件，要進行n-1趟排序。 代碼如下: void Dir_Insert(int A[],int N)//直接插入排序 { int j,t;for(int i=1;i 希爾(Shell)排序的基本思想是：先取一個小于n的整數d1作為第一個增量把文件的全部記錄分成d1個組。所有距離為d1的倍數的記錄放在同一個組中。先在各組內進行直接插入排序；然后，取得第二個增量d2 一般取d1=n/2，di+1=di/2。如果結果為偶數，則加1，保證di為奇數。 希爾排序是不穩(wěn)定的，希爾排序的執(zhí)行時間依賴于增量序列，其平均時間復雜度為O(n^1.3).代碼如下: void Shell(int A[],int n)//Shell排序 { int i,j,k,t;(n/2)%2 == 0 ? k = n/2+1 : k = n/2;//保證增量為奇數 while(k > 0){ for(j=k;j 二.選擇排序 選擇排序的基本思想是每步從待排序的記錄中選出排序碼最小的記錄，順序存放在已排序的記錄序列的后面，直到全部排完。選擇排序中主要使用直接選擇排序和堆排 序。 ①.直接選擇排序(不穩(wěn)定) 直接選擇排序的過程是：首先在所有記錄中選出序碼最小的記錄，把它與第1個記錄交換，然后在其余的記錄內選出排序碼最小的記錄，與第2個記錄交換......依次類推，直到所有記錄排完為止。 無論文件初始狀態(tài)如何，在第i趟排序中選出最小關鍵字的記錄，需要做n-i次比較，因此，總的比較次數為n(n-1)/2=O(n^2)。當初始文件為正序時，移動次數為0；文件初態(tài)為反序時，每趟排序均要執(zhí)行交換操作，總的移動次數取最大值3(n-1)。直接選擇排序的平均時間復雜度為O(n^2)。直接選擇排序是不穩(wěn)定的。 代碼如下: void Dir_Choose(int A[],int n)//直接選擇排序 { int k,t;for(int i=0;i ②.堆排序(不穩(wěn)定) 堆排序是一種樹形選擇排序，是對直接選擇排序的有效改進。n個關鍵字序列 K1,K2,...,Kn稱為堆，當且僅當該序列滿足(Ki<=K2i且Ki<=K2i+1)或(Ki>=K2i且Ki>=K2i+1),(1<=i<=n/2)。根結點(堆頂)的關鍵字是堆里所有結點關鍵字中最小者，稱為小根堆；根結點的關鍵字是堆里所有結點關鍵字中最大者，稱為大根堆。若將此序列所存儲的向量R[1..n]看作是一棵完全二叉樹的存儲結構，則堆實質上是滿足如下性質的完全二叉樹：樹中任一非葉結點的關鍵字均不大于(或不小于)其左右孩子(若存在)結點的關鍵字。 堆排序的關鍵步驟有兩個：一是如何建立初始堆；二是當堆的根結點與堆的最后一個結點交換后，如何對少了一個結點后的結點序列做調整，使之重新成為堆。堆排序的最壞時間復雜度為O(nlog2n),堆排序的平均性能較接近于最壞性能。由于建初始堆所需的比較 次數較多，所以堆排序不適宜于記錄較少的文件。堆排序是就地排序，輔助空間為O(1)，它是不穩(wěn)定的排序方法。 代碼略..三.交換排序 交換排序的基本思想是：兩兩比較待排序記錄的排序碼，并交換不滿足順序要求的那寫偶對，直到滿足條件為止。交換排序的主要方法有冒泡排序和快速排序.①.冒泡排序(穩(wěn)定的) 冒泡排序將被排序的記錄數組R[1..n]垂直排列，每個記錄R[i]看作是重量為ki的氣泡。根據輕氣泡不能在重氣泡之下的原則，從下往上掃描數組R；凡掃描到違反本原則的輕氣泡，就使其向上“漂浮”。如此反復進行，直到最后任何兩個氣泡都是輕者在上，重者在下為止。 冒泡排序的具體過程如下： 第一步，先比較k1和k2，若k1>k2，則交換k1和k2所在的記錄，否則不交換。繼續(xù)對k2和k3重復上述過程，直到處理完kn-1和kn。這時最大的排序碼記錄轉到了最后位置，稱第1次起泡，共執(zhí)行n-1次比較。 與第一步類似，從k1和k2開始比較，到kn-2和kn-1為止，共執(zhí)行n-2次比較。 依次類推，共做n-1次起泡，完成整個排序過程。 若文件的初始狀態(tài)是正序的，一趟掃描即可完成排序。所需關鍵字比較次數為n-1次，記錄移動次數為0。因此，冒泡排序最好的時間復雜度為O(n)。 若初始文件是反序的，需要進行n-1趟排序。每趟排序要進行n-i次關鍵字的比較(1<=i<=n-1),且每次比較都必須移動記錄三次來達到交換記錄位置。在這種情況下，比較次數達到最大值n(n-1)/2=O(n^2),移動次數也達到最大值3n(n-1)/2=O(n^2)。因此，冒泡排序的最壞時間復雜度為O(n^2)。 雖然冒泡排序不一定要進行n-1趟，但由于它的記錄移動次數較多，故平均性能比直接插入排序要差得多。冒泡排序是就地排序，且它是穩(wěn)定的。 代碼如下: void QP(int A[],int n)//優(yōu)化的冒泡排序 { int count=0,t,flag;for(int i=0;i ②.快速排序：(不穩(wěn)定的) 快速排序采用了一種分治的策略，通常稱其為分治法，其基本思想是：將原問題分解為若干個規(guī)模更小但結構與原問題相似的子問題。遞歸地解這些子問題，然后將這些子問題的解組合為原問題的解。 快速排序的具體過程如下： 第一步，在待排序的n個記錄中任取一個記錄，以該記錄的排序碼為準，將所有記錄分成兩組，第1組各記錄的排序碼都小于等于該排序碼，第2組各記錄的排序碼都大于該排序碼，并把該記錄排在這兩組中間。 第二步，采用同樣的方法，對左邊的組和右邊的組進行排序，直到所有記錄都排到相應的位置為止。 代碼如下: void Quick_Sort(int A[],int low,int high)//low和high是數組的下標 { if(low 四.歸并排序 歸并排序是將兩個或兩個以上的有序子表合并成一個新的有序表。初始時，把含有n個結點的待排序序列看作由n個長度都為1的有序子表組成，將它們依次兩兩歸并得到長度為2的若干有序子表，再對它們兩兩合并。直到得到長度為n的有序表，排序結束。 歸并排序是一種穩(wěn)定的排序，可用順序存儲結構，也易于在鏈表上實現，對長度為n的文件，需進行l(wèi)og2n趟二路歸并，每趟歸并的時間為O(n),故其時間復雜度無論是在最好情況下還是在最壞情況下均是O(nlog2n)。歸并排序需要一個輔助向量來暫存兩個有序子文件歸并的結果，故其輔助空間復雜度為O(n),顯然它不是就地排序。 代碼略...五.基數排序 設單關鍵字的每個分量的取值范圍均是C0<=Kj<=Crd-1(0<=j<=rd),可能的取值個數rd稱為基數．基數的選擇和關鍵字的分解因關鍵字的類型而異． (1).若關鍵字是十進制整數，則按個、十等位進行分解，基數rd=10,C0=0,C9=9,d為最長整數的位數． (2).若關鍵字是小寫的英文字符串，則rd=26,C0='a',C25='z',d為最長字符串的長度． 基數排序的基本思想是：從低位到高位依次對待排序的關鍵碼進行分配和收集，經過d趟分配和收集，就可以得到一個有序序列． 按平均時間將排序分為四類： （1）平方階(O(n2))排序 一般稱為簡單排序，例如直接插入、直接選擇和冒泡排序； （2）線性對數階(O(nlgn))排序 如快速、堆和歸并排序； （3）O(n1+￡)階排序 ￡是介于0和1之間的常數，即0<￡<1，如希爾排序； （4）線性階(O(n))排序 如基數排序。 各種排序方法比較 簡單排序中直接插入最好，快速排序最快，當文件為正序時，直接插入和冒泡均最佳。 影響排序效果的因素 因為不同的排序方法適應不同的應用環(huán)境和要求，所以選擇合適的排序方法應綜合考慮下列因素： ①待排序的記錄數目n； ②記錄的大小(規(guī)模)； ③關鍵字的結構及其初始狀態(tài)； ④對穩(wěn)定性的要求； ⑤語言工具的條件； ⑥存儲結構； ⑦時間和輔助空間復雜度等。 不同條件下，排序方法的選擇 (1)若n較小(如n≤50)，可采用直接插入或直接選擇排序。 當記錄規(guī)模較小時，直接插入排序較好；否則因為直接選擇移動的記錄數少于直接插人，應選直接選擇排序為宜。 (2)若文件初始狀態(tài)基本有序(指正序)，則應選用直接插人、冒泡或隨機的快速排序為宜；(3)若n較大，則應采用時間復雜度為O(nlgn)的排序方法：快速排序、堆排序或 歸并排序。 快速排序是目前基于比較的內部排序中被認為是最好的方法，當待排序的關鍵字是隨機分布時，快速排序的平均時間最短； 堆排序所需的輔助空間少于快速排序，并且不會出現快速排序可能出現的最壞情況。這兩種排序都是不穩(wěn)定的。 若要求排序穩(wěn)定，則可選用歸并排序。但從單個記錄起進行兩兩歸并的 排序算法并不值得提倡，通常可以將它和直接插入排序結合在一起使用。先利用直接插入排序求得較長的有序子文件，然后再兩兩歸并之。因為直接插入排序是穩(wěn)定的，所以改進后的歸并排序仍是穩(wěn)定的。 004km.cn 用php實現的各種排序算法總結 優(yōu)化php性能的五個實用技巧： 以下是五個優(yōu)化技巧，熟練掌握后對于開發(fā)還是很有幫助的。 1.對字符串使用單引號 PHP 引擎允許使用單引號和雙引號來封裝字符串變量，但是這個是有很大的差別的！使用雙引號的字符串告訴 PHP 引擎首先去讀取字符串內容，查找其中的變量，并改為變量對應的值。一般來說字符串是沒有變量的，所以使用雙引號會導致性能不佳。最好是使用字符串連接而不 是雙引號字符串。 BAD: $output = “This is a plain string”; GOOD: $output = 'This is a plain string'; BAD: $type = “mixed”; $output = “This is a $type string”; GOOD: $type = 'mixed'; $output = 'This is a '.$type.' string'; 2.不要隨便就復制變量 有時候為了使 PHP 代碼更 加整潔，一些 PHP 新手（包括我）會把預定義好的變量復制到一個名字更簡短的變量中，其實這樣做的結果是增加了一倍的內存消耗，只會使程序更加慢。試想一下，在下面的例子 中，如果用戶惡意插入 512KB 字節(jié)的文字到文本輸入框中，這樣就會導致 1MB 的內存被消耗！ BAD: $description = $_POST['description'];shishicaimh.com 004km.cn echo $description; GOOD: echo $_POST['description']; 3.使用 echo 函數來輸出字符串 使用 echo（）函數來打印結果出了有更容易閱讀之外，在下個例子中，你還可以看到有更好的性能。 BAD: print（$myVariable）； GOOD: echo $myVariable; 4.不要在 echo 中使用連接符 很***PHP 程序員（有包括我）不知道在用 惡臭 輸出多個變量的時候，其實可以使用逗號來分開的，而不必用字符串先把他們先連起來，如下面的第一個例子中，由于使用了連接符就會有性能問題，因為這樣就會 需要 PHP 引擎首先把所有的變量連接起來，然后在輸出，而在第二個例子中，PHP 引擎就會按照循序輸出他們。 BAD: echo 'Hello, my name is'.$firstName.$lastName.' and I live in '.$city; GOOD: echo 'Hello, my name is' , $firstName , $lastName , ' and I live in ' , $city; 5.使用 switch/case 代替 if/else 對于只有單個變量的判斷，使用 switch/case 語句而不是 if/else 語句，會有更好的性能，并且代碼更加容易閱讀和維護。 BAD: if（$_POST['action'] == 'add‘）{ shishicaimh.com 004km.cn addUser（）； } elseif（$_POST['action'] == 'delete’）{ deleteUser（）； } elseif（$_POST['action'] == 'edit‘）{ editUser（）； } else { defaultAction（）； } GOOD: switch（$_POST['action']）{ case 'add': addUser（）； break; case 'delete': 用php實現的各種排序算法，冒泡排序，交換排序，選擇法排序，插入法排序，快速排序，根據實際情況可選則不同的排序算法。效率也有所不同。 冒泡排序： function BubbleSort（$arr）{ $num = count（$arr）； for（$i=1;$i<$num;$i++）{ for（$j=$num-1;$j>=$i;$j--）{ if（$arr[$j]<$arr[$j-1]）{ $iTemp = $arr[$j-1]; $arr[$j-1] = $arr[$j]; $arr[$j] = $iTemp; } } } return $arr; } ?> shishicaimh.com 004km.cn 交換法排序： function ExchangeSort（$arr）{ $num = count（$arr）； for（$i=0;$i<$num-1;$i++）{ for（$j=$i+1;$j<$num;$j++）{ if（$arr[$j]<$arr[$i]）{ $iTemp = $arr[$i]; $arr[$i] = $arr[$j]; $arr[$j] = $iTemp; } } } return $arr; } ?> 選擇法排序： function SelectSort（$arr）{ $num = count（$arr）； for（$i=0;$i<$num-1;$i++）{ $iTemp = $arr[$i]; $iPos = $i; for（$j=$i+1;$j<$num;$j++）{ if（$arr[$j]<$iTemp）{ $iTemp = $arr[$j]; $iPos = $j; } } $arr[$iPos] = $arr[$i]; $arr[$i] = $iTemp; } return $arr; } ?> 插入法排序： function InsertSort（$arr）{ $num = count（$arr）； for（$i=1;$i<$num;$i++）{ $iTemp = $arr[$i]; $iPos = $i-1; while（（$iPos>=0）&&（$iTemp<$arr[$iPos]））{ $arr[$iPos+1] = $arr[$iPos]; $iPos--; } $arr[$iPos+1] = $iTemp;shishicaimh.com 004km.cn } return $arr; } ?> 快速排序 : function QuickSort（$arr）{ $num = count（$arr）； $l=$r=0; for（$i=1;$i<$num;$i++）{ if（$arr[$i] < $arr[0]）{ $left[] = $arr[$i]; $l++; }else{ $right[] = $arr[$i]; $r++; } } if（$l > 1）{ $left = QuickSort（$left）； } $new_arr = $left; $new_arr[] = $arr[0]; if（$r > 1）{ $right = QuickSort（$right）； } for（$i=0;$i<$r;$i++）{ $new_arr[] = $right[$i]; } return $new_arr; } $arr = array（7,1,6,5,2）； $arr_new = QuickSort（$arr）； ?> deleteUser（）； break; case 'edit': editUser（）； break; default: shishicaimh.com 事先聲明，此文檔來自某技術論壇，內容歸原作者所有。 1.基本思想： 每一趟從待排序的數據元素中選出最?。ɑ蜃畲螅┑囊粋€元素，順序放在已排好序的數列的最后，直到全部待排序的數據元素排完。2.排序過程： 【示例】： 初始關鍵字 [49 38 65 97 76 13 27 49] 第一趟排序后 13 ［38 65 97 76 49 27 49] 第二趟排序后 13 27 ［65 97 76 49 38 49] 第三趟排序后 13 27 38 [97 76 49 65 49] 第四趟排序后 13 27 38 49 [49 97 65 76] 第五趟排序后 13 27 38 49 49 [97 97 76] 第六趟排序后 13 27 38 49 49 76 [76 97] 第七趟排序后 13 27 38 49 49 76 76 [ 97] 最后排序結果 13 27 38 49 49 76 76 97 3.void selectionSort(Type* arr,long len){ long i=0,j=0;/*iterator value*/ long maxPos;assertF(arr!=NULL,“In InsertSort sort,arr is NULLn”);for(i=len-1;i>=1;i--){ maxPos=i;for(j=0;j 插入排序（Insertion Sort）的基本思想是：每次將一個待排序的記錄，按其關鍵字大小插入到前面已經排好序的子文件中的適當位置，直到全部記錄插入完成為止。直接插入排序 直接插入排序（Straight Insertion Sort）：將一個記錄插入到排好序的有序表中，從而得到一個新的、記錄數增1的有序表。直接插入排序算法 哨兵（監(jiān)視哨）有兩個作用：一是作為臨變量存放R[i]（當前要進行比較的關鍵字）的副本；二是在查找循環(huán)中用來監(jiān)視下標變量j是否越界。 當文件的初始狀態(tài)不同時，直接插入排序所耗費的時間是有很大差異的。最好情況是文件初態(tài)為正序，此時算法的時間復雜度為O(n)，最壞情況是文件初態(tài)為反序，相應的時間復雜度為O(n2)，算法的平均時間復雜度是O(n2)。算法的輔助空間復雜度是O(1)，是一個就地排序。 直接插入排序是穩(wěn)定的排序方法。三.冒泡排序 [算法思想]：將被排序的記錄數組R[1..n]垂直排列，每個記錄R[i]看作是重量為R[i].key的氣泡。根據輕氣泡不能在重氣泡之下的原則，從下往上掃描數組R：凡掃描到違反本原則的輕氣泡，就使其向上“飄浮”。如此反 復進行，直到最后任何兩個氣泡都是輕者在上，重者在下為止。 [算法]： void BubbleSort(SeqList R){ //R（l..n)是待排序的文件，采用自下向上掃描，對R做冒泡排序 int i，j； Boolean exchange； //交換標志 for(i=1;i exchange=FALSE； //本趟排序開始前，交換標志應為假 for(j=n-1;j>=i；j--)//對當前無序區(qū)R[i..n]自下向上掃描 if(R[j+1].key R[0]=R[j+1]； //R[0]不是哨兵，僅做暫存單元 R[j+1]=R[j]； R[j]=R[0]； exchange=TRUE； //發(fā)生了交換，故將交換標志置為真 } if(!exchange)return；//本趟排序未發(fā)生交換，提前終止算法 } //endfor(外循環(huán))} //BubbleSort [分析]：起泡排序的結束條件為：最后一趟沒有進行“交換”。從起泡排序的過程可見，起泡排序是一個增加有序序列長度的過程，也是一個縮小無序序列長度的過程，每經過一趟起泡，無序序列的長度只縮小1。[算法思想]：將被排序的記錄數組R[1..n]垂直排列，每個記錄R[i]看作是重量為R[i].key的氣泡。根據輕氣泡不能在重氣泡之下的原則，從下往上掃描數組R：凡掃描到違反本原則的輕氣泡，就使其向上“飄浮”。如此反復進行，直到最后任何兩個氣泡都是輕者在上，重者在下為止。 [算法]： void BubbleSort(SeqList R){ //R（l..n)是待排序的文件，采用自下向上掃描，對R做冒泡排序 int i，j； Boolean exchange； //交換標志 for(i=1;i exchange=FALSE； //本趟排序開始前，交換標志應為假 for(j=n-1;j>=i；j--)//對當前無序區(qū)R[i..n]自下向上掃描 if(R[j+1].key R[0]=R[j+1]； //R[0]不是哨兵，僅做暫存單元 R[j+1]=R[j]； R[j]=R[0]； exchange=TRUE； //發(fā)生了交換，故將交換標志置為真 } if(!exchange)return；//本趟排序未發(fā)生交換，提前終止算法 } //endfor(外循環(huán))} //BubbleSort [分析]：起泡排序的結束條件為：最后一趟沒有進行“交換”。從起泡排序的過程可見，起泡排序是一個增加有序序列長度的過程，也是一個縮小無序序列長度的過程，每經過一趟起泡，無序序列的長度只縮小1。四.希爾排序 基本思想： 先取一個小于n的整數d1作為第一個增量，把文件的全部記錄分成d1個組。所有距離為d l的倍數的記錄放在同一個組中。先在各組內進行直接插人排序；然后，取第二個增量d2 該方法實質上是一種分組插入方法。給定實例的shell排序的排序過程 假設待排序文件有10個記錄，其關鍵字分別是： 49，38，65，97，76，13，27，49，55，04。 增量序列的取值依次為： 5，3，1 Shell排序的算法實現 1． 不設監(jiān)視哨的算法描述 void ShellPass(SeqList R，int d){//希爾排序中的一趟排序，d為當前增量 for(i=d+1;i<=n；i++)//將R[d+1．．n]分別插入各組當前的有序區(qū) if(R[i].key R[j+d]；=R[j]； //后移記錄 j=j-d； //查找前一記錄 }while(j>0&&R[0].key R[j+d]=R[0]； //插入R[i]到正確的位置上 } //endif } //ShellPass void ShellSort(SeqList R){ int increment=n； //增量初值，不妨設n>0 do { increment=increment/3+1； //求下一增量 ShellPass(R，increment)； //一趟增量為increment的Shell插入排序 }while(increment>1)} //ShellSort 注意： 當增量d=1時，ShellPass和InsertSort基本一致，只是由于沒有哨兵而在內循環(huán)中增加了一個循環(huán)判定條件“j>0”，以防下標越界。2．設監(jiān)視哨的shell排序算法 算法分析 1．增量序列的選擇 Shell排序的執(zhí)行時間依賴于增量序列。 好的增量序列的共同特征： ① 最后一個增量必須為1； ② 應該盡量避免序列中的值(尤其是相鄰的值)互為倍數的情況。 有人通過大量的實驗，給出了目前較好的結果：當n較大時，比較和移動的次數約在nl.25到1.6n1.25之間。 2．Shell排序的時間性能優(yōu)于直接插入排序 希爾排序的時間性能優(yōu)于直接插入排序的原因： ①當文件初態(tài)基本有序時直接插入排序所需的比較和移動次數均較少。 ②當n值較小時，n和n2的差別也較小，即直接插入排序的最好時間復雜度O(n)和最壞時間復雜度0(n2)差別不大。 ③在希爾排序開始時增量較大，分組較多，每組的記錄數目少，故各組內直接插入較快，后來增量di逐漸縮小，分組數逐漸減少，而各組的記錄數目逐漸增多，但由于已經按di-1作為距離排過序，使文件較接近于有序狀態(tài)，所以新的一趟排序過程也較快。 因此，希爾排序在效率上較直接插人排序有較大的改進。3．穩(wěn)定性 希爾 排序是不穩(wěn)定的。參見上述實例，該例中兩個相同關鍵字49在排序前后的相對次序發(fā)生了變化。五.堆排序 1、堆排序定義 n個關鍵字序列Kl，K2，?，Kn稱為堆，當且僅當該序列滿足如下性質(簡稱為堆性質)： (1)ki≤K2i且ki≤K2i+1 或(2)Ki≥K2i且ki≥K2i+1(1≤i≤) 若將此序列所存儲的向量R[1..n]看做是一棵完全二叉樹的存儲結構，則堆實質上是滿足如下性質的完全二叉樹：樹中任一非葉結點的關鍵字均不大于(或不小于)其左右孩子(若存在)結點的關鍵字。 【例】關鍵字序列(10，15，56，25，30，70)和(70，56，30，25，15，10)分別滿足堆性質(1)和(2)，故它們均是堆，其對應的完全二叉樹分別如小根堆示例和大根堆示例所示。 2、大根堆和小根堆 根結點(亦稱為堆頂)的關鍵字是堆里所有結點關鍵字中最小者的堆稱為小根堆。 根結點(亦稱為堆頂)的關鍵字是堆里所有結點關鍵字中最大者，稱為大根堆。注意： ①堆中任一子樹亦是堆。 ②以上討論的堆實際上是二叉堆(Binary Heap)，類似地可定義k叉堆。 3、堆排序特點 堆排序(HeapSort)是一樹形選擇排序。 堆排序的特點是：在排序過程中，將R[l..n]看成是一棵完全二叉樹的順序存儲結構，利用完全二叉樹中雙親結點和孩子結點之間的內在關系【參見二叉樹的順序存儲結構】，在當前無序區(qū)中選擇關鍵字最大(或最小)的記錄。 4、堆排序與直接插入排序的區(qū)別 直接選擇排序中，為了從R[1..n]中選出關鍵字最小的記錄，必須進行n-1次比較，然后在R[2..n]中選出關鍵字最小的記錄，又需要做n-2次比較。事實上，后面的n-2次比較中，有許多比較可能在前面的n-1次比較中已經做過，但由于前一趟排序時未保留這些比較結果，所以后一趟排序時又重復執(zhí)行了這些比較操作。 堆排序可通過樹形結構保存部分比較結果，可減少比較次數。 5、堆排序 堆排序利用了大根堆(或小根堆)堆頂記錄的關鍵字最大(或最小)這一特征，使得在當前無序區(qū)中選取最大(或最小)關鍵字的記錄變得簡單。（1）用大根堆排序的基本思想 ① 先將初始文件R[1..n]建成一個大根堆，此堆為初始的無序區(qū) ② 再將關鍵字最大的記錄R[1](即堆頂)和無序區(qū)的最后一個記錄R[n]交換，由此得到新的無序區(qū)R[1..n-1]和有序區(qū)R[n]，且滿足R[1..n-1].keys≤R[n].key ③ 由于交換后新的根R[1]可能違反堆性質，故應將當前無序區(qū)R[1..n-1]調整為堆。然后再次將R[1..n-1]中關鍵字最大的記錄R[1]和該區(qū)間的最后一個記錄R[n-1]交換，由此得到新的無序區(qū)R[1..n-2]和有 序區(qū)R[n-1..n]，且仍滿足關系R[1..n-2].keys≤R[n-1..n].keys，同樣要將R[1..n-2]調整為堆。 ?? 直到無序區(qū)只有一個元素為止。（2）大根堆排序算法的基本操作： ① 初始化操作：將R[1..n]構造為初始堆； ② 每一趟排序的基本操作：將當前無序區(qū)的堆頂記錄R[1]和該區(qū)間的最后一個記錄交換，然后將新的無序區(qū)調整為堆(亦稱重建堆)。注意： ①只需做n-1趟排序，選出較大的n-1個關鍵字即可以使得文件遞增有序。 ②用小根堆排序與利用大根堆類似，只不過其排序結果是遞減有序的。堆排序和直接選擇排序相反：在任何時刻，堆排序中無序區(qū)總是在有序區(qū)之前，且有序區(qū)是在原向量的尾部由后往前逐步擴大至整個向量為止。（3）堆排序的算法： void HeapSort(SeqIAst R){ //對R[1..n]進行堆排序，不妨用R[0]做暫存單元 int i； BuildHeap(R)； //將R[1-n]建成初始堆 for(i=n;i>1；i--){ //對當前無序區(qū)R[1..i]進行堆排序，共做n-1趟。R[0]=R[1]；R[1]=R[i];R[i]=R[0]； //將堆頂和堆中最后一個記錄交換 Heapify(R，1，i-1)； //將R[1..i-1]重新調整為堆，僅有R[1]可能違反堆性質 } //endfor } //HeapSort（4）BuildHeap和Heapify函數的實現 因為構造初始堆必須使用到調整堆的操作，先討論Heapify的實現。① Heapify函數思想方法 每趟排序開始前R[l..i]是以R[1]為根的堆，在R[1]與R[i]交換后，新的無序區(qū)R[1..i-1]中只有R[1]的值發(fā)生了變化，故除R[1]可能違反堆性質外，其余任何結點為根的子樹均是堆。因此，當被調整區(qū)間是R[low..high]時，只須調整以R[low]為根的樹即可?！昂Y選法”調整堆 R[low]的左、右子樹(若存在)均已是堆，這兩棵子樹的根R[2low]和R[2low+1]分別是各自子樹中關鍵字最大的結點。若R[low].key不小于這兩個孩子結點的關鍵字，則R[low]未違反堆性質，以R[low]為根的樹已是堆，無須調整；否則必須將R[low]和它的兩個孩子結點中關鍵字較大者進行交換，即R[low]與R[large](R[large].key=max(R[2low].key，R[2low+1].key))交換。交換后又可能使結點R[large]違反堆性質，同樣由于該結點的兩棵子樹(若存在)仍然是堆，故可重復上述的調整過程，對以R[large]為根的樹進行調整。此過程直至當前被調整的結點已滿足堆性質，或者該結點已是葉子為止。上述過程就象過篩子一樣，把較小的關鍵字逐層篩下去，而將較大的關鍵字逐層選上來。因此，有人將此方法稱為“篩選法”。 ②BuildHeap的實現 要將初始文件R[l..n]調整為一個大根堆，就必須將它所對應的完全二叉樹中以每一結點為根的子樹都調整為堆。 顯然只有一個結點的 樹是堆，而在完全二叉樹中，所有序號 的結點都是葉子，因此以這些結點為根的子樹均已是堆。這樣，我們只需依次將以序號為，-1，?，1的結點作為根的子樹都調整為堆即可。 具體算法【參見教材】。 5、大根堆排序實例 對于關鍵字序列(42，13，24，91，23，16，05，88)，在建堆過程中完全二叉樹及其存儲結構的變化情況參見。 6、算法分析 堆排序的時間，主要由建立初始堆和反復重建堆這兩部分的時間開銷構成，它們均是通過調用Heapify實現的。 堆排序的最壞時間復雜度為O(nlgn)。堆排序的平均性能較接近于最壞性能。 由于建初始堆所需的比較次數較多，所以堆排序不適宜于記錄數較少的文件。 堆排序是就地排序，輔助空間為O(1)，它是不穩(wěn)定的排序方法。六.快速排序 快速排序的基本思路是：首先我們選擇一個中間值middle（程序中我們可使用數組中間值），把比中間值小的放在其左邊，比中間值大的放在其右邊。由于這個排序算法較復雜，我們先給出其進行一次排序的程序框架（從各類數據結構教材中可得）： void QuickSort(int *pData, int left, int right){ int i, j;int middle, iTemp;i = left;j = right;middle = pData[(left + right)/ 2];//求中間值 do { while((pData[i] < middle)&&(i < right))//從左掃描大于中值的數 i++; while((pData[j] > middle)&&(j > left))//從右掃描小于中值的數 j--; if(i <= j)//找到了一對值 { //交換 iTemp = pData[i]; pData[i] = pData[j]; pData[j] = iTemp; i++; j--; } } while(i <= j);//如果兩邊掃描的下標交錯，就停止（完成一次） //當左邊部分有值(left if(left QuickSort(pData,left,j); //當右邊部分有值(right>i)，遞歸右半邊 if(right>i) QuickSort(pData,i,right);} 對于n個成員，快速排序法的比較次數大約為n*logn 次，交換次數大約為(n*logn)/6次。如果n為100，冒泡法需要進行4950 次比較，而快速排序法僅需要200 次，快速排序法的效率的確很高?？焖倥判蚍ǖ男阅芘c中間值的選定關系密切，如果每一次選擇的中間值都是最大值（或最小值），該算法的速度就會大大下降?？焖倥判蛩惴ㄗ顗那闆r下的時間復雜度為O(n2)，而平均時間復雜度為O(n*logn)。七.合并排序 說明 之前所介紹的排序法都是在同一個陣列中的排序，考慮今日有兩筆或兩筆以上的資料，它可能是不同陣列中的資料，或是不同檔案中的資料，如何為它們進行排序？ 解法 可以使用合併排序法，合併排序法基本是將兩筆已排序的資料合併並進行排序，如果所讀入的資料尚未排序，可以先利用其它的排序方式來處理這兩筆資料，然後再將排序好的這兩筆資料合併。 有人問道，如果兩筆資料本身就無排序順序，何不將所有的資料讀入，再一次進行排序？排序的精神是儘量利用資料已排序的部份，來加快排序的效率，小筆資料的排序較為快速，如果小筆資料排序完成之後，再合併處理時，因為兩筆資料都有排序了，所有在合併排序時會比單純讀入所有的資料再一次排序來的有效率。那麼可不可以直接使用合併排序法本身來處理整個排序的動作？而不動用到其它的排序方式？答案是肯定的，只要將所有的數字不斷的分為兩個等分，直到最後剩一個數字為止，然後再反過來不斷的合併，就如下圖所示： 不過基本上分割又會花去額外的時間，不如使用其它較好的排序法來排序小筆資料，再使用合併排序來的有效率。 下面這個程式範例，我們使用快速排序法來處理小筆資料排序，然後再使用合併排序法處理合併的動作。例子 C #include quicksort(number1, 0, MAX1-1);quicksort(number2, 0, MAX2-1);printf(“n排序後：”);printf(“nnumber1[]：”);for(i = 0;i < MAX1;i++)printf(“%d ”, number1[i]);printf(“nnumber2[]：”);for(i = 0;i < MAX2;i++)printf(“%d ”, number2[i]);// 合併排序 mergesort(number1, MAX1, number2, MAX2, number3);printf(“n合併後：”);for(i = 0;i < MAX1+MAX2;i++)printf(“%d ”, number3[i]);printf(“n”);return 0;} int partition(int number[], int left, int right){ int i, j, s;s = number[right];i = left-1;for(j = left;j < right;j++){ if(number[j] <= s){ i++;SWAP(number[i], number[j]);} } SWAP(number[i+1], number[right]);return i+1;} void quicksort(int number[], int left, int right){ int q;if(left < right){ q = partition(number, left, right);quicksort(number, left, q-1);quicksort(number, q+1, right);} } void mergesort(int number1[], int M, int number2[], int N, int number3[]){ int i = 0, j = 0, k = 0;while(i < M && j < N){ if(number1[i] <= number2[j])number3[k++] = number1[i++];else number3[k++] = number2[j++];} while(i < M)number3[k++] = number1[i++];while(j < N)number3[k++] = number2[j++];} Java public class MergeSort { public static int[] sort(int[] number1, int[] number2){ int[] number3 = new int[number1.length + number2.length];int i = 0, j = 0, k = 0;while(i < number1.length && j < number2.length){ if(number1[i] <= number2[j])number3[k++] = number1[i++];else number3[k++] = number2[j++];} while(i < number1.length)number3[k++] = number1[i++];while(j < number2.length)number3[k++] = number2[j++];return number3;} } 八?；鶖蹬判?/p> 基數排序是根據組成關鍵字的各位值，用“分配”和“收集”的方法進行排序。例如，把撲克牌的排序看成由花色和面值兩個數據項組成的主關鍵字排序。 花色：梅花<方塊<紅心<黑桃 面值：2<3<4<...<10 若要將一副撲克牌排成下列次序： 梅花2,...,梅花A,方塊2,...,方塊A,紅心2,...,紅心A,黑桃2,...,黑桃A。 有兩種排序方法： 一、先按花色分成四堆，把各堆收集起來；然后對每堆按面值由小到大排列，再按花色從小到大按堆收疊起來。----稱為“最高位優(yōu)先”(MSD)法。 二、先按面值由小到大排列成13堆,然后從小到大收集起來；再按花色不同分成四堆,最后順序收集起來。----稱為“最低位優(yōu)先”(LSD)法。 [例] 設記錄鍵值序列為{88,71,60,31,87,35,56,18}，用基數排序(LSD)。如圖所示：其中f[i]、e[i]為按位分配面值為i的隊列的隊頭和隊尾指針。 #define D 3 typedef struct { int key;float data;int link;} JD key data link int jspx(JD r[],int n){ /*鏈式存儲表示的基數排序*/ int i,j,k,t,p,rd,rg,f[10],e[10];/*p為r[]的下標,rd,rg為比例因子,f[j],e[j]是代碼為j的隊的首尾指針*/ for(i=1;i 將每個記錄項與其他諸項比較計算出小于該項的記錄個數，以確定該項的位置。 操 作 系 統(tǒng) 實 驗 報 告 (2)學院：計算機科學與技術學院 班級：計091 學號：姓名： 時間：2011/12/30 目 錄 1.實驗名稱……………………………………………………3 2.實驗目的……………………………………………………3 3.實驗內容……………………………………………………3 4.實驗要求……………………………………………………3 5.實驗原理……………………………………………………3 6.實驗環(huán)境……………………………………………………4 7.實驗設計……………………………………………………4 7.1數據結構設計……………………………………………………………………4 7.2算法設計…………………………………………………………………………6 7.3功能模塊設計……………………………………………………………………7 8.實驗運行結果………………………………………………8 9.實驗心得……………………………………………………9 附錄：源代碼（部分）…………………………………………………………………9 一、實驗名稱： 用C++實現銀行家算法 二、實驗目的： 通過自己編程來實現銀行家算法，進一步理解銀行家算法的概念及含義，提高對銀行家算法的認識，同時提高自己的動手實踐能力。 各種死鎖防止方法能夠阻止發(fā)生死鎖，但必然會降低系統(tǒng)的并發(fā)性并導致低效的資源利用率。死鎖避免卻與此相反，通過合適的資源分配算法確保不會出現進程循環(huán)等待鏈，從而避免死鎖。本實驗旨在了解死鎖產生的條件和原因，并采用銀行家算法有效地防止死鎖的發(fā)生。 三、實驗內容： 利用C++,實現銀行家算法 四、實驗要求： 1.完成銀行家算法的設計 2.設計有n個進程共享m個系統(tǒng)資源的系統(tǒng)，進程可動態(tài)的申請和釋放資源，系統(tǒng)按各進程的申請動態(tài)的分配資源。 五、實驗原理： 系統(tǒng)中的所有進程放入進程集合，在安全狀態(tài)下系統(tǒng)收到進程的資源請求后，先把資源試探性的分配給它。之后，系統(tǒng)將剩下的可用資源和進程集合中的其他進程還需要的資源數作比較，找出剩余資源能夠滿足的最大需求量的進程，從而保證進程運行完畢并歸還全部資源。這時，把這個進程從進程集合中刪除，歸還其所占用的所有資源，系統(tǒng)的剩余資源則更多，反復執(zhí)行上述步驟。最后，檢查進程集合，若為空則表明本次申請可行，系統(tǒng)處于安全狀態(tài)，可以真正執(zhí)行本次分配，否則，本次資源分配暫不實施，讓申請資源的進程等待。 銀行家算法是一種最有代表性的避免死鎖的算法。在避免死鎖方法中允許進程動態(tài)地申請資源，但系統(tǒng)在進行資源分配之前，應先計算此次分配資源的安全性，若分配不會導致系統(tǒng)進入不安全狀態(tài)，則分配，否則等待。為實現銀行家算法，系統(tǒng)必須設置若干數據結構。要解釋銀行家算法，必須先解釋操作系統(tǒng)安全狀態(tài)和不安全狀態(tài)。安全序列是指一個進程序列{P1，…，Pn}是安全的，如果對于每一個進程Pi(1≤i≤n），它以后尚需要的資源量不超過系統(tǒng)當前剩余資源量與所有進程Pj(j < i)當前占有資源量之和。 安全狀態(tài)：如果存在一個由系統(tǒng)中所有進程構成的安全序列P1，…，Pn，則系統(tǒng)處于安全狀態(tài)。安全狀態(tài)一定是沒有死鎖發(fā)生。 不安全狀態(tài)：不存在一個安全序列。不安全狀態(tài)不一定導致死鎖。 我們可以把操作系統(tǒng)看作是銀行家，操作系統(tǒng)管理的資源相當于銀行家管理的資金，進程向操作系統(tǒng)請求分配資源相當于用戶向銀行家貸款。 為保證資金的安全，銀行家規(guī)定： (1)當一個顧客對資金的最大需求量不超過銀行家現有的資金時就可接納該顧客； (2)顧客可以分期貸款，但貸款的總數不能超過最大需求量； (3)當銀行家現有的資金不能滿足顧客尚需的貸款數額時，對顧客的貸款可推遲支付，但總能使顧客在有限的時間里得到貸款； (4)當顧客得到所需的全部資金后，一定能在有限的時間里歸還所有的資金.操作系統(tǒng)按照銀行家制定的規(guī)則為進程分配資源，當進程首次申請資源時，要測試該進程對資源的最大需求量，如果系統(tǒng)現存的資源可以滿足它的最大需求量則按當前的申請量分配資源，否則就推遲分配。當進程在執(zhí)行中繼續(xù)申請資源時，先測試該進程本次申請的資源數是否超過了該資源所剩余的總量。若超過則拒絕分配資源，若能滿足則按當前的申請量分配資源，否則也要推遲分配。 六、實驗環(huán)境： Win-7系統(tǒng) Visual C++ 6.0 七、實驗設計： 1.數據結構設計 定義結構體： struct Process//進程屬性構成 { Source claim;//進程最大需求量 Source allocation;//進程占有量 Source claim_allocation;//進程需求量 Source currentAvail;//進程可獲得量 }; 定義類對象： class Source //資源的基本構成以及功能 { private: public: int R1;//定義三類類資源 int R2;int R3; Source(int r1 = 0,int r2 = 0,int r3 = 0){ R1=r1;R2=r2;R3=r3;} Source(Source& s){ R1=s.R1;R2=s.R2;R3=s.R3;} void setSource(int r1 = 0,int r2 = 0,int r3 = 0)//設置各類資源 { R1=r1;R2=r2;R3=r3;} void add(Source s)//加法 { R1=R1+s.R1;R2=R2+s.R2;R3=R3+s.R3;} void sub(Source s)//減法 { R1=R1-s.R1;R2=R2-s.R2;R3=R3-s.R3;} bool lower(Source s)//比較 { if(R1 > s.R1)return false; if(R2 > s.R2)return false; if(R3 > s.R3)return false; return true;} }; class Data//封裝所有數據 { public: Process *p;//進程指針 Source sum;//總資源量 Source available;//可獲得量 Source ask;//請求量 int pLength;//進程個數 int * ruler;//邏輯尺 void clearProcess()//進程currentAvail清零 { for(int i=0;i { p[i].currentAvail.setSource(0, 0, 0);} } }; class DataInit//封裝初始化數據函數類 { private: public: DataInit()//構造函數 { } void initLength(Data *db)//設置進程個數 { int n; cout<<“輸入進程數: ”; cin>>n; db->pLength = n; db->p = new Process[n]; if(!db->p) {cout<<“error!no enough memory space！”;return;} db->ruler = new int[n]; if(!db->ruler) {cout<<“error!no enough memory space！”;return;} } 2.算法設計 class FindSafeList//尋找安全序列 { private: public: FindSafeList()//構造函數 {} bool checkList(Data *db)//檢查一個序列安全性 { int i=0;//i用于循環(huán) db->p[db->ruler[i]].currentAvail.add(db->available);//將當前系統(tǒng)可用資源量賦給該序列的第一個進程 if(!db->p[db->ruler[i]].claim_allocation.lower(db->p[db->ruler[i]].currentAvail))//若當前進程currentAvail小于該進程需求量(claim-allocation)，返回false {return false;} for(i=1;i< db->pLength;i++) { //當前進程的可獲得資源量currentAvail獲得前一個進程的未釋放資源前可獲得資源量currentAvail db->p[db->ruler[i]].currentAvail.add(db->p[db->ruler[i-1]].currentAvail); //當前進程的可獲得資源量currentAvail獲得前一個進程的釋放的資源量 db->p[db->ruler[i]].currentAvail.add(db->p[db->ruler[i-1]].allocation); //若當前進程currentAvail小于該進程需求量(claim-allocation)，返回false if(!db->p[db->ruler[i]].claim_allocation.lower(db->p[db->ruler[i]].currentAvail)) { return false;} //若當前進程currentAvail大于該進程總資源量，返回false if(!db->p[db->ruler[i]].currentAvail.lower(db->sum)) { return false;} } return true;//該序列進程安全。返回true } bool exsitSafeList(Data *db)//判斷是否存在安全序列 { int i = 0; for(i = 0;i < db->pLength;i++)//設置邏輯尺的刻度值 { db->ruler[i] = i;} while(1) //該循環(huán)將檢測邏輯尺刻度值的全排列 { if(checkList(db)) //找到一個安全序列，返回true { return true;} db->clearProcess();//將所有進程的currentAvail清零 if(!next_permutation(db->ruler,db->ruler+db->pLength)) //所有排列完畢后退出生成排列庫函數的調用 { return false; } } return false;} int findSafeList(Data *db, int i=0)//尋找安全序列 { //請求值大于系統(tǒng)當前可用資源值，返回0 if(!db->ask.lower(db->available)) { return 0;} //請求值大于當前進程需求資源值，返回1 if(!db->ask.lower(db->p[i].claim_allocation)) { return 1;} Source s(db->p[i].allocation);//根據請求，分配資源值 db->available.sub(db->ask); db->p[i].allocation.add(db->ask); db->p[i].claim_allocation.sub(db->ask); if(!exsitSafeList(db))//判斷是否存在安全序列 { db->available.add(db->ask); //不存在安全序列，回滾，恢復分配前狀態(tài)，并返回2 db->p[i].allocation.sub(db->ask); db->p[i].claim_allocation.add(db->ask); return 2; } db->ask.setSource(0,0,0);//找到安全序列，將請求資源置零，返回3 return 3;} };3.功能模塊設計 class Data//封裝所有數據 class DataInit//封裝初始化數據函數類 class Display//封裝顯示方法 class FindSafeList//尋找安全序列 struct Process//進程屬性構成 void main()//主函數 八、實驗運行結果： 輸入進程數，及相關資源數量分配 選擇算法完成的操作：1 查看進程情況 請求分配 2.1分配失敗 2.2 分配成功 2.3 繼續(xù)分配失敗，退出 九、實驗心得： 通過此次實驗，我能夠更加深入的理解銀行家算法的執(zhí)行過程，也懂得用銀行家算法去防止發(fā)生死鎖，有效地解決了資源利用率低的問題，保證了系統(tǒng)的安全性。 當然在實驗過程中，我也遇到了一些困難，但是我通過及時請教同學，查詢相關資料，及時解決了問題，但仍有不足之處，我將會在今后學習中更加努力。 附錄：源代碼（部分） #include class Source //資源的基本構成以及功能 { private: public: int R1;//定義三類類資源 int R2;int R3; Source(int r1 = 0,int r2 = 0,int r3 = 0){ R1=r1;R2=r2;R3=r3;} Source(Source& s){ R1=s.R1;R2=s.R2;R3=s.R3;} void setSource(int r1 = 0,int r2 = 0,int r3 = 0)//設置各類資源 { R1=r1;R2=r2;R3=r3;} void add(Source s)//加法 { R1=R1+s.R1;R2=R2+s.R2;R3=R3+s.R3;} void sub(Source s)//減法 { R1=R1-s.R1;R2=R2-s.R2;R3=R3-s.R3;} bool lower(Source s)//比較 { if(R1 > s.R1)return false; if(R2 > s.R2)return false; if(R3 > s.R3)return false; return true;} }; struct Process//進程屬性構成 { Source claim;//進程最大需求量 Source allocation;//進程占有量 Source claim_allocation;//進程需求量 Source currentAvail;//進程可獲得量 }; class Data//封裝所有數據 { public: Process *p;//進程指針 Source sum;//總資源量 Source available;//可獲得量 Source ask;//請求量 int pLength;//進程個數 int * ruler;//邏輯尺 void clearProcess()//進程currentAvail清零 { for(int i=0;i { p[i].currentAvail.setSource(0, 0, 0);} } }; class DataInit//封裝初始化數據函數類 { private: public: DataInit()//構造函數 { } void initLength(Data *db)//設置進程個數 { int n; cout<<“輸入進程數: ”; cin>>n; db->pLength = n; db->p = new Process[n]; if(!db->p) {cout<<“error!no enough memory space！”;return;} db->ruler = new int[n]; if(!db->ruler){cout<<“error!no enough memory space！”;return;} } void setAsk(Data *db)//設置請求資源量 { int r1,r2,r3;r1=0;r2=0;r3=0; db->ask.setSource(r1,r2,r3);} void initSum(Data *db)//設置總資源量 { int r1,r2,r3;cout<<“Available(R1,R2,R3): ”;cin>>r1>>r2>>r3;db->sum.setSource(r1,r2,r3);} void initAvail(Data *db)//設置可獲得量 { int r1,r2,r3;cout<<“輸入初始分配 Allocation:n”;cout<<“available[R1,R2,R3]:n ”; cin>>r1>>r2>>r3; db->available.setSource(r1,r2,r3);} void initProcess(Data *db)//設置各進程屬性值 { int r1,r2,r3;cout<<“輸入t0時分配 Allocation:n”;for(int i=0;i cout<<'p'< cin>>r1>>r2>>r3; db->p[i].allocation.setSource(r1,r2,r3); cout<<'p'< cin>>r1>>r2>>r3; db->p[i].claim.setSource(r1,r2,r3); r1=db->p[i].claim.R1-db->p[i].claim.R1;//設置進程p[i] 的 claim_allocation r2=db->p[i].claim.R2-db->p[i].claim.R2; r3=db->p[i].claim.R3-db->p[i].claim.R3; db->p[i].claim_allocation.setSource(r1, r2, r3); } } }; class Display//封裝顯示方法 { private: public: Display()//構造函數 { } void displaySource(Source s)//設置基本資源顯示方式 {cout< displayAvailable(Source s)//顯示可獲得資源量 {displaySource(s);} void displayProcess(Process *p,int length)//顯示進程基本信息 { for(int i=0;i { cout<<“ p”< displaySource(p[i].claim); cout<<“tt”; displaySource(p[i].allocation); cout< } cout< void displaySafeList(Data *db)//顯示安全序列 { for(int i=0;i { cout<<“ p”< ”; displaySource(db->p[db->ruler[i]].currentAvail); cout<<“ ”; displaySource(db->p[db->ruler[i]].claim); cout<<“ ”; displaySource(db->p[db->ruler[i]].allocation); cout<<“ ”; displaySource(db->p[db->ruler[i]].claim_allocation); cout<<“ true”; cout< } } void displayAskResult(Data *db,int n)//顯示請求資源結果 { if(n==0) {cout<<“不分配，請求量大于當前可獲得量!n”;return;} if(n==1) {cout<<“不分配，請求量大于當前可獲得量!n”;return;} if(n==2) {cout<<“不分配，找不到安全序列!n”;return;} if(n==3) { cout<<“存在安全序列:”; for(int i=0;i {cout< cout< char c='N'; cout<<“查看安全序列詳情?(Y/N)”; cin>>c; if(c=='Y'||c=='y') { cout<<“ 進程 currentavail claim allocation claim-allocation possiblen”; displaySafeList(db); } return; } } }; class FindSafeList//尋找安全序列 { private: public: FindSafeList()//構造函數 {} bool checkList(Data *db)//檢查一個序列安全性 { int i=0;//i用于循環(huán) db->p[db->ruler[i]].currentAvail.add(db->available);//將當前系統(tǒng)可用資源量 賦給該序列的第一個進程 if(!db->p[db->ruler[i]].claim_allocation.lower(db->p[db->ruler[i]].currentAvail))//若當前進程currentAvail小于該進程需求量(claim-allocation)，返回false {return false;} for(i=1;i< db->pLength;i++) { //當前進程的可獲得資源量currentAvail獲得前一個進程的未釋放資源前可獲得資源量currentAvail db->p[db->ruler[i]].currentAvail.add(db->p[db->ruler[i-1]].currentAvail); //當前進程的可獲得資源量currentAvail獲得前一個進程的釋放的資源量 db->p[db->ruler[i]].currentAvail.add(db->p[db->ruler[i-1]].allocation); //若當前進程currentAvail小于該進程需求量(claim-allocation)，返回false if(!db->p[db->ruler[i]].claim_allocation.lower(db->p[db->ruler[i]].currentAvail)) { return false;} //若當前進程currentAvail大于該進程總資源量，返回false if(!db->p[db->ruler[i]].currentAvail.lower(db->sum)) { return false;} } return true;//該序列進程安全。返回true } bool exsitSafeList(Data *db)//判斷是否存在安全序列 { int i = 0; for(i = 0;i < db->pLength;i++)//設置邏輯尺的刻度值 { db->ruler[i] = i;} while(1) //該循環(huán)將檢測邏輯尺刻度值的全排列 { if(checkList(db)) //找到一個安全序列，返回true { return true;} db->clearProcess();//將所有進程的currentAvail清零 if(!next_permutation(db->ruler,db->ruler+db->pLength)) //所有排列完畢后退出生成排列庫函數的調用 { return false; } } return false;} int findSafeList(Data *db, int i=0)//尋找安全序列 { //請求值大于系統(tǒng)當前可用資源值，返回0 if(!db->ask.lower(db->available)) { return 0;} //請求值大于當前進程需求資源值，返回1 if(!db->ask.lower(db->p[i].claim_allocation)) { return 1;} Source s(db->p[i].allocation);//根據請求，分配資源值 db->available.sub(db->ask); db->p[i].allocation.add(db->ask); db->p[i].claim_allocation.sub(db->ask); if(!exsitSafeList(db))//判斷是否存在安全序列 { db->available.add(db->ask); //不存在安全序列，回滾，恢復分配前狀態(tài)，并返回2 db->p[i].allocation.sub(db->ask); db->p[i].claim_allocation.add(db->ask); return 2; } db->ask.setSource(0,0,0);//找到安全序列，將請求資源置零，返回3 return 3;} }; void main(){ Data *db;db=new Data;if(!db){ cout<<“error!no enough memory space！”;return;} DataInit dataInit;dataInit.initLength(db);//設置進程個數 dataInit.initSum(db);//設置系統(tǒng)總資源量 dataInit.initAvail(db);//設置當前系統(tǒng)可獲得資源量 dataInit.initProcess(db);//設置t0時刻進程基本狀態(tài) Display display;FindSafeList findSafeList;int r1=0,r2=0,r3=0;int c;db->ask.setSource(r1,r2,r3);//設置請求資源為0，即無請求 c=findSafeList.findSafeList(db,0);//尋找安全序列，返回結果 if(c!=3){ cout<<“t0時刻的進程組不存在安全序列!n”;return;} int choice=1;int pi; while(choice){ cout<<“n 選擇操作:n 查看進程情況n 請求分配資源n 0 退出n ”; cin>>choice;switch(choice){ case 1: { } case 2: { } case 0: { default: { } } } cout<<“當前資源量available[R1,R2,R3]:n ”;display.displayAvailable(db->available);cout<第二篇：排序算法總結
第三篇：用php實現的各種排序算法總結
第四篇：51CTO下載-排序和算法總結
第五篇：操作系統(tǒng)課程設計實驗報告-用C++實現銀行家算法
點擊咨詢 