荷兰国旗问题到快排的实现

如何实现分层呢？双指针

双指针：用两个变量对指针划分区域。
如何实现呢？一个指针less一个指针more，分别为小于区域，和大于区域的边界，初始值分别为-1和最大下标+1，另有一个变量i，去遍历数组。当小于num，和小于区域外的第一个元素交换，less和i都自增；如果等于num，i自增；当大于num，和大于区域外的第一个元素进行交换，more自减，i不能自增，因为换过来的数是一个新数，不能确定和num的关系。那循环结束的条件是什么呢？当i和more相遇的时候，是不是就意味着已经分好了呢。

#include
int main()
{
	int arr[] = { 2,3,5,6,9,6,1,3,4,6,5,8 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	int less = -1;//小于区域的边界
	int more = sz - 1;//大于区域的边界
	int i = 0;
	int num = 5;
	while (i < more)
	{
		if (arr[i] < num)
		{
			int tmp = arr[i];
			arr[i] = arr[less + 1];
			arr[less + 1] = tmp;
			i++;
			less++;
		}
		else if (arr[i] > num)
		{
			int tmp = arr[i];
			arr[i] = arr[more-1];
			arr[more - 1] = tmp;
			more--;
		}
		else
		{
			i++;
		}
	}
	for (i = 0; i < sz; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

快排

以上两个版本的荷兰国旗，就是快排的底层原理。

快排1.0

快排1.0根据荷兰国旗1进而改进的，荷兰国旗中的num在快排中如何体现呢？是以数组下标最大的那个元素作为num，进行分层，当分层完成后，还需要将num和小于等于区域外层第一个数交换，才算完成了一次排序。换好之后，num作为为分界，对左右两边的部分数组重复上述过程。（本质是二叉树的遍历）

代码如下：

做了一些优化，需要熟悉自增，自减

#include
void Swap(int* arr, int a ,int b)
{
	int tmp = arr[a];
	arr[a] = arr[b];
	arr[b] = tmp;
}
int partition(int* arr, int left, int right)
{
	int forntier = left - 1;
	while (left < right)
	{
		if (arr[left] <= arr[right])
		{
			Swap(arr, left++, ++forntier);
		}
		else
		{
			left++;
		}
	}
	Swap(arr, forntier + 1, right);
	return forntier + 1;
}
void QuickSort(int* arr, int left, int right)
{
	if (right <= left)
		return;
	int forntier = partition(arr, left, right);
	QuickSort(arr, left, forntier - 1);
	QuickSort(arr, forntier + 1 , right);
}
int main()
{
	int arr[] = { 2,6,9,8,4,5,6,4,6,7,5 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	int i = 0;
	QuickSort(arr, 0, sz - 1);//参数传的时候要注意区间，传的是闭区间
	for (i = 0; i < sz; i++)
	{
		printf("%d ", arr[i]);
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

第一次partition

和小于等于区域外的第一个数交换

这里是left-1，每一次递归进来它的边界都是不同的，是左边界-1。

快排2.0

快排2.0依据荷兰国旗2进行改版的，同样是以数组下标最大的元素作为划分，划分成小于、等于、大于，三个区域，partition过后，还需要将数组下标最大的元素和大于区域的第一个元素进行交换，并且返回两个边界，等于区域的左边界，和等于区域的右边界，在这以这两个边界为划分，重复上述过程。
这种方法比快排1.0快一点，可以一次排好多个值。

同样把荷兰国旗2的代码进行了优化，需要熟悉自增，自减

#include
void Swap(int* arr, int a ,int b)
{
	int tmp = arr[a];
	arr[a] = arr[b];
	arr[b] = tmp;
}
int* partition(int* arr, int left, int right)
{
	int less = left - 1;
	int more = right;
	while (left < more)
	{
		if (arr[left] > arr[right])
		{
			Swap(arr, left, --more);
		}
		else if (arr[left] < arr[right])
		{
			Swap(arr, left++, ++less);
		}
		else
		{
			left++;
		}
	}
	Swap(arr, more, right);
	int* p = (int*)malloc(sizeof(int) * 2);
	p[0] = less + 1;
	p[1] = more;
	return p;
}
void QuickSort(int* arr, int left, int right)
{
	if (right <= left)
		return;
	int* p = partition(arr, left, right);
	QuickSort(arr, left, p[0] - 1);
	QuickSort(arr, p[0] + 1, right);
	free(p);
}
int main()
{
	int arr[] = { 2,3,5,6,9,6,1,3,4,6,5,5 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	int i = 0;
	QuickSort(arr, 0, sz - 1);//参数传的时候要注意区间，传的是闭区间
	for (i = 0; i < sz; i++)
	{
		printf("%d ", arr[i]);
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

第一次partition

和大于区域的第一个数交换，这也是为什么more不用-1
原本不是等于区域的边界，但是交换后就是了。

返回等于区域的边界

快排3.0

不管是快排1.0，还是快排2.0，都能找到最坏的情况，已经有序（升序），那么时间复杂度是O(N^2)，像快排这种分层最好的情况是，这个划分值，是这些数中的中间值，这样可以把子问题的规模划分为n/2。
左边和右边是等规模的这种，如下图。这样是最好的情况。

其它规模…

如何改进呢？随机取[left,right]中的一个元素作为划分值，这样划分值的选取就变成了概率事件，通过数学中的数学期望什么的计算，最终快排3.0版本的时间复杂度是O(N*logN)

是对快排2.0进行改版。
代码如下，同样的也是优化过后的
随机值

#include
#include
#include
void Swap(int* arr, int a ,int b)
{
	int tmp = arr[a];
	arr[a] = arr[b];
	arr[b] = tmp;
}
int* partition(int* arr, int left, int right)
{
	int less = left - 1;
	int more = right;
	while (left < more)
	{
		if (arr[left] > arr[right])
		{
			Swap(arr, left, --more);
		}
		else if (arr[left] < arr[right])
		{
			Swap(arr, left++, ++less);
		}
		else
		{
			left++;
		}
	}
	Swap(arr, more, right);
	int* p = (int*)malloc(sizeof(int) * 2);
	p[0] = less + 1;
	p[1] = more;
	return p;
}
void QuickSort(int* arr, int left, int right)
{
	if (right <= left)
		return;
	Swap(arr, left + (rand() % (right - left + 1)), right);
	int* p = partition(arr, left, right);
	QuickSort(arr, left, p[0] - 1);
	QuickSort(arr, p[0] + 1, right);
	free(p);
}
int main()
{
	srand((unsigned int)time(NULL));
	int arr[] = { 2,3,5,6,9,6,1,3,4,6,5,5 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	int i = 0;
	QuickSort(arr, 0, sz - 1);//参数传的时候要注意区间，传的是闭区间
	for (i = 0; i < sz; i++)
	{
		printf("%d ", arr[i]);
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

这种分层你学费了吗？

小试牛刀：力扣原题

LeetCode 21.移除元素

int removeElement(int* nums, int numsSize, int val)
{
	int left = -1;//不等于区域
	int i = 0;
	while (i < numsSize)
	{
		if (nums[i] != val)
		{
			int tmp = nums[i];
			nums[i] = nums[left + 1];
			nums[left + 1] = tmp;
			left++;
			i++;
		}
		else
			i++;
	}
	return left + 1;
}
int main()
{
	int arr[] = { 0,1,2,2,3,0,4,2 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	int val = 2;
	int ret = removeElement(arr, sz, val);
	for (int i = 0; i < ret; i++)
	{
		printf("%d ", arr[i]);
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31