Java快速排序QuickSort(实例)

2021-01-15 14:06HankingHu JAVA教程

下面小编就为大家带来一篇Java快速排序QuickSort(实例)。小编觉得挺不错的，现在就分享给大家，也给大家做个参考。一起跟随小编过来看看吧

快速排序

----------------------------------------------------------------------

思想

Java快速排序QuickSort(实例)

如上图：每趟快速排序开始时，设置一个key，key=array[low]，然后由high向左，找到小于key的值，复制到low位置，然后再由low向右找到大于key的值，复制到high位置，直到low=high结束，

将key的复制到low位置。

上图中第一轮划分后找到32的位置，然后递归的对32左边和右边的进行排序。

代码：

									package Sort;

									import java.util.Arrays;

									public class QuickSort {

									 public static void main(String[] args) {

									  int array[]={32, 12, 7, 78, 23, 45};

									  quickSort(array,0,array.length-1);

									  System.out.println(Arrays.toString(array));

									 }

									 public static void quickSort(int array[],int left,int right)

									 {

									  if(left>=right)

									  {

									   return ;

									  }

									  int i=left;

									  int j=right;

									  int key=array[left];

									  while(i<j)

									  {

									   while(i<j&&array[j]>key)

									   {

									    j--;

									   }

									   array[i]=array[j];

									   //从后往前找到第一个比key小的数与array[i]交换；

									   while(i<j&&array[i]<key)

									   {

									    i++;

									   }

									   array[j]=array[i];

									   //从前往后找到第一个比key大的数与array[j]交换；

									  }

									  array[i]=key;

									  //一趟快排之后已经将key的位置找到。

									  quickSort(array,left,i-1);

									  //对key左边的进行排序

									  quickSort(array,i+1,right);

									  //对key右边的进行排序

									 }

									}