快排的原理是:
选择一个关键值作为基准值,(可以选择第一个,也可以选择最后一个,或者随便选一个,我习惯选第一个)。
将比基准值大的都放在右边的序列中,将比基准值小的都放在左边的序列中。
具体循环过程:从后向前比较,用基准值和最后一个值进行比较。如果比基准值小,则换位,如果比基准值大,则继续比较下一个值,知道找到第一个比基准值小的值才交换位置。
再从前向后比较,如果有比基准值大的,交换位置,如果没有,则继续比较下一个,直到找到第一个比基准值大的值才交换位置,
重复执行上述过程。直到左边都是小于基准值的数,右边都是大于基准值的数。
继续重复循环上述过程。
package sort; /** * @author leon * @描述 快速排序算法实现 */ public class quickSort { public static int[] quickSort(int[] arr, int low, int high) { int start = low; int end = high; int pivot = arr[low]; while (end > start) { while (end > start && arr[end] >= pivot) { end--; } if (arr[end] <= pivot) { swap(arr,end,start); } while (end > start && arr[start] <= pivot) { start++; } if (arr[start] >= pivot) { swap(arr,start,end); } } if (start >low) quickSort(arr, low, start-1); if (end < high) quickSort(arr,end + 1, high); return arr; } public static void swap(int[] arr,int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } public static void main(String[] args) { int[] arr = {1,3,5,8,7,4,6}; quickSort(arr,0,arr.length-1); for (int i = 0; i < arr.length ; i++) { System.out.println(arr[i]); } } }