排序总结

排序算法的总结(python实现)

冒泡排序

冒泡排序：是一种交换排序，他的基本思想是：两两比较相邻记录的关键字，如果反序则交换，直到没有反序的记录为止。最好的情况下，时间复杂度是n，最坏的时间复杂度时n^2

1
2
3
4
5
6
def Bubble(list):
    for i in range(len(list))[::-1]:
        for j in range(i):
            if list[j]>list[j+1]:
                list[j],list[j+1] = list[j+1],list[j]
    return list

选择排序

选择排序：就是通过n-i次关键字之间的比较，从n-i+1个记录中选出关键字最小的记录，并和第i个记录交换。
时间复杂度分析：最大的特点是交换移动数据的次数相当少，这样就节约了相应的时间，最终的排序时间是比较与交换的时间的和，因此时间复杂度仍然是n^2。
应该说，尽管与冒泡排序同为n^2，但是选择排序的性能上还是要略优于冒泡排序。

1
2
3
4
5
6
7
8
9
def selectSort(list):
    for i in range(len(list)-1):
        min=i
        for j in range(i+1,len(list)):
            if list[min]>list[j]:
                min=j
        if i!=min:
            list[i],list[min] = list[min],list[i]
    return list

快速排序：

算法描述：1、先从序列中取出一个数作为基准；
2、将比它大的放在右边，比基准小的放在左边；
3、再对左右区间重复第二步，直到各区间只有一个数为止。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
   def quikSort(List):
    if len(List)>1:
        qsort(List,0,len(List)-1)

def qsort(List,start,end):
    base=List[start]
    pl=start
    pr=end
    while pl<pr:
        while pl<pr and List[pr]>=base:
            pr-=1
        if pr==pl:
            break
        else:
            List[pl],List[pr]=List[pr],List[pl]
        while pl<pr and List[pl]<=base:
            pl+=1
        if pr==pl:
            break
        else:
            List[pl], List[pr] = List[pr], List[pl]
    if pl-1>start:
        qsort(List,start,pl-1)
    if pr+1<end:
        qsort(List,pr+1,end)

插入排序：

1
2
3
4
5
6
7
8
9
def insertionSort(A, n):
   for i in range(1,n):
       j=i-1
       tmp=A[i]
       while(j>=0 and A[j]>tmp):
           A[j+1]=A[j]
           j-=1
       A[j+1]=tmp
   return A