您的位置: 首页  >  文章  >  各种快速排序算法

各种快速排序算法

分类: 文章 • 2024-01-05 23:12:46

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

  • 时间复杂度：O(n²)
  • 空间复杂度：O(1)
  • 稳定性：稳定
[python] view plain copy
  1. def insert_sort(ilist):  
  2.     for i in range(len(ilist)):  
  3.         for j in range(i):  
  4.             if ilist[i] < ilist[j]:  
  5.                 ilist.insert(j, ilist.pop(i))  
  6.                 break  
  7.     return ilist  
  8.   
  9. ilist = insert_sort([4,5,6,7,3,2,6,9,8])  
  10. print ilist  

2.希尔排序：希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止

  • 时间复杂度：O(n)
  • 空间复杂度：O(n√n)
  • 稳定性：不稳定
[python] view plain copy
  1. def shell_sort(slist):  
  2.     gap = len(slist)  
  3.     while gap > 1:  
  4.         gap = gap // 2  
  5.         for i in range(gap, len(slist)):  
  6.             for j in range(i % gap, i, gap):  
  7.                 if slist[i] < slist[j]:  
  8.                     slist[i], slist[j] = slist[j], slist[i]  
  9.     return slist  
  10.   
  11. slist = shell_sort([4,5,6,7,3,2,6,9,8])  
  12. print slist  

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

  • 时间复杂度：O(n²)
  • 空间复杂度：O(1)
  • 稳定性：稳定
[python] view plain copy
  1. def bubble_sort(blist):  
  2.     count = len(blist)  
  3.     for i in range(0, count):  
  4.         for j in range(i + 1, count):  
  5.             if blist[i] > blist[j]:  
  6.                 blist[i], blist[j] = blist[j], blist[i]  
  7.     return blist  
  8.   
  9. blist = bubble_sort([4,5,6,7,3,2,6,9,8])  
  10. print blist  

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

  • 时间复杂度：O(nlog₂n)
  • 空间复杂度：O(nlog₂n)
  • 稳定性：不稳定
[python] view plain copy
  1. def quick_sort(qlist):  
  2.     if qlist == []:  
  3.         return []  
  4.     else:  
  5.         qfirst = qlist[0]  
  6.         qless = quick_sort([l for l in qlist[1:] if l < qfirst])  
  7.         qmore = quick_sort([m for m in qlist[1:] if m >= qfirst])  
  8.         return qless + [qfirst] + qmore  
  9.   
  10. qlist = quick_sort([4,5,6,7,3,2,6,9,8])  
  11. print qlist  

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

  • 时间复杂度：O(n²)
  • 空间复杂度：O(1)
  • 稳定性：不稳定
[python] view plain copy
  1. def select_sort(slist):  
  2.     for i in range(len(slist)):  
  3.         x = i  
  4.         for j in range(i, len(slist)):  
  5.             if slist[j] < slist[x]:  
  6.                 x = j  
  7.         slist[i], slist[x] = slist[x], slist[i]  
  8.     return slist  
  9.   
  10. slist = select_sort([4,5,6,7,3,2,6,9,8])  
  11. print slist  

6.堆排序：它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。堆分为大根堆和小根堆，是完全二叉树。大根堆的要求是每个节点的值都不大于其父节点的值，即A[PARENT[i]] >= A[i]。在数组的非降序排序中，需要使用的就是大根堆，因为根据大根堆的要求可知，最大的值一定在堆顶

  • 时间复杂度：O(nlog₂n)
  • 空间复杂度：O(1)
  • 稳定性：不稳定
[python] view plain copy
  1. import copy  
  2.   
  3. def heap_sort(hlist):  
  4.     def heap_adjust(parent):  
  5.         child = 2 * parent + 1  # left child  
  6.         while child < len(heap):  
  7.             if child + 1 < len(heap):  
  8.                 if heap[child + 1] > heap[child]:  
  9.                     child += 1  # right child  
  10.             if heap[parent] >= heap[child]:  
  11.                 break  
  12.             heap[parent], heap[child] = heap[child], heap[parent]  
  13.             parent, child = child, 2 * child + 1  
  14.   
  15.     heap, hlist = copy.copy(hlist), []  
  16.     for i in range(len(heap) // 2, -1, -1):  
  17.         heap_adjust(i)  
  18.     while len(heap) != 0:  
  19.         heap[0], heap[-1] = heap[-1], heap[0]  
  20.         hlist.insert(0, heap.pop())  
  21.         heap_adjust(0)  
  22.     return hlist  
  23.   
  24. hlist = heap_sort([4,5,6,7,3,2,6,9,8])  
  25. print hlist  

7.基数排序：透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用

  • 时间复杂度：O(d(r+n))
  • 空间复杂度：O(rd+n)
  • 稳定性：稳定
[python] view plain copy
  1. def radix_sort(array):  
  2.     bucket, digit = [[]], 0  
  3.     while len(bucket[0]) != len(array):  
  4.         bucket = [[], [], [], [], [], [], [], [], [], []]  
  5.         for i in range(len(array)):  
  6.             num = (array[i] // 10 ** digit) % 10  
  7.             bucket[num].append(array[i])  
  8.         array.clear()  
  9.         for i in range(len(bucket)):  
  10.             array += bucket[i]  
  11.         digit += 1  
  12.     return array  

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

  • 时间复杂度：O(nlog₂n)
  • 空间复杂度：O(1)
  • 稳定性：稳定
[python] view plain copy
  1. def merge_sort(array):  
  2.     def merge_arr(arr_l, arr_r):  
  3.         array = []  
  4.         while len(arr_l) and len(arr_r):  
  5.             if arr_l[0] <= arr_r[0]:  
  6.                 array.append(arr_l.pop(0))  
  7.             elif arr_l[0] > arr_r[0]:  
  8.                 array.append(arr_r.pop(0))  
  9.         if len(arr_l) != 0:  
  10.             array += arr_l  
  11.         elif len(arr_r) != 0:  
  12.             array += arr_r  
  13.         return array  
  14.   
  15.     def recursive(array):  
  16.         if len(array) == 1:  
  17.             return array  
  18.         mid = len(array) // 2  
  19.         arr_l = recursive(array[:mid])  
  20.         arr_r = recursive(array[mid:])  
  21.         return merge_arr(arr_l, arr_r)  
  22.   
  23.     return recursive(array)  
各种快速排序算法

相关推荐