數(shù)據(jù)結(jié)構(gòu)再往后就是比較零散的各種操作，查找與排序是其中最常出現(xiàn)的，今天來總結(jié)一下常用的查找與排序所用的方法

查找

順序查找

• 最簡單的查找方式，遍歷，然后比較

bool search1(int *a,int n,int k){for (int i=1;i<n;i++){//遍歷if (a[i]==k) {//比較return true;break;}}return false;
}

遍歷時(shí)對數(shù)據(jù)i是否越界的判斷可以使用哨兵優(yōu)化掉

int search1(int *a,int n,int k){a[0]=key;//哨兵while(a[n]!=key){n--;}return n;//找到返回位置，找不到返回0
}

二分查找

• 又稱為折半查找，是對順序表進(jìn)行的一種查找方式，每次查找過后，如果目標(biāo)值小于中間值，則肯定小于中間向右的所有值，只需要在左邊數(shù)據(jù)里查找；再對中間值進(jìn)行比較，如此反復(fù)

//二分查找
int binarysearch(int *a,int n,int k){int l,r,m;l=1;//左指針指向一查找的數(shù)組范圍的左邊r=n;//右指針while(l<=r){m=(l+r)/2;if (a[m]==k) return m;//如果相等，返回找到的位置else if(a[m]>k) r=m-1;//在左邊進(jìn)行查找else l=m+1;//在右邊查找}return 0;
}

插值查找

• 與二分查找類似的查找方式，不同的是每次更新查找域并不是對半分，而是根據(jù)目標(biāo)值與最小值的估計(jì)距離，（如果差值大查找域就更往右，反之往左），m=l+(r-l)*(k-a[l])/(a[r]-a[l])

//插值查找
int intersearch(int* a,int n,int k){int l,r m;l=1;r=n;while(l<=r){m=l+(r-l)*(k-a[l])/(a[r]-a[l]);if (a[m]==k) return m;//如果相等，返回找到的位置else if(a[m]>k) r=m-1;else l=m+1;}return 0;
}

斐波那契查找

• 基于斐波那契數(shù)列獨(dú)有的黃金分割性質(zhì)進(jìn)行的查找，原理與二分查找類似，不同點(diǎn)依舊是對二次查找域的分割不是基于一半，而是基于黃金分割

//斐波那契查找
//f[k]為斐波那契數(shù)列
int fibosearch(int* a,int n,int k){int l,r,m;l=1;r=n;while(n>f[k]-1){k++;}for (int i=n;i<f[k]-1;i++){//補(bǔ)全a數(shù)組，將最大的數(shù)補(bǔ)到a數(shù)組后面a[i]=a[n];}while(l<=r){m=l+f[k-1]-1;if (a[m]==k) {if (m>n) return n;//m大于n，說明是補(bǔ)全的數(shù)字中的值與目標(biāo)值相等，返回最大值else return m;}else if(a[m]>k){//此時(shí)去左邊查找，新數(shù)列的總長度為f[k-1]-1個(gè)r=m-1;k--;}else {//此時(shí)去右邊查找，新數(shù)列的總長度為f[k-2]-1個(gè)l=m+1;k-=2;}}return 0;
}

二叉樹的查找操作

• 在BST中查找對應(yīng)值。簡單的樹狀遍歷查找

bool search(BinaryTree* T,int key) {if (!T) {return false;  //樹為空} else if (key==T->data) {return true;//查找成功} else if (key<T->data) {return search(T->leftchild,key); //繼續(xù)在左子樹中查找} else {return search(T->rightchild,key); //向在右子樹中查找}
}

?排序

插入排序

• 插入排序是將數(shù)組分為排好序與未排序的部分，在未排序部分取出元素，比較插入到已排序的部分的合適位置，一般看做第一個(gè)元素已排序完畢，從第二個(gè)元素開始，對已排序部分從前往后掃描，已排序的元素中大于此元素的向后移動，如此反復(fù)

void inserSort(int*a,int n) {for (int i=1;i<n;i++) {//從第二個(gè)元素開始比較，找合適的位置插入int k=a[i];int j=i-1;// 將a[i]插入到已排序序列數(shù)組中while (j>=0&&a[j]>k) {a[j+1]=a[j];j--;}a[j+1]=k;}
}

冒泡排序

• 這個(gè)方法幾乎是新手村必打的小怪。重復(fù)遍歷數(shù)組，一次比較兩個(gè)元素，如果順序不對就交換它們

void bubbleSort(int *a, int n) {for (int i=0; i<n-1; i++) {for (int j=0; j<n-i-1; j++) {if (a[j]>a[j+1]) {//順序不對則交換int temp=a[j];a[j]=a[j+1];a[j+1]=temp;}}}
}

希爾排序

• 希爾排序是對插入排序的一種改進(jìn)，通過比較不相鄰的元素進(jìn)行交換來提高插入排序的效率。基本思想為將數(shù)組分為若干子序列，對每個(gè)子序列進(jìn)行插入排序，再對這個(gè)數(shù)列進(jìn)行插入排序

void shellSort(int *a, int n) {for (int gap=n/2;gap>0;gap/=2) {//對不同步長進(jìn)行排序（即不同長度子序列）for (int i=gap; i<n; i++) {int temp=a[i];//記錄當(dāng)前元素int j;for (j=i;j>=gap&&a[j-gap]>temp;j-=gap) {a[j]=a[j-gap];//往后移動元素}a[j]=temp;//插入到正確位置}}
}

快速排序

• 快排采用了分治法的思想，選擇一個(gè)基準(zhǔn)元素，將待排數(shù)組分為兩個(gè)部分，左邊都小于它，右邊都大于它，然后遞歸地進(jìn)行排序
• 具體方法為：選擇基準(zhǔn)元素（一般為第一個(gè)元素），設(shè)定左右指針指向數(shù)組始末；
• 移動左指針，直到找到小于基準(zhǔn)元素的元素，同時(shí)移動右指針，找到大于基準(zhǔn)元素的元素，交換這兩個(gè)元素的位置；重復(fù)步驟，直到左指針大于右指針
• 將基準(zhǔn)元素與右指針的元素互換，此時(shí)基準(zhǔn)元素左邊的都小于等于它，右邊的大于等于它；
• 重復(fù)以上步驟

int partition(int*nums,int low,int high) {int pivot=nums[low];//選擇第一個(gè)元素為基準(zhǔn)元素while (low<high) {// 從右向左找到小于基準(zhǔn)元素的值while (low<high&&nums[high]>=pivot)high--;nums[low]=nums[high];//將找到的小于基準(zhǔn)元素的值放到左邊// 從左向右找到大于基準(zhǔn)元素的值while (low<high&&nums[low]<=pivot)low++;nums[high]=nums[low];//將找到的大于基準(zhǔn)元素的值放到右邊}nums[low]=pivot;return low;
}
void qsort(int*nums,int low,int high) {if (low<high) {int pos=partition(nums,low,high);//獲取基準(zhǔn)元素位置qsort(nums,low,pos-1);//對左半進(jìn)行排序qsort(nums,pos+1,high);//對右半進(jìn)行排序}
}

堆排序

• 堆排序是一種基于堆形數(shù)據(jù)結(jié)構(gòu)的排序，利用堆的性質(zhì)來實(shí)現(xiàn)。堆分為最大堆和最小堆，分別是父結(jié)點(diǎn)大于子節(jié)點(diǎn)、父結(jié)點(diǎn)小于子節(jié)點(diǎn)的二叉樹結(jié)構(gòu)
• 堆排序是先將待排數(shù)組構(gòu)成一個(gè)最大堆或最小堆，然后每次取出堆頂元素，對剩下的元素進(jìn)行調(diào)整，再繼續(xù)取出，直到所有元素被取出

（c++有堆形數(shù)據(jù)結(jié)構(gòu)的相關(guān)函數(shù)，使用其排序較為方便）

void print(const vector<int>& a) {//輸出排序好的元素for (int i=0;i<a.size();i++)cout<<a[i]<<" ";cout<<endl;
}
// 堆排序
void heapSort(vector<int>& a) {make_heap(a.begin(),a.end());//默認(rèn)構(gòu)建最大堆，最小堆需要自定義比較函數(shù)for (int i=a.size()-1;i>0;i--) { //依次取出堆頂元素，進(jìn)行排序pop_heap(a.begin(),a.begin()+i+1);//將當(dāng)前堆頂元素（最大值）與數(shù)組末尾元素交換swap(a[0],a[i]);push_heap(a.begin(),a.begin()+i);//調(diào)整剩余元素構(gòu)建最大堆}
}