个人技术分享

目录

快速排序（双指针法）

原理

代码

快速排序（非递归）

原理

代码

归并排序

介绍

优点

缺点

图片

原理

代码

归并排序（非递归）

代码

---

快速排序（双指针法）

快速排序的精髓在于将数组根据关键值分成左右两块，由此衍生出霍尔快排，挖坑法等一系列方法，在这里我们要介绍一下双指针法

原理

第一个指针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, tmp, sizeof(int) * n);
		gap *= 2;
	}
	free(tmp);
	tmp = NULL;
}