排序算法的原理与手写代码

本文从三个方面阐述这十种经典的排序算法，分别是：

    A、算法的性质

    B、代码的实现

    C、算法的实用性与适用范围

以下是详细的说明

A、算法的性质

1、选择排序
        1、原理
            每次都选择数组中最小的数，将其依次从第零个放入，直到最后。
        2、属性
            时间复杂度：由于每次都会遍历一遍数组，选出最小的数据。假设有n个数据，则总共需要比对n²。也就是平均复杂度为n²，同理最坏情况下也是如此。
                那么，最好的情况呢？其实也是，原因为，即使是顺序排列，按照原理可知，也需要两个循环。
            空间复杂度：不会暂用其他空间，只要本数组即可，即为1。
            稳定性：为不稳定。
                用数组5,8,5,2,9的例子解释。第一次，选择2为最小值，其与第零位的5交换位置，那么，排序后两个五的相对位置与排序前的
                    相对位置就产生了变化。即为不稳定的

    2、快速排序
        1、原理
            选择第一个数作为基数，比它小的放左边，比它大的放右边，完成一轮对比之后，以基数作为分界线，左右两边两组数据，再用同样的方法排序
                直到最终排序完成
        2、属性
            时间复杂度：平均的时间复杂度为O(nlogn)，最好的情况也是如此，最坏的情况是n²
            空间复杂度：虽然递归的时候会存一些数据，但是，总体还是在常数级。再者它只需要在自身的数组中交换数据，不需要额外开辟空间
            稳定性：为不稳定
                这个很好理解，就拿两个相同的数来说，在比对、交换的过程中，他们之间的相对位置肯定会被改变。
        3、其他
            快速排序的理论核心在于与基数的比对，然后产生两组特别数据，然后对这两组是数据进行与上个步骤相同的处理
            既然都为相同操作，那么就用用到递归，在代码上要特别注意递归的使用，所以引入begin与end是非常好的操作。

    3、插入排序
        1、原理
            可以看作是把一个数据插入到一个有序数据中，一般都是从后面插入。
            从第一个开始，它已经是有序数据了，将他与第二个进行比较，假如大于后者，则把后者插入到前面。
        2、属性 
            时间复杂度：由于它也是两曾循环，所以平均复杂度肯定是n²，最坏的情况也是如此。最好的情况则是排好顺序的数据，则第二层循环用不上
                不需要移动数据，所以为n
            空间复杂度：不会暂用其他空间，只要本数组即可，即为1。
            稳定性：为稳定 
                因为插入的原则是，当两个数据相同时，不用处理，也就是不用插入到前一个数据的前面，那么他们的相对位置就没有任何变化。
        3、其他
            我在实现插入排序时，把问题复杂化了，用了很多变量来表示，结果越来越乱。解决问题的关键在于要插入的数据与它的编号。然后根据编号
                向左移动，此时的移动用一个while循环做，判断的条件是插入数据大于它的前一个数据。
    4、希尔排序
        1、原理 
            插入排序的进阶版。
            按照一定的间隔h,选取一个数据，组成一组新的数组，相应的会产生h组数据，然后对这些数组使用插入排序。
            然后，使用二分之h作为间隔，重复上述步骤，直到h等于1。这种排序方式为希尔排序
        2、属性
            时间复杂度：平均时间复杂度为O(n的1.3次方)，最后的情况是n，最差的情况是n²
            空间复杂度：不会暂用其他空间，只要本数组即可，即为1。
            稳定性：为不稳定
                这个很好理解，按照一定的间隔取了数据之后，原来的相对关系肯定被改变了。
        3、其他
            while leftCnt > (begin - gap) and ShMatrix[leftCnt] > insertValue:
            这句特别关键，leftCnt大于的数值是从开始的位置往左边移动对应间隔的距离。

    5、冒泡排序
        1、原理
            从第一二个数开始比较，较大的数放后面，然后再第二三个数进行比较，较大的数放后面，一直比较到最后一个数
            所以，数组中最大的数就像冒泡的样子，移到了最后。这便是第一轮操作。
            同理，第二轮操作与第一轮一模一样。
        2、属性 
            时间复杂度：由于有两层循环，所以，平均时间复杂度为O(n²)，最坏的情况也是如此
                最好的情况是已经排好序了，所以只要一层循环就够了。
            空间复杂度：不会暂用其他空间，只要本数组即可，即为1。
            稳定性：为稳定
                因为在冒泡的过程中，是两者进行大小比对，不会改变数据的相对位置
        3、其他
            1、冒泡排序相对简单，但是可以参考别的大神用非常简洁的方式实现这套算法。
            2、内层循环与外层循环要相互“独立”，互相直接尽量不要牵扯。这样的目的是使算法更简单明了，也不易出错
            3、用外层循环的次数控制内层循环

