排序算法分析

冒泡排序：

冒泡排序

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

选择排序：

#选择排序
def selectionSort(nums):
    for i in range(len(nums) - 1):
        minIndex = i
        for j in range(i+1, len(nums)):
            if nums[j] < nums[minIndex]:
                minIndex = j
        nums[i], nums[minIndex] = nums[minIndex], nums[i]
    return nums

插入排序：

#插入排序
def insertionSort(nums):
    for i in range(len(nums) - 1):
        currentNum, preIndex, = nums[i+1], i
        while preIndex >= 0 and nums[preIndex] > currentNum:
            nums[preIndex + 1] = nums[preIndex]
            preIndex -= 1
        nums[preIndex + 1] = currentNum
    return nums

希尔排序：

#希尔排序
def shellSort(nums):
    length = len(nums)
    gap = 1
    while gap < length//3:
        gap = gap * 3 + 1
    while gap>0:
        for i in range(gap, length):
            currentNum, preIndex = nums[i], i-gap
            while preIndex > 0 and nums[preIndex] > currentNum:
                nums[preIndex + gap] = nums[preIndex]
                preIndex -= gap
            nums[preIndex + gap] = currentNum
        gap = gap//3
    return nums

归并排序：

#归并排序
def mergeSort(nums):
    def merge(left, right):
        results = []
        i, j = 0, 0
        while i < len(left) and j < len(right):
            if left[i] <= right[j]:
                results.append(left[i])
                i+=1
            else:
                results.append(right[j])
                j+=1
        results = results + left[i:] + right[j:]
        return results
    
    if len(nums) <= 1:
        return nums
    mid = len(nums)//2
    left = mergeSort(nums[:mid])
    right = mergeSort(nums[mid:])
    return merge(left, right)

快速排序：

#快速排序 空间复杂度 O(nlogn)
def quickSort1(nums):
    if len(nums) <= 1:
        return nums
    pivot = nums[0]
    left = [nums[i] for i in range(1, len(nums)) if nums[i] <= pivot]
    right = [nums[i] for i in range(1, len(nums)) if nums[i] > pivot]
    return quickSort1(left) + [pivot] + quickSort1(right)

#快速排序 空间复杂度 O(logn)
def quickSort2(nums, left, right):
    def partition(nums, left, right):
        pivot = nums[left]
        
        while left < right:
            while left < right and nums[right] >= pivot:
                right -= 1
            nums[left] = nums[right]
            while left < right and nums[left] <= pivot:
                left += 1
            nums[right] = nums[left]
        nums[left] = pivot
        return left
    
    if left < right:
        pivotIndex = partition(nums, left, right)
        quickSort2(nums, left, pivotIndex - 1)
        quickSort2(nums, pivotIndex + 1, right)
    return nums
    

堆排序：

#堆排序
def heapSort(nums):
    def adjustHeap(nums, index, size):
        largestIndex = index
        leftIndex = index * 2 + 1
        rightIndex = index * 2 + 2
        if leftIndex < size and nums[leftIndex] > nums[largestIndex]:
            largestIndex = leftIndex
        if rightIndex < size and nums[rightIndex] > nums[largestIndex]:
            largestIndex = rightIndex
        if largestIndex != index:
            nums[largestIndex], nums[index] = nums[index], nums[largestIndex]
            adjustHeap(nums, largestIndex, size)
    def buildHeap(nums, size):
        for i in range(size//2)[::-1]:
            adjustHeap(nums, i, size)
    size = len(nums)
    buildHeap(nums, size)
    for i in range(size)[::-1]:
        nums[0], nums[i] = nums[i], nums[0]
        adjustHeap(nums, 0, i)
    return nums

计数排序：

#计数排序
def countingSort(nums):
    bucket = [0]*(max(nums) + 1)
    for num in nums:
        bucket[num]+=1
    i = 0
    for j in range(len(bucket)):
        while bucket[j] !=0:
            nums[i]=j
            i+=1
            bucket[j]-=1
    return nums

桶排序：

#桶排序
def bucketSort(nums, defaultBucketSize = 5):
    minVal, maxVal = min(nums), max(nums)
    bucketSize = defaultBucketSize
    bucketCount = (maxVal - minVal)//bucketSize + 1
    bucket = []
    for i in range(bucketCount):
        bucket.append([])
    for num in nums:
        bucket[(num-minVal)//bucketSize].append(num)
    nums.clear()
    for value in bucket:
        value = insertionSort(value)
        nums.extend(value)
    return nums

基数排序：

#基数排序
def radixSort(nums):
    div = 1
    mod = 10
    buckets = [[] for _ in range(mod)]
    mostBit = len(str(max(nums)))
    while mostBit:
        for num in nums:
            buckets[num//div%mod].append(num)
        i=0
        for bucket in buckets:
            while bucket:
                nums[i] = bucket.pop(0)
                i+=1
        div *= 10
        mostBit -=1
    return nums

源出处：
https://www.jianshu.com/p/bbbab7fa77a2