数据结构基础10：三路划分（解决快速排序的问题）

一.题目描述：

题目链接：

这个题目有一个问题在hore 挖坑 前后指针 递归或者非递归 并且加上了三数取中的自己实现的快速排序方法但是过不了上面这个oj‘题目：

1.方法一：三路划分：

>1.为什么会有三路划分？

因为在lectcoude上自己写的快速排序通过不了报超出时间限制：
针对了快速排序的明显缺陷设计了测试用例：

>2.三路划分的主要思路：

1.我们下面使用一个动图去演示代码的执行逻辑过程！
2.结束一次会发现产生了一个效果就是非常多相同的中间值到了中间并且已经排和了一个比较大的范围，之后我们递归进入左和右的区间范围再一次进入这样的操作就比较方便：

代码实现：

void partsort4(int* arr , int beging , int end)
{
	if (beging >= end)
		return;

	int tmp = arr[beging];
	int left = beging;
	int right = end;
	int cur = left + 1;

	while (cur <= right)
	{
		//1.cur的值和tmp的相等的时候就直接cur++：
		if (arr[cur] == tmp)
		{
			cur++;
		}
		//2.cur的值比tmp的值小的时候就进行left和cur的交换并且++两个：
		else if (arr[cur] < tmp)
		{
			swap(&arr[cur], &arr[left]);
			cur++;
			left++;
		}
		//3.cur的值比tmp的值大的时候
		//就进行right和cur的交换并且--一个right
		//不++cur是因为我们不知道交换来的数值具体和他mp的大小关系：
		else if (arr[cur] > tmp)
		{
			swap(&arr[cur], &arr[right]);
			right--;
		}
	}

	//结束循环之后：left到right值相等并且是一个大范围：
	//递归进入左右：

	partsort4(arr, beging, left - 1);
	partsort4(arr, right + 1, end);
}

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

2.方法二：取值更加的随机：

>1.产生的问题：

我们运行代码在上面的oj里面出现了下面的问题说通过了所有的测试用例但是呢结果显示我们通过了所有的测试用例但是时间复杂度过高？

这又是怎么回事呢有没有什么办法解决呢？

>2.在一个方向可以去解决：

1.我们前面三数取中的那个数值就是整个数组里面值比较多并且适合中间区域的数值，但是三数取中有可能导致取到的tmp值不是这个数组范围中最适合作为tmp的数值 （tmp满足是这个数组中最多的一个数值中间数值才那最多左右范围才能越小！）
2,总结：在一个重复数据比较多的数组中三数取中和随机获取，随机获取->获取到的那个值比三数取中更加容易得到较多数值的那个值！！！

代码实现！

void swap(int* n1 , int *n2)
{
	int tmp = *n1;
	*n1 = *n2;
	*n2 = tmp;
}

int getmin(int* arr,int left,int right)
{
	int min = (left + right) / 2;

	if (arr[left] < arr[right])
	{
		if (arr[min] < arr[left])
		{
			return left;
		}
		else if (arr[min] < arr[right])
		{
			return min;
		}
		else
		{
			return right;
		}
	}

	else if(arr[left]>arr[right])
	{
		if (arr[min] > arr[left])
		{
			return left;
		}
		else if (arr[min] > arr[right])
		{
			return  min;
		}
		else
		{
			return right;
		}
	}
	return left;
}
//2.三路划分：
void partsort4(int* arr , int beging , int end)
{
	if (beging >= end)
		return;

	//范围不一定从0开始
	int ran = beging + (rand() % (end - beging));
	swap(&arr[ran], &arr[beging]);

	int tmp = arr[beging];
	int left = beging;
	int right = end;
	int cur = left + 1;

	while (cur <= right)
	{
		//1.cur的值和tmp的相等的时候就直接cur++：
		if (arr[cur] == tmp)
		{
			cur++;
		}
		//2.cur的值比tmp的值小的时候就进行left和cur的交换并且++两个：
		else if (arr[cur] < tmp)
		{
			swap(&arr[cur], &arr[left]);
			cur++;
			left++;
		}
		//3.cur的值比tmp的值大的时候
		//就进行right和cur的交换并且--一个right
		//不++cur是因为我们不知道交换来的数值具体和他mp的大小关系：
		else if (arr[cur] > tmp)
		{
			swap(&arr[cur], &arr[right]);
			right--;
		}
	}

	//结束循环之后：left到right值相等并且是一个大范围：
	//递归进入左右：

	partsort4(arr, beging, left - 1);
	partsort4(arr, right + 1, end);
}

int* sortArray(int* nums, int numsSize, int* returnSize){
		srand((unsigned int)time(NULL));
    partsort4(nums,0,numsSize-1);
    *returnSize = numsSize;
    return nums;
}
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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96