以下是個人總結的排序算法，它分為以下幾個類：
交換排序：冒泡排序（BubbleSort）和快速排序（QuickSort）。
插入排序：直接插入排序和希爾排序（ShellSort）。
選擇排序：選擇排序（SelectSort）和堆排序（HeapSort）。
歸并排序：分治的思想。
基數排序：穩定快速的排序。
計數排序：對于待排序元素分布較集中的序列有優勢。
（一）交換排序：
void BubbleSort(int* arry, int size)
{
for (int i = 0; i < size - 1; i++)
{
for (int j = 0; j < size - i - 1; j++)
{
if (arry[j] > arry[j + 1])
{
swap(arry[j], arry[j + 1]);
}
}
}
}
//冒泡排序第一次優化（設置一個標志）
void BubbleSort(int* arry, int size)
{
bool swaped = false;
for (int i = 0; i < size; i++)
{
swaped = false;
for (int j = 0; j < size - i - 1; j++)
{
if (arry[j] > arry[j + 1])
{
swap(arry[j], arry[j + 1]);
swaped = true;
}
}
if (!swaped)
{
break;
}
}
}
//冒泡排序第二次優化（去除已經有序的區間）
void BubbleSort(int* arry, int size)
{
int lastswappos = size-1;
int lastswappos_temp = size-1;
for (int i = 0; i < size; i++)
{
lastswappos = lastswappos_temp;
for (int j = 0; j < lastswappos; j++)//每次冒泡到最后一次交換的位置
{
if (arry[j] > arry[j + 1])
{
swap(arry[j], arry[j + 1]);
lastswappos_temp = j;
}
}
if (lastswappos==lastswappos_temp)
{
break;
}
}
}冒泡排序是最簡單的交換排序，在這里我們給出了2種優化方式。第一種是設置一個標志位標志在一趟排序中是否有過排序，如果沒有則就排序完成，這種優化方式對于在一個數組的后半部分是有序的情況下提高了效率。第二種方式也相當于設置一個標志位，只是這個標志位是標志最后一次交換的數的下標。這種方法是有效的去除了已經有序的區間。
不管怎么優化，對于一般的數組冒泡排序的時間復雜度為O（N^2）。
快速排序：
//挖坑法
void QuickSort(vector<int> &arry, int left, int right)
{
if (left >= right)
return;
int lflag = left;
int rflag = right - 1;
int tmp = arry[left];
while (lflag < rflag)
{
while ((lflag < rflag) && arry[rflag] >= tmp)
{
rflag--;
}
arry[lflag] = arry[rflag];
while ((lflag < rflag) && arry[lflag] <= tmp)
{
lflag++;
}
arry[rflag] = arry[lflag];
}
swap(arry[lflag], tmp);
QuickSort(arry, left, rflag - 1);//左子區間
QuickSort(arry, rflag + 1, right);//右子區間
}
//prev/cur法 [left,right]
void QuickSort(vector<int> &arry, int left, int right)
{
//遞歸結束條件
if (left >= right)
return;
int cur = left;
int prev = cur - 1;
int key = arry[right];
while (cur != right)
{
if (arry[cur] < key && cur != (++prev))
{
swap(arry[cur], arry[prev]);
}
cur++;
}
swap(arry[++prev],arry[right]);
QuickSort(arry, left, prev - 1);
QuickSort(arry, prev + 1, right);
}
//三數取中法
//三數取中法（選取left，right，mid中不大不小的那個值作為key，和arry[right]交換）
int FindMidValue(vector<int> &arry, int left, int right)//[p,q]
{
int mid= left-( left - right ) / 2;
if (arry[left] > arry[mid])
{
if (arry[mid] > arry[right])
{
swap(arry[right], arry[mid]);
}
else if (arry[right] > arry[left])
{
swap(arry[right], arry[left]);
}
}
else if (arry[left] > arry[right])
{
swap(arry[right], arry[left]);
}
return arry[right];
}
void QuickSort(vector<int> &arry, int left, int right)
{
if (left >= right)
return;
int lflag = left;
int rflag = right;
int key = FindMidValue(arry, lflag, rflag);
while (lflag < rflag)
{
while (lflag < rflag && arry[lflag] <= key)
{
lflag++;
}
if (lflag < rflag)
{
arry[rflag] = arry[lflag];
rflag--;
}
while (lflag < rflag && arry[rflag] >= key)
{
rflag--;
}
if (lflag < rflag)
{
arry[lflag] = arry[rflag];
lflag++;
}
}
arry[lflag] = key;
QuickSort(arry, left, lflag - 1);
QuickSort(arry, lflag + 1, right);
}快速排序是利用了劃分子問題的思想。每次選取區間的第一個數據作為中間值，將大于中間值的數據放在右邊，否則放在左邊。再將中間值的左右邊看成一個子區間，遞歸的劃分子區間，直到區間的左邊下標大于或者等于右邊下標結束。
prev/cur法是利用兩個指針，prev和cur，cur一直找小于key值得下標和prev下標的值交換。
而三數取中法是對于快速排序的優化，有時候常常會出現很尷尬的情況：我們選取最左或最右的值為key值，偏偏這個值是整個待排序列的最小或最大的值，這種情況下快速排序就是效率最慢的情況，變成了慢速排序。這時候三數取中法就幫助我們避免這種情況。
快速排序是效率比大部分排序算法的速度要快?？炫乓话闱闆r下是最快的排序，而且具有穩定性。但是快速排序是一個遞歸思想，顯然，對于內存有限的機器來說它不是一個好的選擇。對于很長很長的數組來說也不是一個好的選擇，遞歸的額層數越多，效率越低。
（二）選擇排序：
一般的選擇排序
void SelectSort(int* arry, int size)
{
assert(arry);
int flag = 0;
while (flag != size - 1)
{
int min = flag;
for (int i = flag + 1; i < size; i++)
{
if (arry[i] < arry[min])
{
min = i;
}
}
swap(arry[min], arry[flag]);
flag++;
}
}一般的選擇排序算法的時間復雜度為O（N^2）。
堆排序
void AdjustDown(int* a, size_t size, size_t parent)//下調函數
{
size_t child = parent * 2 + 1;
while (child < size)
{
if (child + 1 < size&&a[child] < a[child + 1])
++child;
if (a[parent] < a[child])
{
swap(a[parent], a[child]);
parent = child;
child = parent * 2 + 1;
}
else
break;
}
}
void HeapSort(int* a, size_t size)
{
//建堆
for (int i = (size - 2) / 2; i >= 0; --i)
//i不能定義為size_t除法會溢出，翻轉成一個很大的數
{
AdjustDown(a, size, i);
}
for (size_t i = 0; i < size; ++i)
{
swap(a[0], a[size - 1 - i]);
AdjustDown(a, size - i - 1, 0);
}
}堆排序是利用大頂堆的性質，可以快速的找出最大值。依次找出最大值，排序完成。時間復雜度為
O（N*lgN）。
（三）插入排序
直接插入排序：
void InsertSort(int *a, size_t size)
{
assert(a);
for (size_t i = 1; i < size; ++i)
{
int tmp = a[i];
size_t j = i;
while (j > 0 && tmp < a[j - 1])
{
a[j] = a[j - 1];
j--;
}
a[j] = tmp;
}
}在數組前面的有序序列里找到合適的位置將待插入數據插入，時間復雜度為O（N^2）。
希爾排序：
//gap為gap/2
void ShellSort(int *a,int size)
{
int gap = size / 2;
while (1 <= gap)
{
// 把距離為 gap 的元素編為一個組，掃描所有組
for (int i = gap; i < size; i++)
{
int j = 0;
int temp = a[i];
// 對距離為 gap 的元素組進行排序
for (j = i - gap; j >= 0 && temp < a[j]; j = j - gap)
{
a[j + gap] = a[j];
}
a[j + gap] = temp;
}
gap = gap / 2; // 減小增量
}
}
//gap為gap/3+1
void HellSort(vector<int>& a, int size)
{
int gap = size;
while (gap > 1)
{
gap = gap / 3 + 1;
for (size_t i = 0; i <size - gap; ++i)
{
int end = i;
int tmp = a[end + gap];
while (end >= 0 && a[end] > a[end+gap])
{
a[end + gap] = a[end];
a[end] = tmp;
end -= gap;
}
}
}
}gap是間隔增量。它控制序列向有序發展。
我們分割待排序記錄的目的是減少待排序記錄的個數，并使整個序列向基本有序發展。因此，我們需要采取跳躍分割的策略：將相距某個“增量”的記錄組成一個子序列，這樣才能保證在子序列內分別進行直接插入排序后得到的結果是基本有序而不是局部有序。
希爾排序的時間復雜度是在O（N^1.25）~O（N^1.66）之間。希爾排序在逆序時效果最好，有序時效果最差，還不如直接排序。
（四）歸并排序
歸并排序是建立在分治思想上的一種排序方法，將大的問題劃分成小問題，逐個解決。我們在排序的時候也時常用到這種思想，比如一個待排序序列很大很大的時候，我們需要將這個大序列劃分成一個個的小序列，歸并排序將是一個非常好的選擇。
void MergeCell(int* arry,int* tmp, int left1, int right1, int left2, int right2)
{
int index = 0;
int begin = left1;
while (left1 <= right1&&left2 <= right2)
{
if (arry[left1] < arry[left2])
{
tmp[index++] = arry[left1++];
}
else
{
tmp[index++] = arry[left2++];
}
}
while (left1 > right1&&left2 <= right2)
{
tmp[index++] = arry[left2++];
}
while (left2 > right2&&left1 <= right1)
{
tmp[index++] = arry[left1++];
}
for (int i = 0; i < index; ++i)
{
arry[begin++] = tmp[i];
}
}
void Merge_(int* arry, int* tmp, int left, int right)
{
if (left < right)
{
int mid = left - (left - right) / 2;
Merge_(arry, tmp, left, mid);
Merge_(arry, tmp, mid+1, right);
MergeCell(arry, tmp, left, mid, mid + 1, right);
}
}
void MergeSort(int *arry, int size)
{
int left = 0;
int right = size - 1;
int* tmp = new int[size];
Merge_(arry, tmp, left, right);
for (int i = 0; i < size; ++i)
{
cout << arry[i] << " ";
}
}（五）計數排序
計數排序的方法就有點簡單粗暴了，計數排序適合那種待排序序列元素分布比較叫集中的序列，如果序列的最大值和最小值相差很大的話，效率實在是低。
void CountSort(int* arry, int size)
{
//找出最大和最小的值，max-min作為開辟空間的大小
int min = arry[0], max = arry[0];
for (int i = 0; i < size; ++i)
{
if (arry[i] < min)
min = arry[i];
if (arry[i] > max)
max = arry[i];
}
int* count = new int[max - min + 1];
memset(count, 0, (max - min + 1)*sizeof(int));
//統計數組中出現數字的次數
for (int i = 0; i < size; ++i)
{
++count[arry[i] - min];
}
int index = 0;
//遍歷計數數組，只要值不為一，就將數組的下標+min拷貝進原始數組，原始數組已經沒用了
for (int i = 0; i < max - min + 1; ++i)
{
while (count[i]--)
{
arry[index++] = min + i;
}
}
}（六）基數排序：
基數排序有LSD和MSD兩種方法，LSD是從低位向高位排序。MSD是從高位向地位排序。這里以LSD實現
//LSD法 適合位數少的排序(此程序排不了含有負數的序列)
void RadixSort(int* arry, int size)
{
int time = 1;
int radix = 10;
//統計最大的位數
for (int i = 0; i < size; ++i)
{
if (arry[i] > radix)
{
time++;
radix *= 10;
}
}
int* count = new int[10];
int* bucket = new int[size];
radix = 1;
//控制排序的次數，從低位排到高位
for (int i = 0; i < time; ++i)
{
memset(count, 0, 10 * sizeof(int));
memset(bucket, 0, size * sizeof(int));
for (int j = 0; j < size; ++j)
{
//統計每個桶中有多少個數據
++count[(arry[j]/radix) % 10];
}
for (int k = 1; k < 10; ++k)
{
count[k] = count[k] + count[k - 1];
}
for (int k = 0; k < size; ++k)
{
int index = count[(arry[k] / radix) % 10 - 1];
while (bucket[index] != 0)
{
index++;
if (index >= size)
{
index = 0;
}
}
bucket[index] = arry[k];
}
for (int k = 0; k < size; ++k)
{
arry[k] = bucket[k];
}
radix *= 10;
}
}
計數排序和基數排序是非比較排序，他們都有適用的場合，熟練掌握多種排序算法是有必要的。
博主的知識有限，文章難免會有紕漏，請多多指正。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
