插入排序
插入排序的相关思想：
将整个数组a分为有序和无序的两个部分。前者在左边，后者在右边。开始有序的部分只有a[0] , 其余都属于无序的部分。每次取出无序部分的第一个（最左边）元素，把它加入有序部分。假设插入合适的位置p，则原p位置及其后面的有序部分元素都向右移动一个位置，有序的部分即增加了一个元素。一直做下去，直到无序的部分没有元素。
插入排序的实现如下：
void InsertSort(int* a, int n)
{
for (int i = 0; i < n-1; ++i)
{//将[end+1]的值插入到有序区间[0,end]中
int end = i;
int tmp = a[end + 1];
while (end >= 0)
{
if (a[end] > tmp)
{
a[end + 1] = a[end];
--end;
}
else
break;
}
a[end + 1] = tmp;
}
}
希尔排序
希尔排序的思想：
希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有记录分成个组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取重复上述分组和排序的工作。当到达gap=1时，所有记录在统一组内的数据就排好序。
希尔排序的实现：
void ShellSort(int* a, int n)
{
int gap = n;
gap = gap / 3 + 1;
for (int i = 0; i<n - gap; ++i)
{
int end = i;
int tmp = a[end + gap];
while (end >= 0)
{
if (a[end] > tmp)
{
a[end + gap] = a[end];
end -= gap;
}
else
break;
}
a[end + gap] = tmp;
}
}
选择排序
选择排序的思想：
定义一个begin和一个end，每次从数组中选取最大的数放在数组的最右边，选取最小的数放在数组的最左边，直到begin与end相遇时停止。
选择排序的实现：
void SelectSort(int* a, int n)
{
int begin = 0;
int end = n - 1;
while (begin < end)
{
int min = begin;
int max = end;
for (int i = begin; i < end; i++)
{
if (a[i] < a[min])
min = i;
if (a[i] > a[max])
max = i;
}
Swap(&a[begin], &a[min]);
if (begin == max)
max = min;
Swap(&a[end], &a[max]);
++begin;
--end;
}
}
堆排序
堆排序的思想：
首先通过向下调整算法创建一个最大堆（排升序创建最大堆，排降序创建最小堆），最大堆创建好之后，每次交换堆头元素和堆尾元素，交换之后再对n-1个元素进行向下调整算法找出次大的元素放在堆头，交换此时的堆头元素和堆尾元素，以此类推，直至数组有序。
堆排序的实现：
void AdjustDown(int* a, int n, int parent)
{
//建大堆
int child = parent * 2 + 1;//利用数组下标计算左孩子的位置
while (child < n)//当左孩子存在时
{
//判断右孩子是否存在且左右孩子哪个更大
if (a[child] < a[child + 1] && child + 1 < n)
++child;
if (a[child] > a[parent])
{
Swap(&a[child], &a[parent]);
parent = child;
child = parent * 2 + 1;
}
else
break;
}
}
void HeapSort(int* a, int n)
{
//1、建大堆
for (int i = (n - 2) / 2; i >= 0; --i)
{
AdjustDown(a, n, i);
}
//2、选数
int end = n - 1;
while (end > 0)
{
Swap(&a[0], &a[end]);
AdjustDown(a, end, 0);
--end;
}
}
冒泡排序
冒泡排序的思想：
根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。
冒泡排序的实现：
void BubbleSort(int* a, int n)
{
int end = n - 1;
while (end > 0)
{
for (int i = 0; i < end; ++i)
{
if(a[i + 1] < a[i])
Swap(&a[i], &a[i + 1]);
}
--end;
}
}
快速排序
快速排序的基本思想：
任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两个子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
快速排序的三种实现方式：
//三数取中间选key法
int GetMidkey(int* a, int begin, int end)
{
int mid = begin + ((end - begin) >> 1);
if (a[begin] > a[mid])
{
if (a[begin] < a[end])//a[mid] < a[begin] < a[end]
return begin;
else if (a[mid] > a[end])//a[end] < a[mid] <a [begin]
return mid;
else//a[mid] < a[end] <a[begin]
return end;
}
else//a[begin] < a[mid]
{
if (a[mid] < a[end])//a[begin] < a[mid] < a[end]
return mid;
else if (a[begin] > a[end])//a[end] < a[begin] <a[mid]
return begin;
else//a[begin] < a[end] <a[mid]
return end;
}
}
快速排序hoare版本：
int PartSort1(int* a, int begin, int end)
{
int key = GetMidkey(a,begin,end);
Swap(&a[begin], &a[end]);
key = begin;
while (begin < end)
{
//从右边找小于key的值放在左边
while (begin < end && a[end] >= a[key])
--end;
//从左边找大于key的值放在右边
while (begin < end && a[begin] <= a[key])
++begin;
//交换找到的两个值
Swap(&a[begin], &a[end]);
}
//将key的值放在begin与end相遇的位置，则key左边都是小于它的数，右边都是大于它的数
Swap(&a[begin], &a[key]);
return begin;
}
快速排序挖坑法：
int PartSort2(int* a, int begin, int end)
{
int key = GetMidkey(a, begin, end);
Swap(&a[begin], &a[key]);
int tmp = a[begin];
while (begin < end)
{
//找小于key的值填在左边的坑里
while (begin < end && a[end] >= tmp)
--end;
a[begin] = a[end];
//找大于key的值放在上一步移走数的坑里
while (begin < end && a[begin] <= tmp)
++begin;
a[end] = a[begin];
}
//将key的值放在最后begin与end相遇的位置上，左边是比key小的值，右边是比key大的值
a[begin] = tmp;
return begin;//返回key所在的位置
}
快速排序快慢指针法：
int PartSort3(int*a, int begin, int end)
{
int prev = begin;
int cur = begin + 1;
while (cur <= end)
{
if (a[cur] < a[begin] && ++prev != cur)
Swap(&a[prev], &a[cur]);
++cur;
}
Swap(&a[begin], &a[prev]);
return prev;
}
void QuickSort(int* a, int left,int right)
{
if (left >= right)
return;
int div = PartSort1(a, left, right);
//左区间[left,div-1]
//右区间[div+1,right]
QuickSort(a, left, div - 1);
QuickSort(a, div + 1, right);
}
void QuickSortOP(int* a, int left, int right)
{
if (left >= right)
return;
int div = PartSort1(a, left, right);
//左区间[left,div-1]
//右区间[div+1,right]
if (right - left > 10)
{
QuickSort(a, left, div - 1);
QuickSort(a, div + 1, right);
}
else
{
InsertSort(a + left, right - left + 1);
}
}
快速排序的非递归实现：
void QuickSortNonP(int* a, int left, int right)
{
Stack st;
StackInit(&st);
StackPush(&st, right);
StackPush(&st, left);
while (StackEmpty(&st) != 0)
{
int begin = StackTop(&st);
StackPop(&st);
int end = StackTop(&st);
StackPop(&st);
int div = PartSort1(a, begin, end);
if (begin < div - 1)
{
StackPush(&st, div - 1);
StackPush(&st, begin);
}
if (div + 1 < end)
{
StackPush(&st, end);
StackPush(&st, div + 1);
}
}
}
归并排序
归并排序的思想：
归并排序是 建立在归并操作上的一种有效的排序算法,该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
归并排序的实现：
void _MergeSort(int* a, int begin, int end, int* tmp)
{
if (begin >= end)
return;
int mid = begin + ((end - begin) >> 1);
//划分子问题：使区间[begin,mid],[mid+1,end]的数有序，递归划分子区间直至其有序
_MergeSort(a, begin, mid, tmp);
_MergeSort(a, mid + 1, end, tmp);
//区间[begin,mid],[mid+1,end]
int begin1 = begin;
int end1 = mid;
int begin2 = mid + 1;
int end2 = end;
int index = begin;
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] < a[begin2])
{
tmp[index++] = a[begin1++];
}
else
{
tmp[index++] = a[begin2++];
}
}
while (begin1 <= end1)
tmp[index++] = a[begin1++];
while (begin2 <= end2)
tmp[index++] = a[begin2++];
//将归并结果拷回原数组
index = begin;
while (begin < end)
a[index++] = tmp[begin++];
}
void MergeSort(int* a, int n)
{
int* tmp = (int*)malloc(sizeof(int)*n);
_MergeSort(a, 0, n - 1, tmp);
free(tmp);
}
计数排序
计数排序的思想：
计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。统计相同元素出现次数，根据统计的结果将序列回收到原来的序列中。
计数排序的实现：
void CountSort(int* a, int n)
{
//确定数组区间大小
int max = a[0];
int min = a[0];
for (int i = 0; i < n; ++i)
{
if (a[i] > max)
max = a[i];
if (a[i] < min)
min = a[i];
}
int range = max - min + 1;
int* count = (int*)malloc(sizeof(int)*range);
memset(count, 0, sizeof(int)*range);
for (int i = 0; i < n; ++i)
{
count[a[i] - min]++;
}
int j = 0;
for (int i = 0; i < range; ++i)
{
while (count[i]--)
{
a[j++] = i + min;
}
}
}
测试各个排序的功能：
void SortTest()
{
int a[] = { 9, 3, 6, 8, 3, 1, 5, 4, 2 };
InsertSort(a, sizeof(a) / sizeof(int));
printf("插入排序：");
ArrayPrint(a, sizeof(a) / sizeof(int));
ShellSort(a, sizeof(a) / sizeof(int));
printf("希尔排序：");
ArrayPrint(a, sizeof(a) / sizeof(int));
SelectSort(a, sizeof(a) / sizeof(int));
printf("选择排序：");
ArrayPrint(a, sizeof(a) / sizeof(int));
HeapSort(a, sizeof(a) / sizeof(int));
printf("堆排序： ");
ArrayPrint(a, sizeof(a) / sizeof(int));
BubbleSort(a, sizeof(a) / sizeof(int));
printf("冒泡排序：");
ArrayPrint(a, sizeof(a) / sizeof(int));
QuickSort(a, 0, (sizeof(a) / sizeof(int)) - 1);
printf("快速排序：");
ArrayPrint(a, sizeof(a) / sizeof(int));
QuickSortOP(a, 0, (sizeof(a) / sizeof(int)) - 1);
printf("快速排序OP：");
ArrayPrint(a, sizeof(a) / sizeof(int));
QuickSortNonP(a, 0, (sizeof(a) / sizeof(int)) - 1);
printf("快速排序非递归：");
ArrayPrint(a, sizeof(a) / sizeof(int));
MergeSort(a,(sizeof(a) / sizeof(int)));
printf("归并排序：");
ArrayPrint(a, sizeof(a) / sizeof(int));
CountSort(a, (sizeof(a) / sizeof(int)));
printf("计数排序：");
ArrayPrint(a, sizeof(a) / sizeof(int));
}
为方便各个排序实现，封装一个交换函数
#include<stdio.h>
#include<string.h>
void Swap(int* pa, int* pb)//封装一个交换函数，提高代码复用性
{
int tmp = *pa;
*pa = *pb;
*pb = tmp;
}
void ArrayPrint(int* a, int n)
{
for (int i = 0; i < n; ++i)
{
printf("%d ", a[i]);
}
printf("\n");
}
