浅谈Divide And Conquer

Day12有提到Divide and conquer(分治法)，简单的说，将问题分解为小问题後，依次解决，最後再将解决後的问题组合起来。今天要提到的快速排序法也是Divide and conquer的其中一种方法。

快速排序(Quick Sort)

快速排序是从数列中随机选择一个数作为基准(Pivot)，接着将剩下的数字分为比Pivot小或比Pivot大的值

(比Pivot小的数) Pivot (比Pivot大的数)

快速排序有使用到Divide and conquer，将原问题分成两个子问题（比Pivot大或小），再分别解决两个子问题。各自排序後，重新将子问题的数列排列，就能得到结果。
解决子问题後，同样使用Quick Sort，直到子问题剩下一个数时，排序结束。在过程中会使用到recursion的概念。

import random

#从1-100中随机读取8个数字
nums = random.sample(range(1,100), 8)
print(nums)

# nums = [60,50,44,82,55,47,99,33]

def quicksort(L, R):
    #当L<R表示还有两个以上的元素需要排列
    if(L < R):
        #i初始化变数为L
        i=L
        #j初始化变数为R+1
        j=R+1
        while(1):
            #变数i不断递增直到找出nums[i]>nums[L]的元素，或i>R就停止
            i=i+1
            while((i < R) and (nums[i] < nums[L])):
                i=i+1
            #变数j不断递减直到找出nums[j]<nums[L]的元素，或j小於L就停止
            j=j-1
            while((j>L) and (nums[j]>nums[L])):
                j=j-1
            #当i>=j就停止回圈
            if(i >= j):break
            nums[i],nums[j] = nums[j], nums[i]   
        nums[L],nums[j] = nums[j],nums[L]
        print("L=", L, " j=", j, " R=", R)
        for item in nums:
            print(item, ' ',end='')
        quicksort(L, j-1)
        quicksort(j+1, R)

for item in nums:
    print(item, ' ',end='')
print()
quicksort(0,7)

let arr = [15, 3, 17, -17, 3.1415, 18, 20, 2, 1, 666];
quickSort(0, arr.length - 1);
console.log(arr);

function partition(p, r) {
  let x = arr[r]; // pivot
  let i = p - 1;
  for (let j = p; j <= r - 1; j++) {
    if (arr[j] <= x) {
      i += 1;
      // swap arr[i] and arr[j]
      let temp = arr[i];
      arr[i] = arr[j];
      arr[j] = temp;
    }
  }
  // swap arr[i+1] and arr[r]
  let temp = arr[i + 1];
  arr[i + 1] = arr[r];
  arr[r] = temp;

  return i + 1;
}

function quickSort(p, r) {
  if (p < r) {
    let q = partition(p, r);
    quickSort(p, q - 1);
    quickSort(q + 1, r);
  }
}

结论

快速排序法的平均效率为O(n log(n))，相较於气泡排序或插入排序的效能较佳，但最差情况的时间为O(n^2)，每次切割时都很不平均，相较於合并排序法，合并排序的最差情况比快速排序法佳。