第九章學生基本信息排序內容目標：排序的基本概念。學生基本信息直接插入排序案例分析學生基本信息折半插入排序案例分析學生基本信息冒泡排序案例分析學生基本信息選擇排序案例分析學生基本信息快速排序案例分析重難點：學生基本信息各類排序的實現1.1功能描述學生基本信息排序表：1.2功能描述學生基本排序界面設計如下：2.1排序的基本概念基本概念排序定義——將一個數據元素（或記錄）的任意序列，重新排列成一個按關鍵字有序的序列叫~排序分類按待排序記錄所在位置內部排序：待排序記錄全部存放在內存中進行排序的過程。外部排序：指待排序的記錄數量，以致內存不能容納全部記錄，在排序過程中尚需對外存進行訪問的排序過程。按排序依據原則插入排序：直接插入排序、折半插入排序、希爾排序交換排序：冒泡排序、快速排序選擇排序：簡單選擇排序、堆排序歸并排序：2-路歸并排序基數排序2.2排序的基本概念按排序所需工作量簡單的排序方法：T(n)=O(n2)先進的排序方法：T(n)=O(logn)排序基本操作比較兩個關鍵字的大小將記錄從一個位置移動到另一個位置。前一種操作對大多數排序方式來說都是必要的，而后一個操作可以通過改變記錄的存儲方式來予以避免。3.1.1業務實現---直接插入排序3.1.2業務實現---直接插入排序具體實現的步驟如下：我們用一個一維數組來裝載排序好的結果。數組下標為0的元素記錄每次要進行插入排序的元素，下標為1、2…N記錄是已由小到大排好的元素。當向一個數組插入第一個元素時，放置在下標為0和1的位置，這時認為第一個元素已經排好序。在向數組插入第2個元素時，首先放置在下標為0的位置，讓它與第1個元素比較，如果比它大，則將元素值放入第2個位置，否則將元素1先移動到第2個位置，再將下標為0的元素放置在第1個位置。在向數組插入第i+1個元素時，前1到i個元素已經排好序，將插入的值放置在下標為0的位置R【0】，從第i個元素開始依次與R【0】比較，若某位置k元素大于R【0】，那么先將第k到i個元素依次向后移動1位，再將R【0】的值放置在第k個元素位置。重復上面的操作，直到所有的數插入完畢。3.1.3業務實現---直接插入排序3.1.4業務實現---直接插入排序構建直接插入排序結點類：構建直接插入排序結點類：publicclassZj_Node{//用于排序的元素結點

publicintKey;//查找的關鍵字

publicStudent_infoData;//數據元素(學生信息）

publicZj_Node() { } publicZj_Node(Student_infoelem) { Key=elem.st_yw; Data=elem; }} 3.1.5業務實現---直接插入排序構建直接插入排序業務類：publicclassZj_Sort{publicintMax;//定義常數，記錄數據容量大小publicZj_Node[]start;//記錄原始的數據publicZj_Node[]end;//記錄排序后的新數據publicStudentMangerBa=newStudentManger();//創建數據控制層對象publicZj_Sort() { Init(); }publicvoidInit() {…}//初始化直接查找表 publicvoidSorting(){…}//對學生信息按語文成績進行排序}

3.1.6業務實現---直接插入排序直接插入排序數據的初始化方法： publicvoidInit() { Max=Ba.Max; start=newZj_Node[Max]; end=newZj_Node[Max+1]; for(inti=0;i<Max;i++) { start[i]=newZj_Node(Ba.base_info[i]); end[i]=newZj_Node(); } end[Max]=newZj_Node(); } 3.1.7業務實現---直接插入排序直接插入排序方法實現：publicvoidSorting(){//直接插入排序inti,j;//定義局部變量用于循環end[0]=start[0];//當插入第一個元素時，認為已經排好序了end[1]=start[0];for(i=1;i<Max;i++)//從原始數據第2個元素起，逐個從中取出元素

{end[0]=start[i];//將取出的元素放入，放入排序數組的第一個元素

j=i;while(end[0].Key<end[j].Key)//從排好序的最后一個元素向前，逐個與待插入的元素進行比較，如果元素比插入元素大

{end[j+1]=end[j]; j--; }end[j+1]=end[0];//將插入元素賦值到對應的位置

}}

算法評價時間復雜度若待排序記錄按關鍵字從小到大排列(正序)關鍵字比較次數：記錄移動次數：0次若待排序記錄按關鍵字從大到小排列(逆序)關鍵字比較次數：記錄移動次數：若待排序記錄是隨機的，取平均值關鍵字比較次數：記錄移動次數：T(n)=O(n2)空間復雜度：S(n)=O(1)3.1.8業務實現---直接插入排序3.2.1業務實現---折半插入排序二分插入排序是在直接插入排序基礎之上改進的一種排序算法。由于插入排序的操作是在一個有序序列中進行比較和插入的，而比較操作實際上就是在有序序列中作查找操作，這個“查找”操作可以用“二分查找”的方法來實現。按照這種思想，對直接插入排序改進后的排序方法稱為二分插入排序，又稱為折半插入排序。與直接插入排序相比，二分插入排序僅僅減少了記錄關鍵字的比較次數，而記錄的移動次數沒有改變。3.2.2業務實現---折半插入排序具體實現的步驟如下：我們用一個一維數組來裝載排序好的結果。數組下標為0的元素記錄每次要進行插入排序的元素，下標為1、2…N記錄已由小到大排好的元素。當向一個數組插入第一個元素時，放置在下標為0和1的位置，這時認為第一個元素已經排好序。在向數組插入第2個元素時，首先放置在下標為0的位置，讓它與第1個元素比較，如果比它大，則將元素值放入第2個位置，否則將元素1先移動到第2個位置，在將下標為0的元素放置在第1個位置。在向數組插入第i+1個元素時，前1到i個元素已經排好序，將插入的值放置在下標為0的位置R【0】，從第1個元素到第i個元素，采用二分查找第一個大于R【0】的位置k，那么先將第k到i個元素依次向后移動1為，再將R【0】的值放置在第k個元素位置。重復上面的操作，直到所有的數插入完畢。3.2.3業務實現---折半插入排序3.2.4業務實現---折半插入排序構建折半插入排序結點類：publicclassZb_Node{//用于排序的元素結點

publicintKey;//查找的關鍵字

publicStudent_infoData;//數據元素(學生信息）

publicZb_Node() { } publicZb_Node(Student_infoelem) { Key=elem.st_yw; Data=elem; }}

3.2.5業務實現---折半插入排序構建折半插入排序業務類：publicclassZb_Sort{publicintMax;//定義常數，記錄數據容量大小publicZb_Node[]start;//記錄原始的數據publicZb_Node[]end;//記錄排序后的新數據 publicStudentMangerBa=newStudentManger();//創建數據控制層對象publicinttimes_all=0;publicZb_Sort() {Max=Ba.Max; start=newZb_Node[Max]; end=newZb_Node[Max+1]; for(inti=0;i<Max;i++) { start[i]=newZb_Node(Ba.base_info[i]); end[i]=newZb_Node(); } end[Max]=newZb_Node();}publicvoidSorting(){…}//對學生信息按語文成績進行排序}

3.2.6業務實現---折半插入排序折半排序方法實現：publicvoidSorting(){//折半插入排序

inti,j;//定義局部變量用于循環

end[0]=start[0];//當插入第一個元素時，認為已經排好序了

end[1]=start[0];for(i=1;i<Max;i++)//從原始數據第2個元素起，逐個從中取出元素{ intleft=1,right=i; end[0]=start[i]; while(left<=right)//在已排好序的元素中采用二分查找來定位要插入的位置

{ intmiddle=(left+right)/2; if(end[0].Key<end[middle].Key) right=middle-1; else left=middle+1; times_all++; } for(j=i;j>=left;j--)//進行元素的移動

end[j+1]=end[j]; end[left]=end[0];//將插入元素賦值到對應的位置

}}

3.3.1業務實現---冒泡排序算法分析：冒泡排序也稱為起泡排序、氣泡排序等，是一種簡單的、容易理解的排序方法。冒泡排序是通過相鄰記錄之間的比較和交換使關鍵字值較小的記錄逐漸從底部移向頂部，即從下標較大的單元向下標較小的單元移動，就像氣泡從水中不斷往上冒。當然，隨著關鍵字較小的記錄的逐漸上移，關鍵字值較大的記錄也逐漸下移。3.3.2業務實現---冒泡排序冒泡排序步驟：先將初始記錄序列的第n個記錄的關鍵字和第n-1個記錄的關鍵字進行比較，若發現次序相反（即逆序，R[n-1].key>R[n].key），則交換兩記錄；然后比較第n-1個記錄和第n-2個記錄，若為逆序，又交換兩個記錄；如此下去，直到第2個記錄和第1個記錄的關鍵字進行比較為止，這樣就完成了第一趟冒泡排序。經過第一趟冒泡排序后，關鍵字最小的記錄被放置到R[0]的位置上.然后再進行第二趟冒泡排序，對剩下的n-1個記錄再進行類似的操作，其結果是關鍵字較小的記錄被放置到R[1]位置上.重復進行n-1趟后，整個冒泡排序結束。3.3.3業務實現---冒泡排序3.3.4業務實現---冒泡排序構建冒泡排序結點類：publicclassMp_Node{//用于排序的元素結點

publicintKey;//查找的關鍵字

publicStudent_infoData;//數據元素(學生信息）

publicMp_Node() { } publicMp_Node(Student_infoelem) { Key=elem.st_sx; Data=elem; }}

3.3.5業務實現---冒泡排序構建冒泡排序業務類：publicclassMp_Sort{ publicintMax;//定義常數，記錄數據容量大小

publicMp_Node[]start;//記錄原始的數據

publicMp_Node[]end;//記錄排序后的新數據

publicStudentMangerBa=newStudentManger();//創建數據控制層對象

publicinttimes_all=0; publicMp_Sort() { Max=Ba.Max; start=newMp_Node[Max]; end=newMp_Node[Max+1]; for(inti=0;i<Max;i++) { start[i]=newMp_Node(Ba.base_info[i]); end[i]=newMp_Node(); } } publicvoidSorting(){…}//對學生信息按語文成績進行排序}

3.3.6業務實現---冒泡排序冒泡排序方法實現：publicvoidSorting() {//冒泡排序 inti,j;//用于循環的局部變量 booleanflag;//用以標志是否排好序 for(i=0;i<Max;i++)//從第一個到最后一個元素進行循環 { flag=true; for(j=Max-2;j>=i;j--)//從最后一個元素到當前元素進行循環獲取元素if(start[j+1].Key<start[j].Key)//如果前面一個元素大于后一個元素，交換位置 {end[0]=start[j+1]; start[j+1]=start[j]; start[j]=end[0]; flag=false; times_all++; } if(flag)//如果排好序，退出循環 break; } }算法評價時間復雜度最好情況（正序）比較次數：n-1移動次數：0最壞情況（逆序）比較次數：移動次數：空間復雜度：S(n)=O(1)T(n)=O(n2)3.4.1業務實現---快速排序算法分析：快速排序（QuickSorting）又稱為劃分交換排序，它是迄今為止所有內排序算法中速度最快的一種。快速排序是對冒泡排序的一種改進。在冒泡排序中，記錄的比較和交換是在相鄰的單元中進行的，記錄每次交換只能上移或下移一個單元，因而總的比較和移動次數較多。而在快速排序中，記錄的比較和交換是從兩端向中間進行的，關鍵字較小的記錄一次就能從后面單元交換到前面去，而關鍵字較大的記錄一次就能從前面的單元交換到后面的單元，記錄每次移動的記錄較遠，因此可以減少記錄總的比較和移動次數。3.4.2業務實現---快速排序快速排序步驟：快速排序的基本做法是：任取待排序的n個記錄中的某個記錄作為基準（一般選取第一個記錄），通過一趟排序，將待排序記錄分成左右兩個子序列，左子序列記錄的關鍵字均小于或等于該基準記錄的關鍵字，右子序列記錄的關鍵字均大于或等于該基準記錄的關鍵字，從而得到該記錄最終排序的位置，然后該記錄不再參加排序，此一趟排序稱為第一趟快速排序。然后對所分的左右子序列分別重復上述方法，直到所有的記錄都處在它們的最終位置，此時排序完成。在快速排序中，有時把待排序序列按照基準記錄的關鍵字分為左右兩個子序列的過程稱為一次劃分。快速排序的過程為：設待排序序列為R[s]到R[t]，其中s為序列的下界，t為序列的上界（），R[s]為該序列的基準記錄，為了實現一次劃分，可設置兩個指針i和j，它們的初值分別為s和t。在劃分的過程中，首先讓j從其初值開始，依次向前掃描，并將掃描到的每一個記錄R[j]的關鍵字同R[s]（即基準記錄）的關鍵字進行比較，直到R[j].key<R[s].key時，交換R[j]和R[s]的順序，使得關鍵字比基準記錄關鍵字小的記錄交換到左邊的子序列中；然后讓i從i+1開始，依次向后掃描，并將掃描到的每一個記錄R[i]的關鍵字同R[j]的關鍵字（此時R[j]作為基準記錄）進行比較，直到R[i].key>R[j].key時交換R[i]和R[j]的順序，使關鍵字大的記錄交換到右邊的子序列中；再接著讓j從j-1開始，依次向前掃描。重復上述過程，如此交替改變掃描方向，從兩端各自向中間位置靠攏，直到i等于j。經過此次劃分后得到的左右兩個子序列分別為R[s]……R[i-1]和R[i+1]……R[t]，依此類推。3.4.3業務實現---快速排序3.4.4業務實現---快速排序構建快速排序結點類：publicclassQk_Node{//用于排序的元素結點

publicintKey;//查找的關鍵字

publicStudent_infoData;//數據元素(學生信息）

publicQk_Node() { } publicQk_Node(Student_infoelem) { Key=elem.st_yw; Data=elem; }}

3.4.5業務實現---快速排序構建快速排序業務類：publicclassQk_Sort{ publicintMax;//定義常數，記錄數據容量大小

publicQk_Node[]start;//記錄原始的數據

publicStudentMangerBa=newStudentManger();//創建數據控制層對象

publicinttimes_all=0; publicQk_Sort() { Max=Ba.Max; start=newQk_Node[Max]; for(inti=0;i<Max;i++) { start[i]=newQk_Node(Ba.base_info[i]); } } public voidSorting(intlow,inthigh){…}//對學生信息按語文成績進行排序}

3.4.6業務實現---快速排序快速排序方法實現：public voidSorting(intlow,inthigh){//快速排序low排序下限，high排序上限inti=low,j=high;Qk_Nodetemp=start[low];//快速排序的支點while(i<j){while((start[j].Key>=temp.Key)&&(i<j))//從表的末端向前收索與支點比較

{j--; times_all++; }if(j>i)//末端的元素比支點小，發生交換

{start[i]=start[j]; i++; }while((start[i].Key<=temp.Key)&&(i<j))//從表的前端向后收索與支點進行比較

{ times_all++; i++; }if(j>i)//前端的元素比支點大，發生交換

{ start[j]=start[i]; j--; } } start[i]=temp;//將支點記錄移到新位置

if(low<(i-1))Sorting(low,i-1);//遞歸調用左半區排序

if(high>(i+1))Sorting(i+1,high);//遞歸調用右半區排序}

例初始關鍵字：4938659776132750ijxji

完成一趟排序：(273813)49(76976550)分別進行快速排序：(13)27(38)49(5065)76(97)快速排序結束：13273849

506576974927ijijij4965ji1349ij4997ij算法評價時間復雜度最好情況（每次總是選到中間值作樞軸）T(n)=O(nlog2n)最壞情況（每次總是選到最小或最大元素作樞軸）T(n)=O(n2)空間復雜度：需棧空間以實現遞歸最壞情況：S(n)=O(n)一般情況：S(n)=O(log2n)T(n)=O(n2)3.5.1業務實現---選擇排序直接選擇排序是一種簡單的排序方法。它每次從待排序的記錄序列中選取關鍵字最小的記錄，把它同當前記錄序列中的第一個記錄相交換位置。具體的作法是：開始時待排序序列為R[0]……R[n-1]，經過選擇和交換后，R[0]中存放最小關鍵字的記錄；第二次待排序記錄序列為R[1]……R[n-1]，經過選擇和交換后，R[1]為僅次于R[0]的具有次小關鍵字的記錄；如此類推，經過n-1次選擇和交換之后，R[0]……R[n-1]成為有序序列，即可實現排序。3.5.2業務實現---選擇排序3.5.3業務實現---選擇排序構建選擇排序結點類：publicclassSe_Node{//用于排序的元素結點

publicintKey;//查找的關鍵字

publicStudent_infoData;//數據元素(學生信息）

publicSe_Node() { } publicSe_Node(Student_infoelem) { Key=elem.st_yw; Data=elem; }}

3.5.4業務實現---選擇排序構建選擇排序業務類：publicclassSelect_Sort{ publicintMax;//定義常數，記錄數據容量大小 publicSe_Node[]start;//記錄原始的數據 publicStudentMangerBa=newStudentManger();//創建數據控制層對象 publicinttimes_all=0; publicSelect_Sort(){ Max=Ba.Max; start=newSe_Node[Max]; for(inti=0;i<Max;i++) { start[i]=newSe_Node(Ba.base_info[i]); } } publicvoidSorting(){…}//對學生信息按語文成績進行排序}3.5.5業務實現---選擇排序選擇排序方法實現