第4章-幾種常見的排序算法

講師：朱興林第4章幾種常見的排序算法本章目標本章概述幾種常見排序算法。本章目標熟悉常見的查找算法和排序算法重點能夠里用函數(shù)庫提供的API進行查找或排序操作難點快速排序算法本章結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)與算法初步常見的排序算法常見的排序算法冒泡排序快速排序直接插入排序希爾排序選擇排序堆排序歸并排序冒泡排序冒泡排序方法是最簡單的排序方法。這種方法的基本思想是，將待排序的元素看作是豎著排列的“氣泡”，較小的元素比較輕，從而要往上浮。在冒泡排序算法中我們要對這個“氣泡”序列處理若干遍。所謂一遍處理，就是自底向上檢查一遍這個序列，并時刻注意兩個相鄰的元素的順序是否正確。如果發(fā)現(xiàn)兩個相鄰元素的順序不對，即“輕”的元素在下面，就交換它們的位置。顯然，處理一遍之后，“最輕”的元素就浮到了最高位置；處理二遍之后“次輕”的元素就浮到了次高位置。在作第二遍處理時，由于最高位置上的元素已是“最輕”元素，所以不必檢查。一般地，第i遍處理時，不必檢查第i高位置以上的元素，因為經(jīng)過前面i-1遍的處理，它們已正確地排好序。冒泡排序是穩(wěn)定的。算法時間復(fù)雜度是O(n^2)。算法描述210825492516214925251608214925251608214925251608214925251608214925251608初始關(guān)鍵字第一趟排序第四趟排序第二趟排序第三趟排序第五趟排序算法實例如下：輸入n個數(shù)給a[1]到a[n]forj=1ton-1fori=1ton-ja[i]>a[i+1]真假a[i]a[i+1]輸出a[1]到a[n]算法實現(xiàn)#include<stdio.h>

voidbubbling_sort(int*a,intn);

intmain(){inta[5]={5,4,3,2,1};bubbling_sort(a,5);

inti;for(i=0;i<5;i++){ printf("%d\n",a[i]);}}

voidbubbling_sort(int*a,intn){ inti,j,temp; for(i=0;i<n-1;i++) { for(j=0;j<n-1-i;j++) { if(a[j]>a[j+1]) { temp=a[j]; a[j]=a[j+1]; a[j+1]=temp; }}}}快速排序算法描述快速排序是對冒泡排序的一種本質(zhì)改進。它的基本思想是通過一趟掃描后，使得排序序列的長度能大幅度地減少。在冒泡排序中，一次掃描只能確保最大數(shù)值的數(shù)移到正確位置，而待排序序列的長度可能只減少1?？焖倥判蛲ㄟ^一趟掃描，就能確保某個數(shù)（以它為基準點吧）的左邊各數(shù)都比它小，右邊各數(shù)都比它大。然后又用同樣的方法處理它左右兩邊的數(shù)，直到基準點的左右只有一個元素為止。2108254925*16始關(guān)鍵字08254925*162108254925*1608254925*1608254925*1608254925*1621pivotkey一次交換二次交換三次交換high-1完成一趟排序lowhighlowlowlowlowlowhighhighhighhighhigh算法實例254925*162108254925*162108完成一趟排序分別進行快速排序有序序列08254925*1621算法實例#include<stdio.h>

voidquick_sort(int*a,intstart,intend);

intmain(){ inta[5]={4,2,6,8,1}; quick_sort(a,0,4); inti; for(i=0;i<5;i++) { printf("%d\n",a[i]); }

return0;}voidquick_sort(int*a,intstart,intend){ inti=start,j=end; intkey=a[start];//在起始位置挖坑，等待被填 while(start<end) {while(start<end) { if(a[end]<=key) { a[start]=a[end];//把a[end]挖出來，填到a[start]坑里 start++;

break;}end--;}while(start<end){if(a[start]>key){a[end]=a[start]; end--; break;} start++;}}

intmid=start; a[mid]=key;

if(i<mid-1) quick_sort(a,i,mid-1); if(j>mid+1) quick_sort(a,mid+1,j); }算法實現(xiàn)算法分析：快速排序是一個遞歸過程;利用序列第一個記錄作為基準，將整個序列劃分為左右兩個子序列。只要是關(guān)鍵字小于基準記錄關(guān)鍵字的記錄都移到序列左側(cè)；快速排序的趟數(shù)取決于遞歸樹的高度。如果每次劃分對一個記錄定位后,該記錄的左側(cè)子序列與右側(cè)子序列的長度相同,則下一步將是對兩個長度減半的子序列進行排序,這是最理想的情況

