对10个数进⾏排序python_⼗⼤排序算法（python实现）
⼗⼤排序算法(python)
在计算机编程时，我们经常需要对⼀系列数进⾏排序，在这⾥，我将列出⼗种不同的排序算法，给出它们的python代码，并计算出它们的时间复杂度。
0排序算法说明
0.1排序的定义
对⼀序列对象根据某个关键字进⾏排序。
0.2 术语说明
稳定 ：如果a原本在b前⾯，⽽a=b，排序之后a仍然在b的前⾯；
不稳定 ：如果a原本在b的前⾯，⽽a=b，排序之后a可能会出现在b的后⾯；
内排序 ：所有排序操作都在内存中完成；
外排序 ：由于数据太⼤，因此把数据放在磁盘中，⽽排序通过磁盘和内存的数据传输才能进⾏；
时间复杂度 ： ⼀个算法执⾏所耗费的时间。
空间复杂度 ：运⾏完⼀个程序所需内存的⼤⼩。
0.3 算法总结
名词解释：
· n: 数据规模
· k: “桶”的个数
· In-place: 占⽤常数内存，不占⽤额外内存
· Out-place: 占⽤额外内存1
0.4算法分类
Figure 1注：我使⽤的shell排序是交换排序，当然也可以⽤插⼊排序
0.5⽐较和⾮⽐较的区别
常见的快速排序、归并排序、堆排序、冒泡排序 等属于⽐较排序 。在排序的最终结果⾥，元素之间的次序依赖于它们之间的⽐较。每个数都必须和其他数进⾏⽐较，才能确定⾃⼰的位置 。
在冒泡排序之类的排序中，问题规模为n，⼜因为需要⽐较n次，所以平均时间复杂度为O(n²)。在归并排序、快速排序之类的排序中，问题规模通过分治法消减为logN次，所以时间复杂度平均O(nlogn)。
⽐较排序的优势是，适⽤于各种规模的数据，也不在乎数据的分布，都能进⾏排序。可以说，⽐较排序适⽤于⼀切需要排序的情况。
计数排序、基数排序、桶排序则属于⾮⽐较排序 。⾮⽐较排序是通过确定每个元素之前，应该有多少个元素来排序。针对数组arr，计算arr[i]之前有多少个元素，则唯⼀确定了arr[i]在排序后数组中的位置 。
⾮⽐较排序只要确定每个元素之前的已有的元素个数即可，所有⼀次遍历即可解决。算法时间复杂度O(n)。
⾮⽐较排序时间复杂度底，但由于⾮⽐较排序需要占⽤空间来确定唯⼀位置。所以对数据规模和数据分布有⼀定的要求。[1]
1冒泡排序(bubble sort)
冒泡排序通过重复⾛访要排序的数列，依次⽐较数列中相邻的两个数，如果逆序，则将这两个数交换，变为顺序。算法终⽌的条件是对数列中的任意两个数我们都不可交换它们的位置，也就是数列中所有数都为顺序。在操作n次之后，整个数列将按从⼩到⼤的顺序排列。在每⼀次操作中，我们需要⽐较O(n)次，共执⾏n次，算法的时间复杂度为O(n^2)。
算法描述：从第⼀个数开始，依次⽐较相邻两个数，如果第⼀个数⼤于第⼆个数，则交换它们之间的位置。在经过⼀轮操作后，最⼤的数将被移动到数列最右端。我们继续对剩下的n-1个数进⾏操作，从⽽可以将这n-1个数中最⼤的数移动到剩下的数最右端。重复进⾏，直到遍历完整个数列，算法终⽌。
def bubble_sort(n):
'''冒泡排序对列表进⾏排序，并返回⼀个排序好的列表:param n: 列表对象:return: 排序结果列表'''
i=len(n)
while i > 1:
j=0
while j < i-1:
if n[j]<=n[j+1]:
j+=1
else:
n[j],n[j+1]=n[j+1],n[j]#不是正序则交换两数
j+=1
i-=1
return n
2选择排序(selection sort)
选择排序是从未排序数列中选择最⼩的数，存放到排序数列中的起始位置，然后再选出第⼆⼩的数，附在已排序数列的最后。这样我们就可以将数列从⼩到⼤地进⾏排序。算法终⽌的条件是遍历完原数列。我们每次操作需要在原数列中⽐较O(n)次，共执⾏n次，算法的时间复杂度为O(n^2)。
算法描述：我们从原数列中选出最⼩的数，将其导出(pop，缩短原列表长度，可以减少运算时间)，并
将其返回到⼀个新数列中。重复操作，直到原数列中不含元素，算法终⽌。
def selection_sort(n):
快速排序python实现
'''选择排序
对列表进⾏排序，并返回⼀个排序好的列表
:param n: 列表对象
:return: 排序结果列表
'''
s=[]#输出列表
i=0
while i < len(n):
min_num=n[i]
for j in range(i,len(n)):
if n[j]
min_num=n[j]
s.append(min_num)
return s
3插⼊排序(insertion sort)
插⼊排序是先构建⼀个有序数列，然后从⽆序数列中选出⼀个数，将其插⼊到有序数列对应位置中。插⼊时需要⽐较O(n)次，共需操作n 次，算法的时间复杂度为O(n^2)
算法描述：选出原数列第⼀个元素作为有序数列的起始，然后从原数列中选出下⼀个数，将所选出的数从后向前与有序数列中的数进⾏⽐较，若⼩于则与有序数列中的前⼀个数进⾏⽐较，直到选出的数⼤于有序数列中的某个数，此时我们将选出的数插⼊到有序数列的中的那个数之后。依次遍历整个原数列，遍历结束，算法终⽌。
def insertion_sort(n):
'''插⼊排序
对列表进⾏排序，并返回⼀个排序好的列表
:param n: 列表对象
:return: 排序结果列表
'''
s=[n[0]]
i=1
while i < len(n):
j=-1
if n[i]>=s[j]:
s.append(n[i])
elif n[i]<=s[0]:
s.insert(0,n[i])
else:
while n[i] < s[j]:
if n[i] >= s[j-1]:
s.insert(j,n[i])
j-=1
i+=1
return s
4希尔排序(shell sort)
希尔排序是通过将原数列进⾏多次分组，在每⼀组内部进⾏排序。它会优先⽐较距离⽐较远的元素，从⽽可以使操作次数⼤幅下降。希尔排序是对原数列按⼀定增量分组，对每组进⾏排序；随着增量逐渐减少，每组包含的数越来越多，当增量减⾄1时，整个⽂件恰被分成⼀组，算法终⽌。每次操作需要⽐较n次共需操作 次，算法的时间复杂度为O(nlogn)。
算法描述：我们先选择增量gap=len(n)//2，每次操作后依次后缩⼩增量为gap=gap//2，直到gap=1。然后我们根据增量对原数列进⾏分组，在每组内部使⽤冒泡排序算法进⾏排序(也可以使⽤插⼊排序算法，插⼊排序算法更快)。当增量为1时，程序进⾏最后⼀次操作，之后算法终⽌。
def shell_sort(n):
'''希尔排序
对列表进⾏排序，并返回⼀个排序好的列表
:param n: 列表对象
:return: 排序结果列表
'''
gap=len(n)//2#间距
while gap > 0:
for i in range(gap,len(n)):
j=i
while j>=gap:
if n[j] < n[j-gap]:
n[j],n[j-gap]=n[j-gap],n[j]
j-=gap
else:
break
gap=gap//2
return n
5归并排序(merge sort)
归并排序是建⽴在归并操作上的⼀种有效的排序算法。该算法是采⽤分治法，将原数列进⾏分组，分为左右两个数列，然后继续对左右两个数列进⾏分组，直到每组所含元素为1。然后对每个⼦序列进⾏排序，将有序的⼦数列合并，然后继续排序，直到得到完全有序的原数列。即先使每个⼦序列有序，再使⼦序列段间有序，最终返回⼀个完全有序的数列。分组需要操作 次，每次操作排序需要n次，算法时间复杂度为O(nlogn)
算法描述：将原数列进⾏分组，分为左右两个数列，然后继续对左右两个数列分别采⽤归并排序。最后将两个排序好的⼦序列合并成⼀个最终的排序序列 。算法终⽌，直到递归结束。
def merge_sort(n):
'''归并排序
对列表进⾏排序，并返回⼀个排序好的列表
:param n: 列表对象
:return: 排序结果列表
'''
if len(n)==1:
return n
mid=len(n)//2
left=merge_sort(n[:mid])
right=merge_sort(n[mid:])
s=[]#输出列表
while left and right:
if left[0]
s.append(left.pop(0))
else:
s.append(right.pop(0))
if left:
if right:
return s
6快速排序(quick sort)
快速排序是通过先选出⼀个数，将所有⼩于等于它的数放到它的左边，将所有⼤于等于它的数放到它的右边。重复操作直到数列有序。我们发现在⼀次操作后就确定了⼀个数的位置，每次操作需要⽐较O(n)次，需要操作 次(以每个递归循环为参考对象)，算法时间复杂度为
O(nlogn)
算法描述：以某个数为参考对象将⼀个数列分为左右两个部分，然后从数列左边开始查，直到到⼀个⼤于该数的数，记录它的位置为左标，再从数列右边开始查，直到到⼀个⼩于该数的数，记录它的位置为右标，将左右标数互换。继续执⾏算法，直到左右标相遇，最后将该数与左标数互换，此时该数满⾜：数列中所有⼩于等于它的数在它的左边，所有⼤于等于它的数在它的右边，该次算法结束。我们再对左右两个数列分别进⾏快速排序。算法完全终⽌，直到每个数列所含元素个数为1个，最后返回⼀个有序的数列。
def quick_sort(n,l,r):#l:left,r:right
'''快速排序
对列表进⾏排序，并返回⼀个排序好的列表
:param n: 列表对象
:return: 排序结果列表
'''
if l>=r:
return n
i,j=l,r
while True:
while l<=r and n[l]
l+=1
while l<=r and n[r]>=n[i]:
r-=1
if l>r:
break
n[l],n[r]=n[r],n[l]

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。