快速排序的实现！递归实现！！超详细！！！

快速排序

快速排序的介绍

快速排序之所以快，是相对于冒泡排序，不再是只有相邻的数之间交换，它是可以跳跃式的交换，交换的距离会变得大的多，所以速度就提高了。
当然也会存在最坏的结果，仍然是跟冒泡一样是相邻的两数之间进行了交换，所以它最差的时间复杂度和冒泡排序是一样的，都是O(N²),它的平均复杂度是O(NlogN)

图文结合介绍逻辑思路

1.给数组放置10个数字，然后设定基准值为第一个元素的值，也就是5.然后设定两个变量i，j用于分别从左和右遍历数组。i在最左边，j在最右边。

2.j向左动找到比基准值5小的数，i向右动找到比基准值5大的数。然后将i，j所指向的值交换
注意:这里是j先动，当j找到比基准值小的数之后，i再动。原因稍后解释

3.第2步，ij交换后二者继续走，分别找到4,9之后再交换

4.第三部之后ij继续走直至i和j走到同一个位置停下，此时将这个位置的值和基准值5交换位置，即 将1和5交换。

5.交换后我们可以看到，5(基准值)左边的数都是小于5的，右边的数都是大于5的！
这里可以解释一个很重要的问题的了，为什么是j先动，直到j找到一个比基准值小的数之后i再动。
原因:j寻找的是比基准值小的数，i寻找的是比基准值大的数，对吧。然后当ij碰面，大概率（有个特殊情况下面步骤会提到）情况下，碰面的位置是在数组中间的某个位置，我们需要的结果是变换后基准值左边都小于基准值，基准值右边都大于基准值。而最开始，基准值在最左边，所以为了满足交换后最左边的最也是小于基准值的，我们就需要碰面的位置的值是小于基准值的，故需要j先动找到这个值。
换个说法:为什么每次都需要j先移动，因为当最后i和j相碰时，此时所指向的是j寻找到比基准值小的数字，然后和基准值交换能确保基准值左边的都是小于基准值的数字，但是如果i先右边移动的话，最后i和j相碰时，i和j所指向的是i寻找得比基准值大的数，此时和基准值相交换，基准值左边是有一个比基准值大的数，没有达到我们需要的排序效果。

6.利用递归，分别将基准值左右两部分再传去函数排序，这里我们拿左边来举例。
此时基准值是1

7.j先走，寻找比基准小的值，一直走到ij相等的位置停下来，i，j，基准都在同一个位置，交换后不变。

8.接着将基准值1右边的递归进行排序即可

关键点

1.选取基准点
2.永远是j先向左移动直到i，j相等或者j找到比基准值小的数之后，i再向右移动
3.当i，j碰面时候，将i和j所指向的数和基准值交换
4.然后处理左半边和右半边（递归）
5.c语言自带快排的函数，叫qsort，可以直接使用，我们这里是实现这个函数的功能

代码

#define _CRT_SECURE_NO_WARNINGS 1

#include

int arr[100] = { 0 };
//定义全局数组的好处:
//如果定义的是在mian里的数组的话，在my_qsort函数传参的时候需要把数组传进去
//更麻烦的是，在递归的时候，需要将变换后的基准点位置左右两侧分别传给两个数组再进行传参，这是及其麻烦且不便的
//但是利用全局数组的话，只需要和第一次使用my_qsort一样传入起始与结尾的下标即可

void my_qsort(int left, int right)
{
	int sta = arr[left];//定义基准变量。基准的单词是standard，取首字母方便理解！
	int tmp = 0;//临时变量，用于后面对两个数组元素的位置交换
	int i = left;
	int j = right;
	//定义i,j分别存储left和right是为了在后面的程序中不改变left和right，为什么不能改变呢，看函数最后几行的递归处，还需要将现在的left和right传到递归函数中。

	if (i > j)//逻辑实现的第一个判断，如果传进来的right比left还行，那肯定就是传参出现了问题。
	{
		return;
	}

	while (i != j)//当ij没走到一块时
	{
		//只能先判断arr[j]，原因的话在我讲解流程的图的时候已经解释了
		while (i < j && arr[j] >= sta)//j一步步左移，直到找到比基准小的数
		{
			j--;
		}
		while (i < j && arr[i] <= sta)//i一步步左移，直到找到比基准大的数
		{
			i++;
		}
		if (i < j)
		{
			//将j找到的比基准小的数和i找到的比基准大的数交换位置
			tmp = arr[i];
			arr[i] = arr[j];
			arr[j] = tmp;
		}
	}
	//将基准归为(这一步过后，基准已经是排好序的了)
	arr[left] = arr[i];//当循环结束，此时i = j，将这个位置的数和基准交换
	arr[i] = sta;

	//递归实现
	my_qsort(left, i - 1);//处理此时基准左边部分的数
	my_qsort(i + 1, right);//处理基准右边部分的数
}

int main()
{
	int n = 0;
	scanf("%d", &n);//给定输入的个数

	for (int i = 0; i < n; i++)//循环给数组赋值
	{
		scanf("%d", &arr[i]);
	}

	my_qsort(0 , n - 1);//由于数组元素对应到下标需要减1，我们这里直接减1再传进去就更方便编写程序者思考和使用
	//y_qsort(1, n);    //不过如果在实际应用中，只能这样传，然后函数实现的时候再减1，因为一般用户是不知道数组的这个特点的，只能让其按常识进行传参

	for (int i = 0; i < n; 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
58
59
60
61
62
63
64
65
66
67
68
69
70

参考文章

https://blog.csdn.net/Czc1357618897/article/details/121600596