第4章-幾種常見(jiàn)的排序算法

講師：朱興林第4章幾種常見(jiàn)的排序算法本章目標(biāo)本章概述幾種常見(jiàn)排序算法。本章目標(biāo)熟悉常見(jiàn)的查找算法和排序算法重點(diǎn)能夠里用函數(shù)庫(kù)提供的API進(jìn)行查找或排序操作難點(diǎn)快速排序算法本章結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)與算法初步常見(jiàn)的排序算法常見(jiàn)的排序算法冒泡排序快速排序直接插入排序希爾排序選擇排序堆排序歸并排序冒泡排序冒泡排序方法是最簡(jiǎn)單的排序方法。這種方法的基本思想是，將待排序的元素看作是豎著排列的“氣泡”，較小的元素比較輕，從而要往上浮。在冒泡排序算法中我們要對(duì)這個(gè)“氣泡”序列處理若干遍。所謂一遍處理，就是自底向上檢查一遍這個(gè)序列，并時(shí)刻注意兩個(gè)相鄰的元素的順序是否正確。如果發(fā)現(xiàn)兩個(gè)相鄰元素的順序不對(duì)，即“輕”的元素在下面，就交換它們的位置。顯然，處理一遍之后，“最輕”的元素就浮到了最高位置；處理二遍之后“次輕”的元素就浮到了次高位置。在作第二遍處理時(shí)，由于最高位置上的元素已是“最輕”元素，所以不必檢查。一般地，第i遍處理時(shí)，不必檢查第i高位置以上的元素，因?yàn)榻?jīng)過(guò)前面i-1遍的處理，它們已正確地排好序。冒泡排序是穩(wěn)定的。算法時(shí)間復(fù)雜度是O(n^2)。算法描述210825492516214925251608214925251608214925251608214925251608214925251608初始關(guān)鍵字第一趟排序第四趟排序第二趟排序第三趟排序第五趟排序算法實(shí)例如下：輸入n個(gè)數(shù)給a[1]到a[n]forj=1ton-1fori=1ton-ja[i]>a[i+1]真假a[i]a[i+1]輸出a[1]到a[n]算法實(shí)現(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; }}}}快速排序算法描述快速排序是對(duì)冒泡排序的一種本質(zhì)改進(jìn)。它的基本思想是通過(guò)一趟掃描后，使得排序序列的長(zhǎng)度能大幅度地減少。在冒泡排序中，一次掃描只能確保最大數(shù)值的數(shù)移到正確位置，而待排序序列的長(zhǎng)度可能只減少1?？焖倥判蛲ㄟ^(guò)一趟掃描，就能確保某個(gè)數(shù)（以它為基準(zhǔn)點(diǎn)吧）的左邊各數(shù)都比它小，右邊各數(shù)都比它大。然后又用同樣的方法處理它左右兩邊的數(shù)，直到基準(zhǔn)點(diǎn)的左右只有一個(gè)元素為止。2108254925*16始關(guān)鍵字08254925*162108254925*1608254925*1608254925*1608254925*1621pivotkey一次交換二次交換三次交換high-1完成一趟排序lowhighlowlowlowlowlowhighhighhighhighhigh算法實(shí)例254925*162108254925*162108完成一趟排序分別進(jìn)行快速排序有序序列08254925*1621算法實(shí)例#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(bǔ)[end]挖出來(lái)，填到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); }算法實(shí)現(xiàn)算法分析：快速排序是一個(gè)遞歸過(guò)程;利用序列第一個(gè)記錄作為基準(zhǔn)，將整個(gè)序列劃分為左右兩個(gè)子序列。只要是關(guān)鍵字小于基準(zhǔn)記錄關(guān)鍵字的記錄都移到序列左側(cè)；快速排序的趟數(shù)取決于遞歸樹(shù)的高度。如果每次劃分對(duì)一個(gè)記錄定位后,該記錄的左側(cè)子序列與右側(cè)子序列的長(zhǎng)度相同,則下一步將是對(duì)兩個(gè)長(zhǎng)度減半的子序列進(jìn)行排序,這是最理想的情況

直接插入排序算法描述插入排序的基本思想是，經(jīng)過(guò)i-1遍處理后,L[1..i-1]己排好序。第i遍處理僅將L[i]插入L[1..i-1]的適當(dāng)位置，使得L[1..i]又是排好序的序列。要達(dá)到這個(gè)目的，我們可以用順序比較的方法。首先比較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]，直到找到某一個(gè)位置j(1≤j≤i-1)，使得L[j]≤L[j+1]時(shí)為止。#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];//往后挪動(dòng)

a[j+1]=temp; }}

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

到倒數(shù)第二個(gè)數(shù)和最后一個(gè)數(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開(kāi)始比較 { if(a[min]>a[j]) min=j; }

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

算法實(shí)例運(yùn)用實(shí)例已知待排序的一組記錄的初始排列為：21,25,49,25*,16,080123452108254925*16t12108254925*162108254925*16t22108254925*162108254925*16t30123452108254925*160123452108254925*16算法實(shí)例#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ù)組元素個(gè)數(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;}}}算法分析開(kāi)始時(shí)gap的值較大,子序列中的記錄較少,排序速度較快隨著排序進(jìn)展,gap值逐漸變小,子序列中記錄個(gè)數(shù)逐漸變多,由于前面大多數(shù)記錄已基本有序,所以排序速度仍然很快Gap的取法有多種。shell提出取gap=n/2，gap=gap/2，直到gap=1。下面是幾種常見(jiàn)的排序算法的封裝封裝的冒泡法：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);}下面是幾種常見(jiàn)的排序算法的封裝封裝的選擇排序法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=