【数据结构】【排序】快速排序

       快速排序的原理就是使用某个中间值将数组切割成两部分，一部分比中间值都小，另一部分比中间值都大，这是一次排序的作用；分别对两部分进行同样的操作，直到只剩下一个数，这样最终的数组就变成了有序的。

以下是java实现：

package com.kdyzm.sort.quicksort;

import java.util.Scanner;

/**
 * 快速排序相关P272
 * 
 * @author kdyzm
 *
 */
public class QuickSortDemo {
	public static void main(String[] args) {
		int[] array = new int[1024];
		Scanner sc = new Scanner(System.in);
		int total = sc.nextInt();
		for (int i = 0; i < total; i++) {
			array[i] = sc.nextInt();
		}
		quickSort(array, 0, total - 1);
		output(array, total);
	}

	private static void output(int[] array, int total) {
		for (int i = 0; i < total; i++) {
			System.out.print(array[i] + " ");
		}
		System.out.println();
	}

	private static void quickSort(int[] array, int low, int high) {
		if (low < high) {
			int pivotLoc = OneQuickSort(array, low, high);
			quickSort(array, low, pivotLoc - 1);
			quickSort(array, pivotLoc + 1, high);
		}
	}

	/**
	 * 一次快速排序，找出中间点出来
	 */
	private static int OneQuickSort(int[] array, int low, int high) {
		int pivotKey = array[high];
		while (low < high) {
			while (low < high && array[low] <= pivotKey)
				++low;
			array[high] = array[low];
			while (low < high && array[low] >= pivotKey)
				--high;
			array[low] = array[high];
		}
		array[low] = pivotKey;
		return low;
	}
}

 输入N个数作为数组长度，然后输入N个无序的整数，回车即可查看排序结果。