排序--快速排序--详细分析

           快速排序是一种分治的排序算法。它将一个数组分成两个子数组，将两部分独立的排序。它和归并排序是互补的。         归并排序将数组分成两个子数组分别排序，并将已经有序的两个子数组按照大小放入也就是归并到一个数组中，形成有序的数组。 而快速排序则是当两个子数组都有序时，整个数组自然有序了。

话不多说，示例代码解释：

package Util;                  public class KuaiPaiSort {                  public static void main(String[] args) {              int[] a = { 9, 4, 7, 1, 7, 10, 45 ,1,1,8,23,100,1};              int len = a.length;              sort(a,0,len-1);              for (int i = 0; i < len; i++) {              System.out.print(a[i]+" ");              }              }              static int getMiddle(int [] list,int left,int right){//每次寻找到的中心点总是位置已经排好的              int temp;//交换时的中间变量              //进行一趟快排 返回中心点位置              int mid=list[left];    //通常把中心置于 a[0] 即新数组的第一个位置              while(left<right){              while(left<right&&list[right]>=mid){  //找到比中心点小的数 交换              right--;              }              temp=list[right];              list[right]=list[left];              list[left]=temp;              while(left<right&&list[left]<=mid){              left++;              }              temp=list[right];              list[right]=list[left];              list[left]=temp;              }              list[left]=mid;//中心移到正确位置  这是关键，确定了位置 下一次不进行比较 并且到这个地方 left已经是mid了              return left;              }              static int[] sort(int [] list,int left,int right){              if(left<right-1){	//不断找到中间点，交换两边值，最终构成有序的数组              int mid=getMiddle(list, left, right);              sort(list, left, mid-1);              sort(list, mid+1, right);              }              return list;              }              }           

    分析：      先看getMiddle()方法，这个方法找到一个点调换点的两边的数组元素，让左边的小于mid，右边的大于mid。可以自定义比较的方法及内容。     三个参数，list是要处理的子数组，left是此子数组的首个元素在整个源数组的位置，right是尾元素的位置。    方法中，先把首字母确定为mid值，继续往下走，当mid右边的 list[right]>=mid 时，位置合理，此时right--，记住，right是整个源数组的下标，即向左移一位。直到遇到list[right]<mid。跳出，继续往下，把这个元素交换到左边去。

继续往下，把左边的进行比较，当遇到第一个比mid大的值时，和右边交换。

这样的一个过程在大循环while(left<right)中，那么它会不断地交换直到left=right为止，此时再将list[left]的值赋为mid，（比如说本来mid在整个源数组的第三位，而排好序后的数组中 mid这个值是在第五位的，那么这个赋值便是把这个数组中的第五位改成mid值，这样每次相对确定一个数的确切位置）。

getMiddle（）最后返回的就是传入数组首元素的一个确切的位置，并且把给这个位置赋上了正确的值。

    再看sort()方法 ，当left<right-1（即两个相邻时就不用比了）时，getMiddle方法得到切分点，这时候right和left值已经被改变，它们总是不断逼近mid的。接下来两个，递归对mid左边sort，再右边sort，同时对上一个子数组不断地切分，最终返回放好一个元素的字数组，然后递归继续。不满足 left<right-1时，会有一个结束，当两个都结束时，所有的元素都已被摆在了正确的位置上。        快排效率很高，它是原地排序，且内循环很小，复杂度NlgN。其他无法比拟。

    大体思想便是这个了……后面我会再把其他几个排序也分析下

2015/08/08