python：实现几种排序算法

冒泡排序

比较相邻两个字符，如果左边大于右边，则交换位置，遍历一遍字符后，则最大的肯定在最右边；继续循环处理剩下的字符（最右边的不用再比较了，已经最大了）

代码实现：

def BubbleSort(sourceStr):

    l = list(sourceStr)

    cnt = len(l)-1

    while cnt >= 0:

        i = 0

        j = 0

        while i < cnt:

            j = i + 1

            if l[i] > l[j]:

                tmp = l[j]

                l[j] = l[i]

                l[i] = tmp

            i+=1

        cnt-=1

    return ''.join(l)

if __name__ == '__main__':

    myStr = ''

    print(' Before Sort: %s \n After  Sort: %s' %(myStr,BubbleSort(myStr)) )

执行结果：

C:\Users\suneee\AppData\Local\Programs\Python\Python36\python.exe E:/wangjz/PyWorkSpace/LearnPython/test_order.py

 Before Sort: 125694520

 After  Sort: 012245569

Process finished with exit code 0

选择排序

每次从字符串中选择最小的值，放到新的列表中，选完一个，原字符串就去掉最小的那个；直到选完，新的列表也组成了

代码实现：

def SelectSort(sourceStr):

    oldList = list(sourceStr)

    newList = []

    maxStr = ''

    while oldList!=[]:

        maxStr = min(oldList)

        newList.append(maxStr)

        oldList.remove(maxStr)

    return ''.join(newList)

if __name__ == '__main__':

    myStr = ''

    # print(' Before Sort: %s \n After  Sort: %s' %(myStr,BubbleSort(myStr)) )

    print(' Before Sort: %s \n After  Sort: %s' %(myStr,SelectSort(myStr)) )

执行结果：

C:\Users\suneee\AppData\Local\Programs\Python\Python36\python.exe E:/wangjz/PyWorkSpace/LearnPython/test_order.py

 Before Sort: 125694520

 After  Sort: 012245569

Process finished with exit code 0

插入排序

选定第一个元素作为已排序的数列（假设为Arr），判断下一个元素，与Arr中元素从后往前比较，如果比某个元素大，则插入到该元素之后（Arr元素相应增加）；如果比Arr中的元素都小，则插入至最开始位置（Arr元素相应增加）

代码实现：

def InserSort(sourceStr):

    l = list(sourceStr)

    cnt = len(l)

    iCur = 1

    while iCur < cnt :

        i = iCur-1

        while i >= 0:

            iFlg = False

            if l[iCur] >= l[i]:

                iFlg = True

                l.insert(i + 1,l[iCur])

                l.pop(iCur+1)

                break

            i -= 1

        if iFlg == False :

            l.insert(0,l[iCur])

            l.pop(iCur+1)

        iCur += 1

    return ''.join(l)

if __name__ == '__main__':

    myStr = ''

    # print(' Before Sort: %s \n After  Sort: %s' %(myStr,BubbleSort(myStr)) )

    # print(' Before Sort: %s \n After  Sort: %s' %(myStr,SelectSort(myStr)) )

    print(' Before Sort: %s \n After  Sort: %s' %(myStr,InserSort(myStr)) )

执行结果：

C:\Users\suneee\AppData\Local\Programs\Python\Python36\python.exe E:/wangjz/PyWorkSpace/LearnPython/test_order.py

 Before Sort: 125694520

 After  Sort: 012245569

Process finished with exit code 0

快速排序

一种特殊的冒泡排序。一个数列，假如取首数字为基准值，则从最右边（下标为right）往左寻找，直至找到一个比基准值小的数，交换位置；从最左边（下标为left）+1的位置往右寻找，直至找到一个大于基准值的数，再次交换位置；循环往复，直至left等于right，则一次分区完成（基准值左边都比他小，右边都比他大）。然后进行递归，对左边和右边依次继续分区，直至分区长度为1。

代码实现：

def division(l,left,right):

    while left < right:

        while left < right and l[right] >= l[left]:

            right -= 1

        if left < right:

            tmp = l[left]

            l[left] = l[right]

            l[right] = tmp

            left += 1

        while left < right and l[left] <= l[right]:

            left += 1

        if left < right:

            tmp = l[left]

            l[left] = l[right]

            l[right] = tmp

            right -= 1

        return left

def fast_sort(l,left,right):

    if left < right:

        pivot = division(l, left, right)

        fast_sort(l,left,pivot-1)

        fast_sort(l,pivot+1,right)

    return l

if __name__ == '__main__':

    l = [71,6,0,25,2,99,-1]

    print(fast_sort(l,0,l.__len__()-1))

执行结果：

E:\kusy\python\venv\Scripts\python.exe E:/kusy/python/testSort.py

[-1, 0, 2, 6, 25, 71, 99]

Process finished with exit code 0

巴特西

python：实现几种排序算法

冒泡排序

选择排序

插入排序

快速排序

最新文章

热门文章