返回快排所需的基准点， 左右中中间选择一个。 若不足3位，选左。
(self, unsorted_list)
| 66 | return self.quickSort(left) + [unsorted_list[meta]] + self.quickSort(right) |
| 67 | |
| 68 | def _getMiddle(self, unsorted_list): |
| 69 | """ |
| 70 | 返回快排所需的基准点， |
| 71 | 左右中中间选择一个。 |
| 72 | 若不足3位，选左。 |
| 73 | """ |
| 74 | if len(unsorted_list) < 3: |
| 75 | return 0 |
| 76 | |
| 77 | left = unsorted_list[0] |
| 78 | right = unsorted_list[-1] |
| 79 | middle = unsorted_list[len(unsorted_list) // 2] |
| 80 | l, r, m = [(0, left), (len(unsorted_list) - 1, right), (len(unsorted_list) // 2, middle)] |
| 81 | # 这里对比了自己写的merge sort 与内置的差距， |
| 82 | # 在有key的情况下差距非常大。 |
| 83 | return sorted([l, r, m], key=lambda x: x[1])[1][0] |
| 84 | |
| 85 | |
| 86 | def mergeSort(self, unsorted_list, key=None): |