1 選擇排序
選擇排序(Selection sort)是一種簡單直觀的排序算法。它的工作原理是：第一次從待排序的數據元素中選出最小(或最大)的一個元素，存放在序列的起始位置，然后再從剩余的未排序元素中尋找到最小(大)元素，然后放到已排序的序列的末尾。以此類推，直到全部待排序的數據元素的個數為零。選擇排序是不穩定的排序方法。
- 穩定性：不穩定
- 時間復雜度：
- 空間復雜度：
void?SelectSort(int?r[],int?n){//簡單選擇
????int?index,i;
????for(i=0;i????????index?=?i;
????????for(int?j=i+1;j????????????if(r[j]????????????????index?=?j;
????????????}
????????}
????????if(index!=i){
????????????int?temp?=?r[i];
????????????r[i]?=?r[index];
????????????r[index]?=?temp;
????????}
????}
}
2 插入排序
直接插入排序
每一趟將一個待排序的記錄，按其關鍵字的大小插入到已經排好序的一組記錄的適當位置上，直到所有待排序記錄全部插入為止。
void?InsertSort(int?r[],int?n){//直接插入排序
????int?j=0;
????for(int?i=2;i????????r[0]=r[i];??????????//哨兵
????????for(j=i-1;r[0]????????????r[j+1]=r[j];
????????}
????????r[j+1]=r[0];
????}
}- 穩定性：穩定
- 時間復雜度：
- 空間復雜度：
折半插入排序
折半插入排序(binary insertion sort)是對插入排序算法的一種改進，由于排序算法過程中，就是不斷的依次將元素插入前面已排好序的序列中。由于前半部分為已排好序的數列，這樣我們不用按順序依次尋找插入點，可以采用折半查找的方法來加快尋找插入點的速度。
void?BinSort(int?r[],int?n){//折半插入排序
????int?low,high,mid;
????for(int?i=2;i????????r[0]=r[i];
????????low=1;
????????high=i-1;
????????while(low<=high){
????????????mid?=(low+high)/2;
????????????if(r[0]????????????????high?=?mid-1;
????????????}else{
????????????????low?=?mid+1;
????????????}
????????}
????????for(int?j=i-1;j>=high+1;j--){
????????????r[j+1]=r[j];
????????}
????????r[high+1]=r[0];
????}
}- 穩定性：穩定
- 時間復雜度：
- 空間復雜度：
3 冒泡排序
冒泡排序(Bubble Sort)，是一種計算機科學領域的較簡單的排序算法。它重復地走訪過要排序的元素列，依次比較兩個相鄰的元素，如果順序(如從大到小、首字母從Z到A)錯誤就把他們交換過來。走訪元素的工作是重復地進行直到沒有相鄰元素需要交換，也就是說該元素列已經排序完成。這個算法的名字由來是因為越小的元素會經由交換慢慢“浮”到數列的頂端(升序或降序排列)，就如同碳酸飲料中二氧化碳的氣泡最終會上浮到頂端一樣，故名“冒泡排序”。
- 穩定性：穩定
- 時間復雜度：
- 空間復雜度：
void?BubbleSort(int?r[],int?n){//冒泡排序
????int?temp;
????for(int?i=0;i-1;i++){for(int?j=0;j-1;j++){if(r[j]>r[j+1]){
????????????????temp?=?r[j];
????????????????r[j]=r[j+1];
????????????????r[j+1]=temp;
????????????}
????????}
????}
}4 希爾排序
希爾排序(Shell's Sort)是插入排序的一種，又稱“縮小增量排序”(Diminishing Increment Sort)，是直接插入排序算法的一種更高效的改進版本。希爾排序是非穩定排序算法。該方法因 D.L.Shell 于 1959 年提出而得名。希爾排序是把記錄按下標的一定增量分組，對每組使用直接插入排序算法排序；隨著增量逐漸減少，每組包含的關鍵詞越來越多，當增量減至 1 時，整個文件恰被分成一組，算法便終止。
- 穩定性：不穩定
- 時間復雜度：到
- 空間復雜度：
void?ShellSort(int?r[],int?n){//希爾排序
????int?j=0;
????for(int?d?=n/2;d>=1;d=d/2){//以增量為d進行直接插入排序
????????for(int?i=d+1;i????????????r[0]=r[i];
????????????for(j=i-d;j>0&&r[0]????????????????r[j+d]=r[j];
????????????}
????????????r[j+d]=r[0];
????????}
????}
}
5 歸并排序
歸并排序(Merge Sort)是建立在歸并操作上的一種有效，穩定的排序算法，該算法是采用分治法(Divide and Conquer)的一個非常典型的應用。將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合并成一個有序表，稱為二路歸并。
- 穩定性：穩定
- 時間復雜度：
- 空間復雜度：
void?merge(int?a[],int?n,int?left,int?mid,int?right){
????int?n1=mid-left,n2=right-mid;
????int?*L?=?new?int[n1+1];
????int?*R?=?new?int[n2+1];
????for(int?i=0;i????????L[i]=a[left+i];
????for(int?i=0;i????????R[i]=a[mid+i];
????L[n1]=10000000;
????R[n2]=10000000;
????int?i=0,j=0;
????for(int?k=left;k????{
????????if(L[i]<=R[j])
????????????a[k]=L[i++];
????????else
????????????a[k]=R[j++];
????}
????delete[]?L;
????delete[]?R;
}
void?MergeSort(int?a[],int?n,int?left,int?right){
????if(left+1????{
????????int?mid=(left+right)/2;
????????MergeSort(a,n,left,mid);
????????MergeSort(a,n,mid,right);
????????merge(a,n,left,mid,right);
????}
}
6 快速排序
快速排序是C.R.A.Hoare于1962年提出的一種劃分交換排序。它采用了一種分治的策略。
該方法的基本思想是：
1．先從數列中取出一個數作為基準數。
2．分區過程，將比這個數大的數全放到它的右邊，小于或等于它的數全放到它的左邊。
3．再對左右區間重復第二步，直到各區間只有一個數。
穩定性：不穩定
時間復雜度：
空間復雜度：
int?Partition(int?r[],int?first,int?end){//快速排序一次劃分算法
????int?i=first,j=end;
????int?temp;
????while(i????????while(i????????????j--;
????????if(i????????????temp?=?r[i];
????????????r[i]?=?r[j];
????????????r[j]?=?temp;
????????}
????????while(i????????????i++;
????????if(i????????????temp?=?r[i];
????????????r[i]?=?r[j];
????????????r[j]?=?temp;
????????????j--;
????????}
????}
????return?i;
}
void?QuickSort(int?r[],int?first,int?end){
????if(first????????int?pivot?=?Partition(r,first,end);
????????QuickSort(r,first,pivot-1);
????????QuickSort(r,pivot+1,end);
????}
}
7 堆排序
堆排序是利用堆這種數據結構而設計的一種排序算法，堆排序是一種選擇排序，它的最壞，最好，平均時間復雜度均為，它也是不穩定排序。首先簡單了解下堆結構。
堆排序的基本思想是：將待排序序列構造成一個大頂堆。此時，整個序列的最大值就是堆頂的根節點。將根節點與末尾元素進行交換，此時末尾就為最大值。然后將剩余n-1個元素重新構造成一個大頂堆，這樣會得到n個元素的次小值。如此反復執行，便能得到一個有序序列。
- 穩定性：不穩定
- 時間復雜度：
- 空間復雜度：
//?堆排序
void?HeapAdjust(int?a[],int?s,int?m)//一次篩選的過程{
????int?rc,j;
????rc=a[s];
????for(j=2*s+1;j<=m;j=j*2+1)//通過循環沿較大的孩子結點向下篩選
????{
????????if(j1])?j++;//j為較大的記錄的下標if(rc>a[j])?break;
????????a[s]=a[j];s=j;
????}
????a[s]=rc;//插入
}void?HeapSort(int?a[],int?n){int?temp,i,j;//找最接近的點int?s?=0;while(2*s+1????????s++;
????}for(i=s;i>=0;i--)//通過循環初始化頂堆
????{
????????HeapAdjust(a,i,n);
????}for(i=n;i>=0;i--)
????{
????????temp=a[0];
????????a[0]=a[i];
????????a[i]=temp;//將堆頂記錄與未排序的最后一個記錄交換
????????HeapAdjust(a,0,i-1);//重新調整為頂堆
????}
}8 基數排序
基數排序(radix sort)屬于“分配式排序”(distribution sort)，又稱“桶子法”(bucket sort)或bin sort，顧名思義，它是透過鍵值的部份資訊，將要排序的元素分配至某些“桶”中，藉以達到排序的作用，基數排序法是屬于穩定性的排序，其時間復雜度為O (nlog(r)m)，其中r為所采取的基數，而m為堆數，在某些時候，基數排序法的效率高于其它的穩定性排序法。
- 穩定性：穩定
- 時間復雜度：，其中r為所采取的基數，而m為堆數
- 空間復雜度：
//獲取數字的位數
int?getLoopTimes(int?num){
????int?count?=?1;
????int?temp?=?num?/?10;
????while(temp?!=?0){
????????count++;
????????temp?/=?10;
????}
????return?count;
}
//查詢數組中的最大數
int?findMaxNum(int?*p,?int?n){
????int?max?=?p[0];
????for(int?i?=?0;?i?????????if(p[i]?>?max){
????????????max?=?p[i];
????????}
????}
????return?max;
}
//將數字分配到各自的桶中，然后按照桶的順序輸出排序結果
void?sortSingle(int?*p,?int?n,?int?loop){
????//建立一組桶此處的20是預設的根據實際數情況修改
????int?buckets[10][20]?=?{};
????//求桶的index的除數
????//如798個位桶index=(798/1)%10=8
????//十位桶index=(798/10)%10=9
????//百位桶index=(798/100)%10=7
????//tempNum為上式中的1、10、100
????int?tempNum?=?(int)pow(10,?loop?-?1);
????int?i,?j;
????for(i?=?0;?i?????????int?row_index?=?(p[i]/tempNum)?%?10;
????????for(j?=?0;?j?20;?j++){
????????????if(buckets[row_index][j]?==?NULL){
????????????????buckets[row_index][j]?=?p[i];
????????????????break;
????????????}
????????}
????}
????//將桶中的數，倒回到原有數組中
????int?k?=?0;
????for(int?i?=?0;?i?10;?i++){
????????for(int?j?=?0;?j?20;?j++){
????????????if(buckets[i][j]?!=?NULL){
????????????????p[k]?=?buckets[i][j];
????????????????buckets[i][j]?=?NULL;
????????????????k++;
????????????}
????????}
????}
}
void?BucketSort(int?*p,?int?n){
????//獲取數組中的最大數
????int?maxNum?=?findMaxNum(p,?n);
????//獲取最大數的位數，次數也是再分配的次數。
????int?loopTimes?=?getLoopTimes(maxNum);
????//對每一位進行桶分配
????for(int?i?=?1;?i?<=?loopTimes;?i++){
????????sortSingle(p,?n,?i);
????}
}
9 線性查找
在常規無序數組中，設數組項個數為N，則一個數組項平均查找長度為N/2。極端情況下，查找數據項在數組最后，則需要N步才能找到。
- 時間復雜度：
- 空間復雜度：
int?findLinear(int*?p,int?n,int?k){
????for(int?i=0;i????????if(p[i]==k){
????????????return?i;
????????}
????}
????//查找失敗，返回-1
????return?-1;
}
10 折半查找
二分查找也稱折半查找(Binary Search)，它是一種效率較高的查找方法。但是，折半查找要求線性表必須采用順序存儲結構，而且表中元素按關鍵字有序排列。
首先，假設表中元素是按升序排列，將表中間位置記錄的關鍵字與查找關鍵字比較，如果兩者相等，則查找成功；否則利用中間位置記錄將表分成前、后兩個子表，如果中間位置記錄的關鍵字大于查找關鍵字，則進一步查找前一子表，否則進一步查找后一子表。重復以上過程，直到找到滿足條件的記錄，使查找成功，或直到子表不存在為止，此時查找不成功。
- 時間復雜度：
- 空間復雜度：看實現方式，遞歸，非遞歸
//?折半查找
int?BinarySearch(int*?p?,int?n,int?k)?{
????int?low?=?0;
????int?high?=?n?-?1;
????int?cur;
????while(low<=high){
????????//?取中間值
????????cur?=?(low?+?high)?/?2;
????????//?待查找的值與中間值匹配則返回
????????if?(p[cur]?==?k)?{
????????????return?cur;
????????}else{
????????????//?如果中間值小于待查找的值，則將查找的最小下限值設為中間值下標+1
????????????if?(p[cur]?????????????????low=?cur?+?1;
????????????}?else?{//?如果中間值大于待查找的值，則將查找的最大上限值設為中間值下標-1
????????????????high?=?cur?-?1;
????????????}
????????}
????}
}
![屬于計算機病毒主要特征的是,[單選] 不屬于計算機病毒的主要特征的是（）](http://pic.xiahunao.cn/屬于計算機病毒主要特征的是,[單選] 不屬于計算機病毒的主要特征的是（）)
)
