常见python中排序的代码详解

这篇文章主要为大家详细介绍了python算法的基础教程，具有一定的参考价值，感兴趣的小伙伴们可以参考一下

for (i=1; i<=n; i++)
 x++;
for (i=1; i<=n; i++)
 for (j=1; j<=n; j++)
 x++; 

def bubble(array):
 for i in range(len(array)-1):
 for j in range(len(array)-1-i):
 if array[j] > array[j+1]: # 如果前一个大于后一个，则交换
 temp = array[j]
 array[j] = array[j+1]
 array[j+1] = temp


if __name__ == "__main__":
 array = [265, 494, 302, 160, 370, 219, 247, 287,
 354, 405, 469, 82, 345, 319, 83, 258, 497, 423, 291, 304]
 print("------->排序前<-------")
 print(array)
 bubble(array)
 print("------->排序后<-------")
 print(array) 

def select_sort(array):
 for i in range(len(array)-1): # 找出最小的数放与array[i]交换
 for j in range(i+1, len(array)):
 if array[i] > array[j]:
 temp = array[i]
 array[i] = array[j]
 array[j] = temp


if __name__ == "__main__":
 array = [265, 494, 302, 160, 370, 219, 247, 287,
 354, 405, 469, 82, 345, 319, 83, 258, 497, 423, 291, 304]
 print(array)
 select_sort(array)
 print(array) 

import time


def insertion_sort(array):
 for i in range(1, len(array)): # 对第i个元素进行插入，i前面是已经排序好的元素
 position = i # 要插入数的下标
 current_val = array[position] # 把当前值存下来
 # 如果前一个数大于要插入数，则将前一个数往后移，比如5,8,12,7;要将7插入，先把7保存下来，比较12与7，将12往后移
 while position > 0 and current_val < array[position-1]:
 array[position] = array[position-1]
 position -= 1
 else: # 当position为０或前一个数比待插入还小时
 array[position] = current_val


if __name__ == "__main__":
 array = [92, 77, 67, 8, 6, 84, 55, 85, 43, 67]
 print(array)
 time_start = time.time()
 insertion_sort(array)
 time_end = time.time()
 print("time: %s" % (time_end-time_start))
 print(array) 

def quick_sort(array, left, right):
 '''
 :param array:
 :param left: 列表的第一个索引
 :param right: 列表最后一个元素的索引
 :return:
 '''
 if left >= right:
 return

 low = left
 high = right
 key = array[low] # 第一个值，即基准元素

 while low < high: # 只要左右未遇见
 while low < high and array[high] > key: # 找到列表右边比key大的值 为止
 high -= 1
 # 此时直接 把key跟 比它大的array[high]进行交换
 array[low] = array[high]
 array[high] = key

 while low < high and array[low] <= key: # 找到key左边比key大的值，这里为何是<=而不是<呢？你要思考。。。
 low += 1
 # 找到了左边比k大的值 ,把array[high](此时应该刚存成了key) 跟这个比key大的array[low]进行调换
 array[high] = array[low]
 array[low] = key

 quick_sort(array, left, low-1) # 最后用同样的方式对分出来的左边的小组进行同上的做法
 quick_sort(array,low+1, right) # 用同样的方式对分出来的右边的小组进行同上的做法


if __name__ == '__main__':
 array = [8,4,1, 14, 6, 2, 3, 9,5, 13, 7,1, 8,10, 12]
 print("-------排序前-------")
 print(array)
 quick_sort(array, 0, len(array)-1)
 print("-------排序后-------")
 print(array) 

输出:

-------排序前-------
[8, 4, 1, 14, 6, 2, 3, 9, 5, 13, 7, 1, 8, 10, 12]
-------排序后-------
[1, 1, 2, 3, 4, 5, 6, 7, 8, 8, 9, 10, 12, 13, 14]

22行那里如果不加＝号， 当排序64，77，64是会死循环，此时key=64,　最后的64与开始的64交换，开始的64与本最后的64交换……　无穷无尽

直接插入排序复杂度:

时间复杂度: 最好情况O(nlogn), 最坏情况O(n^2), 平均情况O(nlogn)

下面空间复杂度是看别人博客的，我也不大懂了……改天再研究下。

最优的情况下空间复杂度为： O(logn)；每一次都平分数组的情况

最差的情况下空间复杂度为： O( n )；退化为冒泡排序的情况

稳定性: 不稳定

快速排序效果：

以上就是常见python中排序的代码详解的详细内容，更多请关注Gxl网其它相关文章！

查看更多关于常见python中排序的代码详解的详细内容...