快速排序的实现

发表于 |

快速排序的一般javascript实现

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
function Sort(num) {
  this.totalNum = num
  this.dataStore = []
  this.genData = function setData() {
    for (let i = 0; i < this.totalNum; ++i) {
      this.dataStore[i] = Math.floor(Math.random() * (this.totalNum + 1))
    }
  }

  this.quickSort = function quickSort(data) {
    let len = data.length
    if (len <= 1) {
      return [...data]
    }
    let left = []
    let right = []
    let pivot = data[0]
    for (let i = 1; i < len; i++) {
      let item = data[i]
      if (item < pivot) {
        left.push(item)
      } else {
        right.push(item)
      }
    }
    return this.quickSort(left).concat(pivot, this.quickSort(right))
  }

  this.quickSort2 = function quickSort2 (data) {
    let len = data.length
    if (len <= 1) {
      return [...data]
    }
    let left = []
    let middle = []
    let right = []
    let pivotLeft = data[0]
    let pivotRight = data[len - 1]
    for (let i = 1; i < len; i++) {
      let item = data[i]
      if (item < pivotLeft) {
        left.push(item)
      } else if (item > pivotRight) {
        right.push(item)
      } else {
        middle.push(item)
      }
    }
    return this.quickSort2(left).concat(pivotLeft, this.quickSort2(middle)).concat(pivotRight, this.quickSort2(right))
  }

  this.quickSort3 = function quickSort3 (start, end) {
    if (start >= end) {
      return
    }
    let data = this.dataStore
    let i = start
    let j = end
    let pivot = data[i]
    while(i < j) {
      while(i < j && data[j] >= pivot) {
        j--;
      }
      data[i] = data[j]
      while(i < j && data[i] <= pivot) {
        i++;
      }
      data[j] = data[i]
    }
    data[i] = pivot
    this.quickSort3(start, i - 1)
    this.quickSort3(j + 1, end)
  }

  this.quickSort4 = function quickSort4 (start, end) {
    if (start >= end) {
      return
    }
    let data = this.dataStore
    let i = start
    let j = end
    let mid = Math.floor((end - start) / 2)
    let pivot = data[mid]
    data[mid] = data[i]
    data[i] = pivot
    while(i < j) {
      while(i < j && data[j] >= pivot) {
        j--;
      }
      data[i] = data[j]
      while(i < j && data[i] <= pivot) {
        i++;
      }
      data[j] = data[i]
    }
    data[i] = pivot
    this.quickSort4(start, i - 1)
    this.quickSort4(j + 1, end)
  }

  this.genData()

  let start = Date.now()
  this.quickSort4(0, this.totalNum - 1)
  let end = Date.now()
  console.log('quickSort4耗时： ' + (end - start) + '毫秒')
}