初夏小谈：排序算法---快速排序（超详解）（三种方式实现及优化版本）

       快速排序正如它的名字一样牛逼，它是实践中最快的已知排序算法。那么快速排序是怎么一种排法呢？往下看 

       快速排序是利用了分治的思想，分而治之。将一个大的问题拆分成几个子问题，那么解决掉这些子问题，用它们的解将得到原问题的解。

       它的算法思想是：三步骤

       ①：首先选择一个基准值（这个基准值可以是待排数列中的任意一个）

       ②：把小于基准值的所有元素全部移到基准值的左边，把所有大于基准值的元素全部移到基准值的右边（切块操作，此时基准值的位置便是最终位置）

       ③：数列被切分为两部分，就继续对这两部分继续进行上述两部操作，直到所有子集合不在满足切分条件

可以简称：选基准，分两边，重复做

        举个例子：5,6,3,8,9,7（去掉3是因为如果基准值是3则第一趟无法看到i与j的变化过程，因为3是最小的）

                           

        开始取到最后一个元素为基准值。（指向数列第一个元素，j指向最后一个）（i先走）

                     

         第一次i所在下标的值和基准值相比较，发现小于7所以i继续向后走一步，j不走

                       

         第二次i所在下标的值和基准值相比较，发现还是小于7所以i继续向后走一步，j不走

                       

        第三次3依旧比7（基准值）小，i继续向后走，j不动

                      

      第四次发现i下标所在的值8比7（基准值）大，则i不在往前走

                     

       第一次j和基准值一样所以j继续往前走

                      

       第二次j下标所在值还是比7大，继续往前走

                    

       第三次j和i相遇终止循环。

                     

     这次交换在这里看着没有意义，其实它是在交换最后一个最小的值和第一个最大的值。

                      

    此时已经将数组分为两部分，即i下标以前都比基准值小，j下标以后都比基准值大（不包含基准值位置），此时将基准值和第一个比基准值大的元素交换。并且记录此时基准值的下标。

  一趟快排就完成了，后面就是一次递归。

代码如下：

头文件：

#include<stdio.h>

//交换两个数
void SwapNum(int* num1, int* num2);

//打印数组
void PrintArray(int array[], int size);

//快速排序
//快速排序1基准值在中间
//left 数组第一个元素下标，right数组最后一个元素下标
void QuickSort(int array[], int left, int right);

函数体：

#include"QuickSort.h"

//交换两个数
void SwapNum(int* num1, int* num2)
{
	int temp = *num1;
	*num1 = *num2;
	*num2 = temp;
}

//打印数组
void PrintArray(int array[], int size)
{
	int i = 0;
	while (i < size)
	{
		printf("%d ", array[i]);
		i++;
	}
	printf("\n");
}

//快速排序1基准值在中间
//left 数组第一个元素下标，right数组最后一个元素下标
void QuickSort(int array[], int left, int right)
{
	if (left >= right)
	{
		return;
	}
	///进行一趟排序
	int mid = right;
	int i = left, j = right;
	while (i < j)
	{
		while (i < j&&array[i] <= array[mid])
		{
			i++;
		}
		while (i < j&&array[j] >= array[mid])
		{
			j--;
		}
		SwapNum(&array[i], &array[j]);
	}
	SwapNum(&array[i], &array[mid]);
	mid = i;
	//尾递归实现
	QuickSort(array, left, mid - 1);
	QuickSort(array, mid + 1, right);
}

main函数：

#include"QuickSort.h"
#include<stdlib.h>

int main()
{
	int array[] = { 5,6,3,8,9,7};
	int size = sizeof(array) / sizeof(array[0]);
	int left = 0;
	int right = size - 1;
	PrintArray(array, size);
	//进行快速排序
	QuickSort(array, left , right);
	printf("快速排序：");
	PrintArray(array, size);
	system("pause");
	return 0;
}

结果显示：

快速排序的其它两种不同版本：

一、挖坑法：就是把基准值先保存起来，然后先去从左到右找比基准值大的数填进去，这时左边就有一个坑，接着从右往左找到比基准值小的填进去。以此类推。最后再把基准值填到最终的坑上。

代码如下：

//快速排序2挖坑法基准值在中间
//left 数组第一个元素下标，right数组最后一个元素下标
void QuickSort2(int array[], int left, int right)
{
	if (left >= right)
	{
		return;
	}
	///进行一趟排序
	int mid = array[right];
	int i = left, j = right;
	while (i < j)
	{
		while (i < j&&array[i] <= mid)
		{
			i++;
		}
		array[j] = array[i];
		while (i < j&&array[j] >= mid)
		{
			j--;
		}
		array[i] = array[j];
	}
	//将基准值放到最后的坑中
	array[i] = mid;
	//尾递归实现
	QuickSort(array, left, i - 1);
	QuickSort(array, i + 1, right);
}

