排序

1 冒泡排序

class BubbleSort:
    def bubbleSort(self, A, n):
        # write code here
        for i in range(n-1):
            for j in range(n-1-i):
                if A[j] > A[j+1]:
                    A[j], A[j+1] = A[j+1], A[j]
        return A

2 选择排序

class SelectionSort:
    def selectionSort(self, A, n):
        # write code here
        for i in range(n-1):
            e = A[i]
            k = i
            for j in range(i+1,n):
                if A[j] < A[i]:
                    A[i] = A[j]
                    k = j
            if k != i:
                A[k] = e
        return A

3 插入排序

class InsertionSort:
    def insertionSort(self, A, n):
        # write code here
        for i in range(1, n):
            x = A[i]
            j = i
            while j > 0 and A[j-1] > x:
                A[j] = A[j-1]
                j -= 1
            A[j] = x
        return A

4 归并排序

class MergeSort:
    def mergeSort(self, A, n):
        # write code here
        if len(A) == 1:
            return A
        
        num = len(A)//2
        left = self.mergeSort(A[:num], num)
        right = self.mergeSort(A[num:], num)
        
        i, j = 0, 0
        result = []
        while i < len(left) and j < len(right):
            if left[i] < right[j]:
                result.append(left[i])
                i += 1
            else:
                result.append(right[j])
                j += 1
        result += left[i:]
        result += right[j:]
        return result

5 快速排序

class QuickSort:
    def quickSort(self, A, n):
        # write code here
        self.qsort(A, 0, n-1)
        return A
        
    def qsort(self, A, l, r):
        if l >= r:
            return
        pivot = A[l]
        i = l
        j = r
        while i < j:
            while i < j and A[j] > pivot:
                j -= 1
            if i < j:
                A[i] = A[j]
                i += 1
            while i < j and A[i] < pivot:
                i += 1
            if i < j:
                A[j] = A[i]
                j -= 1
        A[i] = pivot
        self.qsort(A, l, i-1)
        self.qsort(A, i+1, r)

6 堆排序

class HeapSort:
    def heapSort(self, A, n):
        # write code here
        def siftdown(A, e, begin, end):
            i, j = begin, begin*2+1
            while j<=end:
                if j+1 <= end and A[j+1]<A[j]:
                    j += 1
                if e < A[j]:
                    break
                A[i] = A[j]
                i, j = j, 2*j+1
            A[i] = e
            
        end = n
        for i in range((end-1)/2, -1, -1):
            siftdown(A, A[i], i, end-1)
        for i in range(end-1, 0, -1):
            e = A[i]
            A[i] = A[0]
            siftdown(A, e, 0, i-1)
            
        return A[::-1]