【408数据结构与算法】—快速排序（十九）

一、🤣快速排序的基本思想

任取一个元素（如：第一个）为中心
所有比它小的元素一律前放，比它大的元素一律后放，形成左右两个子表
对各子表重新选择中心元素并依此规则调整
直到每个子表的元素只剩一个

二、😛快速排序演示

基本思想：通过一趟排序，将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录进行排序，以达到整个序列有序。

具体实现：选定一个中间数作为参考，所有元素与之比较，小的调到其左边，大的调到其右边

（枢轴）中间数：可以是第一个数，最后一个数、最中间一个数、任选一个数等
在这里插入图片描述

快速排序的特点

每一趟的子表的形成是采用从两头向中间交替式逼近法

在这里插入图片描述

快排算法

在这里插入图片描述

C语言实现快排

快排是在每轮挑选一个基准元素，并让其比他大的元素移动到数列一边，比他小的元素移动到数列的另一边，从而把数列拆解成两个部分，即分治思想。然后运用递归。
代码演示

#include 

void quickSort(int array[], int left, int right);

int main(void)
{
	int i;
	int array[] = { 5,4,3,2,1,10,9,8,7,6 };	//待排序数组
	int len = sizeof(array) / sizeof(int);	//数组的长度

	quickSort(array, 0, len - 1);	//排序

	for (i = 0; i < 10; i++)	//打印排序后的数组
		printf("%d\n", array[i]);

	return 0;
}

void quickSort(int array[], int left, int right)
{
	int i, j, key;
	if (left >= right)
		return;
	i = left; j = right;
	key = array[i];	//取最左边的元素作为key
	while (i < j)
	{	//始终保持i < j
		while (i < j && array[j] > key)//右指针向左
			j--;
		if (i < j)	//小于key的放左边
			array[i++] = array[j];

		while (i < j && array[i] < key)//左指针向右
			i++;
		if (i < j)	//大于key的放右边
			array[j--] = array[i];
	}
	array[i] = key;	//最终将key放入i==j处

	quickSort(array, left, i - 1);	//左边递归
	quickSort(array, i + 1, right);	//右边递归
}


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