第二种：拉帘法：

此时i，j都指向第一个元素，i往后走遇见比基准值小的，就和j所在下标的值进行交换j往前走一步。直到i走到数组尽头。

函数实现：

//快速排序3基准值在后边i，j都从头开始
//left 数组第一个元素下标，right数组最后一个元素下标
void QuickSort3(int array[], int left, int right)
{
	if (left >= right)
	{
		return;
	}
	///进行一趟排序
	int mid = right;
	int i = left, j = left;
	for (i = left; i <= right; i++)
	{
		if (array[i] < array[mid])
		{
			SwapNum(&array[i], &array[j]);
			j++;
		}
	}
	SwapNum(&array[j], &array[mid]);
	mid = j;
	//尾递归实现
	QuickSort(array, left, mid - 1);
	QuickSort(array, mid + 1, right);
}

快速排序的优化：

              存在问题：在以上排序中都有许多重复的比较，以及基准值的取值可能取到最值的情况。

             解决办法：①：针对基准值：可以采取三数取中值法，就是一次取到数列第一个，中间一个，和最后一个。进行排序，取到中值，确保不会取到最值。

                               ②：针对重复的问题可以中值和数组的倒数第二个交换，j取倒数第三个，因为最后一个一定比中值大，没有必要再去比较。

快速排序优化版本：

头文件：

//快速排序
void QuickSort(int array[], int left, int right);

函数体：

#include"QuickSort.h"


void Swap(int* num1, int* num2)
{
	int temp = *num1;
	*num1 = *num2;
	*num2 = temp;
}
//快速排序
//left左下标 right右下标
void QuickSort(int array[], int left, int right)
{
	//有一个数或者没有
	if (right - left <= 0)
	{
		return;
	}

	int i = left;
	int j = right;
	int mid = (j + i) / 2;

	//有两个数
	if (right - left == 1)
	{
		if (array[mid] > array[mid + 1])
		{
			Swap(&array[mid + 1], &array[mid]);
			mid = mid + 1;
			return;
		}
		return;
	}

	//取三数中值为基准
	//至少有三个数
	//3 6 2
	if (right - left > 1)
	{
		if (array[mid] > array[j])
		{
			Swap(&array[mid], &array[j]);
		}
		if (array[i] > array[j])
		{
			Swap(&array[i], &array[j]);
		}
		if (array[i] > array[mid])
		{
			Swap(&array[i], &array[mid]);
		}
	}

	//至少有四个数
	if (right - left > 2)
	{
		//将中值和倒数第二个值进行交换并且记录中值所在下标
		Swap(&array[mid], &array[right - 1]);
		mid = right - 1;

		//最右边j开始的下标
		j = right - 2;
		i = left + 1;
		while (i < j)
		{
			if (array[i] > array[mid])
			{
				while (i < j)
				{
					if (array[j] < array[mid])
					{
						Swap(&array[i], &array[j]);
						break;
					}
					j--;
				}
			}
			if (i < j)
			{
				i++;
			}
		}
		//将一趟交换后第一个大于中值的元素进行交换并且记录中值下标
		if (array[i] > array[mid])
		{
			Swap(&array[i], &array[mid]);
			mid = i;
		}
		QuickSort(array, left, mid - 1);
		QuickSort(array, mid + 1, right);
	}
}

main函数：

#include"QuickSort.h"
#include<stdio.h>
#include<time.h>
#include<stdlib.h>
#define SIZE 100

int main()
{
	srand((unsigned int)time(NULL));
	int array[SIZE];
	for (int i = 0; i < SIZE; i++)
	{
		array[i] = rand() % 100;
	}
	/*int array[] = { 62,62,2,79,0,15};*/
	int Left = 0;
	int Right = sizeof(array) / sizeof(array[0]) - 1;
	printf("未 排 序：");
	for (int i = 0; i <= Right; i++)
	{
		printf("%d ", array[i]);
	}
	printf("\n");
	QuickSort(array, Left, Right);
	printf("快速排序：");
	for (int i = 0; i <= Right; i++)
	{
		printf("%d ", array[i]);
	}
	printf("\n");
	system("pause");
	return 0;
}

结果显示：

如有疑问欢迎留言。

                                                                                                                                                                                      珍&源码