算法学习笔记（七）快速排序

（一）给定数组arr和一个数num，要求将数组中小于等于num的数放在数组左边，大于num的数放在数组右边（左部分和右部分内部无需有序)。并需要满足额外空间复杂度O(1)，时间复杂度O(N)。

思路：首先可以假定一个“小于等于区域”，用一个变量记录这个区域的边界，初始状态是“小于等于区域”不包括任何数，位于数组左侧之外。然后用另一个变量i记录位置。那么可以分为两种情况：

（1）arr[i] <= num ——> 当前数和“小于等于区域”的下一个数交换，“小于等于区域”向右扩一位，当前数跳至下一个；

（2） arr[i] > num ——> 当前数直接跳下一个

也就是在遍历的过程中已经拉出了区间，使得满足题目要求。用了有限几个变量，因此额外空间复杂度是O(1)，只需要遍历一次，满足时间复杂度O(N)的要求。

（二）荷兰国旗问题

给定数组arr和一个数num，要求将小于num的数放在数组左边，等于num的数放在数组中间，大于num的数放在数组右边。并需要满足额外空间复杂度O(1)，时间复杂度O(N)。

思路：和上面的问题类似，只不过要假定一个“小于区域”和一个“大于区域”。设想初始状态下“小于区域”在数组的左侧之外，“大于区域”在数组的右侧之外，都未包含任意数。同样需要变量i记录位置，那么可以分为三种情况：

（1）arr[i] < num ——> 当前数和“小于区域”的下一个数交换，“小于区域”向右扩一个位置，当前数跳至下一个；

（2）arr[i] = num ——>当前数直接跳至下一个

（3） arr[i] > num ——> 当前数与“大于区域”前一个数交换，“大于区域”向左扩一位，当前数定在原地不变（因为交换过后的数还未比较判断）。

Java

public static int[] partition(int[] arr, int left, int right, int num) {
      // 记录“小于区域”的边界
     int less = left - 1;
     // 记录“大于区域”的边界
     int more = right + 1;
     // 当当前数的下标比大于区域的左边界小时（直接用left记录当前数下标，就不新创建变量了）
     while(left < more) {
         if(arr[left] < num) {
             // 如果当前数小于num时，当前数和小于区域的下一个数交换，小于区域向右扩一位，当前数跳下一个
             swap(arr, left++, ++less);
         } else if(arr[left] > num) {
             // 如果当前数大于num，当前数和大于区域的前一个数交换，大于区域向左扩一位，当前数位置不变
             swap(arr, left, --more);
         } else {
             // 如果当前数等于num，直接跳下一个
             left++;
         }
     }
     return arr;
  }
  
  public static void swap(int[] arr, int j, int k) {
      int tmp = arr[j];
      arr[j] = arr[k];
      arr[k] = tmp;
  }
  
  public static void main(String[] args) {
      int[] arr = {1,5,3,4,6,2};
      int[] res= partition(arr, 0, arr.length-1, 3);
      for(int i=0; i<res.length; i++) {
          System.out.println(res[i]);// 1 2 3 6 4 5
      }
  }

JavaScript

function partition(arr, left, right, num){
    var less = left - 1;
    var more = right + 1;
    while(left < more){
      if(arr[left] < num){
        swap(arr, left++, ++less);
      } else if (arr[left] > num){
        swap(arr, --more, left);
      } else {
        left++;
      }
    }
    return arr;
  }

  function swap(arr, i, j){
    var temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
  }

  var arr = [1,5,3,4,6,2];
  console.log(partition(arr, 0, arr.length-1, 3)); // 1 2 3 6 4 5

（三）原始快速排序

将数组的最后一个值作为荷兰国旗问题中的num，然后通过该问题的思路将数组分为三部分：左侧< num；中间== num，右侧>num；然后递归执行左侧和右侧部分。

当num越靠近两侧时，时间复杂度越高，越靠近中间时，时间复杂度越低。此版本的快速排序时间复杂度为O(N^2)。

（四）随机快速排序（改进版）

在数组中随机选择一个数作为num，同样将数组分为三部分：左侧< num；中间== num，右侧>num；然后递归执行左侧和右侧部分。时间复杂度为O（N×logN）。快排的空间复杂度是O（logN），在有利情况中，随机选取的数的位置接近中点，此时空间复杂度O（logN），如果偏离中点较多，那么空间复杂度为O（N），最终按概率收敛到O（logN）。和时间复杂度的计算类似，都是与概率相关的计算，是一个长期期望的值。

Java

public static void quickSort(int[] arr) {
     if(arr==null || arr.length<2) {
         return;
     } else {
         quickSort(arr, 0, arr.length-1);
     }
 }
 
 public static void quickSort(int[] arr, int left, int right) {
     if(left < right) {
         swap(arr, left+(int)(Math.random()*(right-left+1)), right);
         int[] p = partition(arr, left, right);
         quickSort(arr, left, p[0]-1); // 小于区域的范围中递归
         quickSort(arr, p[1]+1, right); // 大于区域的范围中递归
     }
 }
 
 public static int[] partition(int[] arr, int left, int right) {
     int less = left - 1; // 小于区右边界
     int more = right; // 大于区左边界，arr[right]是划分值，暂时不参与
     while(left < more) {
         if(arr[left] < arr[right]) {
             swap(arr, left++, ++less);
         } else if(arr[left] > arr[right]) {
             swap(arr, left, --more);
         } else {
             left++;
         }
     }
     swap(arr, more, right);
     // 返回等于区域的左边界和右边界（划分值时数组中的数，所以等于区域必存在）
     return new int[] {less+1, more};
 }
 
 public static void swap(int[] arr, int j, int k) {
     int tmp = arr[j];
     arr[j] = arr[k];
     arr[k] = tmp;
 }

JavaScript

function quickSort(arr){
  if(arr==null || arr.length<2){
    return;
  } else{
    sort(arr, 0, arr.length-1);
  }
}

function sort(arr, left, right){
  if(left < right){
    swap(arr, left+Math.floor(Math.random()*(right-left+1)), right);
    var p = partition(arr, left, right);
    sort(arr, left, p[0]-1);
    sort(arr, p[1]+1, right);
  }
}

function partition(arr, left, right){
  var less = left - 1;
  var more = right;
  while (left < more) {
    if(arr[left] < arr[right]){
      swap(arr, left++, ++less);
    } else if(arr[left] > arr[right]){
      swap(arr, left, --more);
    } else{
      left++;
    }
  }
  swap(arr, more, right);
  return [less+1, more];
}

function swap(arr, i, j){
  var temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}