排序算法的python实现

• 排序算法
  • 冒泡排序
    • 逻辑
    • 时间复杂度
    • 代码实现
  • 选择排序
    • 逻辑
    • 时间复杂度
    • 代码实现
  • 插入排序
    • 逻辑
    • 时间复杂度
    • 代码实现
  • 归并排序
    • 逻辑
    • 时间复杂度
      • ONON
      • Divide and Conquer简称DC分治算法
      • 时间复杂度计算
    • 代码实现
  • 快速排序
    • 逻辑
    • 时间复杂度
    • 代码实现
    • 随机快速排序
      • 逻辑
      • 时间复杂度
  • 计数桶排序
    • 逻辑
    • 时间复杂度
    • 代码实现
  • 基数排序
    • 逻辑
    • 时间复杂度
    • 代码实现
  • 希尔排序
    • 逻辑
    • 时间复杂度O1n
    • 代码实现
  • 堆排序
    • 逻辑
    • 堆排序的思想
    • 堆排序的执行过程
    • 代码实现

感谢visualgo
排序算法我在之前这篇文章讲过一遍了，但是实现我忘了，而且那篇文章也没有加入代码
我重新整理下吧

排序算法

排序问题有各种有趣的算法解决方案，体现了许多计算机科学的想法：

• 比较与非比较的策略，
• 迭代与递归实现，
• 分歧和征服范式（这个或这个），
• 最佳/最差/平均时间复杂度分析，
• 随机算法等

当数组被排序时，涉及其内容的许多问题变得容易（或更容易），例如

• 搜索数组中的特定值v - 二进制搜索，
• 在（静态）数组中找到最小/最大/第k个最小/最大值，
• 测试唯一性和删除重复，
• 计算特定值v在阵列中出现多少时间，
• 在两个排序的数组A和B之间设置交集/联合，
• 寻找目标对x和y使得x + y等于目标z等。

前六个算法是基于比较的排序算法，而最后两个算法不是。中间三种算法是递归排序算法，其余算法通常迭代实现。
基于比较的排序算法：

1. 冒泡排序，
2. 选择排序，
3. 插入排序，
4. 归并排序（递归实现），
5. 快速排序（递归执行），
6. 随机快速排序（递归实现）。

不基于比较的排序算法：

1. 计数排序，
2. 基数排序。

冒泡排序

逻辑

给定一个N个元素的数组，冒泡排序将：
比较一对相邻项目（a，b），
如果项目出现故障，交换对（在本例中为> b），
重复步骤1和2，直到我们到达数组的最后（最后一对，（N - 2）项和（N -1）项使用基于0的索引）
到目前为止，最大的项目将在最后的位置。
然后我们将N减少1，并重复步骤1，直到我们有N = 1。
（一个框，可以把框内的两个数按大小排序，框先框住最左边的两个数，排序，然后右移一位，排序，继续…）
（这样循环一次，最大的便移动到最右端了，然后去掉最右端，再来）

时间复杂度

O（N2）
（标准）气泡排序中有两个嵌套循环。

外部循环运行正好N次迭代。
但内循环越来越短：
当i = 0，（N -1）迭代（比较和可能的交换）时，
当i = 1，（N -2）迭代时，
…，
当i =（N -2），1次迭代时，
当i =（N -1），0迭代。
因此，迭代的总数 =（N−1）+（N−2）+...+1+0=N∗（N−1）2
总时间 =c∗N∗（N−1）/2=O（N2）

代码实现

def bubble_sort(lists):
for i in range(len(lists)):
for j in range(len(lists)-i-1):
if lists[j] > lists[j+1]:
                lists[j],lists[j+1] = lists[j+1],lists[j]
        print(lists)
return lists

哦。。。我说看别人的代码怎么和我的都不一样，别人的都是从前往后，从小到大排的，我的是从后往前，从大到小排的，虽然结果是一样的吧
或许因为我是完全跟着那个网站走的吧

def bubble_sort(lists):
# 冒泡排序
    count = len(lists)
for i in range(0, count):
for j in range(i + 1, count):
if lists[i] > lists[j]:
                lists[i], lists[j] = lists[j], lists[i]
return lists

选择排序

逻辑

给定N个项目的数组，L = 0，选择排序将：
在[ L … N -1] 的范围内找到最小项目X的位置，
交换X与第L项，
将下限L增加1并重复步骤1，直到L = N -2。
（找麦子，找最小的，比手上小的就记住位置及大小，一路找到最后，将那个位置与当前位置的交换，走到下一位，再次执行）

时间复杂度

O（N2）
类似与冒泡排序
外循环N次
内循环越来越短
因此，迭代的总数 =（N−1）+（N−2）+...+1+0=N∗（N−1）2
总时间 =c∗N∗（N−1）/2=O（N2）

