基础算法（排序）

这一篇是发现，很长时间不复习，一些基础排序算法自己都忘记了，索性就单独分出来一章，总结一下。

插入排序

插入排序的大体思维如上图，对排序数组的每一个进行遍历，比较大小，比前面元素大的就插入到该元素前面。

时间复杂度在最坏情况下是O(n^2)

下面是python的算法实现

1
2
3
4
5
6
def insetorder(arr,start,d):
    for i in range(start+d,len(arr),d):
        j = i
        while j >= start + d and arr[j-d] > arr[j]:
            arr[j-d],arr[j] = arr[j],arr[j-d]
            j -= d

这边为了方便下面的希尔排序，所以这边是设置了开始参数start和比较间隔d，在初始的插入排序中start=0，d=1.

需要注意插入排序的起始位置其实是数组的第二个元素，第一个元素前面是没有元素的，无法进行插入排序比较。

希尔排序

希尔排序可以看做是对插入排序的算法优化，所以时间复杂度上面是要小于插入排序的O(n^2),在O(n1.3)~O(n1.5)之间。

希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。

希尔排序是基于插入排序的以下两点性质而提出改进方法的：

插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；
但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位；
希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录”基本有序”时，再对全体记录进行依次直接插入排序。

1
2
3
4
5
6
7
def shellsort(arr):
    jump = len(arr) // 2
    while jump > 0:
        for i in range(jump):
            insetorder(arr,i,jump)
        jump = jump // 2

核心是不断不算压缩分割间隔，当分割间隔等于零，完成对整个数组的排序。

快速排序

该方法的基本思想是：

  • 1．先从数列中取出一个数作为基准数。

  • 2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。

  • 3．再对左右区间重复第二步，直到各区间只有一个数。

    平均时间复杂度：O(NlogN)
    最佳时间复杂度：O(NlogN)
    最差时间复杂度：O(N^2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def quick_sort(b):
    if len(b) < 2:
        return b

    mid = b[len(b) // 2]

    left, right = [], []
    # 从原始数组中移除基准值
    b.remove(mid)
    for item in b:
        if item >= mid:
            right.append(item)
        else:
            # 小于基准值放左边
            left.append(item)
    # 使用迭代进行比较
    return quick_sort(left) + [mid] + quick_sort(right)

该排序算法的写法，大多数采用递归思想，所以在理解上，要注意！

冒泡排序

时间复杂度O(n^2)

最最最基础的排序算法，这边直接上代码

1
2
3
4
5
6
7
def maopao(arr):
  for i in range(1,len(arr))
   for j in range(0,len(arr)-i)
     if arr[j] > arr[j+1]:
      arr[j], arr[j + 1] = arr[j + 1], arr[j]
  return arr

每一次的冒泡的排序都会将最大的元素沉到数组底部，所以在第二个循环时候，需要将已经沉底的元素剔除。

归并排序

算法步骤

  1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
  2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置；
  3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
  4. 重复步骤 3 直到某一指针达到序列尾；
  5. 将另一序列剩下的所有元素直接复制到合并序列尾。

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
def merge(a, b):
    c = []
    h = j = 0
    while j < len(a) and h < len(b):
        if a[j] < b[h]:
            c.append(a[j])
            j += 1
        else:
            c.append(b[h])
            h += 1

    if j == len(a):
        for i in b[h:]:
            c.append(i)
    else:
        for i in a[j:]:
            c.append(i)

    return c

def merge_sort(lists):
    #递归思想
    if len(lists) <= 1:
        return lists
    middle = len(lists) // 2
    left = merge_sort(lists[:middle])
    right = merge_sort(lists[middle:])
    return merge(left, right)

这个算法的书写，也是采用递归思想，将数组分割，之后进行子数组的排序，最后进行数组的整合

总结