算法穩定性：
通俗了解------A(1)=80；A(2) = 80;
排序前A(1)在A(2)前，排序後A(1)還在A(2)前則穩定，否則不穩定
代碼中使用到的幾個函數和指針：
typedef int(*Compare)(int left, int right); //函數指針，可靈活選擇排序的順序
int Less(int left, int right)
{
return left < right;
}
int Greater(int left, int right)
{
return left > right;
}
void Swap(int *left, int* right)
{
int tmp = *left;
*left = *right;
*right = tmp;
}
冒泡排序：多在資料規模較小的時候使用 時間複雜度O(n^2) 空間複雜度O(1) 穩定排序
思想：
每次循環比較相鄰的兩個元素的大小，将較大（小）的往後冒，每一趟下來最後一個元素都是最大的，每排一趟，最後的元素下标向前移一位，最終完成排序。
void BubbleSort(int array[], int size, Compare com)
//兩兩進行比較，将大的放置到後面，第一趟下來最後的值就是最大的值，依次類推，完成排序
{
int i = 0;
int j = 0;
int flag = 0; //設定标記，優化冒泡
for (; i < size - 1; i++) //最後一個元素不需要冒泡
{
int flag = 0;
for (j = 0; j < size - i - 1; j++)
{
if (com(array[j], array[j + 1]))
{
Swap(&array[j], &array[j + 1]);
flag = 1;
}
}
if (flag != 1)
{
break;
}
}
}
選擇排序：//元素重複較多時間複雜度O(n^2) 空間複雜度O(1) 不穩定
思想：
内層循環找到最大的元素，标記下标，外層循環控制将最大的元素與最後一個位置的元素進行交換，直到有序
void SelectSort(int array[], int size, Compare com) //初級版本
{
//先預設的把首位置下标為最小值下标。然後周遊後面的數字，出現比這個值還小的數
//就把那個數的下标賦給最小值下标。
//循環周遊直到有序
int i = 0;
int j = 0;
int min = 0;
for (i = 0; i < size - 1; i++)
{
min = i; //預設首元素最小
for (j = i + 1; j < size; j++)
{
if (com(array[min], array[j])) //如果有數比m下标中的數還小，就把這個數的下标放到min中
{
min = j;
}
}
if (min != i) //若是同一位置，不需要交換
Swap(&array[i], &array[min]);
}
}
void SelectSort3(int array[], int size) //優化版
{
int i = 0;
int maxPos = 0; //标記最大的
int minPos = 0; //标記最小的
int begin = 0;
int end = size - 1;
while (begin < end)
{
i = begin;
minPos = begin;
maxPos = begin;
for (; i <= end; i++) //周遊分别找到最大的和最小的下标
{
if (array[i] < array[minPos])
minPos = i;
if (array[i] > array[maxPos])
maxPos = i;
}
if (minPos != begin) //最小的不在最開始的位置
{
Swap(&array[minPos], &array[begin]);
}
if (maxPos == begin)
{
maxPos = minPos;
}
if (maxPos != end) //最大的不在最後的位置
{
Swap(&array[maxPos], &array[end]);
}
begin++;
end--;
}
}
插入排序：// 資料元素接近有序、資料量少時間複雜度O(n^2)空間複雜度O(1)穩定
思想：
預設第1個元素前的元素都已經有序，将之後的元素全部插入到前面
插入方法：
标記待插數，與前面的元素比較，找到插入的位置，将要插入位置的元素全向後搬移，騰出位置插入待插數，依次循環直到有序
void InsertionSort(int array[], int size, Compare com) //普通版
{
int i = 0;
int end = 0;
int tmp = 0;
for (i = 1; i < size; i++)
{
tmp = array[i]; //待測數
end = i - 1; //待測數的前一個數即是有序數的最後一個數
while(end >= 0 && com(array[end], tmp)) //找到要插入的位置
{
array[end + 1] = array[end]; //不是要插入的位置，元素向後搬移
end--;
}
array[end + 1] = tmp; //插入
}
}
void BinInsSort(int array[], int size) //優化版，二分查找法
{
int i = 0;
int j = 0;
int tmp = 0;
int low = 0;
int high = 0;
int mid = 0;
// 1 2 3 4 5 6 7 8 9 0
for (i = 1; i < size; i++)
{
tmp = array[i];
low = 0;
high = i - 1;
while (low <= high) // 當up移動到low左側時，結束循環。注意，此處一定要帶有等号，否則排序會失敗(第一次排序可驗證)
{
mid = low + (high - low)/2; //取中
if (tmp < array[mid]) //當待插入元素小于中間位置的元素時
{
high = mid - 1; //待插入元素應該插在在前半個表中
}
else
{
low = mid + 1;
}
}
for (j = i - 1; j >= low; j--) //從要插入元素的位置開始将元素依次搬移
{
array[j + 1] = array[j];
}
array[low] = tmp; //插入
}
}
希爾排序：//資料元素無序、資料量大時間複雜度O(N^1.3)空間複雜度O(1)不穩定
思想：
分組進行插入排序
先定義一個步長序列，依次遞減至一，然後按照步長将資料分組，所有距離為步長倍數的數分為一組，在組内對資料進行插入排序，步長序列遞減。
void ShellSort(int array[], int size)
{
int end = 0;
int tmp = 0;
int gap = size;
//生成步長序列
while(gap > 1) //gap > 1
{
gap = gap / 3 + 1; //調整步長序列
int i = gap;
//插入排序
for (; i < size; i++) //i一次走一步直至所有元素都排好序
{
tmp = array[i]; //待測數
end = i - gap; //有序數列的最後一個元素
while (end >= 0 && array[end] > tmp) //找到要插入的位置
{
array[end + gap] = array[end]; //
end -= gap;
}
array[end + gap] = tmp; //插入
}
}
}
堆排序：//資料規模較大時
思想：
先将所有元素構成大根堆将堆頂元素和堆最後一個元素交換，交換後重新調整堆為大根堆依次類推直到有序。
函數分為調整部分和排序部分。
void AdjustHeap(int array[], int size, int root, Compare com)//小堆----->向下調整
{
int child = root * 2 + 1; //左孩子
while (child < size)
{
if (child + 1 < size && com(array[child + 1], array[child]))//找到左右孩子中小的,标記為child
{
child += 1;
}
if (com(array[child], array[root])) //判斷是否需要交換位置
{
Swap(&array[root], &array[child]);
root = child;
child = root * 2 + 1;
}
else
{
break;
}
}
}
void HeapSort(int array[], int size, Compare com)
{
int end = size - 1; //标記最後一個結點的下标
int LastRoot = (size - 2) >> 1; //最後一個非葉子節點
while (LastRoot >= 0) //建堆
{
AdjustHeap(array, size, LastRoot, com);
LastRoot--;
}
while (end > 0) //最後一個節點不交換 //堆的删除
{
Swap(&array[0], &array[end]); //先交換
AdjustHeap(array, end, 0, com); //在調整（從end的前一個節點開始調）
end--; //在向前移
}
}
快速排序：資料接近有序時快速排序算法不适用，效率低
标記一個關鍵碼，将比關鍵碼小的元素，向前搬移，将比關鍵碼大的元素向後搬移。
優化：
1. 三值取中确定基準值 (傳回中間值的索引)
取第一個元素，最後一個元素，中間的元素判斷大小
2. 當區間比較小時，就可以使用插入排序，直接對這個區間進行排序進而有效減少遞歸次數
Right - left < 16 -----------------插入排序
int partion(int array[], int left, int right)//雙指針相向移動
{
int key = array[right - 1];
int begin = left;
int end = right - 1;
while (begin < end)
{
while (begin < end && array[begin] <= key)//從左往右找最大的//begin<end防止在查找的時候begin越界
begin++;
while (begin < end && array[end] >= key) //從右往左找最小的
end--;
//找到一個最大的和最小的
if (begin < end) //不在同一位置
{
Swap(&array[begin], &array[end]);
}
}
//begin 和 end 走到同一位置 ，若不是最後位置交換
if (begin != right - 1)
{
Swap(&array[begin], &array[right - 1]);
}
return begin;
}
int partion2(int array[], int left, int right) //挖坑法
{
int key = array[right - 1];
int begin = left;
int end = right - 1;
while (begin < end)
{
while (begin < end && array[begin] <= key)//從左往右找最大的//begin<end防止在查找的時候begin越界
begin++;
if (begin < end) //填坑
array[end] = array[begin];
while (begin < end && array[end] >= key) //從右往左找最小的
end--;
if (begin < end)
array[begin] = array[end];
}
//begin, end到同一位置
array[end] = key; //填最後一個坑
return begin;
}
int partion3(int array[], int left, int right)//雙支指針前移法
{
int key = array[right - 1];
int begin = left - 1;//此處不會發生越界問題，并未通路數組-1處的元素
int end = left;
//定義兩個指針一個begin和end，從左往右周遊，end的值小于基準值時讓begin前進一個位置
//并檢測是否與end為同一位置，若不是則交換位置上的值，end就是檢測所有資料中比基準值小的值
//利用begin将其向前挪，循環結束時需交換begin位置的元素和基準值
while(end < right)//end指向目前元素，每次循環都要往前走，直到周遊完序列
{
if (array[end] < key)
{
//end處的元素小于key，begin前移，并判斷
begin++;
if (begin != end)
{
Swap(&array[begin], &array[end]);
}
}
end++;
}
if (array[++begin] != key) //此時begin的值一定小于key,begin的下一個元素大于等于key
//交換begin+1 和最後的元素
Swap(&array[begin], &array[right - 1]);
return begin ;
}
void QuickSort(int array[], int left, int right) //遞歸版本
{
int div = 0;
if (left < right)
{
div = partion3(array, left, right);
QuickSort(array, left, div);
QuickSort(array, div + 1, right);
}
}
void QickSortByLoop(int array[], int size) //非遞歸版本，借助棧
{
Stack s;
int left = 0;
int mid = 0;
int right = size;
assert(array);
if (size <= 1)
{
return;
}
//用棧儲存每一個待排序子串的首尾元素下标，
//下一次while循環時取出這個範圍，對這段子序列進行partion操作
InitStack(&s);
PushStack(&s, left); //左入棧
PushStack(&s, right); //右入棧
while (!StackEmpty(&s))//棧不為空
{
right = TopStack(&s); //右出棧
PopStack(&s);
left = TopStack(&s); //左出棧
PopStack(&s);
if (left < right)
{
mid = partion3(array, left, right);
PushStack(&s, left);
PushStack(&s, mid);
PushStack(&s, mid + 1);
PushStack(&s, right);
}
}
}
歸并排序： 外部排序，适用于資料量大的情況
假設數組A有N個元素，那麼可以看成數組A是又N個有序的子序列組成，每個子序列的長度為1，然後再兩兩合并，得到了一個 N/2 個長度為2或1的有序子序列，再兩兩合并，如此重複，值得得到一個長度為N的有序資料序列為止。
合并算法：即合并兩個有序的子序列，設定兩個指針，p1,p2,将p1,p2所指向元素當中值較小的不斷複制到臨時空間，最後把沒複制完的子序列的剩餘yuan複制到臨時空間
void _MergeData(int* array, int left, int mid, int right, int* tmp) //左閉右開區間
{
int begin1 = left;
int end1 = mid;
int begin2 = mid;
int end2 = right;
int index = left;
//兩個分組中都有元素時
while (begin1 < end1 && begin2 < end2)
{
if (array[begin1] <= array[begin2]) //将兩部分元素中較小的指派到臨時空間中
{
tmp[index++] = array[begin1++];
}
else
{
tmp[index++] = array[begin2++];
}
}
while (begin1 < end1) //将剩餘元素指派到臨時空間中
tmp[index++] = array[begin1++];
while (begin2 < end2)
tmp[index++] = array[begin2++];
}
void _MergeSort(int* array, int left, int right, int* tmp)
{
//目前分組中隻有一個元素時歸并結束
if (right - left > 1) //遞歸出口
{
int mid = left + ((right - left) >> 1); //取中間值
_MergeSort(array, left, mid, tmp); //拆分
_MergeSort(array, mid, right, tmp);
_MergeData(array, left, mid, right, tmp); //歸并
memcpy(array + left, tmp + left, sizeof(array[0])*(right - left));//将目前tmp數組中的元素拷貝回array
}
}
void MergeSort(int array[], int size)
{
int *tmp = (int*)malloc(sizeof(array[0])*size);
if (NULL == tmp)
{
return;
}
if (size <= 1)
{
return;
}
_MergeSort(array, 0, size, tmp);
free(tmp);
}
void MergeSortNor(int array[], int size)
{
//設定步長從1開始，每次遞增二倍
int gap = 1;
int i = 0;
int left = 0;
int right = size;
int* tmp = (int*)malloc(sizeof(array[0])*size);
if (NULL == tmp)
{
return;
}
while (gap < size)
{
int mid = left + ((right - left) >> 1);
for (i = 0; i < size; i += 2 * gap)
{
left = i;
mid = left + gap;
if (mid > size) //mid越界
mid = size;
right = mid + gap;
if (right > size) //right越界
right = size;
_MergeData(array, left, mid, right, tmp); //資料排序
}
memcpy(array, tmp, sizeof(array[0])*size);
gap *= 2;
}
free(tmp);
}
計數排序：适用于資料量大，但是大小比較集中的資料排序。
1.确定資料大小
2.配置設定适當空間
3.統計資料元素出現次數，将結果儲存至臨時空間
4.資料回收----将tmp中的資料反向放回array數組中
void CountSort(int array[], int size)
{
int i = 0;
int MaxValue = array[0];
int MinValue = array[0];
int TmpSize = 0;
int Index = 0;
//确定大小
for (i = 0; i < size; i++)
{
if (array[i] < MinValue)
{
MinValue = array[i];
}
if (array[i] > MaxValue)
{
MaxValue = array[i];
}
}
//配置設定空間
TmpSize = MaxValue - MinValue + 1;
int* tmp = (int*)malloc(sizeof(int)* TmpSize);
if (NULL == tmp)
{
return;
}
memset(tmp, 0x00, sizeof(int)*TmpSize);
//統計每個資料個數，并将其個數放置進tmp的指定位置
for (i = 0; i < size; i++)
{
tmp[array[i] - MinValue]++;
}
//資料回收---将tmp數組的資料重新放回array
i = 0;
while (i < TmpSize)
{
while (tmp[i]--)
{
array[Index++] = i + MinValue;
}
i++;
}
free(tmp);
}
基數排序：
LSD:低關鍵碼優先----從數字的低位到高位依次排序
MSD:高關鍵碼優先---從高高位到低位依次排序
LSD:
得到數組的最大的數的位數，從個位開始，将資料依次放入指定的桶中，再将桶中的元素拷貝回原數組，在次對原數組中的數的高一位進行處理。
統計每個桶中有效元素個數
計算每個桶的起始位址
将元素按照目前位置放入桶中
對元素進行回收--------将桶中元素拷回原數組
将桶中的資料拷貝回原數組，則會轉化為排序下列資料： 281， 321， 262， 374， 255， 655， 987， 198， 789。再對該組資料按十位進行排序。
将桶中的資料拷貝回原數組，則會轉化為排序下列資料：321， 255， 655， 262， 374， 281， 987， 789， 198。再對該組資料按百位進行排序。
最後形成有序資料： 198,255， 262， 281， 321， 374， 655 ， 789， 987.
代碼：
void _RadixSortLSD(int array[], int size, int* bucket) //M位 個數N
{
int i = 0;
int bitIdx = 0;
int bitIdxNum = 0;
int radix = 1;
bitIdxNum = GetbitNum(array, size);
for (bitIdx = 0; bitIdx < bitIdxNum; bitIdx++)
{
int count[10] = { 0 }; //有效元素個數
int addrStart[10] = { 0 }; //起始位址
//統計每個桶中元素的個數
for (i = 0; i < size; i++)
{
count[array[i] / radix % 10]++;
}
//計算每個桶的起始位址
for (i = 1; i < 10; i++)
{
addrStart[i] = addrStart[i - 1] + count[i - 1];
}
//将元素按照目前位置放入對應的桶中
for (i = 0; i < size; i++)
{
int bucketNo = array[i]/ radix % 10; //桶号
bucket[addrStart[bucketNo]++] = array[i];//先利用桶号計算出起始位址，将元素放入該起始位址處
//然後目前桶的起始位址+1
}
//對元素進行回收
memcpy(array, bucket, sizeof(array[0])* size);
radix *= 10;
}
}
void RadixSort(int array[], int size)
{
if (size < 2)
{
printf("資料量小于2，無需排序！\n");
return;
}
int* bucket = (int*)malloc(sizeof(array[0])*size);
if (NULL == bucket)
{
return;
}
_RadixSortLSD(array, size, bucket);
free(bucket);
}
MSD: 此處需借助遞歸思想，先對将資料按最高位的大小放入指定的桶中，然後對每個桶的低位遞歸的進行置桶和拷貝操作。
代碼：
void _RadixSortMSD(int array[], int left, int right, int* bucket, int bitNum)//高關鍵碼優先，采用遞歸的方式
{
int i = 0;
int radix = pow(10, bitNum);
int count[10] = { 0 }; //有效元素個數
int addrStart[10] = { 0 }; //起始位址
if (bitNum < 0)
{
return;
}
//統計每個桶中元素的個數
for (i = left; i < right; i++)
{
count[array[i] / radix % 10]++;
}
//計算每個桶的起始位址
for (i = 1; i < 10; i++)
{
addrStart[i] = addrStart[i - 1] + count[i - 1];
}
//将元素按照目前位置放入對應的桶中
for (i = left; i < right; i++)
{
int bucketNo = array[i] / radix % 10; //桶号
bucket[addrStart[bucketNo]++] = array[i];//先利用桶号計算出起始位址，将元素放入該起始位址處
//然後目前桶的起始位址+1
}
//對元素進行回收
memcpy(array+ left, bucket, sizeof(array[0])* (right - left)); //拷貝時拷貝到array的對應位置
for (i = 0; i < 10; i++)//排每個桶元素的低一位
{
int begin = addrStart[i] - count[i];//目前桶的起始位址 = 目前桶的位址 - 目前桶的元素個數
int end = addrStart[i];
if (begin + 1 >= end) //目前桶的元素隻有一個或小于1排序下一個桶
{
continue;
}
_RadixSortMSD(array, begin, end, bucket, bitNum--);
}
}
void RadixSort(int array[], int size)
{
if (size < 2)
{
printf("資料量小于2，無需排序！\n");
return;
}
int* bucket = (int*)malloc(sizeof(array[0])*size);
if (NULL == bucket)
{
return;
}
_RadixSortMSD(array, 0, size, bucket, GetbitNum(array, size) - 1);
free(bucket);
}