排序算法

冒泡排序

void bubbleSort(int a[] , int n){for(int i = n-1 ; i > 0 ; i--){for(int j = 0 ; j < i ; j++){if(a[j] < a[j - 1]){  swap(a[j - 1],a[j]);printArr(a,n);}}}
} 

直接插入排序

void straightInsertionSort(int a[] , int n){int tempCout = 0;//a[j] > a[j + gap]換成a[j] < a[j + 1]for(int i = 1 ; i < n ; i++){ for(int j = i-1 ; j >= 0 && a[j]>a[j+1] ; j-- ){ swap(a[j],a[j+1]); //交換2個數 tempCout++;}printArr(a , n);  //打印數字}
}

希爾排序

void shellSort(int a[] , int n){int i ,j , gap;  //gap為分組的大小，此處采用二分法for(gap = n/2 ; gap > 0 ; gap /= 2){  //遍歷每個分組for(i = gap ; i< n ; i += gap){//將a[j] > a[j + gap]換成a[j] < a[j + gap]for( j = i - gap ; j>=0 && a[j] > a[j + gap] ; j -= gap){  swap(a[j] , a[j + gap]);}printArr(a , n);}}
}

直接選擇排序

void straightSelectSort(int a[] , int n){int i , j , minIndex;for(i = 0 ; i < n ; i++){minIndex = i;for(j = i + 1; j < n ; j++){a[j] > a[minIndex]if(a[j] < a[minIndex]){minIndex = j;    }    }swap(a[i] , a[minIndex]); printArr(a , n);        }    
}

快速排序

void quickSort(int a[] , int L , int R){if(L < R){int i=L , j = R , temp = a[i];while(i<j){//從右向左找尋小于基準值a[i]的元素while(i<j && a[j] >= temp){j--;} if(i < j){a[i++] = a[j]; //將小于基準值的元素插入到a[i],同時i指針進一 }//從左向右找尋大于基準值a[i]的元素while(i<j && a[i] < temp){i ++;} if(i < j){a[j--] = a[i];  // 將大于基準值的元素插入到a[j] , 同時j指針減一 }}a[i] = temp;quickSort(a , L, i-1); //對左邊元素遞歸 quickSort(a , i+1, R); //對右邊元素遞歸 printArr(a , R - L + 1);  //要注意數組的長度是R-L+1而不是R-L，因為數組是從0開始的    }        
} 

堆排序

歸并排序

void mergeArr(int a[] , int left , int mid , int right, int temp[]){int i = left , j = mid + 1; //左邊有序的列表 int m = mid , n = right; //右邊有序的列表 int k = 0; //用于歸并后數組的指引while(i<=m && j<=n){if(a[i] < a[j]){  //比較左邊數組和右邊數組之間的大小 temp[k++] = a[i++];  //將左邊數組小的元素放置于臨時數組中，同時數組指針加一 }else{temp[k++] = a[j++]; //將右邊數組中小的元素放置于臨時數組中，同時數組指針加一 } } //將左邊數組中剩下的數組元素加入到temp數組中while(i<=m){temp[k++] = a[i++];//加入元素，同時數組的指針加一 } //將右邊的數組中剩下的元素加入到temp數組中while(j<=n){temp[k++] = a[j++];//加入元素，同時數組的指針加一} //將歸并后的有序數組復制拷貝到原數組a中 for(i=0;i<k;i++){a[left + i] = temp[i];} printArr(a , right - left + 1);//打印數組 
}
void mergeSort(int a[] , int left , int right , int temp[]){if(left < right){int mid = (left + right) / 2 ;mergeSort(a , left , mid , temp); //左邊遞歸mergeSort(a , mid + 1 , right , temp); //右邊遞歸mergeArr(a , left , mid , right , temp);//合并排序好的數組        } 
}

總結

查找算法

順序查找

int SequenceSearch(int a[], int value, int n)
{int i;for(i=0; i<n; i++)if(a[i]==value)return i;return -1;
}

二分查找

int binSearch(int a[] , int val , int len){int start = 0 , mid = 0;int end = len - 1;while(start<=end){mid = (start + end)/2;  //計算中點位置if(val == a[mid] ){return mid;}else if(val < a[mid]){end = mid - 1;}else if(val > a[mid]){start = mid + 1;}}return -1;
}int binSearch_1(int a[] , int val , int start , int end){if(start > end){  //查詢不到的時候返回-1return -1;}int mid = (end + start) / 2;  //計算中點位置if(val == a[mid]){return mid;}else if(val < a[mid]){return binSearch_1(a , val , start , mid - 1);}else if(val > a[mid]){return binSearch_1(a , val , mid + 1 , end);}        
}

插值查找

int insertSearch(int a[] , int val , int low , int high){//正常情況下 while(low <= high){int mid = low + (val-a[low])/(a[high]-a[low])*(high-low); //相比于二分查找改進的地方 if(val == a[mid]){return mid;}else if(val < a[mid]){high = mid -1;}else if(val > a[mid]){low = mid + 1;}}return -1; 
} 

斐波那契查找

樹表查找

平衡查找樹，二叉查找樹，紅黑樹，b樹，b+樹，

分塊查找

哈希查找

總結