基础算法-快速法排序

偏执的太偏执、 2021-09-27 10:02 416阅读 0赞

快速排序是一种常用的排序方法。

快速排序的思想是：

首先在数组中选定一个参考值。这个参考值的作用是：将整个数组分成两个部分。小于这个参考值的所有值都在参考值的左边，大于这个参考值的所有值都在参考值的右边。

<table style="width:500px;">  快速法排序参考值二分示意表  
 <tbody> 
  <tr> 
   <td style="background-color:#ff9900;text-align:center;vertical-align:middle;">小于参考值的部分</td> 
   <td style="background-color:#ff9900;text-align:center;vertical-align:middle;">参考值</td> 
   <td style="background-color:#ff9900;text-align:center;vertical-align:middle;">大于参考值的部分</td> 
  </tr> 
 </tbody> 
</table>

然后对小于参考值的部分和大于参考值的部分，分别使用相同的方法。直到这个部分无法再分为止。这就是快速排序的算法。

--------------------

例子. 给定一个整型数组，使用快速法进行排序。

接下里开始快速法排序。默认的是升序排序。

下面是原始的数据，共有10个元素。记为：

int originalData[10];

数组的内容如下所示。

--------------------

第一轮：

1、选定一个参考值，记为

int standardValue;

这里以第一个位置的元素为参考值，则

standardValue = 1;

2、需要两个下标来访问元素。一个称为左游标，初始化为0；一个称为右游标，初始化为9（数组长度-1）；

记为：

左游标

int leftIndex = 0;

右游标

int rightIndex = 9;

3、让右游标从右向左移动，在移动的过程中寻找到一个比参考值standardValue小的值。当找到这样的值的时候，此时

rightIndex = 3;
    originalData[rightIndex] = -12 < standardValue = 1;

4、将右游标指示位置的值放到左游标指示的位置上；即

originalData[leftIndex] = originalData[rightIndex];

此时数组情况如下：

standardValue = 1;
    leftIndex = 0;
    rightIndex = 3;

数组的内容如下所示。

5、让左游标从左向右移动，在移动的过程中寻找到一个比参考值standardValue大的值。当找到这样的值的时候，此时

leftIndex = 1;
    originalData[leftIndex] = 10 > standardValue = 1;

6、将左游标指示位置的值放到右游标指示的位置上；即

originalData[rightIndex] = originalData[leftIndex];

此时数组情况如下：

standardValue = 1;
    leftIndex = 1;
    rightIndex = 3;

7、让右游标从右向左移动，在移动的过程中寻找到一个比参考值 standardValue 小的值。结果是没有找到。

当

leftIndex = rightIndex

时，结束此轮排序。此时

leftIndex = rightIndex = 1;

需要将参考值放回到数组中。即

originalData[leftIndex] = standardValue = 1;

此时，数组的内容是如下，

--------------------

第二轮：

以元素值1为线，将数组分为两个部分。左边的部分小于等于1，右边的部分大于等于1。

将数组左边部分的子数组（黄色部分）看做是一个新数组，执行同样的操作。

<table style="width:500px;">  左边部分的子数组  
 <tbody> 
  <tr> 
   <td style="background-color:#ff9900;text-align:center;vertical-align:middle;">-12</td> 
  </tr> 
 </tbody> 
</table>

左边部分的子数组已经有序。

将数组右边部分的子数组（蓝色部分）看做是一个新数组，执行同样的操作。

<table style="width:500px;">  右边部分的子数组  
 <tbody> 
  <tr> 
   <td style="background-color:#33ffff;text-align:center;vertical-align:middle;">3</td> 
   <td style="background-color:#33ffff;text-align:center;vertical-align:middle;">10</td> 
   <td style="background-color:#33ffff;text-align:center;vertical-align:middle;">51</td> 
   <td style="background-color:#33ffff;text-align:center;vertical-align:middle;">23</td> 
   <td style="background-color:#33ffff;text-align:center;vertical-align:middle;">1</td> 
   <td style="background-color:#33ffff;text-align:center;vertical-align:middle;">4</td> 
   <td style="background-color:#33ffff;text-align:center;vertical-align:middle;">12</td> 
   <td style="background-color:#33ffff;text-align:center;vertical-align:middle;">4</td> 
  </tr> 
 </tbody> 
</table>

同样的步骤下，会得到结果，如下所示。

<table style="width:500px;">  右边部分的子数组  
 <tbody> 
  <tr> 
   <td style="background-color:#ff9933;text-align:center;vertical-align:middle;">1</td> 
   <td style="background-color:#ff0033;text-align:center;vertical-align:middle;">3</td> 
   <td style="background-color:#33ffff;text-align:center;vertical-align:middle;">51</td> 
   <td style="background-color:#33ffff;text-align:center;vertical-align:middle;">23</td> 
   <td style="background-color:#33ffff;text-align:center;vertical-align:middle;">10</td> 
   <td style="background-color:#33ffff;text-align:center;vertical-align:middle;">4</td> 
   <td style="background-color:#33ffff;text-align:center;vertical-align:middle;">12</td> 
   <td style="background-color:#33ffff;text-align:center;vertical-align:middle;">4</td> 
  </tr> 
 </tbody> 