B、代码的实现

    1、代码实现使用的语言为python，因为其简单易上手。

    2、结合第一部分的原理与代码的注释，应该很好理解代码。通过参考代码也可以进一步加深对算法的理解。

import random 
import time 
import datetime

QuComparision = 0
QuExchange = 0

HeComparision = 0
HeExchange = 0

########################################################################
# Get an array whose elements are unordered integers
def RandomInitList(start, end, length):
    randomList = []
    for i in range(length):
        randomList.append(random.randint(start, end))
    
    # print("The automatically generated unordered array data is:")
    # print(randomList)
    
    return randomList

########################################################################
# Choose a sorting method
def SelectionSort(SeMatrix):
    timeStart = time.time()
    comparision = 0
    exchange = 0
    exNum = 0
    inNum = 0

    while exNum < len(SeMatrix):
        minValue = SeMatrix[exNum]
        inNum = exNum

        while inNum < len(SeMatrix):
            if minValue > SeMatrix[inNum]:
                comparision = comparision + 1
                exchange = exchange + 1
                minTemp = minValue
                minValue = SeMatrix[inNum]
                SeMatrix[inNum] = minTemp
            inNum = inNum + 1

    
        exchange = exchange + 1
        SeMatrix[exNum] = minValue
        exNum = exNum + 1

    timeEnd = time.time()
    timeStart = int(round(timeStart * 1000))
    timeEnd = int(round(timeEnd * 1000))
    timeGap = timeEnd - timeStart

    #print("The result of selecting sort is:")
    #print(SeMatrix)
    print("Select comparision number:%d" % comparision)
    print("Select exchange number:%d" % exchange)
    print("timeGap:%dms" % timeGap)

    return SeMatrix

########################################################################
# Quickly sorted method calls
def QuickSortMathod(left, right, QuMatrix):
    global QuComparision
    global QuExchange
    comparision = 0
    exchange = 0
    begin = left
    end = right

    if left > right:
        return

    while left != right:
        QuComparision = QuComparision + 1
        if QuMatrix[right] <= QuMatrix[begin]:
            QuComparision = QuComparision + 1
            if QuMatrix[left] > QuMatrix[begin]:
                QuComparision = QuComparision + 1
                QuExchange = QuExchange + 1
                quickTemp = QuMatrix[left]
                QuMatrix[left] = QuMatrix[right]
                QuMatrix[right] = quickTemp

                right = right - 1
            else:
                left = left + 1
        else:
            right = right - 1
    
    QuExchange = QuExchange + 1
    quickTemp = QuMatrix[begin]
    QuMatrix[begin] = QuMatrix[right]
    QuMatrix[right] = quickTemp

    QuickSortMathod(begin, (left - 1), QuMatrix)
    QuickSortMathod((right + 1), end, QuMatrix)

