[python实现算法一：冒泡排序]2018-12-03

概述

野路子

八大排序之基本概念简介

分类

一、按照是否数据涉及内外存交换

1-内部排序：适用于记录个数不是很多的小文件

2-外部排序：适用于记录个数太多，不能一次将全部记录放入内存的大文件

二、按照策略划分内部排序方法

1-插入排序：直接插入排序与希尔排序

2-选择排序：直接选择排序与堆排序

3-交换排序：冒泡排序与快速排序

4-归并排序

5-分配排序

  冒泡排序是交换排序的一种；交换排序还包括快速排序。

基本思想

  在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。

冒泡排序的示例：

# -*- coding:utf-8 -*-
# tao.zhang
# 2018.12.03
def bubbleSort(array):

    length=len(array)

    for i in xrange(length-1):    #决定比几次（行）

        for j in xrange(length-1-i):    #怎么比
            if array[j]>array[j+1]:
                array[j],array[j+1]=array[j+1],array[j]

    print array

if __name__=="__main__":

    array=[87,9,23,6,0,76,11,-9,32]
    bubbleSort(array=array)

改进

  传统冒泡排序中每一趟排序操作只能找到一个最大值或最小值,我们考虑利用在每趟排序中进行正向和反向两遍冒泡的方法一次可以得到两个最终值(最大者和最小者) , 从而使排序趟数几乎减少了一半。

改进后的算法实现为:

# -*- coding:utf-8 -*-
# tao.zhang
# 2018.12.03
def bubbleSort(array):

    length=len(array)
    low=0
    heigh=length-1
    while low<=heigh:

        for i in xrange(heigh):
            for j in xrange(heigh):
                if array[j]>array[j+1]:
                    array[j],array[j+1]=array[j+1],array[j]
            heigh-=1
            #print 'heigh--print,heigh--', heigh
            #print array
            for n in reversed(xrange(1,heigh+1)):
                #print n
                if array[n]<array[n-1]:
                    array[n],array[n-1]=array[n-1],array[n]
            low+=1
    print array

if __name__=="__main__":

    array=[5,7,3,9,1,-9]
    bubbleSort(array=array)