代码实现

def select_sort(lists):
for i in range(len(lists)):
        key = i
for j in range(i,len(lists)):
if lists[j] < lists[key]:
                key = j
        lists[i],lists[key] = lists[key],lists[i]
return lists

插入排序

逻辑

（对前两个数进行排序）
（检测第三个数，向左比较，如果比自己大，将那个数右移一位，继续向左比较，直到比自己小（或者没有数（到头了）），在该位置插入）
（检测第四个数…）

时间复杂度

外部循环执行N次，这很清楚。
但内循环的执行次数取决于输入：
在最佳情况下，阵列已经被排序，并且（a [j]> X）总是为假
所以不需要数据移位，并且内循环在O（1）中运行，
在最坏情况下，阵列是反向排序的，（a [j]> X）总是为真
插入总是出现在数组的前面，内部循环在O（N）中运行。
因此，
最佳情况时间为 O（N×1）=O（N）
最坏情况时间为 O（N×N）=O（N2）

代码实现

def insert_sort(lists):
for i in range(1,len(lists)):
        key = lists[i]
for j in range(i-1,-1,-1):
if lists[j] < key:
                lists[j+1] = key
break
            lists[j+1] = lists[j]
else:
            lists[0] = key

return lists

倒着数原来能数到负数啊，但是还是不能直接搞定0位置

def insert_sort(lists):
# 插入排序
    count = len(lists)
for i in range(1, count):
        key = lists[i]
        j = i - 1
while j >= 0:
if lists[j] > key:
                lists[j + 1] = lists[j]
                lists[j] = key
            j -= 1
return lists

我比它少一句赋值，但是用了break，但是他的看起来也不是标准的插入啊

归并排序

逻辑

给定一组N个项目，合并排序将：
将每对单个元素（默认情况下，排序）合并到2个元素的排序数组中，
将2个元素的每对排序的数组合并为4个元素的排序数组，
重复该过程…，
最后一步：合并2个N / 2元素的排序数组（为了简单的讨论，我们假设N是偶数），以获得一个完整排序的N个元素的数组。
这只是一般的想法，我们需要更多的细节，然后才能讨论归并排序的真实形式。
（排序第一第二个数，排序第三第四个数，排序一二三四）
（排序第五第六个数，排序第七第八个数，排序五六七八，排序一二三四五六七八）
（排序第九第十个数，to be continued）

时间复杂度

O（N）

给定大小为N 1和N 2的两个排序的数组A和B，我们可以在O（N）个时间内将它们有效地合并成一个大小为N = N 1 + N 2的较大组合排序的数组。
这是通过简单地比较两个阵列的前端并在任何时候取两个中较小的一个来实现的。但是，我们将需要额外的数组来正确地进行合并。

Divide and Conquer（简称D＆C）（分治算法）

归并排序是一个分治排序算法。
分治算法递归地把一个大问题分解为多个类型相同的子问题,直到这些子问题足够的简单能被直接解决.最后把这些子问题的解结合起来就能得到原始问题的解.
分解步骤很简单：将当前数组划分成两半（如果N是偶数则完全相等，如果N是奇数，则一边稍大一个元素），然后递归地对这两半进行排序。
治理步骤是最有效的工作：使用前面讨论的合并例程合并两个（排序）的一半以形成排序的数组。

时间复杂度计算

在归并排序中，大部分工作是在治理/合并步骤中完成的，因为分解步骤并不真正做任何事情（视为O（1））。

Level 1: 2^0=1 calls to merge() with N/2^1 items each, O(2^0 x 2 x N/2^1) = O(N)
Level 2: 2^1=2 calls to merge() with N/2^2 items each, O(2^1 x 2 x N/2^2) = O(N)
Level 3: 2^2=4 calls to merge() with N/2^3 items each, O(2^2 x 2 x N/2^3) = O(N)
…
Level (log N): 2^(log N-1) (or N/2) calls to merge() with N/2^log N (or 1) item each, O(N)

存在logN级，并且在每个级别中，我们执行O（N）工作，因此总时间复杂度为O（N log N）。我们稍后会看到这是一个最优（基于比较的）排序算法，即我们不能比这更好。

稍稍有些难以理解。

代码实现

def merge(left, right):
    l,r = 0,0
    nlist = []
while l<len(left) and r<len(right):
if left[l] < right[r]:
            nlist.append(left[l])
            l += 1
elif left[l] > right[r]:
            nlist.append(right[r])
            r += 1
while l < len(left):
        nlist.append(left[l])
        l += 1
while r<len(right):
        nlist.append(right[r])
        r += 1
return nlist
def merge_sort(lists):
if len(lists) <= 1:
return lists
    n = len(lists)/2
    left = merge_sort(lists[:n])
    right = merge_sort(lists[n:])
