快速排序或者分区交换排序，是一种排序算法，它是使用划分和征服算法。

快速排序，我们首先选择一个

pivot并分为两个子师，一个将包含元素 lower than pivot其他将有元素 greater than pivot。

快速排序算法

让我们说数组是arr []

• 选择一个 pivot，它通常是列表的中间元素。
• 初始化两个索引变量， left=0和 right=arr.length-1
• 递增左变量，直到获得高于枢轴的元素。
• 递减右变量，直到你得到的元素小于枢轴
• 交换 arr[left]和 arr[right]
• Recursively sort sublists(子钻人物少于枢轴，子夹比枢轴更大)，使用上述算法。
• 最终，你会得到 sorted array。

快速排序实现

package org.igi.theitroad;
 
import java.util.Arrays;
 
public class QuickSortMain {
 
	private static int array[];
 
	public static void sort(int[] arr) {
 
		if (arr == null || arr.length == 0) {
			return;
		}
		array = arr;
		quickSort(0, array.length-1);
	}
 
	private static void quickSort(int left, int right) {
 
		int i = left;
		int j = right;
		//find pivot number, we will take it as mid
		int pivot = array[left+(right-left)/2];
 
		while (i <= j) {
			/**
			 * In each iteration, we will increment left until we find element greater than pivot
			 * We will decrement right until we find element less than pivot
			 */
			while (array[i] < pivot) { i++; } while (array[j] > pivot) {
				j--;
			}
			if (i <= j) {
				exchange(i, j);
				//move index to next position on both sides
				i++;
				j--;
			}
		}
		//call quickSort() method recursively
		if (left < j)
			quickSort(left, j);
		if (i < right)
			quickSort(i, right);
	}
 
	private static void exchange(int i, int j) {
		int temp = array[i];
		array[i] = array[j];
		array[j] = temp;
	}
 
	public static void main(String a[]){
		int[] input = {33,21,45,64,55,34,11,8,3,5,1};
		System.out.println("Before Sorting : ");
		System.out.println(Arrays.toString(input));
		sort(input);
		System.out.println("==================");
		System.out.println("After Sorting : ");
		System.out.println(Arrays.toString(array));
 
	}
}

输出：

Before Sorting :
[33, 21, 45, 64, 55, 34, 11, 8, 3, 5, 1]
==================
After Sorting :
[1, 3, 5, 8, 11, 21, 33, 34, 45, 55, 64]

时间复杂性

最佳情况： O(n log n)平均情况： O(n log n)最坏的情况下 ： O(n^2)