dodoliu的折腾笔记

生命不息，折腾不止！

0%

算法:快速排序

发表于 更新于 分类于

快速排序算法的原理:
在一个长度不小于3的序列A[0..n-1]中,对于任何 0 < n < n-1,以每一个元素p = A[n]为界,都可以将序列分隔为前、后两个子序列 A1 ＝ A[0..n]和 A2 ＝ A[n..n-1],则称p为序列A的轴点。然后对两个子序列排序，当子序列排序完成即可得到整个序列的排序结果(又称为 分治法)。
轴点的要点为：若一个元素是轴点，则经过排序之后，它的位置不应发生变化。
但是，实际应用中，序列中可能不存在这样一个轴点。所以需要选取轴点。
一般轴点的选取都选择数组的第一项或最后一项,但是最高效的方式是随机选取轴点.
下面的代码将采用固定轴点的方式演示快速排序.

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
require 'pry'
#快速排序

def division(arr, left, right)
  # point = arr[Random.new.rand(arr.length - 1)]
  #确定基点
  point = arr[left]
  while left < right
    #如果右边的数大于基点,则不操作,反之交换位置
    while left < right && arr[right] >= point
      right -= 1
    end
    swap arr, left, right
    #如果左边的数小于基点,则不操作,反之交换位置
    while left < right && arr[left] <= point
      left += 1
    end
    swap arr, right, left
  end
  #返回轴点下标
  left
end

#交换位置
def swap(arr,l,h)
  arr[l],arr[h] = arr[h],arr[l]
  p arr
end

def quick_sort!(arr, left, right)
  if left < right
    p = division arr, left, right
    #递归
    quick_sort! arr, left, p - 1
    quick_sort! arr, p + 1, right
  end
end

binding.pry
quick_sort! [66,13,51,76,81,26,57,69,23], 0, 8

排序过程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
[23, 13, 51, 76, 81, 26, 57, 69, 66]
[23, 13, 51, 66, 81, 26, 57, 69, 76]
[23, 13, 51, 57, 81, 26, 66, 69, 76]
[23, 13, 51, 57, 66, 26, 81, 69, 76]
[23, 13, 51, 57, 26, 66, 81, 69, 76]
[23, 13, 51, 57, 26, 66, 81, 69, 76]
[13, 23, 51, 57, 26, 66, 81, 69, 76]
[13, 23, 51, 57, 26, 66, 81, 69, 76]
[13, 23, 26, 57, 51, 66, 81, 69, 76]
[13, 23, 26, 51, 57, 66, 81, 69, 76]
[13, 23, 26, 51, 57, 66, 81, 69, 76]
[13, 23, 26, 51, 57, 66, 81, 69, 76]
[13, 23, 26, 51, 57, 66, 76, 69, 81]
[13, 23, 26, 51, 57, 66, 76, 69, 81]
[13, 23, 26, 51, 57, 66, 69, 76, 81]
[13, 23, 26, 51, 57, 66, 69, 76, 81]