快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略,通常称其为分治法(Divide-and-ConquerMethod)。 该方法的基本思想是: 1.先从数列中取出一个数作为基准数。 2.分区过程,将比这个数大的数全放到它的右边,小于或等于它的数全放到它的左边。 3.再对左右区间重复第二步,直到各区间只有一个数。
代码:
- import java.util.Arrays;
-
- public class QuickSort {
- public static void main(String args[])
- {
- int array[]={49,38,65,97,76,13,27,49};
- System.out.println(Arrays.toString(array));
- quickSort(array,0,array.length-1);
- System.out.println(Arrays.toString(array));
- }
-
- public static void quickSort(int arr[],int low,int high)
- {
- if(low<high)
- {
- int mid = partition(arr,low,high);
-
- quickSort(arr,low,mid-1);
-
- quickSort(arr,mid+1,high);
- }
- }
-
- public static int partition(int array[],int low,int high)
- {
-
- int pivotKey = array[low];
- int i=low,j=high;
-
- if(low<high)
- {
- while(i<j)
- {
-
- while(i<j&&array[j]>=pivotKey)
- {
- j--;
- }
-
- if(i<j)
- {
- array=array[j];
- i++;
- }
-
-
- while(i<j&&array<=pivotKey)
- {
- i++;
- }
-
- if(i<j)
- {
- array[j]=array;
- j--;
- }
- }
-
- array=pivotKey;
-
- }
-
- System.out.println(Arrays.toString(array));
-
- return i;
- }
- }
|