目录
快速排序（双指针法）
原理
代码
快速排序（非递归）
原理
代码
归并排序
介绍
优点
缺点
图片
原理
代码
归并排序（非递归）
代码
快速排序（双指针法）
快速排序的精髓在于将数组根据关键值分成左右两块，由此衍生出霍尔快排，挖坑法等一系列方法，在这里我们要介绍一下双指针法
原理
第一个指针pre指向开头，第二个指针cur指向第二个元素
cur持续向前查找，找到某个位置小于关键值时，将cur指向的值与pre的下一个值进行交换（没错，是下一个，这样就可以将第一个位置的关键值保存下来）
交换还有个限制条件就是pre的下一个位置不能是cur
交换完成后cur与pre指向下一个位置
循环退出条件为cur超出数组范围
退出循环后，将pre位置的值与关键值进行交换（因为pre位置始终小于关键值）
最后和普通的递归一样递归执行左右两侧即可
代码
void quicksort(int* arr, int left, int right) {//双指针
if (left >= right)
return;
int cur = left + 1, pre = left;
while (cur <= right) {
if (arr[cur] < arr[left] && ++pre < cur)
swap(&arr[cur], &arr[pre]);
cur++;
}
swap(&arr[left], &arr[pre]);
quicksort(arr, left, pre - 1);
quicksort(arr, pre + 1, right);
}快速排序（非递归）
原理
我们可以使用栈进行模拟递归，首先创建一个栈，将数组的左右边界打入栈中，进入循环
当栈不为空时持续执行循环
根据自己的实际情况判断左右边界，如果先打入的是右边界，那么栈顶元素就是左边界
取出左右边界后，执行一次快排并返回关键值所在位置
如果关键值左侧不止一个元素，那么就打入左侧的左右边界
右侧同理
这样，我们就实现了非递归的快速排序
代码
int part(int* arr, int left, int right) {
if (left >= right)
return 0;
int cur = left + 1, pre = left;
while (cur <= right) {
if (arr[cur] < arr[left] && ++pre < cur)
swap(&arr[cur], &arr[pre]);
cur++;
}
swap(&arr[left], &arr[pre]);
return arr[pre];
}
void quicksort1(int* arr, int left, int right) {//非递归
Stack stack;
StackInit(&stack);
StackPush(&stack, right);
StackPush(&stack, left);
while (!StackEmpty(&stack)) {
int begin = StackTop(&stack);
StackPop(&stack);
int end = StackTop(&stack);
StackPop(&stack);
int key = part(arr, begin, end);
if (key - 1 > begin) {
StackPush(&stack, key-1);
StackPush(&stack, begin);
}
if (key + 1 < end) {
StackPush(&stack, end);
StackPush(&stack, key + 1);
}
}
}归并排序
介绍
归并排序是通过不断细分左右边界，使局部有序后扩大范围使整体有序的排序
优点
效率较高，且不会受原数组排列顺序影响
缺点
需要额外开辟一块等大的数组
图片
原理
创建等大的辅助数组
拆分为两块数组
先递归自身使左右两边有序
与链表类似
比较分成的两块有序数组的元素大小并排列在辅助数组中
整体有序后拷贝到原数组中
代码
void _Mergesort(int* arr, int*tmp,int left,int right) {
if (left >= right)
return;
int mid = (left + right) / 2;
int begin1 = left, end1 = mid, begin2 = mid + 1, end2 = right,i=left;
_Mergesort(arr, tmp, begin1, end1);
_Mergesort(arr, tmp, begin2, end2);
while (begin1 <= end1 && begin2 <= end2) {
if (arr[begin1] < arr[begin2]) {
tmp[i++] = arr[begin1];
begin1++;
}
else {
tmp[i++] = arr[begin2];
begin2++;
}
}
while (begin1 <= end1) {
tmp[i++] = arr[begin1];
begin1++;
}
while (begin2 <= end2) {
tmp[i++] = arr[begin2];
begin2++;
}
memcpy(arr + left, tmp + left, sizeof(int) * (right - left + 1));
}归并排序（非递归）
我们要用到希尔排序时创建的一个变量:gap
gap为一个数组拆分后单个小数组的元素个数
最小为一
当gap小于总数时
按照gap为一组，两组为一大组的顺序从左到右进行排序
当右侧起始位置超出时，直接退出，因为左侧小数组本身就是有序的
右侧终止位置超出时修正即可
单次遍历结束后将辅助数组元素拷贝回原数组即可
代码
void MergesortNonR(int* arr, int n) {
int gap = 1;//gap为每小组元素个数，两个小组为一大组进行比较
int* tmp = (int*)malloc(sizeof(int) * n),i;
while (gap < n) {
for (i = 0; i < n; i+=2*gap) {
int begin1 = i, end1 = begin1 + gap - 1;
int begin2 = end1 + 1, end2 = begin2 + gap - 1, j = i;
if (begin2 >= n)
break;
if (end2 >= n)
end2 = n - 1;
while (begin1 <= end1 && begin2 <= end2) {
if (arr[begin1] > arr[begin2])
tmp[j++] = arr[begin2++];
else
tmp[j++] = arr[begin1++];
}
while (begin1 <= end1)
tmp[j++] = arr[begin1++];
while (begin2 <= end2)
tmp[j++] = arr[begin2++];
memcpy(arr + i, tmp + i, sizeof(int) * gap * 2);
}
gap *= 2;
}
free(tmp);
tmp = NULL;
}
