基础数据结构——快速排序

• 原理
• • 规则
  • 图示
  • C语言代码（递归）
  • 优化
  • • 1.改变排序方法
    • 2.三数取中法
  • 运行示例
  • 评价

每次找到基准值，以基准值为分界线，左边的值全部比基准值小，右边的值全部比基准值大。

1. 从右向左找比基准值小的数据，找到后放到左边；
2. 从左向右找比基准值大的数据，找到后放到右边；
3. 重复 1、2操作，如果 left == right （下标），循环退出，再将基准值放到nums[left]或nums[right]。

原始数据

int nums[] = {333, 124, 0, 65, 15, 7, 22, 888, 1, 456 };

执行步骤一和二

如果left == right，将保存的基准值放入其中

划分，把上个基准值左边的数据和右边的数据再重复上述步骤。

例如左边数据

#include
#include
#include

static void Quick(int* nums, int left, int right);
static int Partition(int* nums, int left, int right);

void Quick_Sort(int* nums, int numsSize)
{
	assert(nums != NULL);

	Quick(nums, 0, numsSize - 1);
}

static void Quick(int* nums, int left, int right)
{
	if (left < right)  // 1
	{
		int par = Partition(nums, left, right);

		if (left < par - 1)  // 2
		{
			Quick(nums, left, par - 1);
		}

		if (par + 1 < right)  // 3
		{
			Quick(nums, par + 1, right);
		}
	}
}
static int Partition(int* nums, int left, int right)
{
	
	int key = nums[left];  // 4

	//重复三个规则
	while (left < right)  // 5
	{
		while (left < right && nums[right] > key)  //6
			right--;
		if (left == right)  //7
		{
			break;
		}
		nums[left] = nums[right];  // 8

		while (left < right && nums[left] < key) //9
			left++;
		if (left == right) //10
		{
			break;
		}
		nums[right] = nums[left]; //11
	}

	nums[left] = key; //nums[right] = key

	return left; //return right
}

1. 确保需要排序的数据最少有两个
2. 保证基准值左边的数据最少有两个
3. 保证基准值右边的数据至少有两个 （2、3为安全控制，可以不用加，是为了更好解释递归时参数为什么是那样写的）。
4. 保存基准值到key中
5. 保证最少有两个数据
6. 从右向左找比基准值小的
7. 代表找到了基准值该放的位置
8. 否则就是找到了比基准值小的值，放到nums[left]
9. 从左向右找比基准值大的
10. 代表找到了基准值该放的位置
11. 否则就是找到了比基准值大的值，放到nums[right]

几种经典的优化

如果 right - left 判断出数据非常小，可改用其他排序方法，直接插入或冒泡等等都行。

	if(right-left <= 100)
	{
		return BubbleSort(arr, right-left);
	}

取第一个值，中间的值，和最后一个值进行比较，比出一个不大不小的值当作基准值。

void ThreeNumGetMid(int* nums, int left, int mid, int right)
{	
	if(arr[left] > arr[right])//左边的值大于右边的值
	{
		int tmp = arr[left];
		arr[left] = arr[right];
		arr[right] = tmp;
	}//代表着 left和right中较小的值保存在左端   

	if(arr[left] < arr[mid])
	{
		int tmp = arr[left];
		arr[left] = arr[mid];
		arr[mid] = tmp;
	}//此刻能保证left保存的值  肯定比mid的大

	if(left > right)
	{
		int tmp = arr[left];
		arr[left] = arr[right];
		arr[right] = tmp;
	}
}

int main(void)
{
	int nums[] = { 333, 124, 0, 65, 15, 7, 22, 888, 1, 456 };
	int len = sizeof(nums) / sizeof(nums[0]);

	Quick_Sort(nums, len);
	for (int i = 0; i < len; ++i)
	{
		printf("%d ", nums[i]);
	}
	printf("n");

	return 0;
}

特点：
越乱越有序，即越乱效率越高
（如果已经有序，时间复杂度会提高到O(n^2) ）

1. 时间复杂度：O(nlogn)
2. 空间复杂度：O(logn)
3. 稳定性：不稳定（存在跳跃交换）