Quick Sort 快速排序

1. Quick Sort

Quicksort is a divide-and-conquer algorithm. It works by selecting a 'pivot' element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. For this reason, it is sometimes called partition-exchange sort.

时间复杂度(Time Complexity):

• 最坏(Worst-case): $O(n^2)$
• 最好(Best-case): $O(nlogn)$
• 平均(Average): $O(nlogn)$

空间复杂度(Space Complexity):

• 最坏(Worst-case): $O(n)$
• 最好(Best-case): $O(logn)$
• 平均(Average): $O(logn)$

1.1 流程

1. 选取基准(pivot)
2. 分区(partition): 将大于基准的元素放入其右边 小于的放入其左边; 分区结束后形成以基准为界, 形成左右分区
3. 将左右分区**递归(recursive)**执行步骤1), 直到分区只剩下一个元素为止.

1.2 Lomuto Partition

快速排序流程:

1. 选取基准 Pivot
2. 将小于于Pivot的数字放在其左边, 大于等于Pivot的放在右边, 形成左右分区; 左分区所有数字小于基准, 右分区所有数字大于等于基准; 对于左右分区, 继续 步骤1). 直到区间为空为止.
3. 所有数字排序完毕

分区流程:

1. 选取最右边的数作为基准
2. 左分区索引i, 遍历数组, 将小于基准的数字和左分区数字交换; 直到结束为止;
3. 将左分区边界右边的数字和基准交换, 返回当前基准位置

伪代码如下:

// Sorts a (portion of an) array, divides it into partitions, then sorts those
algorithm quicksort(A, lo, hi) is 
  // Ensure indices are in correct order
  if lo >= hi || lo < 0 then 
    return
    
  // Partition array and get the pivot index
  p := partition(A, lo, hi) 
      
  // Sort the two partitions
  quicksort(A, lo, p - 1) // Left side of pivot
  quicksort(A, p + 1, hi) // Right side of pivot

// Divides array into two partitions
algorithm partition(A, lo, hi) is 
  pivot := A[hi] // Choose the last element as the pivot

  // Temporary pivot index
  i := lo - 1

  for j := lo to hi - 1 do 
    // If the current element is less than or equal to the pivot
    if A[j] <= pivot then 
      // Move the temporary pivot index forward
      i := i + 1
      // Swap the current element with the element at the temporary pivot index
      swap A[i] with A[j]

  // Move the pivot element to the correct pivot position (between the smaller and larger elements)
  i := i + 1
  swap A[i] with A[hi]
  return i // the pivot index

func sortArray(nums []int) []int {
    quickSort(nums, 0, len(nums)-1)
    return nums
}

func quickSort(nums []int, left, right int) {
    if left < right {
        pivot := partition(nums, left, right)
        quickSort(nums, left, pivot-1)
        quickSort(nums, pivot+1, right)
    }
}

func partition(nums []int, left, right int) int {
    // random pivot
    pi := rand.Intn(right-left+1) + left
    swap(nums, pi, right) // move pivot to end

    p := nums[right] // pivot value
    i, j := left-1, left
    for j < right {
        // move to left
        if nums[j] < p {
            i++
            swap(nums, i, j)
        }

        j++
    }

    // move pivot to middle
    i++
    swap(nums, i, right)

    // pivot 
    return i    
}

func swap(nums []int, i, j int) {
    nums[i], nums[j] = nums[j], nums[i]
}

1.3 Hoare Partition

快速排序流程:

1. 选取基准 Pivot
2. 将小于于Pivot的数字放在其左边, 大于等于Pivot的放在右边, 形成左右分区; 左分区所有数字小于基准, 右分区所有数字大于等于基准; 对于左右分区, 继续 步骤1). 直到区间为空为止.
3. 所有数字排序完毕

分区流程:

1. 选择中间数字为基准

2. 使用双指针i, j; 分别从数组两端向中间移动, 每次都移动一步:

   • 若nums[i] < pivot, 则i继续向右移动, 跳过这些数字
   • 若nums[j] > pivot, 则j继续向左移动, 跳过这些数字

   当i<j, 则交换. 直到i >= j

