面試時數(shù)據(jù)結構應該是面試官們一定會問到的知識塊，最常見的就是對于排序、查找等算法的考察。這里先列出一些常見易考，并且比較重要的排序算法。這里都以排成增序為例，如有錯誤、不好之處敬請指出。
1、 直接插入排序 假設我們有一個序列｛a0,a1,a2,a3……an｝，將a0看成是一個有序序列，a1～an看成是無序序列，插入排序就是將a1和a0比較，如果比a0小則將其插到a0前面，如果比a0大，則不做事情，這樣一次之后前兩個位置就是有序的，第三個到第n個仍是無序的。然后，再a2和前兩個做比較，將其插入到合適的位置，這樣之后，前三個元素都是有序的，第四個到第n個是無序的。如此往復，直到序列有序即可。
void InsertSort(int a[],int len){ int j,temp; for (int i=1; i<len; i++) { if (a[i]<a[i-1]) { temp=a[i]; for (j=i-1; a[j]>temp&&j>=0; j--) { a[j+1]=a[j]; } a[j+1]=temp; } }}123456789101112131412345678910111213142、 希爾排序 假設我們有一個序列｛a0,a1,a2,a3……an｝，希爾排序的基本思想是會將序列分割成若干個子序列，然后再對各個子序列進行插入排序。因此希爾排序會有一個增量d，其初始值一般為序列長度的一半，即d=n/2，這樣將一個序列分為兩個子序列，再分別對兩個子序列做插入排序。之后d取值為n/4，再對子序列做插入排序，如此往復，直到d=1，此時序列基本有序，再對其進行一次插入排序即可。
void ShellSort(int a[],int len){ int d; for (d=len/2; d>0; d/=2) {//步長 for (int i=0; i<d; i++) {//直接插入排序 for (int j=i+d; j<len; j+=d) { if (a[j]<a[j-d]) { int temp=a[j]; int k=j-d; while (k>=0&&a[k]>temp) { a[k+d]=a[k]; k-=d; } a[k+d]=temp; } } } }}1234567891011121314151617181912345678910111213141516171819上面的代碼是最能體現(xiàn)希爾排序思想的，下面給出兩種稍加改進的代碼。
void shellsort1(int a[], int n){ int j, d; for (d = n / 2; d > 0; d /= 2) for (j = d; j < n; j++)//從數(shù)組第d個元素開始 if (a[j] < a[j - d])//每個元素與自己組內(nèi)的數(shù)據(jù)進行直接插入排序 { int temp = a[j]; int k = j - d; while (k >= 0 && a[k] > temp) { a[k + d] = a[k]; k -= d; } a[k + d] = temp; }}void shellsort2(int a[], int n){ int i, j, d; for (d = n / 2; d > 0; d /= 2) for (i = d; i < n; i++) for (j = i - d; j >= 0 && a[j] > a[j + d]; j -= d) swap(&a[j], &a[j + d]);}12345678910111213141516171819202122232425262728123456789101112131415161718192021222324252627283、 冒泡排序 兩兩比較相鄰記錄的關鍵字，如果反序則交換，直到?jīng)]有反序的記錄為止。
void swap(int *a,int *b){ int temp; temp=*a; *a=*b; *b=temp;}void BubbleSort(int a[],int len){ int i,j; for (i=0;i<len;i++) { for (j=i+1;j<len;j++) { if (a[i]>a[j]) swap(&a[i],&a[j]); } }}1234567891011121314151617181912345678910111213141516171819下面也給出冒泡排序的另外兩種實現(xiàn)。
void BubbleSort1(int a[],int len){ for (int i=0;i<len;i++) { for(int j=len-2;j>=i;j--) { if (a[j]>a[j+1]) //前者與后者比較，這里與前面算法的區(qū)別 swap(&a[j],&a[j+1]); } }}void BubbleSort2(int a[],int len){ int flag=1; for (int i=0;i<len &&flag;i++) { flag=0; for (int j=len-2;j>=i;j--) { if (a[j]>a[j+1]) { swap(&a[j],&a[j+1]); flag=1; } } }}1234567891011121314151617181920212223242526271234567891011121314151617181920212223242526274、 快速排序 假設我們有一個序列｛a0,a1,a2,a3……an｝，在快速排序算法里，我們將第一個元素用作樞軸紀錄關鍵字key，并有一個low指針指向第一個元素，有一個high指針指向最后一個元素，當low < high時，將a[high]和key做比較，如果a[high]>=key，則high–，否則交換low和high位置的元素；當low < high時，將a[low]和key做比較，如果a[low]<=key，則low++，否則交換low和high位置的元素。直到low>=high，一次排序結束，此時key左邊的值都比它小，key右邊的值都比它大。
int Partiton(int a[],int low,int high){ int key; key=a[low];//樞軸的選取可以選取中間值 while (low<high) { while (low<high &&a[high]>=key) high--; swap(&a[high],&a[low]); while (low<high && a[low]<=key) low++; swap(&a[high],&a[low]); } return low;}void Qsort(int a[],int low,int high){ int pivot; if (low<high) { pivot=Partiton1(a,low,high); Qsort(a,low,pivot-1); Qsort(a,pivot+1,high); }}12345678910111213141516171819202122232425261234567891011121314151617181920212223242526下面的代碼是對快排的一種優(yōu)化。
int Partiton1(int a[],int low,int high)/*y優(yōu)化不需要的交換*/{ int temp,key; key=a[low]; temp=key; while (low<high) { while (low<high &&a[high]>=key) high--; a[low]=a[high]; while (low<high && a[low]<=key) low++; a[high]=a[low]; } a[low]=temp; return low;}123456789101112131415161712345678910111213141516175、 簡單選擇排序 假設我們有一個序列｛a0,a1,a2,a3……an｝，簡單選擇排序就是將這n個元素遍歷一遍選出最小的，再和第一個交換；再從剩下2～n個元素中選出最小的和第二個交換，重復以上步驟即可。
void SelectSort(int a[],int len){ int min; for (int i=0;i<len;i++) { min=i; for (int j=i+1;j<len;j++) { if (a[min]>a[j]) min=j; } if (i!=min) swap(&a[min],&a[i]); }}1234567891011121314151234567891011121314156、 堆排序 輸出堆頂?shù)淖钚?#20540;之后，使剩下n-1個元素的序列重又建成一個堆，則得到n個元素中的次小值。如此反復執(zhí)行，便能得到一個有序序列。
void HeapAdjust(int a[],int s,int m){ int temp,j=0; temp=a[s]; for (j=2*s+1;j<m;j=j*2+1) { if (j<m && a[j]<a[j+1]) ++j; if (j<m && temp>=a[j]) break; a[s]=a[j]; s=j; } a[s]=temp;}void HeapSort(int a[],int len){ int i; for (i=(len)/2-1;i>=0;i--) HeapAdjust(a,i,len); for (i=len-1;i>=1;i--) { swap(&a[0],&a[i]); HeapAdjust(a,0,i-1); }}12345678910111213141516171819202122232425261234567891011121314151617181920212223242526下面給出上述各種算法的時間復雜度、空間復雜度、穩(wěn)定性等。 
新聞熱點
疑難解答
