python数据结构的排序算法

目录

• 十大经典的排序算法

•  一、交换排序

• 1、冒泡排序（前后比较-交换）

• 2、快速排序（选取一个基准值，小数在左大数在右）

• 二、插入排序

• 1、简单插入排序（逐个插入到前面的有序数中）

• 2、希尔排序（从大范围到小范围进行比较-交换）

• 三、选择排序

• 1、简单选择排序（选择最小的数据放在前面）

•  2、堆排序（利用最大堆和最小堆的特性）

• 四、归并排序

•  五、其他排序

• 1、计数排序（字典计数-还原）

• 2、桶排序（链表）

• 3、基数排序

十大经典的排序算法

数据结构中的十大经典算法：冒泡排序、快速排序、简单插入排序、希尔排序、简单选择排序、堆排序、归并排序、计数排序、桶排序、基数排序

十大经典算法的复杂度和稳定性（如果a原本在b前面，而a=b，排序之后a仍然在b的前面）:

 一、交换排序

1、冒泡排序（前后比较-交换）

（1）算法思想
       它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成

（2）python实现代码

def bubble_sort(blist):
   count = len(blist)
   for i in range(0, count):
       for j in range(i + 1, count):
           if blist[i] > blist[j]:
               blist[i], blist[j] = blist[j], blist[i]
   return blist

2、快速排序（选取一个基准值，小数在左大数在右）

（1）算法思想
        找基准数，通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列

（2）python实现代码

def quick_sort(qlist):
   if qlist == []:
       return []
   else:
       qfirst = qlist[0]
       qless = quick_sort([l for l in qlist[1:] if l < qfirst])
       qmore = quick_sort([m for m in qlist[1:] if m >= qfirst])
       return qless + [qfirst] + qmore

二、插入排序

1、简单插入排序（逐个插入到前面的有序数中）

（1）算法思想

        插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序；首先将第一个作为已经排好序的，然后每次从后的取出插入到前面并排序

（2）python实现代码

（2）python实现代码
def insert_sort(ilist):
   for i in range(len(ilist)):
       for j in range(i):
           if ilist[i] < ilist[j]:
               ilist.insert(j, ilist.pop(i))
               break
   return ilist

2、希尔排序（从大范围到小范围进行比较-交换）

（1）算法思想
        先取一个正整数 d1，以 d1 间隔分组，先对每个分组内的元素使用插入排序操作，重复上述分组和直接插入排序操作；直至 di = 1，即所有记录放进一个组中排序为止。

 （2）python实现代码

def shell_sort(slist):
   gap = len(slist)
   while gap > 1:
       gap = gap // 2
       for i in range(gap, len(slist)):
           for j in range(i ％ gap, i, gap):
               if slist[i] < slist[j]:
                   slist[i], slist[j] = slist[j], slist[i]
   return slist

三、选择排序

1、简单选择排序（选择最小的数据放在前面）

（1）算法思想
        第1趟，在待排序记录r1 ~ r[n]中选出最小的记录，将它与r1交换；第2趟，在待排序记录r2 ~ r[n]中选出最小的记录，将它与r2交换；以此类推，第i趟在待排序记录r[i] ~ r[n]中选出最小的记录，将它与r[i]交换，使有序序列不断增长直到全部排序完毕

 （2）python实现代码

def select_sort(slist):
   for i in range(len(slist) - 1):
       x = i
       for j in range(i, len(slist)):
           if slist[j] < slist[x]:
               x = j
       slist[i], slist[x] = slist[x], slist[i]
   return slist

 2、堆排序（利用最大堆和最小堆的特性）

（1）算法思想
        它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。堆分为大根堆和小根堆，是完全二叉树。大根堆的要求是每个节点的值都不大于其父节点的值。在数组的非降序排序中，需要使用的就是大根堆，因为根据大根堆的要求可知，最大的值一定在堆顶

 （2）python实现代码

import math
def heap_sort(a):
   al = len(a)
   def heapify(a, i):
       left = 2 * i + 1
       right = 2 * i + 2
       largest = i
       if left < al and a[left] > a[largest]:
           largest = left
       if right < al and a[right] > a[largest]:
           largest = right
       if largest != i:
           a[i], a[largest] = a[largest], a[i]
           heapify(a, largest)
   # 建堆
   for i in range(math.floor(len(a) / 2), -1, -1):
       heapify(a, i)
   # 不断调整堆：根与最后一个元素
   for i in range(len(a) - 1, 0, -1):
       a[0], a[i] = a[i], a[0]
       al -= 1
       heapify(a, 0)
   return a

四、归并排序

（1）算法思想
        采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并

 （2）python实现代码

def merge_sort(a):
   if(len(a)<2):
       return a
   middle = len(a)//2
   left, right = a[0:middle], a[middle:]
   return merge(merge_sort(left), merge_sort(right))
def merge(left,right):
   result = []
   while left and right:
       if left[0] <= right[0]:
           result.append(left.pop(0));
       else:
           result.append(right.pop(0));
   while left:
       result.append(left.pop(0));
   while right:
       result.append(right.pop(0));
   return result

 五、其他排序

1、计数排序（字典计数-还原）

（1）算法思想
        计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

 （2）python实现代码

def countingSort(arr, maxValue):
   bucketLen = maxValue+1
   bucket = [0]*bucketLen
   sortedIndex =0
   arrLen = len(arr)
   for i in range(arrLen):
       if not bucket[arr[i]]:
           bucket[arr[i]]=0
       bucket[arr[i]]+=1
   for j in range(bucketLen):
       while bucket[j]>0:
           arr[sortedIndex] = j
           sortedIndex+=1
           bucket[j]-=1
   return arr

2、桶排序（链表）

（1）算法思想
        为了节省空间和时间，我们需要指定要排序的数据中最小以及最大的数字的值。将数组分到有限数量的桶子里。每个桶子再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）

 （2）python实现代码

def bucketSort(nums):
   bucket=[0]*(max(nums)-min(nums)+1)
   for i in range(len(nums)):
       bucket[nums[i]-min(nums)]+=1
   tmp=[]
   for i in range(len(bucket)):
       if bucket[i]!=0:
           tmp+=[min(nums)+i]*bucket[i]
   return tmp

3、基数排序

（1）算法思想
        基数排序将数据按位进行分桶，然后将桶中的数据合并。每次分桶只关注其中一位数据，其他位的数据不管，最大的数据有多少位，就进行多少次分桶和合并。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。

 （2）python实现代码

def radix_sort(array):
   bucket, digit = [[]], 0
   while len(bucket[0]) != len(array):
       bucket = [[], [], [], [], [], [], [], [], [], []]
       for i in range(len(array)):
           num = (array[i] // 10 ** digit) ％ 10
           bucket[num].append(array[i])
       array.clear()
       for i in range(len(bucket)):
           array += bucket[i]
       digit += 1
   return array

来源：https://blog.csdn.net/weixin_43840280/article/details/119739655