直接插入排序 (穩(wěn)定）O(
)
希爾排序（不穩(wěn)定）O(
)
冒泡排序（穩(wěn)定）O()
快速排序（不穩(wěn)定）O()
直接選擇排序（不穩(wěn)定）O()
堆排序（不穩(wěn)定）O()
歸并排序（穩(wěn)定）O()
基數(shù)排序（穩(wěn)定）
二分查找在最下面....
直接插入：?
分析：
1，從第一個數(shù)的下一個數(shù)開始外層遍歷
2煮岁，然后用當(dāng)前這個數(shù)和這個數(shù)前面的所有數(shù)進行比較，比他大的數(shù)就向后移動移動，提前把這個數(shù)弄到一個temp中存儲起來匠楚。
3，一直到這個數(shù)碰到比他小的數(shù)就退出厂财，并把temp的值賦予退出這個位置
具體舉例：
5,6,1,7,4,8,3,2,9
第一次：從6開始往后遍歷芋簿，用6和5比較
5,6,1,7,4,8,3,2,9
第二次：用1和6比，6>1,所以6向后移動一位璃饱，1然后和5比与斤，5>1,所以5也向后移動一位
1,5,6,7,4,8,3,2,9
第三次：用7和前面的比較
....一直類似的比較到最后
1,2,3,4,5,6,7,8,9
具體算法：
????int a[6]={1,2,3,2,1,6};
? ? int i,j,temp;
? // 插入排序
? ? for(i=1;i<N;i++){
? ? ? ? temp=a[i];
? ? ? ? for(j=i-1;j>=0;j--){
? ? ? ? ? ? if(a[j]>temp){
? ? ? ? ? ? ? ? a[j+1]=a[j];
? ? ? ? ? ? }else{
? ? ? ? ? ? ? ? break;
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? a[j+1]=temp;
? ? }
希爾排序：
分析：他是一種縮小增量排序，將相隔某個增量的記錄組成一個子序列，這個序列采用的直接插入排序幽告，增量一趟一趟都在減少梅鹦，知道減少到1，進行最后一次排序
比如：49? 38? ?65? ?97? ?76? ?13? ?27? ?49? ? 55? ? 04
增量是5,3,1
一趟排序：49? 38? ?65? ?97? ?76? ?13? ?27? ?49? ? 55? ? 04
其中 49和13,38和27,65和49...
13 27 49 55 04 49 38 65 97 76
二趟排序：
13,55,38,76排序冗锁，27,04,65排序齐唆，49,49,97排序
13 04 49 38 27 49 55 65 97 76
三趟排序：
14 13? 27 38 49 49 55 65 76 97
折半插入：
void b_insert(int *a,int len){
? ? int i,j,temp,m,low,high;
? ? for(i=1;i<len;i++){
? ? ? ? low=0;
? ? ? ? high=i-1;
? ? ? ? while(low<=high){
? ? ? ? ? ? m=(low+high)/2;
? ? ? ? ? ? if(a[m]>a[i]){
? ? ? ? ? ? ? ? high=m-1;
? ? ? ? ? ? }else{
? ? ? ? ? ? ? ? low=m+1;
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? temp=a[i];
? ? ? ? for(j=i;j>high+1;j--){
? ? ? ? ? ? a[j]=a[j-1];
? ? ? ? }
? ? ? ? a[high+1]=temp;
? ? }
}
冒泡排序：
分析：記錄兩兩比較關(guān)鍵字，如果前面的比后面的大冻河，就交換箍邮，每一次排序，都保證有最大的升上去了叨叙，有n個記錄锭弊，外層比較次數(shù)，n-1擂错，內(nèi)層每次比較n-i-1
這個比較簡單味滞，就不舉例了，直接上算法：
for(i=0;i<N-1;i++){
? ? ? ? int leap=1;
? ? ? ? for(j=0;j<N-i-1;j++){
? ? ? ? ? ? if(a[j]>a[j+1]){
? ? ? ? ? ? ? ? temp=a[j];
? ? ? ? ? ? ? ? a[j]=a[j+1];
? ? ? ? ? ? ? ? a[j+1]=temp;
? ? ? ? ? ? ? ? leap=0;
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? if(leap){
? ? ? ? ? ? break;
? ? ? ? }
? ? }
快速排序：
分析：
1钮呀，找一個中樞記錄剑鞍，一般是第一個值
2，i指向第一個值爽醋，j指向最后一個值
3蚁署，如果j==i，就把中樞記錄賦值給a[i]
4蚂四，如果j>i,一直循環(huán)光戈，如果a[j]>=中樞，j--遂赠，否則久妆，a[i]=a[j]
5，如果j>i,一直循環(huán)跷睦，如果a[i]<=中樞镇饺，i++，否則送讲，a[j]=a[i]
6奸笤，采用遞歸的形式，進行排序
比如：49? ?38? ? ?65? ? ?97? ? ? 76? ? ? ?13? ? ? ?27? ? ? ?49
取p=49
i=0,j=7,分別指向第一個和最后一個值
第一趟排序的過程：
27(i)? ? 38? ? ? 65? ? ? 97? ? ? ? 76? ? ? 13? ? ? ?_j_? ?49
27? ? ? ?38? ? ? _i_? ? ? ?97? ? ? 76? ? ?13? ? ? 65(j)? ? ? 49
27? ? ? ?38? ? ? 13(i)? ? ? 97? ? ? 76? ? ?_j_? ? ? 65? ? ?49
27? ? ? ?38? ? ? 13? ? ? _i_? ? ? 76? ? ? 97(j)? ? ? 65? ? ?49
完成一趟排序：27? ? ? ?38? ? ? 13? ? ? 49(i,j)? ? ?76? ? ? 97? ? ?65? ? ?49
第二趟排序：
{27? ? ? ?38? ? ? 13?}? 49? {?76? ? ? 97? ? ?65? ? ?49}
{13(i)? ? ? 38? ? ? ? _j_}? ?49? { 49(i)? ? ?97? ? ? 65? ? ?_j_}
{13? ? ? ?_i_? ? ? ?38(j)}? ?49? {49? ? _i_? ? ?65? ? ? 97(j)}
{13? ? ? 27? ? ? 38}? ?49? ?{ 49? 65(i)? ?_j_? ? 97}
完成兩趟排序：{13? ? ? 27(i,j)? ? ? ?38}? 49? ?{49? ?65? ? ?76(i,j)? ? ?97}
......{13? ? 27? ? ?38? ? ?49? ? ? 49? ? ? 65? ? ?76? ? ? 97}
具體代碼哼鬓，有遞歸和非遞歸算法：
#include <iostream>
using namespace std;
int zhixing(int *a,int low,int high){
? ? int key=a[low];
? ? int i=low;
? ? int j=high;
? ? while(i<j){
? ? ? ? while(i<j && a[j]>=key){
? ? ? ? ? ? j--;
? ? ? ? }
? ? ? ? if(i<j){
? ? ? ? ? ? a[i]=a[j];
? ? ? ? ? ? i++;
? ? ? ? }
? ? ? ? while(i<j && a[i]<=key){
? ? ? ? ? ? i++;
? ? ? ? }
? ? ? ? if(i<j){
? ? ? ? ? ? a[j]=a[i];
? ? ? ? ? ? j--;
? ? ? ? }
? ? }
? ? a[i]=key;
? ? return i;
}
void kp(int *a,int low,int high){
? ? if(low<high){
? ? ? ? int p=zhixing(a,low,high);
? ? ? ? kp(a,0,p-1);
? ? ? ? kp(a,p+1,high);
? ? }
}
//非遞歸算法
void fei_kuaipai(int *a,int low,int high){
? ? //使用棧监右，來存儲每次分開的列的頭和尾
? ? //使用上面的zhixing(a,low,high)這個方法，把每次的列都排好序异希，low和high從棧中取出健盒，一直到棧為空，就排完序了
? ? int mid=zhixing(a,low,high);//首先把這個數(shù)組分開，mid左邊都是比他小的扣癣，右邊都是比他大的
? ? //定義一個棧
? ? stack<int> s;
? ? if(low<mid-1){
? ? ? ? s.push(low);
? ? ? ? s.push(mid-1);
? ? }
? ? if(high>mid+1){
? ? ? ? s.push(high);
? ? ? ? s.push(mid+1);
? ? }
? ? while(!s.empty()){//棧為空退出循環(huán)
? ? ? ? low=s.top();
? ? ? ? s.pop();
? ? ? ? high=s.top();
? ? ? ? s.pop();
? ? ? ? mid=zhixing(a,low,high);//在對子序列進行排序
? ? ? ? if(low<mid-1){
? ? ? ? ? ? s.push(low);
? ? ? ? ? ? s.push(mid-1);
? ? ? ? }
? ? ? ? if(high>mid+1){
? ? ? ? ? ? s.push(high);
? ? ? ? ? ? s.push(mid+1);
? ? ? ? }
? ? }
}
int main()
{
? ? //快速排序
? ? int a[6]={1,2,3,4,2,1};
? ? kp(a,0,5);
? ? fei_kuaipai(a,0,5);
? ? int i;
? ? for(i=0;i<6;i++){
? ? ? ? cout<<a[i]<<" ";
? ? }
? ? return 0;
}
選擇排序：
分析：
1惰帽，每次保證確定是最小的，從0開始遍歷父虑，每次都假設(shè)第一個數(shù)是最小的该酗，向后遍歷
2，如果碰到比這個數(shù)小的士嚎，就把下標(biāo)賦值給min
3呜魄，判斷一下看這個最小的是否還是剛開始的，如果不是莱衩，就把最小的和這個數(shù)交換位置
4爵嗅，然后進行下次遍歷，保證最前面是最小的
代碼如下：
for(i=0;i<N;i++){
? ? ? ? int min=i;
? ? ? ? for(j=i+1;j<N;j++){
? ? ? ? ? ? if(a[j]<a[min]){
? ? ? ? ? ? ? ? min=j;
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? if(min!=i){
? ? ? ? ? ? temp=a[i];
? ? ? ? ? ? a[i]=a[min];
? ? ? ? ? ? a[min]=temp;
? ? ? ? }
? ? }
堆排序：
構(gòu)建大頂堆（父大于子）笨蚁，或構(gòu)建小頂堆（父小于子）睹晒，然后進行調(diào)整，再構(gòu)建括细，在調(diào)整伪很，....直到最后的根節(jié)點，排序完成勒极。
歸并排序：
2路歸并排序---先對子集排序是掰，歸并
比如：
3? ? 2? ? ?5? ? ?1? ? ? 6? ? ? ? 8? ? ? 4
第一趟：{2? ? ? 3}? ? ? ?{1? ? ? ? 5}? ? ? ? {6? ? ? ? 8 }? ? ? {4}
第二趟：{1? ? ? ? 2? ? ? ? 3? ? ? ? 5? }? ? ?{ 4? ? ? ? 6? ? ? ? 8}
第三趟：{1? ? ? ? 2? ? ? ? 3? ? ? ? 4? ? ? ? 5? ? ? ? 6? ? ? ? 8}
基數(shù)排序（桶排序）：
分析：
從個位開始進行第一趟虑鼎，下來的是從小到大排序的辱匿，每次依序進入桶中，進入完成之后炫彩，從下面依次出來匾七，然后在從十位開始進入，...直到最后一趟江兢，排序完成
二分查找：
分析：必須是有序序列昨忆，才可以進行二分查找，在做題的過程中可以構(gòu)造折半二叉樹杉允，就是一顆二叉排序樹邑贴。每次找的中間的數(shù)都是下標(biāo)(a+b)/2向下取整的下標(biāo)對應(yīng)的數(shù)。
算法：
int min=0,max=N-1,mid=(min+max)/2;
? ? int n;
? ? scanf("%d",&n);
? ? while(min<=max){
? ? ? ? if(a[mid]==n){
? ? ? ? ? ? printf("%d ",mid);
? ? ? ? ? ? break;
? ? ? ? }else if(n>a[mid]){
? ? ? ? ? ? min=mid+1;
? ? ? ? }else if(n<a[mid]){
? ? ? ? ? ? max=mid-1;
? ? ? ? }
? ? ? ? mid=(max+min)/2;
? ? }
