快速排序算法(Quicksort)

快速排序算法的基本思想可以描述为以下步骤：

如果数组只包含一个元素或者零个元素，则对数组进行排序。
如果数组包含多个元素，则：

• 选择一个元素作为枢轴元素，一般从中间但不是必须的。
• 数据元素分为两部分：一组元素的顺序低于枢轴元素，另一部分的元素顺序高于枢轴元素。
• 重复步骤 1 和 2，分别对这两个部分进行排序。

快速排序算法是最常用的排序算法之一，尤其是对大型列表/数组进行排序。
快速排序是一种分而治之的算法，这意味着将原始数组分成两个数组，每个数组单独排序，然后合并排序后的输出以生成排序后的数组。
平均而言，它具有 O(n log n) 复杂度，使得快速排序适合对大数据量进行排序。

快速排序 Java 示例

下面是快速排序 java 实现示例。

public class QuickSortExample 
{
	public static void main(String[] args) 
	{
		//  为排序的数组
		Integer[] array = new Integer[] { 12, 13, 24, 10, 3, 6, 90, 70 };
		// 执行快速排序
		quickSort( array, 0, array.length - 1 );
		// 查看排序后的数组
		System.out.println(Arrays.toString(array));
	}
	public static void quickSort(Integer[] arr, int low, int high) 
	{
		// 检查是否为空数组
		if (arr == null || arr.length == 0){
			return;
		}

		if (low >= high){
			return;
		}
		// 从列表中间获取pivot元素
		int middle = low + (high - low) / 2;
		int pivot = arr[middle];
		// 使 left < pivot 并且 right > pivot
		int i = low, j = high;
		while (i <= j) 
		{
			// 检查直到左侧数组上的所有值都低于pivot值
			while (arr[i] < pivot) 
			{
				i++;
			}
			// 检查直到左侧数组上的所有值都大于pivot
			while (arr[j] > pivot) 
			{
				j--;
			}
			//现在比较列表两侧的值，看看它们是否需要交换
			//交换后，在两个列表上移动迭代器
			if (i <= j) 
			{
				swap (arr, i, j);
				i++;
				j--;
			}
		}
		//递归地执行与上面相同的操作来对两个子数组进行排序
		if (low < j){
			quickSort(arr, low, j);
		}
		if (high > i){
			quickSort(arr, i, high);
		}
	}

	public static void swap (Integer array[], int x, int y)
    {
		int temp = array[x];
		array[x] = array[y];
		array[y] = temp;
    }
}
Output: [3, 6, 10, 12, 13, 24, 70, 90]

在 Java 中，Arrays.sort()方法使用快速排序算法使用双枢轴元素对基元数组进行排序。
双枢轴使该算法更快。