通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

代码实现

  1. class QuickSort:
  2.     def __init__(self, data: list):
  3.         self.data = data
  5.     def sort(self):
  6.         """
  7.         就地进行快速排序，不使用额外的空间
  8.         """
  9.         self.__sort(0, len(self.data) - 1)
  11.     def __sort(self, l:int, r:int):
  12.         if l >= r:
  13.             return
  14.         p = self.__partition(l, r)
  15.         self.__sort(l, p - 1)
  16.         self.__sort(p + 1, r)
  18.     def __partition(self, l: int, r: int):
  19.         # print(self.data,self.data[l])
  20.         j = l
  21.         # [l+1,j]< v  [j+1,i-1]>v
  22.         # 选择数组第一个元素后面的元素开始比较
  23.         for i in range(l + 1, r + 1):
  24.             if (self.data[i] - self.data[l]) < 0:
  25.                 # 小于参考值 需要把当前遍历的数据放到参考数据的左边
  26.                 j = j + 1
  27.                 self.data[i], self.data[j] = self.data[j], self.data[i]
  29.         self.data[l], self.data[j] = self.data[j], self.data[l]
  31.         return j
  33.     def sort_by_new_arr(self):
  34.         """
  35.         开辟新空间来存储数据
  36.         """
  37.         self.data = self.__sort_by_new_arr(self.data)
  39.     def __sort_by_new_arr(self,data:list):
  40.         if len(data) < 2:
  41.             return data
  42.         # 选取基准，随便选哪个都可以，选中间的便于理解
  43.         # mid = data[len(data) // 2]
  44.         mid = data[0]
  46.         # 定义基准值左右两个数列
  47.         left, right = [], []
  48.         # 从原始数组中移除基准值
  49.         data.remove(mid)
  50.         for item in data:
  51.             # 大于基准值放右边
  52.             if item >= mid:
  53.                 right.append(item)
  54.             else:
  55.                 # 小于基准值放左边
  56.                 left.append(item)
  57.         # 使用迭代进行比较
  58.         return self.__sort_by_new_arr(left) + [mid] + self.__sort_by_new_arr(right)

以上是基于开辟新空间和就地排序的两个不同版本。

优化方案

数据有序

  1.     def __partition(self, l: int, r: int):
  2.         """
  3.         对于完全有序的数据来讲，每次排序之后右边的数组只比上次排序前的数组少了一个元素
  4.         以此类推递时间复杂度为O(n^2) 递归深度变成O(n)
  5.         优化方案:
  6.             在待处理的数据中随机选择分界点
  7.         """
  8.         import random
  9.         # 随机下标
  10.         p = random.randint(l, r) # l-r之前的随机值
  11.         self.data[l],self.data[p] = self.data[p],self.data[l]
  12.         # print(self.data,self.data[l])
  13.         j = l
  14.         # [l+1,j]< v  [j+1,i-1]>v
  15.         # 选择数组第一个元素后面的元素开始比较
  16.         for i in range(l + 1, r + 1):
  17.             if (self.data[i] - self.data[l]) < 0:
  18.                 # 小于参考值 需要把当前遍历的数据放到参考数据的左边
  19.                 j = j + 1
  20.                 self.data[i], self.data[j] = self.data[j], self.data[i]
  21.         self.data[l], self.data[j] = self.data[j], self.data[l]
  22.         return j

二路快排

  1.     def sort_two_ways(self):
  2.         """
  3.         双路快速排序
  4.         """
  5.         self.__sort_two_ways(0, len(self.data) - 1)
  7.     def __sort_two_ways(self, l, r):
  8.         if l >= r:
  9.             return
  10.         p = self.__sort_two_ways_partition(l, r)
  12.         self.__sort_two_ways(l, p - 1)
  13.         self.__sort_two_ways(p + 1, r)
  15.     def __sort_two_ways_partition(self, l: int, r: int):
  16.         import random
  17.         # 随机下标
  18.         p = random.randint(l, r)  # l-r之前的随机值
  19.         self.data[l], self.data[p] = self.data[p], self.data[l]
  20.         # [l+1,i-1] <= v [j+1,r]>=v
  21.         j = r
  22.         i = l + 1
  23.         while (True):
  24.             while (i <= j and self.data[i] - self.data[l] < 0):
  25.                 i += 1
  27.             while (j >= i and self.data[j] - self.data[l] > 0):
  28.                 j -= 1
  30.             if (i >= j):
  31.                 break
  32.             self.data[i], self.data[j] = self.data[j], self.data[i]
  33.             i += 1
  34.             j -= 1
  36.         self.data[l], self.data[j] = self.data[j], self.data[l]
  37.         return j

三路快排

  1. def sort_three_ways(self):
  2.         """
  3.         三路快速排序
  4.         """
  5.         self.__sort_three_ways(0, len(self.data) - 1)
  7.     def __sort_three_ways(self, l, r):
  8.         if l >= r:
  9.             return
  10.         import random
  11.         # 随机下标
  12.         # p = random.randint(l, r)  # l-r之前的随机值
  13.         # self.data[l], self.data[p] = self.data[p], self.data[l]
  14.         # [l+1,i-1] <= v [j+1,r]>=v
  15.         lt = l
  16.         i = l + 1
  17.         gt = r + 1
  18.         while (i < gt):
  19.             if self.data[i] - self.data[l] < 0:
  20.                 lt += 1
  21.                 self.data[i], self.data[lt] = self.data[lt], self.data[i]
  22.                 i+=1
  23.             elif self.data[i] - self.data[l] > 0:
  24.                 gt -= 1
  25.                 self.data[i], self.data[gt] = self.data[gt], self.data[i]
  26.             else:
  27.                 i += 1
  28.         self.data[l], self.data[lt] = self.data[lt], self.data[l]
  29.         self.__sort_three_ways(l,lt-1)
  30.         self.__sort_three_ways(gt,r)

时间复杂度

  • 最坏情况下 O(n^2) 概率极低
  • 复杂度期望值 O(Nlogn) 层数的期望 O(logn)