排序算法

冒泡排序

简单的说就是两个数依次比较,比如一个list[1,5,3,2],我们对它做升序排序，过程如下

第一次循环：

比较	处理	结果
1 < 5	无需处理	[1，5，3，2]
5 > 3	3和5交换位置	[1，3，5，2]
5 > 2	5和2交换位置	[1，3，2，5]

第二次循环(由于5最大已经被挑了出来，5可以不用处理了)：

比较	处理	结果
1 < 3	无需处理	[1，3，2，5]
3 > 2	3和2交换位置	[1，2，3，5]

第三次循环(由于3，5最大已经被挑了出来，3，5可以不用处理了)：

比较	处理	结果
1 < 2	无需处理	[1，2，3，5]

至此，排序完成，当然可以发现，最后一次的结果和前一次的结果一致，可以优化，这里暂时不作处理，只是做原理解释

python代码如下

def bubble(unSortList):
    length = len(unSortList)
    for i in range(length - 1):
        print(i)
        for j in range(length - 1 - i):
            if unSortList[j] > unSortList[j + 1]:
                unSortList[j], unSortList[j + 1] = unSortList[j + 1], unSortList[j]
            print(unSortList)
    return unSortList

选择排序

搜索整个列表，并将最小的数字传递到列表的最前，一次循环只做一次交换位置，还是拿前面的list[1,5,3,2]做为例子

第一次循环(取第一个元素1作为比较对象)：

比较	处理	结果
1 < 5	无需处理	[1，5，3，2]
1 < 3	无需处理	[1，5，3，2]
1 < 2	无需处理	[1，5，3，2]

第二次循环(由于最小的数1已经被挑了出来，1可以不用处理了，此时取5作为比较对象)：

比较	处理	结果
5 > 3	3此时为最小比较对象，但是不交换位置	[1，5，3，2]
3 > 2	2最小，但是循环完成了，5和2交换位置	[1，2，3，5]

第三次循环(1，2最小已经被挑了出来，1，2可以不用处理了，此时取3作为比较对象)：

比较	处理	结果
3 < 5	无需处理	[1，2，3，5]

python代码如下

def choose(unSortList):
    length = len(unSortList)
    for i in range(length - 1):
        minIndex = i
        for j in range(i + 1, length):
            if unSortList[minIndex] > unSortList[j]:
                minIndex = j
        unSortList[i], unSortList[minIndex] = unSortList[minIndex], unSortList[i]
        print(unSortList)
    return unSortList

快速排序

将要排序的数据分割成独立的三部分,其中一部分比基准数据小(less_than []),一部分相等(equal [])，还有一部分比基准数据大(more_than [])，然后再按此方法对这大小两部分数据分别进行相同的处理,直到每部分只有一个元素为止，这次以list[5,1,7,3,8]做为例子

取第一个元素5作为基准数据：

分割处理	分割处理	分割处理
less_than [1,3]	equal [5]	more_than [7，8]
取 1 作为基准数据	equal [5]	取 7 作为基准数据
less_than [] ,equal[1] ,more_than[3]	equal [5]	less_than [] ,equal[7] ,more_than[8]

python代码如下

def quick(unSortList):
    less_than = []
    more_than = []
    equal = []
    if len(unSortList) <= 1:
        return unSortList
    else:
        base = unSortList[0]
        for num in unSortList:
            if num > base:
                more_than.append(num)
            elif num < base:
                less_than.append(num)
            else:
                equal.append(num)
        less_than = quick(less_than)
        more_than = quick(more_than)
        return less_than + equal + more_than