# Quickly sorted method
def QuickSort(QuMatrix):
    timeStart = time.time()

    global QuComparision
    global QuExchange
    QuickSortMathod(0, (len(QuMatrix) - 1), QuMatrix)
        
    timeEnd = time.time()
    timeStart = int(round(timeStart * 1000))
    timeEnd = int(round(timeEnd * 1000))
    timeGap = timeEnd - timeStart
    #print("The result of quick sort is:")
    #print(QuMatrix)
    print("Quick comparision number:%d" % QuComparision)
    print("Quick exchange number:%d" % QuExchange)
    print("timeGap:%dms" % timeGap)

    return QuMatrix

########################################################################
def InsertSort(InMatrix):
    timeStart = time.time()
    comparision = 0
    exchange = 0
    rightCnt = 1
    while rightCnt < len(InMatrix):
        comparision = comparision + 1
        if InMatrix[rightCnt] < InMatrix[rightCnt-1]:
            comparision = comparision + 1
            insertValue = InMatrix[rightCnt]
            leftCnt = rightCnt - 1
            while leftCnt > -1 and insertValue < InMatrix[leftCnt]:
                comparision = comparision + 1
                exchange = exchange + 1
                InMatrix[leftCnt+1] = InMatrix[leftCnt] 
                leftCnt = leftCnt - 1
            exchange = exchange + 1
            InMatrix[leftCnt+1] = insertValue

        rightCnt = rightCnt + 1
    
    timeEnd = time.time()
    timeStart = int(round(timeStart * 1000))
    timeEnd = int(round(timeEnd * 1000))
    timeGap = timeEnd - timeStart
    #print("The result of insert sort is:")
    #print(InMatrix)
    print("Insert comparision number:%d" % comparision)
    print("Insert exchange number:%d" % exchange)
    print("timeGap:%dms" % timeGap)

    return InMatrix

########################################################################
def ShellSort(ShMatrix):
    timeStart = time.time()

    comparision = 0
    exchange = 0
    gap = int((len(ShMatrix) / 2))
    
    while gap > 0:
        begin = 0
        # Set each data loop
        while begin < gap:
            rightCnt = begin + gap

            # Sorting of each group of data after separation by gaps
            while rightCnt < len(ShMatrix):
                if ShMatrix[rightCnt] < ShMatrix[rightCnt - gap]:
                    comparision = comparision + 1
                    leftCnt = rightCnt - gap
                    insertValue = ShMatrix[rightCnt]
                    while leftCnt > (begin - gap) and ShMatrix[leftCnt] > insertValue:
                        comparision = comparision + 1
                        ShMatrix[leftCnt + gap] = ShMatrix[leftCnt]
                        exchange = exchange + 1
                        leftCnt = leftCnt - gap
                    ShMatrix[leftCnt + gap] = insertValue

                rightCnt = rightCnt + gap
            begin = begin + 1
        gap = int((gap / 2))

    timeEnd = time.time()
    timeStart = int(round(timeStart * 1000))
    timeEnd = int(round(timeEnd * 1000))
    timeGap = timeEnd - timeStart
    #print("The result of shell sort is:")
    #print(ShMatrix)
    print("Shell comparision number:%d" % comparision)
    print("Shell exchange number:%d" % exchange)
    print("timeGap:%dms" % timeGap)

    return ShMatrix

########################################################################
def BubbleSort(BuMatrix):
    timeStart = time.time()
    comparision = 0
    exchange = 0

    exCnt = 0
    while exCnt < len(BuMatrix):
        inCnt = 0
        while (inCnt + 1) < (len(BuMatrix) - exCnt):
            if BuMatrix[inCnt] > BuMatrix[inCnt+1]:
                exchange = exchange + 1
                BuTemp = BuMatrix[inCnt+1]
                BuMatrix[inCnt+1] = BuMatrix[inCnt]
                BuMatrix[inCnt] = BuTemp
            inCnt= inCnt + 1
            comparision = comparision + 1

        exCnt = exCnt + 1
    
    timeEnd = time.time()
    timeStart = int(round(timeStart * 1000))
    timeEnd = int(round(timeEnd * 1000))
    timeGap = timeEnd - timeStart
    #print("The result of bubble sort is:")
    #print(BuMatrix)
    print("Bubble comparision number:%d" % comparision)
    print("Bubble exchange number:%d" % exchange)
    print("timeGap:%dms" % timeGap)

