排序

排序是指将数据按照一定顺序排列起来的一种算法。以下逐个介绍。

一、冒泡排序

冒泡排序是将列表之间的元素依次两两比较，大的调换位置至右边。第一次两两比较时一定会将最大的元素放在最右边，故第二次遍历只需遍历n-1次。

def bubble_sort(urlist):
	#所需遍历的次数
    for j in range(len(urlist) - 1, 0, -1):
    	#两两互相比较
        for i in range(j):
            if urlist[i] > urlist[i + 1]:
            	#借助中间变量互换位置
                m = urlist[i + 1]
                urlist[i + 1] = urlist[i]
                urlist[i] = m
    print(urlist)


li = [54, 26, 93, 17, 77, 31, 44, 55, 20]
bubble_sort(li)

二、选择排序

选择排序的主要思想是，首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上，则它不会被移动。选择排序每次交换一对元素，它们当中至少有一个将被移到其最终位置上，因此对n个元素的表进行排序总共进行至多n-1次交换。在所有的完全依靠交换去移动元素的排序方法中，选择排序属于非常好的一种。

# 1.选出列表中最小的数值，将其放在最小的索引上
def choose_sort(urlist):
    n = len(urlist)
    for i in range(n - 1):  # 要循环的次数，最小的元素确定位置后 不必再循环
        min_index = i  # 确定最小位置索引
        for j in range(i, n):  # 从最小位置遍历至表尾
            if urlist[j] < urlist[min_index]:
                min_index = j
        if min_index != i:
            m = urlist[min_index]
            urlist[min_index] = urlist[i]
            urlist[i] = m
    print(urlist)


urlist = [54, 226, 93, 17, 77, 31, 44, 55, 20]
choose_sort(urlist)

# 2.选出列表中最大的数值，将其放在最大的索引上
def big_sort(alist):
    n = len(alist)
    for i in range(n - 1, 0, -1):  # 从表尾遍历至表头
        max_index = i  # 确定最右边的位置
        for j in range(i, -1, -1):  # 从最右边的位置往左遍历
            if alist[j] > alist[max_index]:  # 寻找最大值
                max_index = j
        if max_index != i:
            alist[i], alist[max_index] = alist[max_index], alist[i]  # 交换位置
    print(alist)


urlist = [54, 226, 93, 17, 77, 31, 44, 55, 20]
big_sort(urlist)

三、插入排序

它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

# 插入排序
# 从列表第二个位置开始，逐个往前比较，符合条件则调换位置。
def insert_sort(alist):
    n=len(alist)
    for i in range(1,n):
        for j in range(i,0,-1):# 与自己的前一个位置比较 后面有j-1，故此处位置0不必包含
            if alist[j]<alist[j-1]:
                alist[j],alist[j-1]=alist[j-1],alist[j] #调换位置
    print(alist)
urlist = [54, 226, 93, 17, 77, 31, 44, 55, 20]
insert_sort(urlist)

四、快速排序

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
步骤为：

1.从数列中挑出一个元素，称为"基准"（pivot），
2.重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
3.递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递归下去，但是这个算法总会结束，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。

# 快速排序
def quick_sort(alist, start, end):
    """快速排序"""
    # 递归推出条件
    if start >= end:
        return
    # 设定起始元素为要寻找位置的基准元素
    mid = alist[start]
    # low为序列左边的由左向右移动的游标
    low = start
    # high为序列右边的由右向左移动的游标
    high = end
    while low < high:
        # 如果low与high未重合，high指向的元素不比基准元素小，则high向左移动
        while low < high and alist[high] >= mid:
            high -= 1
        alist[low] = alist[high]
        # 如果low与high未重合，low指向的元素比基准元素小，则low向右移动
        while low < high and alist[low] < mid:
            low += 1
        alist[high] = alist[low]

    alist[low] = mid
    # 对基准元素左边的子序列进行快速排序
    quick_sort(alist, start, low - 1)
    # 对基准元素右边的子序列进行快速排序
    quick_sort(alist, low + 1, end)


alist = [54, 26, 93, 17, 77, 31, 44, 55, 20]
quick_sort(alist, 0, len(alist) - 1)
print(alist)