hello-algo/codes/ruby/chapter_sorting/quick_sort.rb at 4c6b30137092d22d59de5bc6d7ce481c0909de81 · krahets/hello-algo · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
=begin
File: quick_sort.rb
Created Time: 2024-04-01
Author: Cy (3739004@gmail.com), Xuan Khoa Tu Nguyen (ngxktuzkai2000@gmail.com)
=end

### 快速排序类 ###
class QuickSort
  class << self
    ### 哨兵划分 ###
    def partition(nums, left, right)
      # 以 nums[left] 为基准数
      i, j = left, right
      while i < j
        while i < j && nums[j] >= nums[left]
          j -= 1 # 从右向左找首个小于基准数的元素
        end
        while i < j && nums[i] <= nums[left]
          i += 1 # 从左向右找首个大于基准数的元素
        end
        # 元素交换
        nums[i], nums[j] = nums[j], nums[i]
      end
      # 将基准数交换至两子数组的分界线
      nums[i], nums[left] = nums[left], nums[i]
      i # 返回基准数的索引
    end

    ### 快速排序类 ###
    def quick_sort(nums, left, right)
      # 子数组长度不为 1 时递归
      if left < right
        # 哨兵划分
        pivot = partition(nums, left, right)
        # 递归左子数组、右子数组
        quick_sort(nums, left, pivot - 1)
        quick_sort(nums, pivot + 1, right)
      end
      nums
    end
  end
end

### 快速排序类（中位数优化）###
class QuickSortMedian
  class << self
    ### 选取三个候选元素的中位数 ###
    def median_three(nums, left, mid, right)
      # 选取三个候选元素的中位数
      _l, _m, _r = nums[left], nums[mid], nums[right]
      # m 在 l 和 r 之间
      return mid if (_l <= _m && _m <= _r) || (_r <= _m && _m <= _l)
      # l 在 m 和 r 之间
      return left if (_m <= _l && _l <= _r) || (_r <= _l && _l <= _m)
      return right
    end

    ### 哨兵划分（三数取中值）###
    def partition(nums, left, right)
      ### 以 nums[left] 为基准数
      med = median_three(nums, left, (left + right) / 2, right)
      # 将中位数交换至数组最左断
      nums[left], nums[med] = nums[med], nums[left]
      i, j = left, right
      while i < j
        while i < j && nums[j] >= nums[left]
          j -= 1 # 从右向左找首个小于基准数的元素
        end
        while i < j && nums[i] <= nums[left]
          i += 1 # 从左向右找首个大于基准数的元素
        end
        # 元素交换
        nums[i], nums[j] = nums[j], nums[i]
      end
      # 将基准数交换至两子数组的分界线
      nums[i], nums[left] = nums[left], nums[i]
      i # 返回基准数的索引
    end

    ### 快速排序 ###
    def quick_sort(nums, left, right)
      # 子数组长度不为 1 时递归
      if left < right
        # 哨兵划分
        pivot = partition(nums, left, right)
        # 递归左子数组、右子数组
        quick_sort(nums, left, pivot - 1)
        quick_sort(nums, pivot + 1, right)
      end
      nums
    end
  end
end

### 快速排序类（递归深度优化）###
class QuickSortTailCall
  class << self
    ### 哨兵划分 ###
    def partition(nums, left, right)
      # 以 nums[left]为基准数
      i = left
      j = right
      while i < j
        while i < j && nums[j] >= nums[left]
          j -= 1 # 从右向左找首个小于基准数的元素
        end
        while i < j && nums[i] <= nums[left]
          i += 1 # 从左向右找首个大于基准数的元素
        end
        # 元素交换
        nums[i], nums[j] = nums[j], nums[i]
      end
      # 将基准数交换至两子数组的分界线
      nums[i], nums[left] = nums[left], nums[i]
      i # 返回基准数的索引
    end

    ### 快速排序（递归深度优化）###
    def quick_sort(nums, left, right)
      # 子数组长度不为 1 时递归
      while left < right
        # 哨兵划分
        pivot = partition(nums, left, right)
        # 对两个子数组中较短的那个执行快速排序
        if pivot - left < right - pivot
          quick_sort(nums, left, pivot - 1)
          left = pivot + 1 # 剩余未排序区间为 [pivot + 1, right]
        else
          quick_sort(nums, pivot + 1, right)
          right = pivot - 1 # 剩余未排序区间为 [left, pivot - 1]
        end
      end
    end
  end
end

### Driver Code ###
if __FILE__ == $0
  # 快速排序
  nums = [2, 4, 1, 0, 3, 5]
  QuickSort.quick_sort(nums, 0, nums.length - 1)
  puts "快速排序完成后 nums = #{nums}"

  # 快速排序（中位基准数优化）
  nums1 = [2, 4, 1, 0, 3, 5]
  QuickSortMedian.quick_sort(nums1, 0, nums1.length - 1)
  puts "快速排序（中位基准数优化）完成后 nums1 = #{nums1}"

  # 快速排序（递归深度优化）
  nums2 = [2, 4, 1, 0, 3, 5]
  QuickSortTailCall.quick_sort(nums2, 0, nums2.length - 1)
  puts "快速排序（递归深度优化）完成后 nums2 = #{nums2}"
end