八大排序之快速排序

﹏ヽ暗。殇╰゛Y 2022-04-22 06:16 215阅读 0赞

**快速排序**（英语：Quicksort），又称划分交换排序（partition-exchange sort），简称快排。

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

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

快速排序有三种方法：hover（左右指针法），挖坑法，快慢指针法。虽然有三种方法，但这三种方法的核心思想都是一样的。

## hover（左右指针法） ##

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

*  选择最后一个元素为基准值
 *  begin从前面开始走，找到比基准值大的元素
 *  end从后面开始走，找到比基准值小的元素
 *  将这两个元素交换，直到begin == end结束
 *  将基准值放在中间位置
 *  基准值左右两边的数据重复此过程

int arr[10] = { 5, 2, 6, 8, 1, 9, 0, 3, 7, 4 };

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpeGlhb2Rlc2h1c2h1_size_16_color_FFFFFF_t_70]  
代码如下：

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);
    	}

## 挖坑法 ##

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

*  将最后一个元素（基准值）先保存起来，然后把这个位置当做一个坑
 *  begin从前面找一个比基准值大的元素a，将a放入上述坑中，a原来的位置就是新坑
 *  end开始从后面找一个比基准值小的元素b，将b放入上述坑中，b原来的位置就是新坑
 *  直到begin == end结束
 *  最后将基准值放入中间的坑中
 *  基准值左右两边的数据按照同样的方法进行操作

int arr[10] = { 5, 2, 6, 8, 1, 9, 0, 3, 7, 4 };

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpeGlhb2Rlc2h1c2h1_size_16_color_FFFFFF_t_70 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);
    	}

## 快慢指针 ##

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

*  快慢指针都从头开始
 *  快指针找到比基准值小的数，将快慢指针交换位置，慢指针走一步  
    这样就能保证，慢指针要么和快指针指向头一个元素，要么就指向比基准值大的元素
 *  最后将基准值放在慢指针的位置
 *  对基准值左右两边的数据重复上述过程

int arr[10] = { 5, 2, 6, 8, 1, 9, 0, 3, 7, 4 };

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpeGlhb2Rlc2h1c2h1_size_16_color_FFFFFF_t_70 2]

代码如下：

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);
    	}

## 总结： ##

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

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpeGlhb2Rlc2h1c2h1_size_16_color_FFFFFF_t_70]: /images/20220422/1a0d1b7ae53549548ec1e54e6f95b145.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpeGlhb2Rlc2h1c2h1_size_16_color_FFFFFF_t_70 1]: /images/20220422/795f0418fbf1458883075e492d59f22a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpeGlhb2Rlc2h1c2h1_size_16_color_FFFFFF_t_70 2]: /images/20220422/c639f1ee4fe74a698d6da2a5e5bc6880.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpeGlhb2Rlc2h1c2h1_size_16_color_FFFFFF_t_70 3]: /images/20220422/80823d090db343289f3b797b46f0da4b.png