一：插入排序：
思路：end指向有序區間結束位置，插入資料比[end]大，就插在[end+1],比[end]小，end–，直至比[end]大或者end<0。
代碼如下：
void InsertSort(int *a, int n)
{
assert(a);
int end = ;
for (int i = ; i < n-; i++)//注意：i<n-1
{
end = i;
int tmp = a[end+];//需要将插入資料進行儲存
while (end >= && a[end] > tmp)
{
//如果插入資料在和前面有序區間資料進行比較最小，
//将會有end=-1,那麼也可以歸為[end+1]=[-1+1]=tmp;
a[end + ] = a[end];//将大的資料向後移動
end--;
}
a[end + ] = tmp;
}
}
二：希爾排序：
希爾排序是直接插入排序的優化，對于資料量大及資料逆序相對直接插入排序效率高：分為兩步：
1.預排序：使資料接近有序，大的資料盡量向後移動，小的資料盡量向前移動
2.當gap=1時，即為直接插入排序
代碼如下：
void ShellSort(int *a, int n)
{
assert(a);
int end = ;
int gap = n;//間距
while (gap > )//如果大于0，将是死循環
{
gap = gap / + ;//不斷縮小gap,加1使最後一次為直接插入排序
for (int i = ; i < n - gap; i++)//如果是i+=gap,需要有一個外循環，循環gap次
{
end = i;
int tmp = a[end + gap];//要排的資料
while (end >= && a[end] > tmp)
{
a[end + gap] = a[end];//大的資料向後移動
end -= gap;
}
a[end + gap] = tmp;//end小于0或者[end]<tmp，tmp在[end+gap]插入
}
}
}
交換兩個數及列印函數：
void print(int *a, int n)
{
for (int i = ; i < n; i++)
{
printf("%d ", a[i]);
}
printf("\n");
}
void Swap(int *a1,int *a2)
{
int c = *a1;
*a1 = *a2;
*a2 = c;
}
三：選擇排序：
思路為：找到一段區間内的最大值和最小值，将最大值放在區間右邊，最小值放在區間左邊，然後區間縮小，重複上述步驟,直至begin=end,排序結束
代碼如下：
void SelectSort(int *a, int n)
{
assert(a);
int begin = , end = n-, max = , min = ;
while (begin < end)
{
min = max = begin;
for (int i = begin; i <= end; i++)
{
if (a[min] > a[i])
min = i;
if (a[max] < a[i])
max = i;
}
Swap(&a[begin], &a[min]);
if (max == begin)
max = min;
//特殊情況，當begin和max重合
//[min]和[begin]交換後，begin存的是最小值，那[max]也就變為最小值，是以當[begin]和[min]交換後，max=min
Swap(&a[end], &a[max]);
begin++;
end--;
}
}
四：冒泡排序：
是指将相鄰兩個數進行比較然後交換，一趟冒泡可以将最大的數放在最後。
void BubbleSort(int *a, int n)
{
assert(a);
for (int i = ; i < n; i++)
{
int flag = ;
for (int j = ; j < n - i; j++)
{
if (a[j] > a[j + ])
{
Swap(&a[j], &a[j + ]);
flag = ;
}
}
if (flag == )//如果有序，将不會進入循環
break;
}
}
五：堆排
如果是升序數組在邏輯結構上是大堆。一趟排序是将堆頂元素和最後一個元素交換，然後再對剩餘元素建大堆，重複上述操作。
void AdjustDown(int *a, int root,int n)//向下調整
{
int parent = root;
int child = parent * + ;
while (child < n)
{
if (child + < n && a[child] < a[child + ])
child++;
if (child < n && a[parent] < a[child])
{
Swap(&a[parent], &a[child]);
parent = child;
child = parent * + ;
}
else
break;
}
}
//堆排
void HeapSort(int *a, int n)
{
assert(a);
int i = ;
for (i = (n - - ) / ; i >= ; i--)
{
AdjustDown(a, i, n);//将第一個元素向下調整為最大元素
}
int size = n;
for (i = ; i < n; i++)
{
Swap(&a[], &a[size - ]);//将最大元素和數組最後一個元素交換
size--;//再排序size-1個元素
AdjustDown(a, , size);
}
}
六：快排
快排：一趟排序将key放在排好序後的位置，即key左邊都比key小，key右邊都比key大。
下面将用三種方法快排：
1.左右指針法(hoare版本)
解釋相遇點：（為什麼Key就放在begin和end相遇點？）
整體如何排序？
代碼如下：
int GetMidIndex(int *a, int left, int right)//三數取中,找到三個數中位數
{
assert(a);
int mid = left + (right - left) / ;
if (a[left] < a[mid])//左比中小
{
if (a[mid] < a[right])
return mid;//mid是中位數
else if (a[left] > a[right])
return right;
else
return left;
}
else
{
if (a[mid] > a[right])
return mid;
else if (a[left] > a[right])
return right;
else
return left;
}
}
int partsort1(int *a, int left, int right)//左右指針即hoare版本
{
assert(a);
int begin = left;
int end = right;
int mid = GetMidIndex(a, left, right);
//找到中位數，和[right]交換，盡量為完全二叉樹，時間複雜度：N*logN
Swap(&a[mid], &a[right]);
int key = a[right];
while (begin < end)
{
//begin找大
while (begin < end && a[begin] <= key)
begin++;
//end找小
while (begin < end && a[end] >= key)
end--;
if (begin < end)
Swap(&a[begin], &a[end]);
}
Swap(&a[begin], &a[right]);//不能和key交換，因為key是局部變量
return begin;
}
2.挖坑法：
代碼如下：
int partsort2(int *a, int left, int right)//挖坑
{
assert(a);
int begin = left;
int end = right;
int key = a[right];
while (begin < end)
{
while (begin < end && a[begin] <= key)
begin++;
a[end] = a[begin];//[end]是坑
while (begin < end && a[end] >= key)
end--;
a[begin]=a[end];//[begin]是坑
}
a[begin] = key;
return begin;
}
3.前後指針法
代碼如下：
int partsort3(int *a, int left, int right)//前後指針
{
assert(a);
int prev = left - ;
int cur = left;
int key = a[right];
while (cur < right)
{
if (a[cur] < key && ++prev != cur)
Swap(&a[prev], &a[cur]);
++cur;
}
Swap(&a[++prev], &a[right]);
return prev;
}
快排遞歸：
void QuickSort(int *a, int left, int right)
{
//遞歸思想：适用于很多資料
assert(a);
if (left >= right)//注意：必須加>，否則棧溢出
return;
if (right - left + < )//小區間優化：當資料個數（閉區間需要加1）小于20時，直接插入排序
{
InsertSort(a + left, right - left + );
return;
}
int div = partsort1(a, left, right);
//int div = partsort2(a, left, right);
//int div = partsort3(a, left, right);
printf("div:%d\n", div);
//left div-1
QuickSort(a, left, div - );
//div+1 right
QuickSort(a, div + , right);
}
快排非遞歸：
棧的相關操作可參考這篇部落格：https://mp.csdn.net/postedit/80022185
void QuickSortNonR(int *a, int left, int right)//快排非遞歸
{
assert(a);
if (left >= right)
return;
Stack st;
StackInit(&st);
int topl;//棧頂的左
int topr;//棧頂的右
int div = ;
//進棧順序：先左後右
StackPush(&st, left);
StackPush(&st, right);
while (StackEmpty(&st))
{
//出棧先右後左
topr = StackTop(&st);
StackPop(&st);
topl = StackTop(&st);
StackPop(&st);
div = partsort1(a, topl, topr);
// topr div-1 div div+1 topr
//div的左邊區間先入棧，右邊區間後入棧，但是棧先進後出，先排右邊區間再排左邊區間
if (topl < div - )
{
StackPush(&st, topl);
StackPush(&st, div - );
}
if (div + < topr)
{
StackPush(&st, div + );
StackPush(&st, topr);
}
}
}
七：歸并排序
屬于外排序：可以在磁盤上排序 。
将待排序的元素序列分成兩個長度相等的子序列，對每一個子序列進行排序，然後将他們合并成一個序列。
代碼如下：
void _MergeSort(int *a, int left, int right, int *tmp)
{
if (left >= right)
return;
if (right - left + < )
{
InsertSort(a + left, right - left + );//小區間優化：當資料個數（閉區間需要加1）小于20時，直接插入排序
return;
}
int mid = left + (right - left) / ;
_MergeSort(a, left, mid, tmp);//将左邊劃分為有序
_MergeSort(a, mid + , right, tmp);//将右邊劃分語序
int begin1 = left, end1 = mid;
int begin2 = mid + , end2 = right;
int index = left;
// begin1--end1是有序區間 begin2--end2是有序區間
//将兩段有序區間合并為一段有序區間
while (begin1 <= end1 && begin2 <= end2)
{
//把小的資料放在tmp中
if (a[begin1] <= a[begin2])//等于号保證歸并是穩定的
{
tmp[index] = a[begin1];
index++;
begin1++;
}
else
{
tmp[index] = a[begin2];
index++;
begin2++;
}
}
if (begin1 > end1)//說明begin2-end2還有資料
{
while (begin2 <= end2)
tmp[index++] = a[begin2++];
}
else //說明begin1 - end1還有資料
{
while (begin1 <= end1)
tmp[index++] = a[begin1++];
}
index = left;
while (index <= right)//由于tmp隻是個臨時數組，需要将有序資料重新放到數組a中
{
a[index] = tmp[index];
index++;
}
}
void MergeSort(int *a, int n)
{
assert(a);
int *tmp = (int *)malloc(sizeof(int)*n);
_MergeSort(a, , n - , tmp);//tmp是臨時數組
free(tmp);
tmp = NULL;
}
八：計數排序
非比較排序:記錄資料在相對最小值位置出現次數,根據資料在相對位置回收資料。
代碼如下：
void CountSort(int *a, int n)
{
assert(a);
int min = a[];
int max = a[];
int i = ;
//找序列的最大值和最小值确定數組範圍
for (i = ; i < n; i++)
{
if (min > a[i])
min = a[i];
if (max < a[i])
max = a[i];
}
//範圍
int range = max - min + ;
int *counts = (int *)malloc(sizeof(int)*range);
memset(counts, , sizeof(int)*range);//将counts[]初始化為0，每個資料初始化出現0次
//記錄元素出現的次數
for (i = ; i < n; i++)
{
counts[a[i] - min]++;//最小值在counts數組第一個，算得是資料較最小值的相對位置，該位置記錄資料出現次數
}
int index = ;
for (i = ; i < range; i++)
{
while (counts[i])//不為0即與資料
{
a[index] = min + i;//将資料放入a數組：最小值+相對位置
counts[i]--;
index++;
}
}
}
main函數：
int main()
{
int a[] = { };
srand((unsigned int)time());//設定時間戳種子，保證每次測試值不同，值随時間變化
for (int i = ; i < ; i++)
{
a[i] = rand() % ;
}
int size = sizeof(a) / sizeof(a[]);
print(a, size);
//InsertSort(a, size); //快排
//ShellSort(a,size); //希爾
//SelectSort(a, size);//選擇
//BubbleSort(a, size);//冒泡
//HeapSort(a, size);//堆排
//QuickSortNonR(a, 0, size - 1);//非遞歸快排
//QuickSort(a, 0,size-1);//遞歸快排
//MergeSort(a, size);//歸并
CountSort(a, size);//計數排序
print(a, size);
system("pause");
return ;
}
排序性能比較：
1.選擇排序和插入排序：插入排序較好
兩者時間複雜度都為0(n^2),但對于有序的插入排序時間複雜度為0(n),
直接插入在有序區間後面，不用再挪動資料，選擇排序依然是0(n^2);
2.冒泡排序、插入排序、選擇排序：插入排序較好
如 1 2 3 5 4
插入排序是5次可以有序，而冒泡在4和5交換有序後還需要再判斷是否有序，才結束排序，即7次
3.經過測試，大量資料快排性能優于堆排
各種排序穩定性：
穩定性指兩個相同的值在排序後相對位置不變。
插入排序：穩定（相等就插在後面）
希爾排序：不穩定（有gap,跳躍着排序，可能回影響相對位置）
選擇排序：不穩定（3 5 9* 9 2 7—>2 5 7 9 3 9*)
冒泡排序：穩定（兩個資料相等，不交換）
堆排：不穩定（5 4 5*，第一個5和最後一個5*交換，相對位置發生變化）
快速排序：不穩定( 6 7 1 5* 5—>1 5 6 5* 7)
歸并排序：穩定（相等就将前一個資料放入tmp數組）
以上為排序的各種分析及代碼。