########################################################################
def HeapSortOne(HeMatrix):
    timeStart = time.time()
    global HeComparision
    global HeExchange
    constructionCnt = 0

    while constructionCnt < len(HeMatrix):
        # Get the first non-leaf node
        begin = (int((len(HeMatrix)-constructionCnt) / 2) - 1)
        HeMatrix = ConstructionHeap(HeMatrix, begin, constructionCnt)
        # Each time a large top pile is constructed, the number of participating structures is reduced next time
        constructionCnt = constructionCnt + 1
        
        HeMatrix = SwapValue(HeMatrix, 0, (len(HeMatrix) - constructionCnt))
    
    timeEnd = time.time()
    timeStart = int(round(timeStart * 1000))
    timeEnd = int(round(timeEnd * 1000))
    timeGap = timeEnd - timeStart
    #print("The result of heap sort is:")
    #print(HeMatrix)
    print("Heap comparision number:%d" % HeComparision)
    print("Heap exchange number:%d" % HeExchange)
    print("timeGap:%dms" % timeGap)
    
    return HeMatrix

# Constructing a Big Top Binary Tree
def ConstructionHeap(HeMatrix, begin, constructionCnt):
    global HeComparision
    global HeExchange
    # Get the starting non-leaf node
    noLeafNodeCnt = begin

    while noLeafNodeCnt >= 0:
        # Determine if there is a left child
        if (noLeafNodeCnt * 2 + 2) < (len(HeMatrix) - constructionCnt):
            if HeMatrix[noLeafNodeCnt*2+1] > HeMatrix[noLeafNodeCnt*2+2]:
                HeMatrix = SwapMax(HeMatrix, noLeafNodeCnt, noLeafNodeCnt*2 + 1)
            else:
                HeMatrix = SwapMax(HeMatrix, noLeafNodeCnt, noLeafNodeCnt*2 + 2)
        else:
            # Compare directly with right child
            HeMatrix = SwapMax(HeMatrix, noLeafNodeCnt, noLeafNodeCnt*2 + 1)
        
        HeComparision = HeComparision + 1
        HeExchange = HeExchange + 1

        noLeafNodeCnt = noLeafNodeCnt - 1

    return HeMatrix

def SwapMax(HeMatrix, large, small):
    if HeMatrix[large] < HeMatrix[small]:
        temp = HeMatrix[large]
        HeMatrix[large] = HeMatrix[small]
        HeMatrix[small] = temp
    return HeMatrix

def SwapValue(HeMatrix, left, right):
    temp = HeMatrix[left]
    HeMatrix[left] = HeMatrix[right]
    HeMatrix[right] = temp

    return HeMatrix


########################################################################
if __name__ == "__main__":
    Matrix = []
    Matrix = RandomInitList(1, 1000, 800)

    SeMatrix = Matrix.copy()
    QuMatrix = Matrix.copy()
    InMatrix = Matrix.copy()
    ShMatrix = Matrix.copy()
    BuMatrix = Matrix.copy()
    HeOneMatrix = Matrix.copy()
    HeTwoMatrix = Matrix.copy()
    
    # Select Sort
    #SelectionSort(SeMatrix)

    # Quick Sort
    QuickSort(QuMatrix)

    # Insert Sort
    #InsertSort(InMatrix)
    
    # Shell Sort
    ShellSort(ShMatrix)

    # Bubble Sort
    #BubbleSort(BuMatrix)

    # Heap Sort
    HeapSortOne(HeOneMatrix)
    #HeapSortTwo(HeTwoMatrix)

C、算法的实用性与适用范围

此部分待更新，我也正在学习中，等理解透彻了，一定不忘分享

谢谢阅读，希望对你有帮助。