3. 返回j.

算法伪代码:

// Sorts a (portion of an) array, divides it into partitions, then sorts those
algorithm quicksort(A, lo, hi) is 
  if lo >= 0 && hi >= 0 && lo < hi then
    p := partition(A, lo, hi) 
    quicksort(A, lo, p) // Note: the pivot is now included
    quicksort(A, p + 1, hi) 

// Divides array into two partitions
algorithm partition(A, lo, hi) is 
  // Pivot value
  pivot := A[ floor((hi - lo)/2) + lo ] // The value in the middle of the array

  // Left index
  i := lo - 1 

  // Right index
  j := hi + 1

  loop forever 
    // Move the left index to the right at least once and while the element at
    // the left index is less than the pivot
    do i := i + 1 while A[i] < pivot
    
    // Move the right index to the left at least once and while the element at
    // the right index is greater than the pivot
    do j := j - 1 while A[j] > pivot

    // If the indices crossed, return
    if i >= j then return j
    
    // Swap the elements at the left and right indices
    swap A[i] with A[j]

func sortArray(nums []int) []int {
    quickSort(nums, 0, len(nums)-1)
    return nums
}

func quickSort(nums []int, left, right int) {
    if left < right {
        p := hoarePartition(nums, left, right)
        quickSort(nums, left, p)
        quickSort(nums, p+1, right)
    }
}

func hoarePartition(nums []int, left, right int) int{
    pi := rand.Intn(right-left+1) + left
    p := nums[pi]

    i, j := left-1, right+1
    for i < j {
        for i++; nums[i] < p; {
            i++
        }
        for j--; nums[j] > p; {
            j--
        }
        if i < j {
            nums[i], nums[j] = nums[j], nums[i]
        }
    }

    return j
}

2. Three-way Radix Quicksort

Multi-key quicksort, also known as three-way radix quicksort.

三路快速排序, 将数据分为三个分区(基准pivot):

• 小于pivot
• 等于pivot
• 大于pivot

可以避免某一区全部都是重复元素, 依然进行分区

func sortArray(nums []int) []int {
    quickSort(nums, 0, len(nums)-1)
    return nums
}

func quickSort(nums []int, left, right int) {
    if left < right {
        less, great := partition(nums, left, right)
        quickSort(nums, left, less-1)
        quickSort(nums, great+1, right)
    }
}

func partition(nums []int, left, right int) (int, int) {
    // random pivot
    pi := rand.Intn(right-left+1) + left
    p := nums[pi]
    swap(nums, pi, right) // move to right

    // partition
    // three part
    less := left 
    great := right
    idx := left
    for idx <= great {
        ele := nums[idx]
        // less part
        if ele < p {
            swap(nums, idx, less)
            less++
            idx++
        } 
        // great part
        if ele > p {
            // 从右边来的数字大小未知, 后序还需要比较
            // idx 不动
            swap(nums, idx, great)
            great-- 
        }
        // equals part
        if ele == p {
            idx++
        }
    }

    // less 和 great 指向分区边界外
    // less-1, great+1 才是分区边界
    return less, great
}


func swap(nums []int, i, j int) {
    nums[i], nums[j] = nums[j], nums[i]
}

注意:

• idx<=grear: 因为great实际指向下一个需要去比较的元素, 若改成idx<great, 那么在两者相遇时就会结束循环, 从而漏掉一个元素.

• great--时, idx不能自增: 因为从 great 区来的元素其大小是未知的, 下一次循环需要再次判断. 所以交换元素到great区时, idx不动,

• partition 返回的less great不是边界, less-1, great+1 才是分区边界

3. LeetCode

LeetCode: 912. 排序数组

• 此问题的测试案例, 存在大量重复数据, 直接使用快速排序将超时.
• 可以使用三路快排

Reference

1. https://en.wikipedia.org/wiki/Quicksort#
2. https://www.runoob.com/w3cnote/quick-sort-2.html
3. https://en.wikipedia.org/wiki/Multi-key_quicksort
4. https://zhuanlan.zhihu.com/p/406976071
5. 912. 排序数组