快速排序算法的思考
快速排序算法
快速排序是基于冒泡排序的改进的一种排序方式，它是递归的，它在数据很多的时候排序效果很好，在java内部的排序就用到了快速排序，是我比较喜欢的一种排序方式。
百度百科里的这张图十分生动形象的描绘了快速排序的过程。
首先选取一个中间值，就是图中红色的值，然后把比这个数小的值放在这个数前面，比这个数大的放在它后面，我称之为一次快排过程。经过这一次快排过程，我们并不能够完成排序，而是通过递归的方式，对这个数前后两部分再进行排序，直到所有数都排序完成（如何判断所有数都排序完成接下来会讨论）。
有些话就是说出来容易做出来难，在算法里更是这样，如何把 比这个数小的值放在这个数前面，比这个数大的放在它后面 是一件很容易想到却不容易实现的事情。你会很容易想到，把所有数和这个关键数比较，如果小，放入一个新的数组的前面，然后再放这个关键数和其他比他大的数。这里需要循环一次，new一个新的数组。有没有更好的方法呢？
有，并不需要new一个新的数组。在原有的数组进行交换即可。
这个过程是先选择一个数为关键数，然后从最后一个数（索引为j）开始向前依次和它比较，比它小（即不满足前小后大的要求），就停止，然后和第一个数交换；然后从前面第一个数（索引为i）开始向后依次和关键数比较，比关键数大（即不满足前小后大的要求），则停止，然后和第j个数交换，其实就是我们的关键数，只不过它的索引在变化。通过这样不断的交换，直到i>＝j停止，就完成了一次快排过程。
快排过程讲完了，还要对剩余两部分继续递归进行快排，那么进行到什么时候停止呢（即递归的限定条件）？
要快排的数组哪怕只有两个，比如｛2，1｝，它的次序也不对，需要排序，那么只要数组长度大于1就要进行快排，这就是限定条件.
1
if(i>low+1){
sort(array,low,i-1);
i>low+1 可以转换成 i-low>1,即前半部分长度大于1，进行排序。
参数是low和i-1是因为关键数不需要再进行排序了，所以是i-1.
后半部分同理，代码如下：
import java.util.Scanner;
public class Practice {
public static void main(String[] args) {
System.out.println("请输入数组长度：");
Scanner scanner = new Scanner(System.in);
int[] array = new int[Integer.parseInt(scanner.next())];
System.out.println("请输入" + array.length + "长度的数组：");
for(int i =0;i<array.length;i++){
array[i] = Integer.parseInt(scanner.next());
}
sort(array,0,array.length-1);
for(int item:array){
System.out.println(item);
}
}
public static void sort(int[] array,int low,int high) {
int i = low;
int j = high;
int mid = array[low];
int temp;
while(i<j){
while(i<j && mid<=array[j]){
j--;
}
if(i<j){
temp = array[i];
array[i] = array[j];
array[j] = temp;
i++;
}
while(i<j&&mid>=array[i]){
i++;
}
if(i<j){
temp = array[i];
array[i] = array[j];
array[j] = temp;
j--;
}
}
if(i>low+1){
sort(array,low,i-1);
}
if(j<high-1){
sort(array,j+1,high);
}
}
}