Algorithm-排序算法-快速排序

快速排序算法是交换类排序算法，核心思想是分治思想，将待排序元素分割成两个待排序序列进行排序。

算法描述

1. 从待排序序列中选择一个元素作为基准值（pivot）；
2. 以基准值为标准分割待排序序列，使得所有比基准值大的元素排列在基准值的后面，所有比基准值小的元素排列在基准值的前面；
3. 在分割后的待排序序列中重复1）2）步骤，直到排序完成。

动态演示

算法实现

1.快速排序算法

package com.lreis.algorithm.sort;

public class QuickSort {

	public static void sort(int arr[]) {
		if (arr == null || arr.length == 0)
			return;
		quickSort(arr, 0, arr.length - 1);

	}

	/**
	 * 递归分片排序
	 */
	private static void quickSort(int arr[], int low, int high) {
		if (low >= high)
			return;
		int part_index = partation(arr, low, high);
		quickSort(arr, low, part_index - 1);
		quickSort(arr, part_index + 1, high);
	}

	/**
	 * 分片排列待排序元素 </br>
	 * 1.选择比较基数</br>
	 * 2.排列数组元素，使得大于基数的元素在基数的右侧，小于基数的元素在基数的左侧</br>
	 * 3.返回基数目前的索引位置
	 */
	private static int partation(int arr[], int low, int high) {
		// 基数
		int pivot = low;
		int base = arr[pivot];
		// 比较
		int index = pivot + 1;
		for (int i = index; i <= high; i++) {
			if (arr[i] < base) {
				int tmp = arr[index];
				arr[index] = arr[i];
				arr[i] = tmp;
				index++;
			}
		}
		if (index != pivot + 1) {
			int tmp = arr[index - 1];
			arr[index - 1] = base;
			arr[pivot] = tmp;
		}
		return index - 1;
	}

	public static void main(String[] args) {
		int arr[] = { 1, 6, 79, 214, 745, 4, 7, 19, 4, 10 };
		QuickSort.sort(arr);
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i] + " ");
		}
	}

}