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] + " ");
		}
	}

}