目录

前言：

一.算法思想：

 二.步骤：

三.算法优化：

四.代码实现：

五.算法评判：

六.小结：

前言：

        前两周因为机器人省赛以及后续和大家出去庆祝，学习java数据节后和算法的节奏被打断了。今天就用这一篇博客来重返学习状态，也借此给大家提醒：学习计划中不应该单单包含计划，还应该包含计划中断后怎么办，也就是容错。

        接下来我们正式开始快速排序：

一.算法思想：

        快速排序采用分治的思想，先找一个基准，比基准小的放到基准左边，比基准大的放基准右边。接下来去递归基准的左边，再去递归基准的右边，使得数组达到有序。

 二.步骤：

        原数组：int[ ] array = {2, 8, 3, 5, 9, 1, 7, 4, 6};

                              

        给定排序的范围begin 和 end 并选定最左侧的2作为基准，让 left 从 begin 开始，right 从 end 开始，先让 right 从右往左找比基准(2)小的数，right找到1，再让left从左往右找比2大的数，left找到8.

                                        

        让此时 left < right ，让二者指向的数字进行交换。

                                   

        让 right 继续从右往左找比2小的数，找到1，此时 right 和 left 相等。我们就让基准和left 与 right 相遇的下标所指向的数字进行交换。并把相遇的位置作为我们的 pivot。我么把这个过程叫做一次划分，(partition)，经过一次划分。pivot就来到了排序后的正确的位置，接下来只需要递归pivot的左侧和右侧即可。

                                            

        接下来去递归 pivot 的左侧，begin 依旧是之前的 begin , end 变成了 pivot - 1 . 此时我们可以发现，begin 和 end 相遇了，说明需要排序的子数组只有一个元素，我们直接 return 即可。

                        

        接下来去递归 pivot 的右侧，注意，return 后的 pivot 还是在1下标，那么右侧的 begin 就是pivot + 1，end 就是 之前的 end。

                     

        继续一次划分，right 找比3小的，直接找到了left，此时 left 和 right 相等，我们就让left 和 right 相等的下标和基准(3)的下标进行交换，也就是让3和3自己交换。此时我们就会发现让right先动的好处：

        right从右往左找比基准小的

        left从左往右找比基准大的

        我们最后要把相遇点和基准进行交换，就要保证 相遇点 <= pivot 

        若左边先走，停下来的条件是比基准大，若此时右边追上来，相遇点的值比基准大。

        若右边先走，停下来的条件是比基准小，若此时左边追上来，相遇点的值比基准小。

        若右侧停下来的时候是一路走到了最左侧，我们就让 left 和自己交换，也没问题。

        总结一下就是 ，相遇点的值必须 ≤ pivot，才能和最左边的pivot安全交换。右边先走保证了这一点。

                            

        接下来的过程就是一次划分的过程，我们直接用图来表示： 

               

        

                     

            

       

        此时再去递归8的左右会发现已然有序，当begin = right ，也就是 子数组只有一个元素时，返回。我们就完成了快速排序。

三.算法优化：

        当待排序数组完全有序的时候，我们把left作为基准，会发现每次一趟划分的基准都只有"右子树"，没有"左子树"，就会出现下图的情况：

                           

        递归层数为n，每次递归都会开辟新的栈空间，就会造成内存的浪费。我们可以采用三数取中法来解决这个问题。

        三数取中法，顾名思义，就是找到left,right,和mid下标的中位数。把这个中位数放到开头，作为基准。这样一来，如果数组是排好序的，我们就可以保证基准的左右子树的节点数是一样的，若数组是无序的，那就和把left作为基准相差不大。

四.代码实现：

                

        

class Sort{
  public static void quickSort(int[] array,int left,int right){
    if(left >= right) return;
    int oriRight = right;
    int poivt = left;
    while(left < right){
      while(array[right] >= array[poivt] && left < right){
        right--;
      }
      while(array[left] <= array[poivt] && left < right){
        left++;
      }
      if(left < right){
        swap(array,left,right);
      }
    }
    swap(array,left,poivt);
    quickSort(array,poivt,left - 1);
    quickSort(array,left + 1,oriRight);
  }
  
  //交换
  public static void swap(int[] array,int i,int j){
    int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
  }
}

class Test{
  public static void main(String[] args){
    int[] array = {2,8,3,5,9,1,7,4,6};
    Sort.quickSort(array,0,array.length - 1);
  }
}

        运行结果：

快速排序：
排序前：[2, 8, 3, 5, 9, 1, 7, 4, 6]
排序后：[1, 2, 3, 4, 5, 6, 7, 8, 9]

五.算法评判：

        时间复杂度：O(nlog n)

        空间复杂度：O(log n)

        稳定性：不稳定

六.小结：

       

        自学编程的过程中，卡住并不可怕。可怕的是卡住之后把代码扔一边去逃避。

这次的经历让我明白，“看懂了”和“会写了”之间隔着一条大鸿沟。当你代码卡住时，试着用最朴实的语言把它的执行流程讲给别人（或者写在博客里）听。当你能清晰解释的那一刻，Bug 往往自己就浮出水面了。