無需額外記憶體的基礎交換函數
void swap(int& temp1, int& temp2)
{
temp1 = temp1 ^ temp2;
temp2 = temp1 ^ temp2;
temp1 = temp1 ^ temp2;
}
1. 冒泡排序
void bubbleSort(int array[], int len)
{
// 需要循環比較 len-1 輪ß
for (int i = 0; i<len-1; i++)
{
// 每論比較都隻需要len-1-i個，i是輪數，也是已排序的數字個數。
for (int j = 0; j < len -1 -i; j++)
{
if (array[j] > array[j+1])
{
swap(array[j], array[i]);
}
}
}
}
選擇排序
void selectSort(int array[], int len) {
int minIndex;
// 需要選擇 len-1 輪
for (int i = 0; i < len - 1; i++) {
// 初始化每輪最小值下标，取第一位
minIndex = i;
// 從未排序位置，開始找最小數
for (int j = i + 1; j < len; j++) {
if ( array[j] < array[minIndex] ) {
// 儲存最小數下标，循環結束後交換。
minIndex = j;
}
}
swap(array[i], array[minIndex]);
}
}
插入排序
// 類似鬥地主疊排，預設第一個已經排好，待插入的值與前面的比較，若滿足要求則插入。
void insertSort(int array[], int len)
{
int index, current;
// 預設第一個數有序，從第二個數開始插入。
for (int i = 1; i < len; i++) {
index = i - 1; // 已排序數組用于比較的下标
current = array[i]; // 帶插入的數值
// 向前尋找插入位置，
while (index >= 0 && array[index] > current) {
// 不滿足插入條件的時候，需要将比較過的數後移
array[index + 1] = array[index];
// 代比較的位置前移
index--;
}
// 找到插入位置，插入
array[index + 1] = current;
}
}
希爾排序
// 分組排序思想
void shellSort(int array[], int len)
{
// 定義分組間隔，可以手動輸入。
int gap = 1;
while (gap < len / 3) {
gap = gap * 3 + 1;
}
// gap不斷下降成為1，進行多次間隔不同的直接插入排序。
for ( ; gap > 0; gap = floor(gap / 3 ) ) {
// 同插入排序
int index, current;
// 從間隔長度開始，每個數都需要與之前的數比較，插入，隻是間隔不為1.
for (int i = gap; i < len; i++) {
current = array[i];
index = i - gap;
// 注意取值範圍
while (index >= 0 && array[index] > current) {
array[index + gap] = array[index];
index = index - gap;
}
array[index + gap] = current;
}
}
}
歸并排序
// 空間換時間的排序算法，采用了分而治之的思想。
void merge(int array[], int start, int middle, int end) {
int len1 = middle - start + 1;
int len2 = end - middle;
int i, j;
// 定義中間變量
int *arr1 = new int[len1 + 1];
int *arr2 = new int[len2 + 1];
// 賦初值
for (i = 0; i < len1; i++)
{
*(arr1 + i) = array[start + i];
}
for (j = 0; j < len2; j++)
{
*(arr2 + j) = array[middle + j + 1];
}
// 設定哨兵
arr1[len1] = 10000;
arr2[len2] = 10000;
// 從最前面周遊
i = 0;
j = 0;
for (int k = start; k <= end; k++)
{
if (arr1[i] < arr2[j])
{
array[k] = arr1[i];
i++;
}
else
{
array[k] = arr2[j];
j++;
}
}
delete arr1;
delete arr2;
}
// 拆分比較
void mergeSort(int array[], int start, int end)
{
int middle = (end + start) / 2;
if (start < end) {
// 拆分左邊部分
mergeSort(array, start, middle);
// 拆分右邊部分
mergeSort(array, middle + 1, end);
// 合并
merge(array, start, middle, end);
}
}
快速排序
void quickSort(int array[], int left, int right)
{
if (left < right) {
int base = array[left];
int indexL = left;
int indexR = right;
while (indexR > indexL)
{
// 右振蕩
while (indexR > indexL && array[indexR] >= base)
{
indexR--;
}
// 確定不是因為 indexR <= indexL 結束。
if(indexR > indexL)
array[indexL++] = array[indexR];
// 左振蕩
while (indexR > indexL && array[indexL] < base)
{
indexL++;
}
// 確定不是因為 indexR <= indexL 結束。
if (indexR > indexL)
array[indexR--] = array[indexL];
}
// 計算完後 indexR = indexL = 最中間的下标
array[indexR] = base;
// 遞歸
quickSort(array, left, indexR - 1);
quickSort(array, indexR + 1, right);
}
}
堆排序
void adjustHeap(int array[], int len)
{
int maxIndex, rootIndex, subLeftIndex, subRightIndex;
// 從1/2節點處開始調整。
for (int i = len / 2; i > 0; i--){
// 計算真實下标
rootIndex = i - 1;
subLeftIndex = 2 * i -1;
subRightIndex = 2 * i;
maxIndex = rootIndex;
if (array[maxIndex] < array[subLeftIndex])
maxIndex = subLeftIndex;
// 右子節點需要判斷是否越界
if ( subRightIndex< len && array[maxIndex] < array[subRightIndex])
maxIndex = subRightIndex;
// 根節點與最大節點交換
if( maxIndex != rootIndex)
swap(array[rootIndex], array[maxIndex]);
}
}
void heapSort(int array[], int len)
{
for (int i = 0; i < len - 1 ; i++) {
adjustHeap(array, len - i);
// 将最大值，移動到最後
swap(array[0], array[len - i - 1]);
}
}
計數排序
void countSort(int array[], int len)
{
int minValue = array[0];
int maxValue = array[0];
// 獲得最小最大值，确定排序邊界
for (int i = 1; i < len; i++) {
if (array[i] < minValue)
minValue = array[i];
if (array[i] > maxValue)
maxValue = array[i];
}
int countLen = maxValue - minValue + 1;
int * countArray = new int[countLen];
// 清0
for (int i = 0; i < countLen; i++) {
countArray[i] = 0;
}
// 計算數目
for (int i = 0; i < len; i++) {
countArray[array[i] - minValue] ++;
}
// 排序
int j = 0;
for (int i = 0; i < countLen; i++) {
while ( countArray[i] != 0 )
{
array[j++] = i + minValue;
countArray[i]--;
}
}
delete countArray;
}
其他推薦算法：
必知的資料結構
1. 連結清單
2. 樹
3. 最小堆，最大堆
4. 棧
5. 隊列
6. Hash結構與基礎算法
圖相關：
- 圖的存儲： 鄰接矩陣(稠密網)，鄰接表（連結清單,稀疏圖），圖的表示反而是難點
- 圖的周遊算法
1 深度優先周遊算法：遞歸算法 VS 非遞歸算法
2 廣度優先周遊算法
圖的周遊 - Matrix海子 - 部落格園www.cnblogs.com
-
最短路徑算法
單源最短路徑: Dijkstra算法， 核心：最優子結構性質 O(n^2)）
Dijkstra算法（單源最短路徑） - Matrix海子 - 部落格園www.cnblogs.com
多源最短路徑: 1.多次調用Dijkstra算法 （O(n^3)） 2.Floyd算法
Floyd算法(二)之 C++詳解 - 如果天空不死 - 部落格園www.cnblogs.com
-
最小生成樹算法
Prim算法: 将頂點歸并，與邊數無關，适于稠密網。
Prim算法(一)之 C語言詳解 - 如果天空不死 - 部落格園www.cnblogs.com
Kruskal算法: 将邊歸并，适于求稀疏網的最小生成樹。
Kruskal算法www.cnblogs.com
樹相關：
- 二叉樹
二叉查找樹(一)之 圖文解析 和 C語言的實作www.cnblogs.com
- 平衡二叉樹，算法非重點，但必須知道其定義
AVL樹(一)之 圖文解析 和 C語言的實作www.cnblogs.com
- 紅黑樹，是一種非嚴格的AVL數，出自算法導論，在Linux中被實作，以提高資料的查找效率。
紅黑樹(一)之 原理和算法詳細介紹 - 如果天空不死 - 部落格園www.cnblogs.com
-
B樹，B+樹。
首先說明一個概念，如果看到文章提到B-樹，一般就是指的B數，而B+樹是B樹的一種變形。
B樹結構使得一個節點上可以儲存多個資料，提高了對于運作速度慢的外部存儲的通路能力，同時緩解了大量資料下，樹的深度過深的問題。是為了儲存設備或者磁盤而設計的一種平衡查找樹。常見于資料庫，檔案系統中（B+樹更适用于檔案系統）。
B樹族www.cnblogs.com
- 哈夫曼樹
哈夫曼樹(一)之 C語言詳解 - 如果天空不死 - 部落格園www.cnblogs.com
字元串算法：
- 暴力比較算法(BP算法)：
- KMP算法：
（原創）詳解KMP算法 - 孤~影 - 部落格園www.cnblogs.com
這裡我印象最深刻的一句話就是：“我不能說你錯，隻能說你不對”。是以，不是行業現狀中的最優解的解，不是真的解。
斐波那契數列
青蛙跳台階問題，可以參考劍指Offer中的幾個變形。
大數計算算法
數字轉字元串計算。
+，-： 逆序計算
布隆過濾器
大資料中，緩解記憶體不夠用的算法，但存在一定的誤判率。
布隆過濾器 - Matrix海子 - 部落格園www.cnblogs.com
平方根 --- 二分法和牛頓法
平方根算法www.cnblogs.com
top K 問題
可以刷一下劍指Offer，重點學習最大最小堆的應用。
算法必學：經典的 Top K 問題www.jianshu.com
神秘算法————平方根倒數速算法
神秘數字：0x5f3759df，浮點數在計算機中的表示，數學近似等，該算法肯定不會被面試考到，但是如此神一般的算法，建議大家自行Google學習，以下貼代碼。
float Q_rsqrt( float number )
{
long i;
float x2, y;
const float threehalfs = 1.5F;
x2 = number * 0.5F;
y = number;
i = * ( long * ) &y; // evil floating point bit level hacking
i = 0x5f3759df - ( i >> 1 ); // what the fuck?
y = * ( float * ) &i;
y = y * ( threehalfs - ( x2 * y * y ) ); // 1st iteration
// y = y * ( threehalfs - ( x2 * y * y ) ); // 2nd iteration, this can be removed
return y;
}
劍指Offer 第二版
常見資料結構以及算法的應用，66道題。
1. 通過讀課本了解算法原理。
2. 通過牛客網刷題提升代碼能力。
LeetCode
分為：難，中等，容易三種級别的題目，适合希望在算法能有更多進步的人進一步刷題，我沒怎麼刷過，不過多的評價。
常見算法思想
五大常用算法之一：分治算法 - 紅臉書生 - 部落格園www.cnblogs.com 五大常用算法之二：動态規劃算法 - 紅臉書生 - 部落格園www.cnblogs.com 五大常用算法之三：貪心算法 - 紅臉書生 - 部落格園www.cnblogs.com 五大常用算法之四：回溯法 - 紅臉書生 - 部落格園www.cnblogs.com