锐客网

  1. 首页 > it技术 > >

线性表排序算法

1、排序算法的稳定性
指经过特定规则进行排序后，两个都满足排序规则，无法判断，哪一个排在前面，哪一个排在后面，这类的元素，如果按照原来的顺序，进行排列，则为稳定，否则为不稳定。
举例， （4,1），（3,1），（3,7），（5,6），我们将这个四个元祖，以第一个元素的大小，从小到大进行排序。那么对于（3,1）和（3,7）而言有两种排列方式
（3,1），（3,7），（4,1），（5,6）这种排序中的（3,1），（3,7）是以原来的顺序进行排列的，称之为稳定。
（3,7），（3,1），（4,1），（5,6）这种改变了原来的排序方式，称之为不稳定。


2、排序算法们
2.1 冒泡排序
冒泡排序的基本思想：
每一个元素都和下一个元素进行比较大小，哪一个元素大就将大的元素向后移动，然后这个大的元素，在和下一个元素进行比较，一次向下进行，直到队列的尾部，这样就找了最大数。
【线性表排序算法】然后开始第二次进行进行上面的步骤，找到第二大的数。依次向下进行。

def bubblesort(sequence): length = len(sequence) #获取序列的长度 for i in range(length-1):#一共要循环这个序列多少次 #考虑特殊情况 ，就是这个序列本身就是一个有序的,那么对于这个序列来讲，我就没有 #进行过位置互换，所以，当进入循环进行判断后，这个count一遍是一直没有执行的，# #如果第一次全部比较过后，都没有发生过替换，直接退出即可 count = 0 for j in range(length-1-i):#每一次循环，循环序列中元素的个数 ifsequence[j]>sequence[j+1]:#当前元素和后一个元素进行大小判断 sequence[j], sequence[j+1] = sequence[j+1], sequence[j]#进行位置互换 count += 1 if count == 0: return sequence return sequenceif __name__ == '__main__': a = [10,30,15,12,6,9,45,2,6,50] print(a) print(bubblesort(a))


2.2 选择排序

def selectsort(sequence): '''选择排序'''n = len(sequence)#获取列表的长度for i in range(n-1):#判断这种逻辑需要多少次 min=i for j in range(1+i , n-1): #每一次循环，都是取current为最小值，和后面进行判断，找到最小值后，将最小值与当前值位置互换。 if sequence[min] >sequence[j]: min = j sequence[i], sequence[min] = sequence[min], sequence[i] return sequenceprint(selectsort([1,10,50,22,12,44,66]))


2.3插入排序
#插入排序与选择排序类似，都输将一个序列分为两个部分，针对插入排序，将前面作为有序部分，将一个元素，作为有序部分的第一个元素，然后从 #第二个元素开始和前面有序中的每一个元素进行循环对比，如果比有序部分的元素小，就交换位置。def insert_sort(sequence):n = len(sequence) for i in range(1, n):while i>0: if sequence[i] < sequence[i-1]: sequence[i-1], sequence[i] = sequence[i], sequence[i-1] i -=1 else: breakreturn sequenceprint(insert_sort([1,10,50,22,12,44,66]))


2.4希尔排序

#首先说一下希尔排序的一个思想，希尔排序是一个间隙gap和插入排序的组成。 #首先说他的gap ，他根据gap，将一个序列分成若干个部分 #例如 一个队列[1,10,8,9,33,15,99]，加入说gap是3 ，那么分成的[1,10,8], #[9,33,15], 和[9]这三部分进行对比 ， # [1,10,8] # [9,33,15] # [99] # 他们进行竖向对比，就是竖向对比的规则就是插入排序。 # 当一次对比完成后，将gap缩小，直到是1，当gap是1的，就完全就是插入排序了。有点鸡肋这个希尔排序def shell_sort(sequence):n = len(sequence)gap = n//2#获取间隙大小while gap >= 1: for i in range(gap, n):#循环多少次 ,这个次数的判断，就看上面我们竖向对比的时候，有一个中间位置， [1][9][99] j =i#[10][33] while j>0:#[8][15] if sequence[j] < sequence[j-gap]:#那么对我们来说就是从9和你开始做对比，9是第一次，99是最后一次，99对应的下标是n-1,9对应的下标是gap，所以二者相减就是次数 sequence[j-gap], sequence[j] = sequence[j], sequence[j-gap] j -= gap gap = gap//2return sequenceprint(shell_sort([1,10,50,22,12,44,66]))


2.5
快速排序，使用递归实现快排
#使用递归，重要的思想有三点， 1、递归必须要有一个基线条件（就是终止递归的条件），一般像线性表这种数据结构， 递归条件就表中的元素为1或者为空。2、就是排序算法本身，先取列表中一个元素为中间元素，循环整个列表，将大于当前元素，放入一个新的列表，然后在将小于这个元素放入一个列表。然后将列表中不断按照这种原则进行一个分拆，最后，在将这些列表相加在一起。3、关于为什么，递归能够获取之前函数的值，因为递归会产生调用栈，每一次递归都会在栈中保存，上一次函数调用的变量的值。def quick_sort(sequence):if len(sequence)==0: return sequenceelse: middle = sequence[0] min = [i for i in sequence[1::] if i < middle] max = [i for i in sequence[1::] if i > middle] return quick_sort(min) + [middle] + quick_sort(max)print(quick_sort([33,10,50,22,12,44,66,55,999,24]))


