快速排序（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）

最新文章

热门文章