各种快速排序算法 - Go语言中文社区

各种快速排序算法

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时，整个文件恰被分成一组，算法便终止

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

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

[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 版权声明：本文来源CSDN，感谢博主原创文章，遵循 CC 4.0 by-sa 版权协议，转载请附上原文出处链接和本声明。
    原文链接：https://blog.csdn.net/lmz_lmz/article/details/80641475
    站方申明：本站部分内容来自社区用户分享，若涉及侵权，请联系站方删除。
  • 发表于 2020-03-01 23:12:56
  • 阅读 ( 791 )
  • 分类：算法

你可能感兴趣的文章

精选的优质文章

0 条评论

请先 登录 后评论

官方社群

GO教程

推荐文章

猜你喜欢

随便看看

来源51CTO

如果觉得我的文章对您有用，请随意打赏。你的支持将鼓励我继续创作！