一.交換類
冒泡排序：
void BubbleSort(int*src, int n)//冒泡
{
int i, j, flag = 0;
for (i = 0; i < n-1; i++)//最後一次不需要，因為出最後最後隻剩一個元素待排
{
flag = 0;
for (j = 0; j < n - i - 1; j++)
{
if (src[j] > src[j + 1])
{
int tmp = src[j];
src[j] = src[j + 1];
src[j + 1] = tmp;
flag = 1;
}
}
if (0 == flag)
{
break;
}
}
}
冒泡排序類似于海浪，一波一撥，每次将無序中的最值冒到最邊上，一趟一趟重複進行。
選擇排序：
void SelectSort(int* src, int n)//選擇排序
{
int i, j;
int min;//始終标記接下來周遊中最小的資料下标
for (i = 0; i < n-1; i++)
{
min = i;
for (j = i; j < n; j++)
{
if (src[min] > src[j])
{
min = j;
}
}
if (min != i)
{
int tmp = src[i];
src[i] = src[min];
src[min] = tmp;
}
}
}
該算法是從頭開始不斷周遊後面的未排序列，找到最值，并與本節點交換，每次得到未排序列的最值
二.插入排序類
直接插入排序：
void InsertSort(int*src, int n)//插入排序
{
int i, j;
for (i = 1; i < n; i++)
{
int tmp = src[i];
if (src[i - 1] > tmp)//前面已經有序，如果當i-1小于等于tmp，則說明前面所有資料均小于等于tmp，故不用找位置插入
{
for (j = i; j > 0 && src[j - 1]> tmp; j--)//j前面資料已經有序，隻需要找到第一個比tmp小的資料，插在它之後
{
src[j] = src[j - 1];
}
src[j] = tmp;
}
}
}
直接插入排序是從第二個元素為基準點，然後在前面已經有序的數列中尋找合适的位置插入，若沒有合适位置就保持不動，基準點後移。圖解：
注意：
- 當資料規模越小，直接插入排序越優
- 當數組越接近于有序，該排序算法越快
希爾排序：
void ShellSort(int* src, int n)//希爾排序:分組插排
{
int gap = n / 2;
int i, j;
for (gap=n /2; gap >= 1; gap /= 2)//gap為每次分的組數
{
for (i = gap; i < n; i++)
{
int tmp = src[i];
for (j = i; j - gap >= 0 && src[j -gap] > tmp; j -= gap)
{
src[j] = src[j-gap];
}
src[j] = tmp;
}
}
}
希爾排序是直接插入排序進階版本，它先将資料分組插排，使得數組趨于有序化，當分得組内個數特别小時，數組排序完成。圖解
三.選擇排序類
堆排序：
//向下調整算法，将下标為i的節點向下調整
void adjustDown(int* arr, int size, int n)//n為下标c
{
int cur = n;
while ((cur + 1) * 2 <= size)//隻要有左孩子存在就要進入循環
{
if ((cur + 1) * 2 + 1 > size)
{
n = cur * 2 + 1;//沒有右孩子，左孩子為孩子節點的最大值
}
else
{
if (arr[cur * 2 + 1] > arr[cur * 2 + 2])//找出右節點和左節點中的較大節點，并用n标記
{
n = cur * 2 + 1;
}
else
{
n = cur * 2 + 2;
}
}
if (arr[cur] < arr[n])//當左右孩子節點大于該節點時，向下調整該節點，否則，就已經形成大頂根，不再繼續循環
{
int tmp = arr[cur];
arr[cur] = arr[n];
arr[n] = tmp;
cur = n;//每次交換完之後将cur更新到n下标,使後面繼續向下調整
}
else
{
break;//孩子節點均小于根節點，已經構成大頂堆
}
}
}
void HeapSort(int* src, int n)
{
int i = n / 2 + 1;
//int j ;
for (i = n / 2-1; i >= 0; i--)
{
adjustDown(src, n, i); //構成大頂堆
}
//每次将堆中最大的元素（對頂）換下來放在最後，然後再調整一個大的上去，重複
for (i = n - 1; i > 0; i--)
{
SwapArgs(src + i, src);
adjustDown(src, --n, 0);//每次對交換後的節點向下調整，n--
}
}
主要借助向下調整算法構造大根堆，再不斷将最大元素出堆，得到排序。圖助了解：
四.分治類排序
歸并排序：
void Merging(int* src,int* tmp,int start,int end)
{
if (start >= end)
{
return;
}
int mid = start + (end - start) / 2;
int i = start, j = mid+1;
int k = start;
Merging(src, tmp, start, mid );
Merging(src,tmp,mid+1,end);
while (i<=mid && j<=end)
{
if (src[i] < src[j])
{
tmp[k] = src[i];
i++;
k++;
}
else
{
tmp[k] = src[j];
k++;
j++;
}
}
while (i <= mid)
{
tmp[k] = src[i];
i++;
k++;
}
while (j <= end)
{
tmp[k] = src[j];
k++;
j++;
}
for (i = start; i <= end; i++)//将合并好的資料回執到src内
//這裡end最後的下标，start是第一個下标，下标範圍易錯
{
src[i] = tmp[i];
}
}
void MergeSort(int* src, int n)//歸并排序
{
int* tmp = (int*)malloc(sizeof(int)*n);
Merging(src, tmp, 0, n-1);
free(tmp);
}
歸并思路類似與樹的後序周遊，先調整左右，再有序歸并在一起。相比于其他排序有一定的空間犧牲。
快速排序：
int PointerWay(int* src, int start, int end)
{
int point = src[start];
while (start<end)
{
while (start< end && src[end] >= point)
{
end--;
}
SwapArgs(&src[start], &src[end]);
while ( start<end && src[start] <= point)
{
start++;
}
SwapArgs(&src[start], &src[end]);
}
return start;
}
void Quicking(int*src, int start, int end)
{
int mid;//作為基準點
if (start < end)//滿足條件，快速排序遞歸調用
{
mid = PointerWay(src,start,end);
Quicking(src, start, mid-1);
Quicking(src, mid + 1, end);
}
}
void QuickSort(int* src, int n)//快速排序
{
Quicking(src,0, n-1);
}
快速排序基礎實作如上将第一個作為基準值，後續比較，将比基準值小的放在一側，比基準值大的放在另一側，再縮小排序範圍将左右已同樣方法排序。
最後說一個細節，對于插入排序，有的地方說不穩定，有地方說穩定，我通過簡短的學習認為選擇排序的是否穩定與實作方法有關。例如上面的實作就是穩定的，而如果将第六行和第八行代碼中的src[i - 1] > tmp改為src[i - 1] >= tmp之後，穩定性就不一定了！