Python实现基本排序算法

一、Python实现基本排序算法

1.冒泡排序

基本思想：
比较相邻的两个数据，如果第二个数小，就交换位置。
从后向前两两比较，一直到比较最前两个数据。最终最小数被交换到起始的位置，这样第一个最小数的位置就排好了。
继续重复上述过程，依次将第2.3…n-1个最小数排好位置。

Python代码实现如下

import random
alist=list(range(20))
random.shuffle(alist)
print("打乱后的列表：",alist)

def bubbleSort01(alist):
    for i in range(len(alist)-1,0,-1):
        for j in range(i):
            if alist[j]>alist[j+1]:
                alist[j],alist[j+1]=alist[j+1],alist[j]
                
def bubbleSort02(alist):
    for i in range(len(alist)-1):
        for j in  range(len(alist)-i-1):
            if alist[j]>alist[j+1]:
                alist[j],alist[j+1]=alist[j+1],alist[j]
                
bubbleSort01(alist)
print("冒泡01排序：",alist)

random.shuffle(alist)
print("打乱后的列表：",alist)
bubbleSort02(alist)
print("冒泡02排序：",alist)

2.选择排序

基本思想：
在长度为N的无序数组中，第一次遍历n-1个数，找到最小的数值与第一个元素交换；
第二次遍历n-2个数，找到最小的数值与第二个元素交换；
…
第n-1次遍历，找到最小的数值与第n-1个元素交换，排序完成。

Python代码实现如下

import random
alist=list(range(20))
random.shuffle(alist)
print("打乱后的列表：",alist)

def select_sort(alist):
    for i in range(len(alist)):
        for j in range(i+1,len(alist)):
            if alist[i]>alist[j]:
                alist[i],alist[j]=alist[j],alist[i]
                
select_sort(alist)
print("选择排序：",alist)

3.插入排序

基本思想：
在要排序的一组数中，假定前n-1个数已经排好序，现在将第n个数插到前面的有序数列中，使得这n个数也是排好顺序的。如此反复循环，直到全部排好顺序。

Python代码实现如下

import random
alist=list(range(20))
random.shuffle(alist)
print("打乱后的列表：",alist)

def insertionSort(alist): 
    for i in range(1,len(alist)):
        key = alist[i] 
        j=i-1
        while j>=0 and  alist[j]>key:
            alist[j+1]=alist[j]
            j -= 1
        alist[j+1]=key

insertionSort(alist)
print("插入排序：",alist)

4.shell(希尔)排序

基本思想：
在要排序的一组数中，根据某一增量分为若干子序列，并对子序列分别进行插入排序。
然后逐渐将增量减小,并重复上述过程。直至增量为1,此时数据序列基本有序,最后进行插入排序。

Python代码实现如下

import random
alist=list(range(20))
random.shuffle(alist)
print("打乱后的列表：",alist)

def shell_insertSort(alist,dk):
    n=len(alist)
    for k in range(dk):
        for i in range(k+dk,n,dk):
            key = alist[i] 
            j=i-dk
            while j>=k and  alist[j]>key:
                alist[j+dk]=alist[j]
                j -= dk
            alist[j+dk]=key



def shell_sort(alist):
    n=len(alist)
    dk=n//2  #间隔
    while dk>0:
        shell_insertSort(alist,dk)
        dk=dk//2

 
shell_sort(alist)
print("shell排序：",alist)

5.归并排序

基本思想：
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法的一个非常典型的应用。
首先考虑下如何将2个有序数列合并。这个非常简单，只要从比较2个数列的第一个数，谁小就先取谁，取了后就在对应数列中删除这个数。然后再进行比较，如果有数列为空，那直接将另一个数列的数据依次取出即可。

Python代码实现如下

import random
alist=list(range(20))
random.shuffle(alist)
print("打乱后的列表：",alist)

#合并两个集合
def merage(x,y):
    c=[]
    h=j=0  #h ,j 分别是用来指  x,y的索引
    if x==None:
        return y
    if y==None:
        return x
    while j<len(x) and h<len(y):
        if x[j]<y[h]:
            c.append(x[j])
            j+=1
        else:
            c.append(y[h])
            h+=1
    if j==len(x):
        for i in y[h:]:
            c.append(i)
    else:
        for i in x[j:]:
            c.append(i )
    return c

def merage_sort(x):
    if len(x)<=1:
        return x
    middle=len(x)//2
    left=merage_sort(x[middle:])
    right=merage_sort(x[:middle])
    return merage(left,right)
    
alist=merage_sort(alist)                
print("归并排序",alist)

6.快速排序

基本思想：
快速排序使用分治法策略来把一个序列分为较小和较大的2个子序列，然后递归地排序两个子序列。
步骤为：

挑选基准值：从数列中挑出一个元素，称为”基准”（pivot）;
分割：重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（与基准值相等的数可以到任何一边）。在这个分割结束之后，对基准值的排序就已经完成;
递归排序子序列：递归地将小于基准值元素的子序列和大于基准值元素的子序列排序。

递归到最底部的判断条件是数列的大小是零或一，此时该数列显然已经有序。
选取基准值有数种具体方法，此选取方法对排序的时间性能有决定性影响。

Python代码实现如下

import random
alist=list(range(20))
random.shuffle(alist)
print("打乱后的列表：",alist)

def quicksort(x):
    if len(x)<=1:
        return x
    base=x[0]
    left=[ i  for i in x[1:] if i<base ]
    right=[ i  for i in x[1:] if i>base ]
    middle=[ i  for i in x if i==base ]
    return  quicksort(left)+middle+quicksort(right)

alist=quicksort(alist)                
print("快速排序",alist)