return merge(left,right)

def merge(left, right):
    i, j = 0, 0
    result = []
while i < len(left) and j < len(right):
if left[i] <= right[j]:
            result.append(left[i])
            i += 1
else:
            result.append(right[j])
            j += 1
    result += left[i:]
    result += right[j:]
return result

def merge_sort(lists):
# 归并排序
if len(lists) <= 1:
return lists
    num = len(lists) / 2
    left = merge_sort(lists[:num])
    right = merge_sort(lists[num:])
return merge(left, right)

不需要用while循环的

快速排序

逻辑

分解步骤：选择项目p（称为枢纽）
然后将[i..j]的项目分为三部分：a [i..m-1]，a [m]和[m + 1 ..j]。
a [i..m-1]（可能为空）包含小于p的项目。
a [m]是枢轴p，即索引m是数组a的排序顺序中p的正确位置。a [m + 1..j]（可能为空）包含大于或等于p的项目。然后，递归地分类这两个部分。
治理步骤：不要惊讶…我们什么都不做：哦！
（选择第一个数，将其它所有的数同它进行比较，比它小的放到前一个序列，比它大的放到后边的序列（这样这个数的位置就确定了））
（这样我们有了一个位置已经确定的数以及两个序列，在对那两个序列进行同样的步骤（递归））

时间复杂度

我们将通过首先讨论其最重要的子例程O（N）分区来剖析此快速排序算法。

为了分割一个[i..j]，我们首先选择一个[i]作为枢轴点p。
其余项目（即[i + 1..j]）分为3个区域：
S1 = a [i + 1..m]其中项目为< p，
S2 = 一个[M + 1..k-1] ，其中项目≥ p，和
未知= a [k..j]，其中项目尚未分配给S1或S2。
最初，S1和S2两个区域都是空的，即除了指定枢轴p之外的所有项目都在未知区域。
然后，对于未知区域中的每个项目a [k]，我们将a [k]与p进行比较，并确定两种情况之一：
如果一个[K] ≥ p，把一个[K]为S2，或
否则，将[k]设为S1。
最后，我们交换一个[i]和[m]将枢轴p右移到S1和S2的中间。


只有一个循环遍历（ji）次。由于j可以和N -1 一样大，我可以低至0，所以分区的时间复杂度为O（N）。
在这种最糟糕的情况输入情况下，会发生什么：

当分区总是将阵列分成两个相等的两半，如合并排序时，出现快速排序的最佳情况。

当这种情况发生时，递归的深度只有日志n。

当每个级别采用O（N）比较时，时间复杂度为O（N log N）。

代码实现

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

如序列[6，8，1，4，3，9]，选择6作为基准数。从右向左扫描，寻找比基准数小的数字为3，交换6和3的位置，[3，8，1，4，6，9]，接着从左向右扫描，寻找比基准数大的数字为8，交换6和8的位置，[3，6，1，4，8，9]。重复上述过程，直到基准数左边的数字都比其小，右边的数字都比其大。然后分别对基准数左边和右边的序列递归进行上述方法。

def quick_sort(lists,left,right):
if left >= right:
        return lists
    key = lists[left]
    low = left
    high = right
while left < right:
while left < right and lists[right] >= key:
right -= 1
        lists[left] = lists[right]
while left < right and lists[left] <= key:
left += 1
        lists[right] = lists[left]
    lists[right] = key
    quick_sort(lists, low, left - 1)
    quick_sort(lists, left + 1, high)
    return lists

其它方法的快速排序，说起来和我最初的设想是一样的，可是我写的时候不知怎么就递归超时了，尴尬

def pythonic_quick_sort(a):
if len(a) <= 1:
return a
    pivot = a[-1]
    pivots = [i for i in a if i == pivot]
    left = pythonic_quick_sort([i for i in a if i < pivot])
    right = pythonic_quick_sort([i for i in a if i > pivot])
return left + pivots + right
#def qsort(L): 
# if not L: return [] 
# return qsort([x for x in L[1:] if x< L[0]]) + L[0:1] + \ 
# qsort([x for x in L[1:] if x>=L[0]]) 

随机快速排序

逻辑

不选第一个数，随便选个位置的数

时间复杂度

O（NlogN)
不想写了

计数(桶)排序

如果存在输入数组的某些假设，我们可以实现更快的排序算法 - 即在O（N）中，因此我们可以避免比较项目以确定排序顺序。

逻辑

假设：如果要排序的项目是小范围的整数，我们可以计算每个整数的出现频率（在该小范围内），并循环通过该小范围以排序顺序输出项目。
尝试计数对上面的示例数组进行排序，其中所有整数都在[1..9]内，因此我们只需要计算整数1出现多少次，出现多少次整数2，出现多少次整数9，然后循环1到9。
（假设序列中的数都在1到9中，只要统计下个数，就能进行排序了）

