快速排序（QuiteSort）

快速排序算法（QuiteSort）是基于分治策略的一个算法。其基本算法是，对于输入的子数组a[p,r]，按以下3个步骤进行排序：

(1)分解(divide):以 a[p]为基准元素将a[p:r]划分成3段，a[:p:q-1],a[q]和a[q+1:r],使得a[p:q-1]中任何元素小于等于a[q],a[q+1:r]中任何元素大于等于a[q]。下标q在划分过程中确定。

(2)递归求解(conquer):通过递归调用快速排序算法,分别对a[p:q-1]和a[q+1:r]进行排序。

(3)合并(merge):由于对a[p:q-1]和a[q+1:r]的排序是就地进行的,所以在a[p:q一1]和 a[q＋1:r]都已排好的序后不需要执行任何计算,a[p:r]就已排好序。

算法如下：

package jj;

import java.util.Arrays;

public class quitesort {
      private static int partition(int[] arr, int low, int high) {
          int i = low;
          int j= high;
          int x = arr[low];
          while(i<j){//5  8
                  while(arr[j]>=x && i<j){
                          j--;
                  }
                  if(i<j){
                          arr[i] = arr[j];
                          i++;
                  }
                  while(arr[i]<x && i<j){
                          i++;
                  }
                  if(i<j){
                          arr[j] = arr[i];
                          j--;
                  }
          }
          
          arr[i] = x;//arr[j] = y;
          return i; //return j;
  }
  private static void quickSort(int[] arr, int low, int high) {
          if(low < high){
                  int index = partition(arr,low,high);
                  quickSort(arr,low,index-1);
                  quickSort(arr,index+1,high);
          }
  }
}

插入测试代码：

 public static void quickSort(int[] arr) {
          int low = 0;
          int high = arr.length-1;
          quickSort(arr,low,high);
  }
  
  public static void main(String[] args) {
          //给出无序数组
          int arr[] = {72,6,57,88,60,42,83,73,48,85};

  //输出无序数组
  System.out.println(Arrays.toString(arr));
  //快速排序
  quickSort(arr);
  //partition(arr,0,arr.length-1);
  //输出有序数组
  System.out.println(Arrays.toString(arr));
  }

输出结果：

快速排序（QuiteSort）

推荐阅读