基础算法题总结8--排序算法

排序算法有冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序、计数排序、桶排序、基数排序等等

Python 实现

不断的遍历，每次将最大的换到未排序的数组的最后

class Solution:
    def bubbleSort(self,arr):
        n = len(arr)
        for i in range(n):
            for j in range(n-i-1):
                if arr[j] > arr[j+1]: ## 将大的一直向后换
                    arr[j],arr[j+1] = arr[j+1],arr[j]
        return arr

不断的遍历，每次选取一个最小的放在未排序的数组的前面

class Solution:
    def selectSort(self,arr):
        n = len(arr)
        for i in range(n-1):
            min = i
            for j in range(i+1,n):
                if arr[j] < arr[min]: ## 当找到一个比当前最小的还小的数就进行替换
                    min = j
                    arr[min],arr[j] = arr[j],arr[min]
        return arr

从数组的最开始遍历，选中一个值，比较该放在哪个位置就插入，采用 in-place 排序

class Solution:
    def insertSort(self,arr):
        n = len(arr)
        for i in range(1,n): ## 将第一个元素当做一个有序序列
            j = i-1
            current = arr[i]  ## 当前要插入的值
            ## 遍历前面有序序列，判断小于便插入，继续向前比较
            while j>=0 and arr[j] > current: 
                arr[j+1] = arr[j]
                j -= 1
            arr[j+1] = current  ## 当比较结束，将当前的值插入到相应的位置上       
        return arr

class Solution:
    def partition(self, arr, left,right):
        pivot = arr[left] ## 选中第一个元素作为基准
        while left<right:
            while left<right and arr[right] >= pivot:  ## 从后往前查找小于基准的
                right -= 1
            arr[left],arr[right] = arr[right],arr[left]
            while left < right and arr[left] <= pivot:  ## 从前往后找大于基准的
                left += 1
            arr[left],arr[right] = arr[right],arr[left]
        arr[right] = pivot
        return right

def quickSort(self, arr, left, right):
        if left < right:
            q = self.partition(arr,left,right)
            self.quickSort(arr,left,q-1)
            self.quickSort(arr,q+1,right)
        return arr

class Solution:
    def quickSort2(self, arr):
        if len(arr) < 2:
            return arr
        else:
            temp = arr[0]
            more = [i for i in arr[1:] if i > temp]
            less = [i for i in arr[1:] if i <= temp]
        return self.quickSort2(less) + [temp] + self.quickSort2(more)

class Solution:
    def heapify(self,arr,n,i):  ## 构建大根堆
        largest = i  ## 最大值的节点位置
        left = 2*i + 1  ## 左孩子的位置
        right = 2*i + 2 ## 右孩子的位置

## 如果改成arr[i] > arr[left],则是小顶堆
        if left < n and arr[i] < arr[left]: ## 有左孩子且左孩子比当前的大
            largest = left
        if right < n and arr[largest] < arr[right]: ## 有右孩子且右孩子比当前的大
            largest = right

if largest != i:  ## 如果左右孩子有比当前节点大的值，则要交换
            arr[i],arr[largest] = arr[largest],arr[i]
            self.heapify(arr,n,largest) ## 继续遍历下一个节点

def heapSort(self,arr):  ## 对堆顶进行抽取，实现堆排序
        n = len(arr)
        ## 建立一个大根堆
        for i in range(n,-1,-1): ## 自底向上建堆
            self.heapify(arr,n,i)


        ## 交换元素，堆顶元素和最后的元素互换
        for i in range(n-1,0,-1):
            arr[i],arr[0] = arr[0],arr[i]
            #需注意建堆起始位置为0，堆形状大小为i，即建堆的规模逐步缩小。已经有序的部分不需要再改动
            self.heapify(arr,i,0)

return arr