冒泡排序

一、排序流程

• 1.比较相邻的元素。如果第一个比第二个大，就交换他们两个。
• 2.对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
• 3.针对所有的元素重复以上的步骤，除了最后一个。
• 4.持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

最好时间复杂度	最坏时间复杂度	平均时间复杂度
O(n)	O(n^2)	O(n^2)

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

二、选择排序

def find_smallest(nums):
    smallest = nums[0]
    smallest_index = 0
    for index, num in enumerate(nums):
        if num < smallest:
            smallest = num
            smallest_index = index
    return smallest_index

def select_sort(nums):
    sorted_nums = []
    while len(nums) > 0:
        smallest_index = find_smallest(nums)
        smallest_num = nums.pop(smallest_index)
        sorted_nums.append(smallest_selected)
    return sorted_nums

最好时间复杂度	最坏时间复杂度	平均时间复杂度
O(n^2)	O(n^2)	O(n^2)

三、插入排序

• 插入排序是指在待排序的元素中，假设前面n-1(其中n>=2)个数已经是排好顺序的，现将第n个数插到前面已经排好的序列中，然后找到合适自己的位置，使得插入第n个数的这个序列也是排好顺序的。按照此法对所有元素进行插入，直到整个序列排为有序的过程，称为插入排序

def insert_sort(nums):
    for index, num in enumerate(nums):
        pointer = index
        while pointer > 0 and nums[pointer] > num:
            nums[pointer] = nums[pointer - 1]
            pointer -= 1
        nums[pointer] = num
    return nums

最好时间复杂度	最坏时间复杂度	平均时间复杂度
O(n)	O(n^2)	O(n^2)

四、希尔排序

• 1.算法先将要排序的一组数按某个增量d分成若干组，每组中记录的下标相差d.对每组中全部元素进行排序，然后再用一个较小的增量对它进行，在每组中再进行排序。当增量减到1时，整个要排序的数被分成一组，排序完成。

• 2.一般的初次取序列的一半为增量，以后每次减半，直到增量为1。

def shell_sort(nums):
    length = len(nums)
    gap = length // 2
    while gap > 0:
        for i in range(gap, length):
            temp = nums[i]
            j = i
            while j >= gap and num[j - gap] > temp:
                j -= gap
            nums[j] = temp
        gap = gap // 2
    return nums

最好时间复杂度	最坏时间复杂度	平均时间复杂度
O(n^1.3)	O(n^2)	-

希尔排序

五、归并排序

归并排序（Merge Sort）是建立在归并操作上的一种有效，稳定的排序算法，该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

def merge(left, right):
    result = []
    while left and right:
        if left[0] < right[0]:
            result.append(left.pop(0))
        else:
            result.append(right.pop(0))
    if left:
        result += left
    if right:
        result  += right
    return result
def merge_sort(nums):
    if len(nums) <= 1:
        return nums
    mid = len(nums) // 2
    left = nums[:mid]
    right = nums[mid:]
    left = merge_sort(left)
    right = merge_sort(right)
    return merge(left, right)

最好时间复杂度	最坏时间复杂度	平均时间复杂度	稳定性
O(nlogn)	O(nlogn)	O(nlogn)	稳定

六、快速排序

• 1.首先设定一个分界值，通过该分界值将数组分成左右两部分。

• 2.将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值。

• 3.然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。

• 4.重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。

def quick_sort(nums):
    if len(nums) <= 1:
        return nums
    pivot = nums[0]
    less = [i for i in nums[1:] if i <= pivot]
    greater = [i for i in nums[i:] if i > pivot]
    return quick_sort(less) + [pivot] + quick_sort(greater)

class QuickSort:
    def quick_sort(self, nums):
        self.random_quicksort(nums, left, right)
        return nums
    def random_quicksort(self, nums, left, right):
        if left >= right:
            return
        pivot = self.random_paritition(nums, left, right)
        self.random_quicksort(nums, left, pivot - 1)
        self.random_quicksort(nums, pivot + 1, right)
    def random_partition(self, nums, left, right):
        pivot = random.randint(left, right)
        nums[right], nums[pivot] = nums[pivot], nums[right]
        i = left - 1
        for j in range(left, right):
            if nums[j] < nums[right]:
                i += 1
                nums[i], nums[j] = nums[j], nums[i]
        i += 1
        nums[i], nums[right] = nums[right], nums[i]
        return i

最好时间复杂度	最坏时间复杂度	平均时间复杂度
O(nlogn)	O(n^2)	O(nlogn)

七、堆排序

heapSort.gif

def build_heap(nums, length, i):
    largest = i
    left = 2 * i + 1
    right = 2 * i + 1
    
def heap_sort(nums):
    length = len(nums)
    for i in range(length, -1, -1):
        build_heap(nums, length, i)

八、计数排序

def counting_sort(nums, max):  # maxnumber为数组中的最大值
    length = len(nums)
    if length <= 1:
        return nums
    count_array= [0] * (max + 1)
    for num in nums:
        count_array[num] += 1
    result = []
    for i in range(max + 1):
        for j in range(count_array[i]):
            result.append(i)
    return result

计数排序的时间复杂度	基于比较的排序时间复杂度下限
O(n + k)k是整数范围	O(nlogn)

若O(k) > O(nlogn)时其效率反而不如基于比较的排序