排序算法:Python 实现

import sys print (sys.version) # 3.5.2 |Continuum Analytics, Inc.| (default, Jul 5 2016, 11:41:13) [MSC v.1900 64 bit (AMD64)]

1、交换排序—冒泡排序

通过两两交换,小的先冒出来,大的后冒出来。O(N2),稳定,排序过程如下:

代码如下:

def bubble_sort(num): n = len(num) for i in range(n): for j in range(i, n): if num[i] > num[j]: num[i], num[j] = num[j], num[i] return num

算法的稳定性定义为:对于待排序列中相同元素的原来次序不被排序算法改变,则称该算法稳定。

2、交换排序—快速排序(Quick sort)

1). 首先选择一个基准元素,通常选择第一个元素或者最后一个元素。

2). 通过一轮排序,将待排序的数组分割成独立的两部分,其中一部分数组的元素值均比基准元素值小,另一部分数组的元素值比基准值大。

3). 然后分别对这两部分数组用同样的方法继续进行排序,直到整个数组有序。

O(NlogN),不稳定,排序过程如下:

代码如下:

def quick_sort(num):    
 if len(num) <= 1:        
 return num    
 larger = []     
smaller = []     
p = num.pop(random.randint(0, len(num)-1))  
 # 这里我们随机选择基准元素     
for i in num:        
 if i <= p:            
 smaller.append(i)        
 else:            
 larger.append(i)      
return quick_sort(smaller) + [p] + quick_sort(larger)

3、选择排序—直接选择排序

在要排序的一组数中,选出最小(或者最大)的一个数与第1个位置的数交换;然后在剩下的数当中再找最小(或者最大)的与第2个位置的数交换,依次类推。O(N2),不稳定。

代码如下:

def selection_sort(num):     
n = len(num)     
for i in range(n):        
 min = i         
for j in range(i, n):            
 if num[min] > num[j]:                
 min = j        
 num[min], num[i] = num[i], num[min]     
 return num

4、选择排序—堆排序

完全二叉树:叶节点只能出现在最下层和次下层,并且最下面一层的结点都集中在该层最左边的若干位置的二叉树。

满二叉树:除最后一层无任何子节点外,每一层上的所有结点都有两个子结点。

堆 是一种完全二叉树,堆排序是一种树形选择排序,利用了大顶堆堆顶元素最大的特点,不断取出最大元素,并调整使剩下的元素使之还是大顶堆,依次取出最大元素就实现了排序。O(NlogN),不稳定。 举例如下:

待排序列: [16, 7, 3, 20, 17, 8]

首先根据该序列构建一个完全二叉树,得到:

然后需要构造初始堆,从最后一个非叶节点开始调整(从右往左,从下至上),调整过程如下,得到初始堆:

得到初始堆后,将堆顶元素与最后一个元素交换,得到:

此时3位于堆顶,不满足大顶堆的性质,需调整如下(忽略最后一个元素):

然后继续将堆顶元素与倒数第二个元素交换,如此进行下去,最终得到:

代码如下:

def MAX_Heapify(heap,HeapSize,root):   #在堆中做调整使得父节点的值大于子节点     
left = 2*root + 1   # 左子节点     
right = left + 1    # 右子节点    
 larger = root    
 if left < HeapSize and heap[larger] < heap[left]:        
 larger = left    
 if right < HeapSize and heap[larger] < heap[right]:         
