lcg_magic算法笔记：快速排序

待我称王封你为后i 2021-09-24 18:18 230阅读 0赞

### 文章目录 ###

*  1. 思想
 *  2. 示例
 *  3. 代码

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

# 1. 思想 #

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

快速排序的思想是：

*  首先在数组中选定一个参考值。  
    这个参考值的作用是：将整个数组分成两个部分。小于这个参考值的所有值都在参考值的左边，大于这个参考值的所有值都在参考值的右边。
 *  然后对小于参考值的部分和大于参考值的部分，分别使用相同的方法。直到这个部分无法再分为止。这就是快速排序的算法。

快速法排序参考值二分示意表  
![在这里插入图片描述][20200926163909561.jpg_pic_center]

# 2. 示例 #

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

下面是原始的数据，共有10个元素。记为 ：  
![在这里插入图片描述][2020092616401433.jpg_pic_center]

第一轮排序：  
![在这里插入图片描述][20200926165822288.gif_pic_center]

具体的可以参看文章[基础算法-快速排序][-]，更详细。

# 3. 代码 #

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

[20200926163909561.jpg_pic_center]: /images/20210923/52f965f127f44047acd758735a3e20cc.png
[2020092616401433.jpg_pic_center]: /images/20210923/4072b2c570b14f57ab3166cc3d9ee0e8.png
[20200926165822288.gif_pic_center]: /images/20210923/f36620c3bc104c879b45bdbc006a4ded.png
[-]: https://blog.csdn.net/PursueLuo/article/details/82459600