</table>

--------------------

第三轮：

以元素值3为线，将数组分为两个部分。左边的部分小于等于3，右边的部分大于等于3。

将数组左边部分的子数组（黄色部分）看做是一个新数组，执行同样的操作。

<table style="width:500px;">  左边部分的子数组  
 <tbody> 
  <tr> 
   <td style="background-color:#ff9900;text-align:center;vertical-align:middle;">1</td> 
  </tr> 
 </tbody> 
</table>

将数组右边部分的子数组（蓝色部分）看做是一个新数组，执行同样的操作。

<table style="width:500px;">  右边部分的子数组  
 <tbody> 
  <tr> 
   <td style="background-color:#33ffff;text-align:center;vertical-align:middle;">51</td> 
   <td style="background-color:#33ffff;text-align:center;vertical-align:middle;">23</td> 
   <td style="background-color:#33ffff;text-align:center;vertical-align:middle;">10</td> 
   <td style="background-color:#33ffff;text-align:center;vertical-align:middle;">4</td> 
   <td style="background-color:#33ffff;text-align:center;vertical-align:middle;">12</td> 
   <td style="background-color:#33ffff;text-align:center;vertical-align:middle;">4</td> 
  </tr> 
 </tbody> 
</table>

同样的步骤下，会得到结果，如下所示。

--------------------

第四轮：

以元素值51为线，将数组分为两个部分。左边的部分小于等于51，右边的部分大于等于51。

现在只剩下左边的部分了。

将数组左边部分的子数组（黄色部分）看做是一个新数组，执行同样的操作。

<table style="width:500px;">  左边的子数组  
 <tbody> 
  <tr> 
   <td style="background-color:#ff9900;text-align:center;vertical-align:middle;">4</td> 
   <td style="background-color:#ff9900;text-align:center;vertical-align:middle;">23</td> 
   <td style="background-color:#ff9900;text-align:center;vertical-align:middle;">10</td> 
   <td style="background-color:#ff9900;text-align:center;vertical-align:middle;">4</td> 
   <td style="background-color:#ff9900;text-align:center;vertical-align:middle;">12</td> 
  </tr> 
 </tbody> 
</table>

同样的步骤下，会得到结果，如下所示。

--------------------

第五轮：

以元素值4为线，将数组分为两个部分。左边的部分小于等于4，右边的部分大于等于4。

现在只剩下右边的部分了。

<table style="width:500px;">  右边的子数组  
 <tbody> 
  <tr> 
   <td style="background-color:#33ffff;text-align:center;vertical-align:middle;">23</td> 
   <td style="background-color:#33ffff;text-align:center;vertical-align:middle;">10</td> 
   <td style="background-color:#33ffff;text-align:center;vertical-align:middle;">4</td> 
   <td style="background-color:#33ffff;text-align:center;vertical-align:middle;">12</td> 
  </tr> 
 </tbody> 
</table>

同样的步骤下，会得到结果，如下所示。

--------------------

第六轮：

以元素值23为线，将数组分为两个部分。左边的部分小于等于23，右边的部分大于等于23。

现在只剩下左边的部分了。

<table style="width:500px;">  左边的子数组  
 <tbody> 
  <tr> 
   <td style="background-color:#ff9933;text-align:center;vertical-align:middle;">12</td> 
   <td style="background-color:#ff9933;text-align:center;vertical-align:middle;">10</td> 
   <td style="background-color:#ff9933;text-align:center;vertical-align:middle;">4</td> 
  </tr> 
 </tbody> 
</table>

同样的步骤下，会得到结果，如下所示。

--------------------

第七轮：

以元素值12为线，将数组分为两个部分。左边的部分小于等于12，右边的部分大于等于12。

现在只剩下左边的部分了。

<table style="width:500px;">  左边的子数组  
 <tbody> 
  <tr> 
   <td style="background-color:#ff9933;text-align:center;vertical-align:middle;">4</td> 
   <td style="background-color:#ff9933;text-align:center;vertical-align:middle;">10</td> 
  </tr> 
 </tbody> 
</table>

现在剩下的数组已经有序了。

并且所有的元素都已经有序，所以任务结束。

--------------------

按照位置顺序将这些子数组拼凑起来，得到如下的数组。

