[Python知识库]python实现选择排序、冒泡排序、快速排序

一、选择排序
思想：从头至尾顺序扫描序列，找出最小的元素，和第一个元素进行交换， 接着从剩下的元素中继续这种选择和交换，直至最终数组有序。

def SelectSort(list):
    for i in range(0,len(list)): #第一趟循环排出有序数列
        # 设置最小值的索引值
        min = i
        for j in range(i+1,len(list)):#第二趟排序让min去和无序数列的数作比较找出真正最小值
            if list[min] > list[j]:
                min = j
        list[min],list[i] = list[i],list[min]
    return list

print(SelectSort([10,9,3,2,7,5,65]))

二、冒泡排序
思想：重复遍历要排序的数列，每次比较两个位置的元素，如果不符合排序规则，则交换两个位置的元素，一直遍历到没有需要交换的元素后，排序才算完成。

def bubble_sort(list):
    for i in range(len(list)-1):
        for j in range(len(list)-1-i):
            if list[j] > list[j+1]:
                list[j],list[j+1] = list[j+1],list[j]
    return list
print(bubble_sort([10,9,3,2,7,5,65]))

三、快速排序
思想：快速排序使用分而治之的思想，通过一趟排序将待排序列分割成两部分， 其中一部分记录的关键字均比另一部分记录的关键字小。之后分别对这两部分记录继续进行排序，以达到整个序列有序的目的。

def QuickSort(arr):
    if len(arr) < 2:
        return arr
    else:
        left = []
        right = []
        # 基准数
        prov = arr[0]
        for i in range(1,len(arr)):
            if arr[i] < prov:
                right.append(arr[i])
            else:
                left.append(arr[i])
        right = QuickSort(right)
        left = QuickSort(left)
        return  right+[prov]+left
print(QuickSort([10,9,3,2,7,5,65]))