时间复杂度

时间复杂度是O（N）来计算频率，O（k）其中k是输入整数的范围，在这个例子中为9-1 + 1 = 9。计数排序的时间复杂度是O（N + k），如果k是（非常）小，则为O（N）。

代码实现

def bucket_sort(lists):
    buckets = [0 for i in range(10)]
for i in lists:
        buckets[i] += 1
    nlist=[]
for i,j in enumerate(buckets):
while j>0:
            nlist.append(i)
            j -= 1
return nlist

基数排序

逻辑

把每一个项目进行排序为字符串ð数字（我们垫整数有小于ð位数字加上零如果必要的话）。

对于最高有效位（最右边）的数字（最左边），我们通过N个项目，并将它们根据活动数字放入10个队列（每个数字[0..9]一个），这就像一个修改的计数排序这个保持稳定性。然后我们再重新连接组，以便后续的迭代。
（将序列中的每一个数的最后一位按从0到9进行排列）

（然后逐项扔出（先进先出））

（将序列中的每一个数的倒数第二位按从0到9进行排列）

（然后逐项扔出（先进先出））

（依此类推，直到最高位）

时间复杂度

注意，我们只执行O（d×（N + k））次迭代。d为最大数字位数，k为数量。

代码实现

def radix_sort(lists):
    lmax = max(lists)
    d=0
while lmax > 0:
        lmax /= 10
        d += 1
for k in range(d):
        s=[[] for i in range(10)]
for i in lists:
            s[i/(10**k)%10].append(i)
        lists=[j for i in s for j in i]
return lists

希尔排序

逻辑

希尔排序的实质就是分组插入排序，该方法又称缩小增量排序，因DL．Shell于1959年提出而得名。
希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。
希尔排序是基于插入排序的以下两点性质而提出改进方法的：
插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率
但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位

时间复杂度:O((1+τ)n)

代码实现

def shell_sort(lists):
    step = len(lists)/2
while step > 0:
for i in range(step, len(lists)):
while i >= step and lists[i-step] > lists[i]:
                lists[i], lists[i-step] = lists[i-step], lists[i]
                i -= step
        step = step/2
return lists

堆排序

逻辑

堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。堆分为大根堆和小根堆，是完全二叉树。大根堆的要求是每个节点的值都不大于其父节点的值，即A[PARENT[i]] >= A[i]。在数组的非降序排序中，需要使用的就是大根堆，因为根据大根堆的要求可知，最大的值一定在堆顶。

堆排序的思想

堆是一种数据结构，可以将堆看作一棵完全二叉树，这棵二叉树满足，任何一个非叶节点的值都不大于（或不小于）其左右孩子节点的值。 将一个无序序列调整为一个堆，就可以找出这个序列的最大值（或最小值），然后将找出的这个值交换到序列的最后一个，这样有序序列就元素就增加一个，无序序列元素就减少一个，对新的无序序列重复这样的操作，就实现了排序。

堆排序的执行过程

1.从无序序列所确定的完全二叉树的第一个非叶子节点开始，从右至左，从下至上，对每个节点进行调整，最终将得到一个大顶堆。
对节点的调整方法：将当前节点（假设为a）的值与其孩子节点进行比较，如果存在大于a的值的孩子节点，则从中选出最大的一个与a交换。当a来到下一层的时候重复上述过程，直到a的孩子节点的值都小于a为止

2.将当前无序序列中的第一个元素（反映在数中是根节点b），与无序序列中的最后一个元素交换（假设为c），b进入有序序列，到达最终位置。无序序列元素减少1个，有序序列元素增加1个，此时只有节点c可能不满足堆的定义，对其进行调整。

3.重复2 的过程，直到无序序列的元素剩下一个时排序结束。

代码实现

这个不是自己写的了

def sift_down(arr, start, end):
    root = start
while True:
# 从root开始对最大堆调整
        child = 2 * root + 1
if child > end:
break

# 找出两个child中交大的一个
if child + 1 <= end and arr[child] < arr[child + 1]:
            child += 1

if arr[root] < arr[child]:
# 最大堆小于较大的child, 交换顺序
            arr[root], arr[child] = arr[child], arr[root]

# 正在调整的节点设置为root
            root = child
else:
# 无需调整的时候, 退出
break


def heap_sort(arr):
# 从最后一个有子节点的孩子还是调整最大堆
    first = len(arr) // 2 - 1
for start in range(first, -1, -1):
        sift_down(arr, start, len(arr) - 1)

# 将最大的放到堆的最后一个, 堆-1, 继续调整排序
for end in range(len(arr) -1, 0, -1):
        arr[0], arr[end] = arr[end], arr[0]
        sift_down(arr, 0, end - 1)