Python常用排序算法

1.冒泡排序

思路:将左右元素两两相比较，将值小的放在列表的头部，值大的放到列表的尾部

效率:O(n²)

 def bubble_sort(li):

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

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

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

                 li[j],li[j+1] = li[j+1],li[j]

2.选择排序

思路:遍历列表，挑出一个最小的数字，放到列表的第一个索引位。在一趟遍历剩余列表中的最小数，继续放置。

效率:O(n²)

 def select_sort(li):

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

         mim_loc = i

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

             if li[j] < li[mim_loc]:

                 mim_loc = j

         if mim_loc != i:

             li[i],li[mim_loc] = li[mim_loc],li[i]

3.插入排序

思路：列表分为有序区和无序区两个部分，最初有序区只有一个元素。每次从无序区选择一个元素，插入到有序区的位置，直到无序区变空

效率:O(n²)

 def insert_sort(li):

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

         tmp = li[i]

         j = i - 1

         while j >= 0 and tmp < li[j]:

             li[j+1] = li[j]

             j= j-1

         li[j+1] = tmp

4.快速排序

思路:取一个元素P,使元素P归位,列表被P分为两个部分,左边的比P小,右边比P大,递归完成排序。

效率:O(nlogn)

 def quick_sort(li,left,right):

     if left < right:

         mid = partition(li,left,right)

         quick_sort(li,left,mid-1)

         quick_sort(li,mid+1,right)

 def partition(li,left,right):

     tmp = li[left] #随机取出一个数

     while left < right:

 　　　　 #如果遇到比tmp大的数,右指针向左移动,否则将右边的值放到左边

         while left < right and li[right] >= tmp:

             right -= 1

         li[left] = li[right]

 　　　　 #如果遇到比tmp小的数,左指针向右移动,否则将左边的值放到右边　

         while left < right and li[left] <= tmp:

             left += 1

         li[right] = li[left]

     li[left] = tmp #将原先的数回填

     return left

5.堆排序

思路:建立堆,得到堆顶元素为最大元素,去掉堆顶元素,将堆的最后一个元素放到堆顶,此时通过一次调整使得堆有序.堆顶元素为第二大元素,重复步骤直到堆变空

