几种基础排序算法的python实现

发表于 | 分类于 |

最近希望能够弥补一下数据结构与算法相关基础知识，便先尝试用python去实现常见的几种基础排序算法,实现代码归纳如下。

冒泡排序
1
2
3
4
5
6
7
8
def bubbleSort(nums):
    count = len(nums) - 2
    while count > 0:
        for i in range(count + 1):
            if nums[i] > nums[i + 1]:
                nums[i], nums[i + 1] = nums[i + 1], nums[i]
        count -= 1
    return nums
选择排序
1
2
3
4
5
6
def insert_sorted(a_list):
    for i in range(len(a_list) - 1):
        for j in range((i + 1), len(a_list)):
            if a_list[i] > a_list[j]:
                a_list[i], a_list[j] = a_list[j], a_list[i]
    return a_list
归并排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def mergeSort(A, n):
    # write code here
    if n <= 1:
        return A
    num = int(n / 2)
    left = mergeSort(A[:num], len(A[:num]))
    right = mergeSort(A[num:], len(A[num:]))
    return merge(left, right)


def merge(list1, list2):
    result = []
    i, j = 0, 0
    while i < len(list1) and j < len(list2):
        if list1[i] < list2[j]:
            result.append(list1[i])
            i += 1
        else:
            result.append(list2[j])
            j += 1
    result += list1[i:]
    result += list2[j:]
    return result
快速排序
1
2
3
4
5
6
7
8
9
10
11
12
13
def quickSort(aList):
    if len(aList) <= 1:
        return aList
    else:
        smaller = []        
        bigger = []
        piv = aList.pop(0)
        for i in aList:
            if i <= piv:
                smaller.append(i)
            else:
                bigger.append(i)
        return quickSort(smaller) + [piv] + quickSort(bigger)