直接插入排序算法描述插入排序的基本思想是，經(jīng)過i-1遍處理后,L[1..i-1]己排好序。第i遍處理僅將L[i]插入L[1..i-1]的適當位置，使得L[1..i]又是排好序的序列。要達到這個目的，我們可以用順序比較的方法。首先比較L[i]和L[i-1]，如果L[i-1]≤L[i]，則L[1..i]已排好序，第i遍處理就結(jié)束了；否則交換L[i]與L[i-1]的位置，繼續(xù)比較L[i-1]和L[i-2]，直到找到某一個位置j(1≤j≤i-1)，使得L[j]≤L[j+1]時為止。#include<stdio.h>voiddirectinsert_sort(int*a,intn);

intmain(){ inta[5]={5,7,3,1,2}; directinsert_sort(a,5); inti; for(i=0;i<5;i++) { printf("%d\n",a[i]); }}voiddirectinsert_sort(int*a,intn){ inti,j,temp;; for(i=1;i<n;i++) { temp=a[i]; for(j=i-1;j>=0&&temp<a[j];j--) a[j+1]=a[j];//往后挪動

a[j+1]=temp; }}

算法實現(xiàn)選擇排序在要排序的一組數(shù)中，選出最小的一個數(shù)與第一個位置的數(shù)交換；然后在剩下的數(shù)當中再找最小的與第二個位置的數(shù)交換，如此循環(huán)

到倒數(shù)第二個數(shù)和最后一個數(shù)比較為止。算法描述算法實例#include<stdio.h>voidselect_sort(int*a,intn);

intmain(){ intarr[5]={5,7,3,1,2}; select_sort(arr,5);

inti; for(i=0;i<5;i++) { printf("%d\n",arr[i]); }}

voidselect_sort(int*a,intn){ inti,j,min,temp; for(i=0;i<n-1;i++)//循環(huán)n-1趟 { min=i; for(j=i+1;j<n;j++)//從i+1開始比較 { if(a[min]>a[j]) min=j; }

if(min!=i) { temp=a[min]; a[min]=a[i]; a[i]=temp; } }}希爾排序希爾排序是插入排序的增強版。D.L.shell于1959年在以他名字命名的排序算法中實現(xiàn)了這一思想。算法先將要排序的一組數(shù)按某個增量d分成若干組，每組中記錄的下標相差d.對每組中全部元素進行排序，然后再用一個較小的增量對它進行，在每組中再進行排序。當增量減到1時，整個要排序的數(shù)被分成一組，排序完成。

算法實例運用實例已知待排序的一組記錄的初始排列為：21,25,49,25*,16,080123452108254925*16t12108254925*162108254925*16t22108254925*162108254925*16t30123452108254925*160123452108254925*16算法實例#include<stdio.h>

voidshell_sort(int*a,intn);

intmain(){ inta[5]={4,2,5,7,1}; shell_sort(a,5); inti; for(i=0;i<5;i++) { printf("%d\n",a[i]);

}}

voidshell_sort(int*a,intn){inti,j,d,temp;for(d=n/2;d>=1;d/=2)//增量改變一般是數(shù)組元素個數(shù)累除2{for(i=d;i<n;i++)//注意這里的i++不是i=i+d;temp=a[i];for(j=i-d;j>=0&&temp<a[j];j-=d){a[j+d]=a[j];}a[j+d]=temp;}}}算法分析開始時gap的值較大,子序列中的記錄較少,排序速度較快隨著排序進展,gap值逐漸變小,子序列中記錄個數(shù)逐漸變多,由于前面大多數(shù)記錄已基本有序,所以排序速度仍然很快Gap的取法有多種。shell提出取gap=n/2，gap=gap/2，直到gap=1。下面是幾種常見的排序算法的封裝封裝的冒泡法：voidmybubbling_sort(int*a,intn,intsize,int(*cmp)(void*,void*)){inti,j;void*temp=malloc(size);if(temp==NULL){ printf("cannotmalloc\n"); return;}for(i=0;i<n-1;i++){ for(j=0;j<n-1-i;j++) { if(cmp((char*)a+j*size,(char*)a+(j+1)*size)>0) { memcpy(temp,(char*)a+j*size,size); memcpy((char*)a+j*size,(char*)a+(j+1)*size,size); memcpy((char*)a+(j+1)*size,temp,size); } } } free(temp);}下面是幾種常見的排序算法的封裝封裝的選擇排序法voidmyselect_sort(void*a,intnmeb,intsize,int(*cmp)(void*,void*)){ inti,j,min; void*temp=malloc(size); if(temp==NULL) { printf("cannotmalloc\n"); return;} for(i=0;i<nmeb-1;i++) { min=i; for(j=