import java.util.Arrays;

import java.util.Random;

/**

* 快速排序

* 分治算法,选准一个基准值(一般选择数组中第一个值),将数组分成两部分,前一部分比基准值小,后一部分比基准值大.

* 然后将分割后的两个数组继续分割,一直到不能分割为止,那么所有子数组都是排序好的,最后汇总起来也是排序好的数组

* 算法时间复杂度:O(nLogn),最差为O(n^2)

*/

@SuppressWarnings("unused")

public class QuickSort implements AlgorithmInGraph{

@SuppressWarnings("Duplicates")

public void showAlgorithm() {

int [] array = new int[10];

Random random = new Random();

for(int i = 0;i<10;i++){

array[i] = random.nextInt(100);

}

array = new int[]{58, 67, 58, 72, 1, 52, 91, 80, 42, 58};

System.out.println("排序前生成的数组的顺序是: \t" + Arrays.toString(array));

sort(array);

System.out.println("排序后的数组的顺序是: \t" + Arrays.toString(array));

}

private void sort(int [] array){

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

}

private void quickSort(int [] array,int start,int end){

if(start >= end){

return;

}

int left = start;

int right = end;

int value = array[start];

while(left < right){

//这里为什么是大于等于?因为在右边的大于等于标准值就可以了.如果不加等号,那么相等的值就没有办法

while(array[right] >= value && left < right)

right--;

array[left] = array[right];

while(array[left] <= value && left < right)

left++;

array[right] = array[left];

}

array[left] = value;

quickSort(array,left+1,end);

quickSort(array,start,left-1);

}

}