1：排序算法分為如下5類：
- 插入排序：普通插入排序竹观，shell排序等；
- 選擇排序：普通選擇排序潜索，堆排序臭增；
- 交換排序：冒泡法，快速排序竹习；
- 歸并排序：
- 基數(shù)排序誊抛。
待排數(shù)據(jù)為：9,6,2,3,10，有小到大排列整陌；下面來(lái)實(shí)現(xiàn)上面的各種排序算法
2：插入排序(希爾排序)
基本插入排序：每次將一個(gè)待排序的數(shù)據(jù)元素拗窃，插入到前面已經(jīng)排好序的數(shù)列中的適當(dāng)位置，使數(shù)列依然有序泌辫；直到待排序數(shù)據(jù)元素全部插入完為止随夸。
穩(wěn)定排序：指待排序序列中可能存在兩個(gè)或兩個(gè)以上關(guān)鍵字相等的記錄。排序前的序列中Ri領(lǐng)先于Rj（即i<j）震放。若在排序后的序列中Ri仍然領(lǐng)先于Rj逃魄，則稱所用的方法是穩(wěn)定的。比如序列：3,6,1a,2,1b,8,4,7澜搅，其中1a和1b的值都是1，為了區(qū)別邪锌，1a在1b的前面勉躺。如果排序之后，1a依然在1b的前面觅丰，那么就是穩(wěn)定排序饵溅，否則就是非穩(wěn)定排序。
//基本插入排序
//基本插入排序的時(shí)間復(fù)雜度為O(n^2)妇萄，是一種穩(wěn)定排序算法
void insert_sort(int a[], int n) {
int i, j, tmp;
for(int i=1; i<n; i++) {
tmp = a[i];
j = i - 1;
while(tmp < a[j]) {//當(dāng)tmp大于等于a[j]時(shí)不用交換
a[j+1] = a[j];
j--;
}
a[j+1] = tmp;
}
}
希爾排序：是一種經(jīng)過(guò)改進(jìn)的插入排序算法蜕企。
希爾排序基本思想：先將整個(gè)待排元素序列分割成若干個(gè)子序列（由相隔某個(gè)“增量”的元素組成的）分別進(jìn)行直接插入排序，然后依次縮減增量再進(jìn)行排序冠句，待整個(gè)序列中的元素基本有序（增量足夠星嵫凇）時(shí)，再對(duì)全體元素進(jìn)行一次直接插入排序懦底。因?yàn)橹苯硬迦肱判蛟谠鼗居行虻那闆r下（接近最好情況）唇牧，效率是很高的，因此希爾排序在時(shí)間效率上比前兩種方法有較大提高。具體做法：首先確定一組增量d0丐重，d1腔召，d2，d3扮惦，...,dt-1()其中n>d0>d1>...>dt-1=1)臀蛛，對(duì)于i =0,1,2,...,t-1,依次進(jìn)行下面的各趟處理：根據(jù)當(dāng)前增量di將n個(gè)元素分成di個(gè)組，每組中元素的下標(biāo)相隔為di;再對(duì)各組中元素進(jìn)行直接插入排序崖蜜。
//希爾排序的實(shí)現(xiàn)算法：
//希爾排序的復(fù)雜度為：O(n^1.25)浊仆，它不是穩(wěn)定排序。
void shellsort(int a[], int n) {
int i, j, gap, tmp;
gap = n/2;
while (gap > 0) {
for (i = gap + 1; i <= n; i++) {
j = i - gap;
while (j > 0) {
if (a[j] > a[j+gap]) {
tmp = a[j];
a[j] = a[j+gap];
a[j+gap] = a[j];
} else {
j = 0;
}
}
}
gap /= 2;
}
}
3：選擇排序(堆排序)
選擇排序：每一次都是從待排序的數(shù)據(jù)元素中選出最心芍怼（或最大）的一個(gè)元素氧卧，順序放在已排好序的數(shù)列的最后，直到全部待排序的數(shù)據(jù)元素排完氏堤。
//簡(jiǎn)單選擇排序
//時(shí)間復(fù)雜度為O(n^2)沙绝，它是不穩(wěn)定排序。
void selectsort(int a[], int n) {
int i, j, k, tmp;
for (i = 0; i < n-1; i++) {
k = i;
for (j = i + 1; j < n; j++) {
if (a[j] < a[k])
k = j;
}
if (k != i) {
tmp = a[i];
a[i] = a[k];
a[k] = tmp;
}
}
}
堆排序：是一樹形選擇排序鼠锈，在排序過(guò)程中闪檬，將R[1..N]看成是一顆完全二叉樹的順序存儲(chǔ)結(jié)構(gòu)，利用完全二叉樹中雙親結(jié)點(diǎn)和孩子結(jié)點(diǎn)之間的內(nèi)在關(guān)系來(lái)選擇最小的元素购笆。
//堆排序
//時(shí)間復(fù)雜度為O(nlogn)粗悯，是不穩(wěn)定排序
void sfilter(int a[], int l, int m) {
int i, j x;
i = l;
j = 2 * i;
x = a[i];
while ( j <= m) {
if (j < m && a[j] < a[j+1])
j++;
if (x < a[j]) {
a[i] = a[j];
i = j;
j = 2 * i;
} else {
j = m + 1;
}
}
a[i] = x;
}
void heapsort(int a[], int n) {
int i, w;
for (i = n/2; i >= 1; i--)
sfilter(a, i, n);
for (i = n; i >= 2; i--) {
w = a[i];
a[i] = a[1];
a[1] = w;
sfilter(a, 1, i - 1);
}
}
4：交換排序(冒泡排序/快排)
交換排序：兩兩比較待排序記錄的關(guān)鍵字，發(fā)現(xiàn)兩個(gè)記錄的次序相反時(shí)即進(jìn)行交換同欠，直到?jīng)]有反序的記錄為止样傍。
首先來(lái)看著名的交換排序算法：冒泡法。冒泡法的排序思想是：從第n個(gè)元素(a[n-1])開始铺遂，掃描數(shù)組衫哥，比較相鄰兩個(gè)元素，如果次序相反則交換襟锐。如此反復(fù)撤逢，直到?jīng)]有任何兩個(gè)違反相反原則的元素
//冒泡排序：
//時(shí)間復(fù)雜度為O(n^2)，它是穩(wěn)定排序
void bubble_sort(int a[], int n) {
int i, j, tmp;
for (i = 0; i < n-1; i++) {
for (j = n-1; j >= i+1; j--) {
if (a[j] < a[j-1]) {
tmp = a[j];
a[j] = a[j-1];
a[j-1] = tmp;
}
}
}
}
快速排序：在當(dāng)前無(wú)序區(qū)R[1..H]中任取一個(gè)數(shù)據(jù)元素作為比較的“基準(zhǔn)”(不妨記為X粮坞，R[1])蚊荣，用此基準(zhǔn)將當(dāng)前無(wú)序區(qū)劃分為左右兩個(gè)較小的無(wú)序區(qū)：R[1..I-1]和R[I+1..H]，且左邊的無(wú)序子區(qū)中數(shù)據(jù)元素均小于等于基準(zhǔn)元素莫杈，右邊的無(wú)序子區(qū)中數(shù)據(jù)元素均大于等于基準(zhǔn)元素互例，而基準(zhǔn)X則位于最終排序的位置上，即R[1..I-1]≤X≤RI+ 1..H筝闹，當(dāng)R[1..I-1]和R[I+1..H]均非空時(shí)敲霍，分別對(duì)它們進(jìn)行上述的劃分過(guò)程俊马，直至所有無(wú)序子區(qū)中的數(shù)據(jù)元素均已排序?yàn)橹埂?/p>
找一個(gè)數(shù)X（比如頭一個(gè)元素）做基準(zhǔn)，右邊比X小的移動(dòng)到左邊肩杈，左邊比X大的移動(dòng)到右邊柴我，最后空出的位置就是X自己的位置
快速排序的時(shí)間復(fù)雜度為O(nlogn)，最壞情況為O(n^2)扩然。對(duì)于大的艘儒、亂數(shù)序列一般相信是最快的已知排序。待排記錄序列按關(guān)鍵字順序有序時(shí)夫偶，直接插入排序和起泡排序能達(dá)到O(n)的時(shí)間復(fù)雜度界睁，而對(duì)于快速排序而言，這是最不好的情況兵拢。對(duì)于很小的數(shù)組（如N<=20）翻斟，快速排序不如插入排序好。
void quickSort(int a[],int left,int right) {
int i,j,temp;
i=left;
j=right;
temp=a[left];
if(left>right)
return;
while(i<j) {/*找到最終位置*/
while(a[j]>=temp && j>i)
j--;
if(j>i)
a[i++]=a[j];
while(a[i]<=temp && j>i)
i++;
if(j>i)
a[j--]=a[i];
}
a[i]=temp;
quickSort(a,left,i-1);/*遞歸左邊*/
quickSort(a,i+1,right);/*遞歸右邊*/
}
void qsort(int a[], int n) {
quickSort(a, 0, n-1);
}
5：排序時(shí)間復(fù)雜度空間復(fù)雜度比較
| 排序算法 | 平均時(shí)間 | 最壞情況 | 輔助存儲(chǔ) | 是否是穩(wěn)定算法 |
|---|---|---|---|---|
| 簡(jiǎn)單排序 | O(n^2) | O(n^2) | O(1) | |
| 快速排序 | O(nlogn) | O(n^2) | O(logn) | |
| 堆排序 | O(nlogn) | O(nlogn) | 0(1) | |
| 歸并排序 | O(nlogn) | O(nlogn) | O(n) | |
| 基數(shù)排序 | O(d(n+rd)) | O(d(n+rd)) | O(rd) |
6：查找(折半查找/HASH查找)
查找：將表中記錄的關(guān)鍵字與查找關(guān)鍵字比較说铃，如果兩者相等访惜，則查找成功，返回查找位置腻扇。
包含：鏈表查找债热，數(shù)組查找，二叉樹查找幼苛，hash
6.1: 折半查找
折半查找：又叫二分查找窒篱，首先，假設(shè)表中元素是按升序排列舶沿，將表中間位置記錄的關(guān)鍵字與查找關(guān)鍵字比較墙杯，如果兩者相等，則查找成功括荡；否則利用中間位置記錄將表分成前霍转、后兩個(gè)子表，如果中間位置記錄的關(guān)鍵字大于查找關(guān)鍵字一汽，則進(jìn)一步查找前一子表，否則進(jìn)一步查找后一子表低滩。重復(fù)以上過(guò)程召夹，直到找到滿足條件的記錄，使查找成功恕沫，或直到子表不存在為止监憎，此時(shí)查找不成功。
注意：折半查找必須滿足兩個(gè)條件：一婶溯，元素必須是連續(xù)存儲(chǔ)鲸阔；二偷霉，元素必須有序。時(shí)間復(fù)雜度：O(logn)
//折半查找算法：
//a為存放數(shù)據(jù)的有序表褐筛，n為數(shù)據(jù)元素個(gè)數(shù)类少，k為要查找的元素
int bin_search(int a[], int n, int k) {
int low, high, mid, i;
low = 0;
high = n-1;
while (low <= high) {
mid = (low + high)/2;
if (a[mid] < k)
low = mid + 1;
else if (a[mid] > k)
high = mid - 1;
else {
return mid;
}
}
return -1;
}
//遞歸版本：
int iter_biSearch(int data[], const int x, int beg, int last) {
int mid = -1;
mid = (beg + last) / 2;
if (x == data[mid]) {
return mid;
} else if (x < data[mid]) {
return iter_biSearch(data, x, beg, mid - 1);
} else if (x > data[mid]) {
return iter_biSearch(data, x, mid + 1, last);
}
return -1;
}
int bin_search2(int a[], int n, int k) {
return iter_biSearch(a,k,0,n-1);
}
6.2：Hash表
Hash表用于存放key-value數(shù)據(jù)。比如一個(gè)學(xué)生的成績(jī)渔扎，那么學(xué)生的學(xué)號(hào)可以當(dāng)做key硫狞，成績(jī)當(dāng)做value，存放與hash表中晃痴。
Hash查找必須提供一個(gè)Hash函數(shù)残吩，用于通過(guò)Key來(lái)計(jì)算數(shù)據(jù)存放在hash表中的位置。一般hash函數(shù)可以設(shè)計(jì)為key%N倘核，其中N為hash表中元素的個(gè)數(shù)（一般為質(zhì)數(shù)）泣侮。
假如HASH表的大小為N，那么Hash函數(shù)為：Hash(key)=key%N
當(dāng)對(duì)于不同的兩個(gè)key紧唱，計(jì)算出來(lái)的hash值可能相同活尊，在相同的時(shí)候，就叫做hash沖突琼蚯。解決hash沖突的方法不止一種酬凳，比如通過(guò)鏈?zhǔn)椒ń鉀Q，即將所有含有相同hash值的數(shù)據(jù)存放在同一個(gè)鏈表中遭庶，而將鏈表的頭結(jié)點(diǎn)存放在HASH表中宁仔。
所謂hash查找，就是通過(guò)對(duì)應(yīng)的key峦睡，按照hash函數(shù)翎苫，計(jì)算出數(shù)據(jù)在hash表中的位置。Hash查找的復(fù)雜度為O(1)榨了，所以具有較高的查找效率煎谍。
6.3：二叉搜索樹查找
typedef struct _node {
int data;
struct _node *left;
struct _node *right;
} node, btree;
btree *search(btree *b, int x) {
if (b == NULL) {
return NULL;
} else {
if (b->data == x) {
return b;
} else if (x < b->data) {
return (search(b->left));
} else {
return (search(b->right));
}
}
}
