当前位置:   article > 正文

八大排序之快速排序_快速排序又称

快速排序又称

快速排序(英语:Quicksort),又称划分交换排序(partition-exchange sort),简称快排。

基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

通俗的说,就是先选一个标准值,比标准值小的放在左边,比标准值大的放在右边,再将标准值放在中间(这个位置一定是标准值的最终位置)。然后再分别对左右两边的数据进行同样的操作。

快速排序有三种方法:hover(左右指针法),挖坑法,快慢指针法。虽然有三种方法,但这三种方法的核心思想都是一样的。

hover(左右指针法)

首先说明,这里虽然叫指针,但实际还是通过下标来处理
步骤:

  • 选择最后一个元素为基准值
  • begin从前面开始走,找到比基准值大的元素
  • end从后面开始走,找到比基准值小的元素
  • 将这两个元素交换,直到begin == end结束
  • 将基准值放在中间位置
  • 基准值左右两边的数据重复此过程
	int arr[10] = { 5, 2, 6, 8, 1, 9, 0, 3, 7, 4 };
  • 1

在这里插入图片描述
代码如下:


	int Partition_01(int arr[], int left, int right)
	{
		int begin = left;
		int end = right;
		while (begin < end)
		{
			while (begin < end && arr[begin] <= arr[right])
			{
				begin++;
			}
			while (begin < end && arr[end] >= arr[right])
			{
				end--;
			}
			Swap(arr + begin, arr + end);
		}
		Swap(arr + begin, arr + right);
		return begin;
	}
	void __QuickSort(int arr[], int left, int right)
	{
		if (left == right)
		{
			return;
		}
		if (left > right)
		{
			return;
		}
		int div = Partition_01(arr, left, right);
	
		__QuickSort(arr, left, div - 1);
		__QuickSort(arr, div + 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

挖坑法

挖坑法和左右指针法思想都差不多
步骤:

  • 将最后一个元素(基准值)先保存起来,然后把这个位置当做一个坑
  • begin从前面找一个比基准值大的元素a,将a放入上述坑中,a原来的位置就是新坑
  • end开始从后面找一个比基准值小的元素b,将b放入上述坑中,b原来的位置就是新坑
  • 直到begin == end结束
  • 最后将基准值放入中间的坑中
  • 基准值左右两边的数据按照同样的方法进行操作
	int arr[10] = { 5, 2, 6, 8, 1, 9, 0, 3, 7, 4 };
  • 1

在这里插入图片描述
代码如下:

	int Partition_02(int arr[], int left, int right)
	{
		int begin = left;
		int end = right;
		int priot = arr[right];
	
		while (begin < end)
		{
			while (begin < end && arr[begin] <= priot)
			{
				begin++;
			}
			arr[end] = arr[begin];
			while (begin < end && arr[end] >= priot)
			{
				end--;
			}
			arr[begin] = arr[end];
		}
		arr[begin] = priot;
		return begin;
	}
	void __QuickSort(int arr[], int left, int right)
	{
		if (left == right)
		{
			return;
		}
		if (left > right)
		{
			return;
		}
		int div = Partition_02(arr, left, right);
	
		__QuickSort(arr, left, div - 1);
		__QuickSort(arr, div + 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

快慢指针

快慢指针思想:慢指针找一个比基准值大的数,快指针找一个比基准值小的数,将两者交换位置。
步骤:

  • 快慢指针都从头开始
  • 快指针找到比基准值小的数,将快慢指针交换位置,慢指针走一步
    这样就能保证,慢指针要么和快指针指向头一个元素,要么就指向比基准值大的元素
  • 最后将基准值放在慢指针的位置
  • 对基准值左右两边的数据重复上述过程
	int arr[10] = { 5, 2, 6, 8, 1, 9, 0, 3, 7, 4 };
  • 1

在这里插入图片描述

代码如下:

	int Partition_03(int arr[], int left, int right)
	{
		int cur = left;
		int div = left;
		for (; cur < right; cur++)
		{
			if (arr[cur] < arr[right])
			{
				Swap(arr + cur, arr + div);
				div++;
			}
		}
		Swap(arr + div, arr + right);
		return div;
	}
	
	void __QuickSort(int arr[], int left, int right)
	{
		if (left == right)
		{
			return;
		}
		if (left > right)
		{
			return;
		}
		int div = Partition_03(arr, left, right);
	
		__QuickSort(arr, left, div - 1);
		__QuickSort(arr, div + 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

总结:

上述快排的三种方法都运用了分而治之的思想,也就是将一个大的问题分割成许多个规模相同的小问题来解决。这三种方法都用到了基准值,都是最后将基准值放在中间位置,确定了基准值的位置,然后将基准值两边的数据按照同样的方法进行操作。
在这里插入图片描述

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/繁依Fanyi0/article/detail/499026
推荐阅读
相关标签
  

闽ICP备14008679号