<table style="width:500px;">  排序后的数组  
 <tbody> 
  <tr> 
   <td style="background-color:#ff9933;text-align:center;vertical-align:middle;">-12</td> 
   <td style="background-color:#ff9933;text-align:center;vertical-align:middle;">1</td> 
   <td style="background-color:#ff9933;text-align:center;vertical-align:middle;">1</td> 
   <td style="background-color:#ff9933;text-align:center;vertical-align:middle;">3</td> 
   <td style="background-color:#ff9933;text-align:center;vertical-align:middle;">4</td> 
   <td style="background-color:#ff9933;text-align:center;vertical-align:middle;">4</td> 
   <td style="background-color:#ff9933;text-align:center;vertical-align:middle;">10</td> 
   <td style="background-color:#ff9933;text-align:center;vertical-align:middle;">12</td> 
   <td style="background-color:#ff9933;text-align:center;vertical-align:middle;">23</td> 
   <td style="background-color:#ff9933;text-align:center;vertical-align:middle;">51</td> 
  </tr> 
 </tbody> 
</table>

原数组为：

排序得到了正确的升序结果。（相等的值没有改变相对位置，所以是稳定的排序算法。）

--------------------

下面给出C++的代码实现，源代码仅供参考。

#include <iostream>
    using namespace std;
    
    // 前向声明.
    void quickSort(int *originalArray, int leftIndex, int rightIndex);
    
    int main()
    {
    	// 整数的个数.
    	int numbers = 0;
    	cin >> numbers;
    
    	// 保存整数的数组.
    	int *originalData = new int[numbers];
    
    	// 从标准输入中读取数据.
    	for (int i = 0; i < numbers; ++i)
    	{
    		cin >> originalData[i];
    	}
    
    	// 对数据进行排序.
    	// 使用二分排序法.
    	quickSort(originalData, 0, numbers - 1);
    
    	// 输出最小值和最大值.
    	cout << originalData[0] << " " << originalData[numbers - 1] << endl;
    
    	return 0;
    }
    
    void quickSort(int *originalArray, int leftIndex, int rightIndex)
    {
    	// leftIndex 的备份.
    	int backLeft = leftIndex;
    
    	// rightIndex 的备份.
    	int backRight = rightIndex;
    
    	// 递归结束条件.
    	if (leftIndex > rightIndex)
    	{
    		// nothing to do.
    	}
    	else
    	{
    		// 参考标准.
    		int standardValue = originalArray[leftIndex];
    
    		while (leftIndex < rightIndex)
    		{
    			// 在 middleIndex 的右边部分,从后往前找到一个比 middleIndex 元素值小的元素.
    			while (leftIndex < rightIndex)
    			{
    				if (originalArray[rightIndex] >= standardValue)
    				{
    					// next element.
    					--rightIndex;
    				}
    				else
    				{
    					break;
    				}
    			}
    			originalArray[leftIndex] = originalArray[rightIndex];
    			
    			// 在 middleIndex 的左边部分,从前往后找到一个比 middleIndex 元素值大的元素.
    			while (leftIndex < rightIndex)
    			{
    				if (originalArray[leftIndex] <= standardValue)
    				{
    					// next element.
    					++leftIndex;
    				}
    				else
    				{
    					break;
    				}
    			}
    			originalArray[rightIndex] = originalArray[leftIndex];
    		}
    
    		// 保存标准值.
    		originalArray[leftIndex] = standardValue;
    
    		// 递归调用自身.
    		quickSort(originalArray, backLeft, leftIndex - 1);
    		quickSort(originalArray, leftIndex + 1, backRight);
    	}
    }

以下为Java 代码，源代码仅供参考.

import java.util.Arrays;
    import java.util.Scanner;
    
    public class QuickSort
    {
    	public static void main(String[] args)
    	{
    		Scanner scanner = new Scanner(System.in);
    
    		int numbers = Integer.parseInt(scanner.nextLine());
    
    		int[] originalArray = new int[numbers];
    		for (int i = 0; i < numbers; ++i)
    		{
    			originalArray[i] = scanner.nextInt();
    		}
    		quickSort(originalArray, 0, numbers - 1);
    		System.out.println(Arrays.toString(originalArray));
    		scanner.close();
    	}
    
    	public static void quickSort(int[] originalData, int leftIndex, int rightIndex)
    	{
    		int backLeft = leftIndex;
    		int backRight = rightIndex;
    		if (leftIndex > rightIndex)
    		{
    			// nothing to do.
    		}
    		else
    		{
    			int standardValue = originalData[leftIndex];
    			while (leftIndex < rightIndex)
    			{
    				while (leftIndex < rightIndex)
    				{
    					if (originalData[rightIndex] >= standardValue)
    					{
    						// next element.
    						--rightIndex;
    					}
    					else
    					{
    						break;
    					}
    				}
    				originalData[leftIndex] = originalData[rightIndex];
    
    				while (leftIndex < rightIndex)
    				{
    					if (originalData[leftIndex] <= standardValue)
    					{
    						// next element.
    						++leftIndex;
    					}
    					else
    					{
    						break;
    					}
    				}
    				originalData[rightIndex] = originalData[leftIndex];
    			}
    
    			originalData[leftIndex] = standardValue;
    
    			// 递归调用自身.
    			quickSort(originalData, backLeft, leftIndex - 1);
    			quickSort(originalData, leftIndex + 1, backRight);
    		}
    	}
    }

Over!