DoubleRight The past of the world Blog's

快速排序 Java 示例

快速排序 Java 示例

原文： https://howtodoinjava.com/algorithm/quicksort-java-example/

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

用更标准的词来说，快速排序算法通过与枢轴元素进行比较，将未排序的部分重复地分为低阶子部分和高阶子部分。 递归结束时，我们得到了排序数组。 请注意，可以将快速排序实现为“就地”排序。 这意味着排序在数组中进行，不需要创建其他数组。

快速排序算法

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

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

  1. 通常从中间选择一个元素作为枢轴元素，但这不是必需的。
  2. 数据元素分为两部分：一个元素的顺序比枢轴元素低，一个元素的顺序比枢轴元素高。
  3. 重复步骤 1 和 2，分别对这两部分进行排序。

快速排序 Java 示例

以下是示例快速排序 Java 实现。

public class QuickSortExample 
{
	public static void main(String[] args) 
	{
		// This is unsorted array
		Integer[] array = new Integer[] { 12, 13, 24, 10, 3, 6, 90, 70 };

		// Let's sort using quick sort
		quickSort( array, 0, array.length - 1 );

		// Verify sorted array
		System.out.println(Arrays.toString(array));
	}

	public static void quickSort(Integer[] arr, int low, int high) 
	{
		//check for empty or null array
		if (arr == null || arr.length == 0){
			return;
		}

		if (low >= high){
			return;
		}

		//Get the pivot element from the middle of the list
		int middle = low + (high - low) / 2;
		int pivot = arr[middle];

		// make left < pivot and right > pivot
		int i = low, j = high;
		while (i <= j) 
		{
			//Check until all values on left side array are lower than pivot
			while (arr[i] < pivot) 
			{
				i++;
			}
			//Check until all values on left side array are greater than pivot
			while (arr[j] > pivot) 
			{
				j--;
			}
			//Now compare values from both side of lists to see if they need swapping 
			//After swapping move the iterator on both lists
			if (i <= j) 
			{
				swap (arr, i, j);
				i++;
				j--;
			}
		}
		//Do same operation as above recursively to sort two sub arrays
		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()方法使用快速排序算法使用双枢轴元素对原始类型数组进行排序。 双枢轴使该算法更快。 检查出。

学习愉快！

搜索