larger = right    
 if larger != root:  #如果做了堆调整则larger的值等于左节点或者右节点,则对调值         heap[larger], heap[root] = heap[root], heap[larger]        
 MAX_Heapify(heap, HeapSize, larger)

 def Build_MAX_Heap(heap):   # 构造一个堆,然后调整成最大堆    
 HeapSize = len(heap)    
 for i in range((HeapSize-2)//2,-1,-1):   # 从最后一个非叶节点往前开始调整         MAX_Heapify(heap,HeapSize,i)

 def HeapSort(heap):    
 Build_MAX_Heap(heap)   # 得到初始(大顶)堆    
 #print(heap)    
 for i in range(len(heap)-1,-1,-1):         
heap[0], heap[i] = heap[i], heap[0]    # 堆顶元素与最后一个元素交换         
MAX_Heapify(heap, i, 0)     
return heap
 if __name__ == '__main__':    
 a = [16, 7, 3, 20, 17, 8]     
print (a)    
 print (HeapSort(a))

5、插入排序—直接插入排序

每次将一个待排序的元素与已排序好的元素进行逐一比较,直到找到合适的位置按大小插入。O(N2),稳定。排序过程如下:

代码如下:

def insertion_sort(num):     
for i in range(1,len(num)):         
j = i        
 tmp = num[i]         
while j > 0 and tmp < num[j-1]:            
 num[j] = num[j-1]            
 j -= 1       
  num[j] = tmp     
 return num
 print (insertion_sort(num))

6、插入排序—希尔排序

先将整个待排元素序列分割成若干个子序列(由相隔某个“增量”的元素组成的)分别进行直接插入排序,然后依次缩减增量再进行排序,待整个序列中的元素基本有序(增量足够小)时,再对全体元素进行一次直接插入排序。O(N1.3),不稳定。

排序过程如下(下面希尔排序的步长选择都是从n/2开始,每次再减半,直到最后为1):

代码如下:

def shell_sort(lists):     
count = len(lists)    
 step = 2    
 group = count // step     
while group > 0:         
for i in range(0, group):            
 j = i + group             
while j < count:                
 k = j - group                
 key = lists[j]                 
while k >= 0:                     
if lists[k] > key:                       
  lists[k+group] = lists[k]                        
 lists[k] = key                    
 k -= group                
 j += group         
group //= step    
 return lists  print(shell_sort([49,38,65,97,26,13,27,49,55,4]))

7、归并排序

归并排序是利用归并的思想实现的排序方法,该算法采用经典的分治(divide-and-conquer)策略(分治法将问题分(divide)成一些小的问题然后递归求解,而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起,即分而治之)。简单来讲,就是将待排序列不停的分为左边和右边两份,然后以此递归分下去。然后再将她们按照两个有序数组的样子合并起来。O(NlogN),稳定。

举例如下(引自博文):

代码如下:

def merge(left,right):   
  i, j = 0, 0     
  result = []     
  while i < len(left) and j < len(right):        
   if left[i] <= right[j]:             
   result.append(left[i])             i += 1         else:        
        result.append(right[j])             j += 1      
        result += left[i:]     
        result += right[j:]     
        return result   def MergeSort(list):     
        if len(list) <= 1:         
        return list     mid = len(list)//2     
        left = MergeSort(list[:mid])     
        right = MergeSort(list[mid:])     
        return merge(left, right)   
        if __name__ == '__main__':     
        a = [16, 7, 3, 20, 17, 8]     print (a)     print (MergeSort(a))

原文发布于微信公众号 - 人工智能LeadAI(atleadai)

原文发表时间:2017-09-29

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏小樱的经验随笔

洛谷 P1553 数字反转(升级版)【字符串+STL stack】

P1553 数字反转(升级版) 题目描述 给定一个数,请将该数各个位上数字反转得到一个新数。 这次与NOIp2011普及组第一题不同的是:这个数可以是小数,分数...

3094
来自专栏程序员互动联盟

八大排序算法

排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。 我们这里说说...

3948
来自专栏Java开发者杂谈

重读算法导论之算法基础

重读算法导论之算法基础 ---- 插入排序 ​ 对于少量数据的一种有效算法。原理: 整个过程中将数组中的元素分为两部分,已排序部分A和未排序部分B 插入过程中,...

4129
来自专栏人工智能LeadAI

讨厌算法的程序员 | 第七章 归并排序的时间复杂度分析

上一篇归并排序基于分治思想通过递归的调用自身完成了排序,本篇是关于归并排序的最后一部分——分析其时间复杂度。 这个过程中会解释清楚在各种时间复杂度中经常看到的一...

37611
来自专栏LEo的网络日志

关于算法复杂度

3678
来自专栏Java帮帮-微信公众号-技术文章全总结

八大排序算法详解_面试+提升

八大排序算法详解_面试+提升 概述 排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排...

3989
来自专栏钱塘大数据

【推荐收藏】十大经典排序算法(动图演示)

冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也...

932
来自专栏机器学习和数学

[编程经验]Python生成器、迭代器与yield语句小结

今天要分享的内容是Python的生成器、迭代器与yield语句。主要包括什么是生成器,如何定义一个生成器,如何调用生成器包含的元素。迭代器也是一样的,最后介绍y...

3156
来自专栏Dawnzhang的开发者手册

数据结构与算法学习笔记之为用于高考名次排序的排序算法

  在高考结束以后,所有人都在等着成绩,政府部门面对几百万的数据,你知道他们是怎么算名次的么?上一次学到递归排序以及快排,确实,用他们可以实现,可是他们的时间复...

591
来自专栏玄魂工作室

Python算法与数据结构--求所有子数组的和的最大值

题目:输入一个整形数组,数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和。

1462

扫码关注云+社区

领取腾讯云代金券