python排序(冒泡、直接选择、直接插入等)

冒泡排序

冒泡法：第一趟：相邻的两数相比，大的往下沉。最后一个元素是最大的。

第二趟：相邻的两数相比，大的往下沉。最后一个元素不用比。

 #冒泡排序

 array = [1,5,6,2,9,4,3]

 def bubble_sort(array):

     for i in range(len(array)-1):

         for j in range(len(array)-i-1):

             if array[j] > array[j+1]:

                 array[j],array[j+1] = array[j+1],array[j]

     return array

 bubble = bubble_sort(array)

 print(bubble)

时间复杂度：O(n^2)

稳定性：稳定

改进：如果一趟比较没有发生位置变换，则认为排序完成

 array = [1,2,3,5,7]

 def bubble_sort(array):

     for i in range(len(array)-1):

         flag = 1   #建立标志位

         for j in range(len(array)-i-1):

             if array[j] > array[j+1]:

                 array[j],array[j+1] = array[j+1],array[j]

                 flag = 0

         if not flag:

             break

     return array

 bubble = bubble_sort(array)

 print(bubble)

直接选择排序

选择排序法：每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放到序列的起始位置，直到全部排完。

 def select_sort(array):

     for i in range(len(array)-1):

         min = i

         for j in range(i+1, len(array)):

             if array[j] < array[min]:

                 min = j

         array[i], array[min] = array[min], array[i]

     return array

 array = [1,5,6,2,9,4,3]

 select = select_sort(array)

 print(select)

直接插入排序

列表被分为有序区和无序区两个部分。最初有序区只有一个元素。
每次从无序区选择一个元素，插入到有序区的位置，直到无序区变空。
其实就相当于摸牌：

 def insert_sort(array):

     # 循环的是第二个到最后（待摸的牌）

     for i in range(1, len(array)):

         # 待插入的数（摸上来的牌）

         min = array[i]

         # 已排好序的最右边一个元素（手里的牌的最右边）

         j = i - 1

         # 一只和排好的牌比较，排好的牌的牌的索引必须大于等于0

         # 比较过程中，如果手里的比摸上来的大，

         while j >= 0 and array[j] < min:

             # 那么手里的牌往右边移动一位，就是把j付给j+1

             array[j+1] = array[j]

             # 换完以后在和下一张比较

             j -= 1

         # 找到了手里的牌比摸上来的牌小或等于的时候，就把摸上来的放到它右边

         else:array[j+1] = min

     return array

 list=[5,6,1,2,8,3,4]

 print(insert_sort(list))

巴特西

python排序(冒泡、直接选择、直接插入等)

最新文章

热门文章