首页 > 代码库 > 快速排序算法

快速排序算法

快速排序

快速排序属于交换排序中的一种,它通过选定一个元素为中间元素,然后将表中所有元素与该中间元素相比较,将表中比中间元素小的放到表前面,大的放表后面,再将中间元素放置在这两部分之间作为分界点,这样便得到一个划分,使左边的元素都小于右边的,然后对左边与右边的再进行快速排序。

 

 

 

 

Java代码实现如下

public class QuickSort {	public static void main(String[] args) {		int[] arr = { 6, 3, 7, 10, 2, 9, 15, 10, 8, 17 };		qsort(arr, 0, arr.length - 1);				for (int temp : arr) {			System.out.println(temp);		}	}	private static void qsort(int[] arr, int low, int high) {		if (low < high) {			int pivot = partition(arr, low, high); // 将数组分为两部分			qsort(arr, low, pivot - 1); // 递归排序左子数组			qsort(arr, pivot + 1, high); // 递归排序右子数组		}	}	private static int partition(int[] arr, int low, int high) {		int pivot = arr[low]; // 保存中间元素以腾出空位		while (low < high) {			while (low < high && arr[high] >= pivot)				--high;			arr[low] = arr[high]; // 交换比中间元素小的记录到左端			while (low < high && arr[low] <= pivot)				++low;			arr[high] = arr[low]; // 交换比中间元素小的记录到右端		}		// 扫描完成		arr[low] = pivot;		// 返回的是中间元素的位置		return low;	}}

 

快速排序算法