一、直接插入排序
算法思想：把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列。平时我们玩扑克牌的时候就用了这个思想。
实现方法：在插入第i个元素时，前面的（i-1）个元素已经有序，只需要从后往前依次比较，找到合适的插入位置并插入，原来位置上的元素顺序后移。
void InsertSort(int array[], int size) {
for (int i = 1; i < size; i++) {
int end = i - 1;
int key = array[i];//待插入元素
//找待插入元素的位置
while (end >= 0 && key < array[end]) {
array[end + 1] = array[end];
end--;
}
//插入
array[end + 1] = key;
}
}
特性总结：
1、时间复杂度：O(N^2)
2、空间复杂度：O(1)
3、稳定性：稳定（因为它没有隔着元素插入或交换）
4、适合场景：序列接近有序或者元素个数较小
二、希尔排序
算法思想：希尔排序其实是对直接插入排序的优化。先选定一个整数gap,把待排序文件中的所有的记录分为多组，所有距离为gap的在同一组内，并对每一组的记录进行直接插入排序。然后不断缩小gap,重复上述过程，直到gap=1时，所有记录排好序。
void ShellSort(int array[], int size) {
int gap = size;
while (gap > 1) {
gap = gap / 3 + 1;
for (int i = gap; i < size; i++) {
//单个元素的插入过程
int end = i - gap;
int key = array[i];
//找待插入元素位置
while (end >= 0 && key < array[end]) {
array[end + gap] = array[end];
end = end - gap;
}
array[end + gap] = key;
}
}
}
希尔排序特性：
1、时间复杂度：由于gap的取值方法不同，所以它的时间复杂度不固定。我用的之歌取值方法是Knuth提出的，时间复杂度为O(N^1.25)到O(1.6N^1.25)之间。
2、空间复杂度：O(1)
3、稳定性：不稳定
4、应用场景：数据比较随机，数据量大
三、直接选择排序
算法思想：在元素集合中选择一个最大（小）的元素，若它不是这组元素的最后一个元素，则将它与这组元素的最后一个元素交换，则最后一个元素已经排好序了。再在剩余的无序的集合中，重复上述步骤，直到剩余一个无序元素。
void SelectSort(int array[], int size) {
//控制选择趟数
for (int i = 0; i < size - 1; i++) {
int maxPos = 0;
//找最大元素
for (int j = 1; j < size - i; j++) {
if (array[j] > array[maxPos]) {
maxPos = j;
}
}
//将最大元素与区间随后一个元素交换
if (maxPos != size - 1 - i) {
swap(&array[size - 1 - i], &array[maxPos]);
}
}
}
直接选择排序的优化：在一次选择过程中既然可以找到最大的元素位置，那也可以同时找到最小的元素的位置。则可以先把最大元素和本次集合中最后一个元素交换，再把最小元素与集合中第一个元素交换，这样就可以一次排好两个元素。但这里有一点需要注意：在进行最大元素交换的时候，可能集合当中最后一个元素就是最小的元素。
void SelectSortOP(int array[], int size) {
int begin = 0;
int end = size - 1;
while (begin < end) {
int maxPos = begin;
int minPos = begin;
int index = begin + 1;
//在[begin,end]找最大值和最小值的位置
while (index <= end) {
if (array[index] > array[maxPos]) {
maxPos = index;
}
if (array[index] < array[minPos]) {
minPos = index;
}
index++;
}
if (maxPos != end) {
swap(&array[maxPos], &array[end]);
}
//注意end位置上刚好存的是最小值
if (minPos == end) {
minPos = maxPos;
}
if (minPos != begin) {
swap(&array[minPos], &array[begin]);
}
begin++;
end--;
}
}
直接选择排序特性：时间复杂度为O(N^2),空间复杂度为O(1),稳定性为不稳定。由于直接选择排序得性能不好，所以现实中很少用。
四、堆排序
算法思想：堆排序也是选择排序的一种，因为堆顶就是最大（小）的元素，这样就可以用堆删除的思想来对它进行排序。排升序建大堆，排降序建小堆。
void SortAdjustDown(int array[], int size, int parent) {
int child = parent * 2 + 1;
while (child < size) {
if (child + 1 < size && array[child + 1] > array[child]) {
child++;
}
if (array[child] > array[parent]) {
swap(&array[child], &array[parent]);
parent = child;
child = parent * 2 + 1;
}
else {
return;
}
}
}
void HeapSort(int array[], int size) {
//创建一个大堆
for (int root = (size - 2) / 2; root >= 0; root--) {
SortAdjustDown(array, size, root);
}
int end = size - 1;
while (end > 0) {
swap(&array[0], &array[end]);
SortAdjustDown(array, end, 0);
end--;
}
}
堆排序特性：时间复杂度O(logN),空间复杂度为O(1),不稳定。
五、冒泡排序：
算法思想：对所有相邻的元素进行比较，如果是逆顺，则将其交换，这样此集合的最后一个元素就有序。再在无序的集合中重复此过程，直到无序集合中只剩一个元素。
void BubbleSort(int array[], int size) {
//最后一趟冒泡区间中只剩一个元素了，所以减一
for (int i = 0; i < size - 1; i++) {
//如果此次冒泡过程中没有元素交换，则已经有序
int ischange = 0;
for (int j = 0; j < size - 1 - i; j++) {
if (array[j] > array[j + 1]) {
swap(&array[j], &array[j + 1]);
ischange = 1;
}
}
if (!ischange) {
return;
}
}
}
冒泡排序特性：时间复杂度为O(N^2),空间复杂度为O(1),稳定。适合场景：元素接近有序。
六、快速排序
算法思想：任取排序元素序列中的某元素作为基准值，然后按照将此序列分为两个子序列，左子序列中的所有元素均小于基准值，右子序列中的所有元素都大于基准值。然后将左右序列重复该过程，直到有序。此思想与二叉树的前序遍历相像。
代码主框架（递归）：
void QuickSort(int array[], int left, int right) {
if (right - left > 1) {
//在[left,right)区间中找一个基准值对区间进行划分
int div = Partion3(array, left, right);
QuickSort(array, left, div);
QuickSort(array, div + 1, right);
}
}
而对划分区间的方法主要有三种，假如把区间的最后一个元素作为基准值，对下面的序列划分：
1、hoare版本
给两个指针，begin从左往右找比基准值大的元素，end从右往左找比基准值小的元素，找到后将它们交换，重复此过程直到begin和end相遇。最后再把begin位置的元素与序列的最后一个元素交换。
//区间[left,right)
int Partion1(int array[], int left, int right) {
int begin = left;
int end = right - 1;
int mid = GetMiddleIndex(array, left, right);
swap(&array[mid], &array[end]);
int key = array[end];
while (begin < end) {
//从前往后找比基准值大的元素
while (begin < end && array[begin] <= key) {
begin++;
}
//从后往前找比基准值小的元素
while (begin < end && array[end] >= key) {
end--;
}
if (begin != end) {
swap(&array[begin], &array[end]);
}
}
if (begin != right - 1) {
//注意这里是和最后一个元素交换不是和key交换
swap(&array[begin], &array[right - 1]);
}
return begin;
}
2、挖坑法：将最后一个元素作为基准值就可以将它看作是一个坑，让begin从左往右找比基准值大的元素，找到后去填这个坑，然后begin这个位置就成了新的坑位，再让end指针从右往左找比基准值小的元素去填上个坑位。重复此过程，直到begin和end相遇。
//挖坑法
int Partion2(int array[], int left, int right) {
int begin = left;
int end = right - 1;
int mid = GetMiddleIndex(array, left, right);
swap(&array[mid], &array[end]);
int key = array[end];
while (begin < end) {
while (begin < end && array[begin] <= key) {
begin++;
}
if (begin != end) {
array[end] = array[begin];
}
while (begin < end && array[end] >= key) {
end--;
}
if (begin != end) {
array[begin] = array[end];
}
}
array[begin] = key;
return begin;
}
3、前后指针法：prev这个指针往左的存的都是比基准值小的元素，prev到cur之间存的都是比基准值大的元素，cur向右遍历，遇到比基准值小的元素时，则将他和prev位置的元素交换。
//前后指针法
int Partion3(int array[], int left, int right) {
int cur = left;
int prev = cur - 1;
int mid = GetMiddleIndex(array, left, right);
swap(&array[mid], &array[right - 1]);
int key = array[right - 1];
while (cur < right) {
if (array[cur] < key && ++prev != cur) {
swap(&array[prev], &array[cur]);
}
cur++;
}
if (++prev != right) {
swap(&array[prev], &array[right - 1]);
}
return prev;
}
优化：为了防止基准值取到极值的情况导致性能差的原因，可以使用三数取中法来确定基准值。
//三数取中法
int GetMiddleIndex(int array[], int left, int right)
{
int mid = left + ((right - left) >> 1);
if (array[left] < array[right - 1])
{
if (array[mid] < array[left])
return left;
else if (array[mid] > array[right - 1])
return right - 1;
else
return mid;
}
else
{
if (array[mid] > array[left])
return left;
else if (array[mid] < array[right - 1])
return right - 1;
else
return mid;
}
}
上面是使用递归的方式写的快排，当然也可以用循环的方式实现，这里得借助栈来实现，栈里面存的是分割得区间。
void QuickSortNor(int array[], int size) {
Stack s;
StackInit(&s);
StackPush(&s, size);
StackPush(&s, 0);
while (!StackEmpty(&s)) {
int left = StackTop(&s);
StackPop(&s);
int right = StackTop(&s);
StackPop(&s);
if (right - left > 1) { //left可能等于right
//划分
int div = Partion1(array, left, right);
//要先处理基准值左侧[left,div)，后处理基准值右侧[div + 1,right)，所以先让右侧的入栈
StackPush(&s, right);
StackPush(&s, div + 1);
StackPush(&s, div);
StackPush(&s, left);
}
}
StackDestroy(&s);
}
快排特性：时间复杂度为O(NlogN),虽然他再最差情况下的时间复杂度为O(N^2)，但是基准值取到极值情况下得概率很小，小到可以忽略，同时可以用三数取中法来优化。空间复杂度为O(logN)。不稳定。
七、归并排序
算法思想：归并排序是建立在归并操纵上得一种有效的排序算法，该算法是采用分治法的一个非常典型的应用。将以有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段有序。
实现思路：1、对区间进行均分。2、在辅助空间上进行归并。3、将元素拷贝回原区间上。
递归实现：
// 将[left, mid) 和 [mid, right)两个有序区间中的元素合并成一个，合并好之后放到temp中
MergeDate(int array[], int left, int mid, int right, int temp[]) {
//区间为左闭右开
int begin1 = left, end1 = mid;
int begin2 = mid, end2 = right;
int index = left;
while (begin1 < end1 && begin2 < end2) {
if (array[begin1] <= array[begin2]) {
temp[index++] = array[begin1++];
}
else {
temp[index++] = array[begin2++];
}
}
while (begin1 < end1) {
temp[index++] = array[begin1++];
}
while (begin2 < end2) {
temp[index++] = array[begin2++];
}
}
void _MergeSort(int array[], int left, int right, int temp[]) {
if (right - left > 1) {
//对区间进行均分
int mid = left + ((right - left) >> 1);
_MergeSort(array, left, mid, temp);
_MergeSort(array, mid, right, temp);
//归并
MergeDate(array, left, mid, right, temp);
//将元素拷回到原区间当中
memcpy(array + left, temp + left, sizeof(array[0]) * (right - left));
}
}
void MergeSort(int array[], int size) {
int* temp = (int*)malloc(sizeof(array[0]) * size);
if (temp == NULL) {
assert(0);
}
_MergeSort(array, 0, size, temp);
free(temp);
}
循环实现：
void MergeSortNor(int array[], int size) {
int* temp = (int*)malloc(sizeof(array[0]) * size);
if (temp == NULL) {
assert(0);
}
int gap = 1;
while (gap < size) {
for (int i = 0; i < size; i +=2 * gap) {
int left = i;
int mid = left + gap;
int right = mid + gap;
//mid和right可能会越界
if (mid > size) {
mid = size;
}
if (right > size) {
right = size;
}
MergeDate(array, left, mid, right, temp);
}
memcpy(array, temp, sizeof(array[0]) * size);
gap *= 2;
}
free(temp);
}
特性分析：时间复杂度为O(NlogN)；空间复杂度为O(N)；稳定；更多解决的外排序问题。
八、计数排序
应用场景：数据密集集中在某个范围中----一般都会告诉范围
如果没有告诉范围，先要统计出范围--->计算计数空间大小--->申请计数空间--->统计元素出现的次数--->回收
时间复杂度：O(N)
空间复杂度：O(M)：M表示范围
稳定性：稳定
void CountSort(int array[], int size) {
//获取区间范围
int maxValue = array[0];
int minValue = array[0];
for (int i = 0; i < size; i++) {
if (array[i] > maxValue) {
maxValue = array[i];
}
if (array[i] < minValue) {
minValue = array[i];
}
}
int range = maxValue - minValue + 1;
//申请计数空间
int* count = (int*)malloc(sizeof(array[0]) * range);
if (count == NULL) {
assert(0);
}
//将初始值设置为0
memset(count, 0, sizeof(array[0]) * range);
for (int i = 0; i < size; i++) {
count[array[i] - minValue]++;
}
int index = 0;
//回收
for (int i = 0; i < range; i++) {
while (count[i]) {
array[index++] = minValue + i;
count[i]--;
}
}
free(count);
}
