python3写排序,查找以及链表常考题

   声明:本站部分内容来自互联网,如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。

22

一:python3实现常考的排序算法:插入排序, 冒泡排序, 快速排序

def insert_sort(lists):length = len(lists)for i in range(1, length):key = lists[i]j = i-1while j >= 0:if lists[j] > key:lists[j + 1] = lists[j]lists[j] = keyj -= 1return listsdef bubble_sort(lists):length = len(lists)for i in range(0, length):for j in range(i+1, length):if lists[j] < lists[i]:lists[j], lists[i] = lists[i], lists[j]return listsdef quick_sort(lists, left, right):if left >= right:return listskey = lists[left]low = lefthigh = rightwhile left < right:while left < right and lists[right] >= key:right -= 1lists[left] = lists[right]while left < right and lists[left] <= key:left += 1lists[right] = lists[left]lists[right] = keyquick_sort(lists, low, left-1)quick_sort(lists, left+1, high)return lists

二:python3实现二分查找(递归和非递归方式)

def binary_search(num_list, x):'''二分查找'''num_list = sorted(num_list)left, right = 0, len(num_list)while left < right:mid = int((left + right) / 2)if num_list[mid] > x:right = midelif num_list[mid] < x:left = mid + 1else:return '待查元素{0}在列表中下标为:{1}'.format(x, mid)return '待查找元素%s不存在指定列表中'%xdef binary_search_(list, left, right, num):lis = sorted(list)if left > right:  # 递归结束条件return -1mid = (left + right) // 2if num < lis[mid]:right = mid - 1elif num > lis[mid]:left = mid + 1else:return midreturn binary_search_(lis, left, right, num)

三:pyhon3实现链表以及链表的基本操作

class Node(object):def __init__(self, val, p=0):self.data = valself.next = pclass LinkList(object):def __init__(self):self.head = 0def init_list(self, data):self.head = Node(data[0])p = self.headfor item in data[1:]:node = Node(item)p.next = nodep = nodedef get_len(self):if self.head == 0:return 0p = self.headlength = 1while p.next != 0:p = p.nextlength += 1return lengthdef is_empty(self):if self.head == 0:return Trueelse:return Falsedef clear(self):self.head = 0def append(self, item):if self.head == 0:self.head = Node(item)p = self.headwhile p.next != 0:p = p.nextnode = Node(item)p.next = nodedef print_item(self, index):if self.is_empty():print("链表为空")returnif index < 0 or index > self.get_len():print("位置信息错误")returnp = self.headfor i in range(0, index):p = p.nextprint(p.data)def insert(self, item, index):if self.is_empty():print("链表为空")returnif index < 0 or index > self.get_len():print("位置信息错误")returnp = self.headfor i in range(0, index-1):p = p.nexttmp = p.nextnode = Node(item, tmp)p.next = nodedef delete(self, index):if self.is_empty():print("链表为空")returnif index < 0 or index > self.get_len():print("位置信息错误")returnp = self.headfor i in range(0, index-1):p = p.nextp.next = p.next.nextdef print_list(self):if self.is_empty():print("链表为空")returnp = self.headwhile p != 0:print(p.data, end="->")p = p.nextif __name__ == "__main__":l = LinkList()print(l.is_empty())l.init_list([2, 3, 4, 5])# l.append(7)# l.print_list()l.insert(0, 2)l.print_list()# l.delete(2)# l.print_list()# l.print_item(2)