效率:O(nlogn)

 def sift(data,low,high):

     i = low #根节点下标

     j = 2 * i +1 #左子节点的下标

     tmp = data[i]

     while j <= high:

         if j < high and data[j] < data[j+1]:

             j += 1

         if tmp < data[j]:

             data[i] = data[j]

             i = j

             j = 2 * i +1

         else:

             break

     data[i] = tmp

 def heap_sort(data):

     n = len(data)

     for i in range(n//2-1,-1,-1):

         sift(data,i,n-1)

     for i in range(n-1,-1,-1):

         data[0],data[i] = data[i],data[0]

         sift(data,0,i-1)

  6.归并排序

 思路:将列表越分越小,直到分成一个元素,此时一个元素是有序的.然后将两个有序的列表合并

 def merge(data,low,mid,high):

     i = low #左指针

     j = mid+1 #右指针

     tmp = []#临时列表

     #如果列表还有值

     while i <= mid and j <= high:

         #如果左边的值比右边的值小,则放入到tmp中

         if data[i] <= data[j]:

             tmp.append(data[i])

             i+=1

         else:#否则将右边的值放入到tmp中

             tmp.append(data[j])

             j-=1

     #如果左边还有剩下的值,则一起放入到tmp中的左边

     while i <= mid:

         tmp.append(data[i])

         i+=1

     #如果右边还有剩下的值,则一起放入到tmp中的右边

     while j <= high:

         tmp.append(data[j])

         j+=1

     data[low:high+1] = tmp

 def merge_sort(data,low,high):

     if low< high:

         mid = (low+high)//2

         merge_sort(data,low,mid)

         merge_sort(data,mid+1,high)

         merge(data,low,mid,high)

6.归并排序

思路：使用递归的方式，将列表越分越小，直至一个元素，然后将列表组合成一个有序的列表

     def merge(self,data,low,mid,high):

         i = low

         j = mid +1

         ltmp = []

         while i <= mid and j <= high:

             if data[i] <= data[j]:

                 ltmp.append(data[i])

                 i+=1

             else:

                 ltmp.append(data[j])

                 j+=1

             while i <= mid:#如果左边还有数据继续将左边的数据放入临时列表中

                 ltmp.append(data[i])

                 i+=1

             while j <= high:#如果右边还有数据继续将右边的数据放入临时列表中

                 ltmp.append(data[j])

                 j+=1

         data[low:high+1] =ltmp #将新列表的值替换原列表的值

     def merge_sort(self,data,low,high):

         if low< high:

             mid = (low+high)//2

             self.merge_sort(data,0,mid)

             self.merge_sort(data,mid+1,high)

             self.merge(data,low,mid,high)

7.希尔排序

思路:首先取一个整数d1=n/2,将列表中的元素分成d1个组,每组相邻两元素的之间的距离为d1,在各组内直接进行插入排序.取第二个整数d2=d1/2,重复上述的分组过程,直到di=1,

然后在同一组内进行插入排序

效率:O(1.3n)

 def shell_sort(data):

 　　#获取步长

     gap = len(data)//2

     while gap > 0:

         #根据步长gap进行插入排序

         for i in range(gap,len(data)):

             tmp = data[i]

             j = i - gap

             while j >= 0 and tmp < data[j]:

                 data[j+gap] = data[j]

                 j-=gap

             data[j+gap] = tmp

         gap/=2

排序总结

练习:

1.给定一个升序列表和一个整数,返回该整数在列表中的下标范围.例如:列表[1,2,3,3,3,4,4,5],若查找3,则返回(2,4),查找1,返回(0,0)

思路:利用二分查找,如果查到3,在看看3的左边和右边是否有相等的元素,有则返回下标

 def binary_list_search(data,val):

     low = 0

     high = len(data)-1

     while low <= high:

         mid = (low+high)//2

         #如果找到val的值

         if data[mid] == val:

             #创建两个指针

             left=mid

             right=mid

             #如果左边指针的值等于val,则指针向左移

             while left >= 0 and data[left] == val:

                 left -= 1

             #右边指针的值等于val,则指针向右移

             while right <= high and data[right] == val:

                 right += 1

             #如果都找到则返回val在列表中的下标范围

             return (left,right)

         elif data[mid] < val:

             low = mid + 1

         else:

             high = mid-1

2.给定一个列表和一个整数,设计算法找到两个数的下标,使得两个数之和为给定的整数,保证仅有一个结果.例如列表[1,2,5,4]与目标整数3,结果为(0,1)

思路: 1.使用两重循环进行查找匹配,时间复杂度O(n²)

　　 2.使用二分查找进行匹配,时间复杂度O(nlogn)

3.使用列表下标倒序进行匹配,时间复杂度O(n)

 1.双重for循环

 def sum_list1(data,val):

     for i in range(len(data)):

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

             if data[i] + data[j] == val:

                 return (i,j)

 2.利用二分法查找进行返回

 import copy

 def bin_search(data,val,low,high):

     while low<=high:

         mid = (low + high) // 2

         if data[mid] == val:

             return mid

         elif data[mid] < val:

             low = mid+1

         else:

             high = mid-1

 def sum_list2(data,val):

     data2 = copy.deepcopy(data)

     data2.sort()

     for i in range(len(data2)):

         a = i

         b = bin_search(data2,val-data[a],i+1,len(data2)-1)

         if b:

             return (data.index(data2[a]),data.index(data2[b]))

 3.反向下标,必须提供查找的范围

 def sum_list3(data,val,max_val):

     a = [None for i in range(max_val)]

     for i in range(len(data)):

         a[data[i]] = i

         if a[val-data[i]]:

             return (a[data[i]],a[val-data[i]])

3.现在有一个列表,列表中数的范为在0-100之间,列表的长度大概为100万,设计算法在O(n)的复杂度内将列表进行排序

思路:创建一个新列表,用来存放每个数字出现的次数,元素出现几次就遍历输出几次,完成O(n)的复杂度

 def count_sort(li,max_val):

     #统计每个数出现的次数

     count = [0 for i in range(max_val+1)]

     for num in li:

         count[num] += 1

     i = 0

     #找出下标,值,通过遍历把每一个次数对应的值重新赋值给li

     #因为count和n的值不同,所以虽然是两重for,count表示每个数出现的次数,n表示列表但复杂度依然是O(n)

     for num,n in enumerate(count):

         for j in range(n):

             li[i] = num

             i += 1

     return li

4.现在有n个数(n>10000),设计算法,按照大小顺序得到前10大的数

思路:创建长度为10的临时列表来存放目标数据,然后通过插入排序来调整列表中数的顺序

 def insert(li,i):

     tmp = li[i]

     j = i-1

     while j>=0 and li[j]>tmp:

         li[j+1]=li[j]

         j-=1

     li[j+1]=tmp

 def insert_sort(li):

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

         insert(li,i)

 def topk(li,k):

     top=li[0:k+1]

     insert_sort(li)

     for i in range(k+1,len(li)):

         top[k] = li[i]

         insert(top,k)

     return top[:-1]

巴特西

Python常用排序算法

最新文章

热门文章