常见排序算法

Posted on | Post modified:
常见排序算法以及python的实现

常见排序算法

插入排序

原理：类似于在排序的时候，创建一个新数组，新数组中是已经排好序的数组，然后从老数组中依次取值，拿出的值在新数组中依次比较，找到自己的位置，然后再从老数组中取新，重复上述办法

1
2
3
4
5
6
7
8
9
10
11
12
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

希尔算法

原理：

  1. 先取一个正整数 d1(d1 < n)，把全部记录分成 d1 个组，所有距离为 d1 的倍数的记录看成一组，然后在各组内进行插入排序
  2. 然后取 d2(d2 < d1)
  3. 重复上述分组和排序操作；直到取 di = 1(i >= 1) 位置，即所有记录成为一个组，最后对这个组进行插入排序。一般选 d1 约为 n/2，d2 为 d1 /2， d3 为 d2/2 ，…， di = 1。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def shell_sort(lists):
    # 希尔排序
    count = len(lists)
    step = 2
    group = count / step
    while group > 0:
            for i in range(0, group):
            j = i + group
            while j < count:
                k = j - group
                key = lists[j]
                while k >= 0:
                    if lists[k] > key:
                        lists[k + group] = lists[k]
                        lists[k] = key
                    k -= group
                j += group
        group /= step
    return lists

冒泡排序

原理： 遍历数组，每次都拿一个值和剩下的所有值比较，判断是否交换位置。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。

1
2
3
4
5
6
7
8
9
10
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]:
                temp = lists[j]
                lists[j] = lists[i]
                lists[i] = temp
    return lists

快速排序

原理： 取老数组的第一个数，将比他大的放左边，比他小的放右边，然后分别对左右两边的数组进行递归操作

  1. i =L; j = R; 将基准数挖出形成第一个坑a[i]。
  1. j–由后向前找比它小的数，找到后挖出此数填前一个坑a[i]中。
  1. i++由前向后找比它大的数，找到后也挖出此数填到前一个坑a[j]中。
  1. 再重复执行2，3二步，直到i==j，将基准数填入a[i]中。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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

直接选择排序

原理： 每次都查找剩下数组里面最小的元素到循环次数的位置，例如第0次循环，就找老数组最小的数，放到索引0的位置，下一次找剩下的数组中最小的元素放到索引1的位置，依次类推

1
2
3
4
5
6
7
8
9
10
11
12
def select_sort(lists):
    # 选择排序
    count = len(lists)
    for i in range(0, count):
        min = i
        for j in range(i + 1, count):
            if lists[min] > lists[j]:
                min = j
        temp = lists[min]
        lists[min] = lists[i]
        lists[i] = temp
    return lists