二分查找 - BinarySearch

发表于 2017-12-23 更新于 2021-03-22 分类于 LeetCode

详细原文这里：特别好用的二分查找法模板

1. 二分查找的基本思想

二分查找的基本思想是：夹逼法或者叫排除法

在每一轮循环中，都可以排除候选区间里将近一半的元素，进而使得候选区间越来越小，直至有限个数（通常为1个），而这个数就有可能是我们要找的数（在一些情况下，还需要单独做判断）。

阅读全文 »

归并排序 - MergeSort

发表于 2017-12-22 更新于 2021-03-22 分类于 LeetCode

归并排序 - MergeSort

合并函数

void merge(int *arr, int left, int mid, int right)
{
	int *tmparr = new int[right - left + 1];
	int leftindex = left, rightindex = mid + 1;
	int tmpindex = 0;
	while (leftindex <= mid && rightindex <= right)
	{
		if (arr[leftindex] < arr[rightindex])
			tmparr[tmpindex++] = arr[leftindex++];
		else
			tmparr[tmpindex++] = arr[rightindex++];
	}
	while (leftindex <= mid)
		tmparr[tmpindex++] = arr[leftindex++];
	while (rightindex <= right)
		tmparr[tmpindex++] = arr[rightindex++];
	tmpindex = 0;
	while (left <= right)
		arr[left++] = tmparr[tmpindex++];
}

阅读全文 »

快速排序 - QSort

发表于 2017-12-21 更新于 2021-03-22 分类于 LeetCode

快速排序 - QSort

第一种Partition的方法

int Partition(int* data, int length, int start, int end)
{
	if (data == nullptr || length <= 0 || start < 0 || end >= length)
		return -1;

	int small = start - 1;
	for (int index = start; index < end; index++)
	{
		if (data[index] < data[end])
		{
			small++;
			if (small != index)
				swap(data[index], data[small]);
		}
	}
	small++;
	swap(data[small], data[end]);
	return small;
}
void Qsort(int* data, int length, int start, int end)
{
	if (start == end)
		return;
	int index = Partition(data, length, start, end);
	if (index > start)
		Qsort(data, length, start, index - 1);
	if (index < end)
		Qsort(data, length, index + 1, end);
}