package com.sw.demo.test; /** * 关于快速排序 * @author Song * */ public class TestQuickSort { public static void main(String[] args) { int[] arr = {5,9,8,4,7,3,6,2,1}; quickSort(arr,0,arr.length-1); // 快速排序 for (int i = 0; i < arr.length; i++) { System.out.print(arr[i]+" "); } } /** * 快速排序 * @param arr * @param low * @param high */ public static void quickSort(int[] arr, int low , int high){ if(low >= high){ // 如果low(低位)大于等于high(高位),则直接返回 return; } if((high - low) == 1){ // 如果只有两个数字,则直接比较 if(arr[0] > arr[1]){ swap(arr,0,1); } return ; } int pivot = arr[low]; // 任取一个数字做为中间数字(一般,这里也是去第一个数字) int left = low +1; // 定义左滑块,当前的游标 int right = high; // 定义右滑块,当前的游标 while(left < right){ // 从左右开始循环 while(left < right && left <= high){ // 如果左边小于右边,并且左边小于高位 if(arr[left] > pivot){ // 从左边找到一个大于中间数字的值,并记录下标 break; } left++; // 如果找不到,left++,一直向后找 } while(left <= right && right > low){ // 如果右边大于左边,并且右边大于低位 if(arr[right] <= pivot){ // 从右边找到一个小于中间数字的值,并记录下标 break; } right--; // 如果找不到,right++,一直向前找 } if(left < right){ // 如果还没有找完,则交换数字 swap(arr, right, left); } swap(arr,low,right); // 交换中间数字 quickSort(arr,low,right); // 排序前面数组 quickSort(arr,right+1,high); // 排序后边数组 } } // 掉位方法 public static void swap(int[] array, int i, int j){ int temp; temp = array[i]; array[i] = array[j]; array[j] = temp; } }