2.6 merge_sort
''' 归并排序的思想是，将sequence，均分成两个部分，直接将每一个部分，都分成，只有一个元素位置 例如 [10,8,22,15] ,先分成[10,8],[22,15]然后在将这个两个数组在划分，[10,8]划分成[10],[8]到达这种状态。 分成每一个部分都只有一个元素后,就开始对比合并 ，首先我们看[10],[8],两个对比，[8]，将先8放入到一个空数组中 然后在和[10]merge ，筒体[22,15】重复上述操作，合并成了[15,22] ,这时候[8,10]和[15,22]在开始合并， 先将每一个数组中的第一个元素进行对比，小的先放到一个数组中，然后在拿这个数和[10]比较，如果还是10小,就将10也 放到这个列表中，然后在将[8,10]和[15,22]合并，最后就是一个有序的序列了'''def mergesort(sequence): '''归并排序''' if len(sequence)==1: return sequencen = len(sequence) middle = n // 2 left_li = mergesort(sequence[:middle]) right_li = mergesort(sequence[middle:])res = [] left_cursor, right_cursor=0, 0 while left_cursor



二、 树

有序树
1、二叉树
1.1完全二叉树
1.2
2、霍夫曼树
3、B树

下面所有的代码都是基于二叉树实现，都是为了实现一个满二叉树

2、1 二叉树添加节点及，广度serversal
class Node(object): '''树节点''' def __init__(self, ele): self._ele = ele self.left_node = None self.right_node = Noneclass Tree(object): def __init__(self): self.__root = Nonedef add(self, item): '''添加节点,通过层级遍历，实现二叉树'''node = Node(item) if self.__root is None: self.__root = node return queue = [self.__root]#先将跟节点放入队列中 while queue: cur_node = queue.pop(0) if cur_node.left_node is None: cur_node.left_node = node return else: queue.append(cur_node.left_node)if cur_node.right_node is None: cur_node.right_node = node return else: queue.append(cur_node.right_node)def leveltraversal(self):queue = [] queue = [self.__root]# 先将跟节点放入队列中 while queue: cur_node = queue.pop(0) print(cur_node._ele)if cur_node.left_node is None: pass else: queue.append(cur_node.left_node)if cur_node.right_node is None: pass else: queue.append(cur_node.right_node)if __name__ == '__main__':tree = Tree()for i in range(10): tree.add(i)tree.leveltraversal()


二叉树纵向遍历，分为三中分别是前序、中序、后序。这三种遍历的区别在遍历顺序前序是根节点 - 左边的节点 - 右边的节点 ， 中序是 左边的节点 - 根节点 - 右边的节点 ， 后序是做节点 - 右节点 - 根节点。（这个根节点如果是子树，对应的就是父节点）
这个要注意的是在纵向遍历时，如果向下遍历的节点，不是叶节点，也就是对应的仍然是一个子树，那么就要按照遍历规则，继续向下遍历。这些遍历利用了递归的思想。
class Node(object): '''树节点''' def __init__(self, ele): self._ele = ele self.left_node = None self.right_node = Noneclass Tree(object): def __init__(self): self.root = Nonedef add(self, item): '''添加节点,通过层级遍历，实现二叉树'''node = Node(item) if self.root is None: self.root = node return queue = [self.root]#先将跟节点放入队列中 while queue: cur_node = queue.pop(0) if cur_node.left_node is None: cur_node.left_node = node return else: queue.append(cur_node.left_node)if cur_node.right_node is None: cur_node.right_node = node return else: queue.append(cur_node.right_node)def leveltraversal(self):queue = [] queue = [self.root]# 先将跟节点放入队列中 while queue: cur_node = queue.pop(0) print(cur_node._ele)if cur_node.left_node is None: pass else: queue.append(cur_node.left_node)if cur_node.right_node is None: pass else: queue.append(cur_node.right_node)def prevtraversal(self, node): '''先序''' if node is None: return print(node._ele, end='') print('') self.prevtraversal(node.left_node)self.prevtraversal(node.right_node)def infixtraversal(self, node): '''中序'''if node is None: returnself.infixtraversal(node.left_node) print(node._ele, end='') print('') self.infixtraversal(node.right_node)def postordertraversal(self, node): '''后序'''if node is None: return self.postordertraversal(node.left_node) self.postordertraversal(node.right_node) print(node._ele, end='')




转载于:https://www.cnblogs.com/python-ERIC/p/10747412.html

    推荐阅读


    上一篇：C/C++二维数组的用法

    下一篇：Nuxt.Js爬坑小记