排序及复杂度、反转单链表_链表反转时间复杂度
赞
踩
1.什么是计算机科学？
计算机科学：实际上是对问题、解决问题以及解决问题的过程中产生的解决方案的研究。也可以看做定义算法的研究，即对问题进行处理且求解的一种实现思路或者思想。
2 十大排序时间复杂度及稳定性
1.什么是时间复杂度？
- 时间复杂度：量化算法执行的操作/执行步骤的数量
- 大O记法：就是使用时间复杂度衡量算法好坏的表现形式。O（最重要或复杂的一项）
- 最常见的时间复杂度：O(1)<O(logn)<O(n)<O(nlogn)<O(n平方) < O(n三次方)<O(2的n次方)<O(n!)<O(n的n次方)
例子
- 例如O(n)：循环了n次，
比如冒泡和选择的最好情况
- 例如O(n平方)：循环内又嵌入了一套循环，所以循环了nxn=n平方次，
比如冒泡、选择、插入排序
- 例如O(logn)：循环内是等比数列，即2×2^x次方=n，则x=log2n,忽略底数，记为 O(logn)。 - 如果一段代码的时间复杂度是 O(logn)，我们循环执行 n 遍，时间复杂度就是 O(nlogn) 了，
比如，归并排序、快速排序的时间复杂度都是 O(nlogn)。
i=1;
while (i <= n) {
i = i * 2;
}
- 1
- 2
- 3
- 4
- 例如O(m+n),从下面代码中可以看出，m 和 n 是表示两个数据规模。我们无法事先评估 m 和 n 谁的量级大，所以我们在表示复杂度的时候，就不能简单地利用加法法则，省略掉其中一个。所以，上面代码的时间复杂度就是 O(m+n)。
比如计数、桶排序
function cal(m, n) {
var sum_1 = 0;
var i = 1;
for (; i < m; ++i) {
sum_1 = sum_1 + i;
}
var sum_2 = 0;
var j = 1;
for (; j < n; ++j) {
sum_2 = sum_2 + j;
}
return sum_1 + sum_2;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
2.什么是空间复杂度？
- 空间复杂度:表示算法的存储空间与数据规模之间的增长关系。
function print(n) {
var i = 0;
var a = [];
for (i; i <n; ++i) {
a[i] = i * i;
}
for (i = n-1; i >= 0; --i) {
console.log(a[i])
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
1)跟时间复杂度分析一样，我们可以看到，第 2 行代码中，我们申请了一个空间存储变量 i，但是它是常量阶的，跟数据规模 n 没有关系，所以我们可以忽略。
2)第 3 行申请了一个大小为 n 的 int 类型数组，除此之外，剩下的代码都没有占用更多的空间，所以整段代码的空间复杂度就是 O(n)。
3)我们常见的空间复杂度就是 O(1)、O(n)、O(n2 )，冒泡、选择、插入、堆排序和希尔的空间复杂度都是O(1),快速排序是 O(logn)。
概念：
- 稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
- 不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。
for (int j = 0; j < n - 1; j++)
{
for (int i = 0; i < n - 1 - j; i++)
{
if (A[i] > A[i + 1]) // 如果条件改成A[i] >= A[i + 1],则变为不稳定的排序算法
{
exchange(A, i, i + 1);
}
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
4 冒泡排序
冒泡排序流程：
- 比较相邻的两个元素，如果前者比后者大（反之倒序），则交换，大的元素逐渐向后移动。
- 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。
- 针对所有的元素重复以上的步骤，直到没有任何一对数字需要比较。
冒泡排序代码实现：
def bubble_sort(nums):
for i in range(len(nums) - 1): # 这个循环负责设置冒泡排序进行的次数
for j in range(len(nums) - i - 1): # j为列表下标
if nums[j] > nums[j + 1]:
nums[j], nums[j + 1] = nums[j + 1], nums[j]
return nums
print(bubble_sort([45, 32, 8, 33, 12, 22, 19, 97]))
# 输出：[8, 12, 19, 22, 32, 33, 45, 97]
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
5 选择排序
选择排序流程：
- 比较相邻的两个元素，大的元素直接放到序列最后位置。
- 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。
- 针对所有的元素重复以上的步骤，直到没有任何一对数字需要比较。
选择排序代码实现：
def sort(alist):
for j in range(len(alist)-1):
max_index=0
for i in range(len(alist)-1-j):
if alist[max_index]<alist[i+1]:
max_index=i+1
#循环结束后，max_index最大值得下标
alist[len(alist)-1-j],alist[max_index]=alist[max_index],alist[len(alist)-1-j]#最大值和最后一个元素换位
return alist
alist=[3,8,5,7,6]
print(sort(alist))
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
6 快速排序
快速排序流程：
快速排序（Quicksort）是对冒泡排序算法的一种改进
当排序已经成为基本有序状态时，复杂度最坏为n^2
- 首先设定一个分界值，通过该分界值将数组分成左右两部分。
- 将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值。
- 然后，左边和右边的数据可以重复上步独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。
- 重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。
快速排序代码实现：
def quick_sort(data): """快速排序""" if len(data) >= 2: # 递归入口及出口 mid = data[len(data)//2] # 选取基准值，也可以选取第一个或最后一个元素 left, right = [], [] # 定义基准值左右两侧的列表 data.remove(mid) # 从原始数组中移除基准值 for num in data: if num >= mid: right.append(num) else: left.append(num) return quick_sort(left) + [mid] + quick_sort(right) else: return data # 示例： array = [2,3,5,7,1,4,6,15,5,2,7,9,10,15,9,17,12] print(quick_sort(array)) # 输出为[1, 2, 2, 3, 4, 5, 5, 6, 7, 7, 9, 9, 10, 12, 15, 15, 17]
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
6 堆排序
堆的定义如下：
1)具有n个元素的序列（k1,k2,…,kn)
2)若以一维数组存储一个堆，则堆对应一棵完全二叉树，且所有非叶结点的值均不大于(或不小于)其子女的值，根结点（堆顶元素）的值是最小(或最大)的。
堆排序流程：
1）将无序序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆;
2）将堆顶元素与末尾元素交换，将最大元素"沉"（或最小）到数组末端;
3）重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。
从算法描述来看，堆排序需要两个过程，一是建立堆，二是堆顶与堆的最后一个元素交换位置。所以堆排序有两个函数组成。一是建堆的渗透函数，二是反复调用渗透函数实现排序的函数。
# 调整堆 def adjust_heap(lists, i, size): lchild = 2 * i + 1 rchild = 2 * i + 2 max = i if i < size / 2: if lchild < size and lists[lchild] > lists[max]: max = lchild if rchild < size and lists[rchild] > lists[max]: max = rchild if max != i: lists[max], lists[i] = lists[i], lists[max] adjust_heap(lists, max, size) # 创建堆 def build_heap(lists, size): for i in range(0, (size/2))[::-1]: adjust_heap(lists, i, size) # 堆排序 def heap_sort(lists): size = len(lists) build_heap(lists, size) for i in range(0, size)[::-1]: lists[0], lists[i] = lists[i], lists[0] adjust_heap(lists, 0, i) return lists ###测试 test_list = [5, 6, 1, 9, 11, 10, 4, 2] result = heap_sort(test_list) print(result)
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
7 插入排序-直接插入排序
1）将无序序列中的数据插入到有序的序列中
2）在遍历无序序列时，首先拿无序序列中的首元素去与有序序列中的每一个元素比较并插入到合适的位置，一直到无序序列中的所有元素插完为止。
算法的实现：
lists=[49,38,65,97,76,13,27,49,55,04] '''插入排序—————直接插入排序(Straight Insertion Sort)''' def insert_sort(lists): count=len(lists) for i in range(1,count): j=i-1 key=lists[i] while j>=0: if key<lists[j]: # lists[j]=key lists[j+1]=lists[j] lists[j]=key print lists j=j-1 return lists insert_sort(lists)
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
效率：
时间复杂度：O（n^2）.
其他的插入排序有二分插入排序，2-路插入排序。
8 归并排序
排序原理:
1尽可能的一组数据拆分成两个元素相等的子组.并对每一个子组继续拆分.直到拆分后的每个子组的元素个数是1为止。
2.将相邻的两个子组进行合并成一个有序的大组 ;
3.不断的重复步骤2。直到最终只有一个组为止。
代码
# 递归分解 def merge_sort(array): mid = int((len(array)+1)/2) if len(array) == 1: # 递归结束的条件，分解到列表只有一个数据时结束 return array list_left = merge_sort(array[:mid]) list_right = merge_sort(array[mid:]) return merge(list_left, list_right) # 进行归并,#merge合并，不指定on则以两个DataDataFrame的列名交集做为连接键 ，这里指的是"key,。结果为key，data1,data2" # 进行归并 def merge(list_left, list_right): final = [] while list_left and list_right: if list_left[0] <= list_right[0]: # 如果将"<="改为"<",则归并排序不稳定 final.append(list_left.pop(0))#pop(0)表示它删除索引中作为列表第一个元素的元素 else: final.append(list_right.pop(0)) return final+list_left+list_right # 返回排序好的列表 if __name__=="__main__": array = [49, 38, 65, 97, 76] print(merge_sort(array))输出: [38, 49, 65, 76, 97] 时间度杂度: 平均情况＝最好情况＝最坏情况＝O(nlogn) 空间复杂度: O(n) 稳定性: 稳定
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
8 桶排序
流程：
简单来说，就是把数据分组，放在一个个的桶中，然后对每个桶里面的在进行排序。 再对每个桶中的数字排序，这时可用冒泡，快排.
桶排序的优点就是特别快，真的是特别快！特别快！特别块！而缺点就是特别耗资源
算法步骤
设置固定数量的空桶。
把数据放到对应的桶中。
对每个不为空的桶中数据进行排序。
拼接不为空的桶中数据，得到结果。
def bucketSort(nums):
max_num = max(nums)# 选择一个最大的数
bucket = [0]*(max_num+1)# 创建一个元素全是0的列表, 当做桶
for i in nums: # 把所有元素放入桶中, 即把对应元素个数加一
bucket[i] += 1
sort_nums = []
for j in range(len(bucket)): # 取出桶中的元素
if bucket[j] != 0:
for y in range(bucket[j]):
sort_nums.append(j)
return sort_nums
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
9 基数排序
10 计数排序
面试常见代码
1）对一堆数组按照第二个字母进行排序（利用冒泡的思想）
s = ['172.25.254.1','172.24.254.6','172.23.254.8']
b = []
for i in range(len(s)):
b.append(int((s[i].split('.')[1])))
n = len(s)
for i in range(n):
for j in range(0,n-i-1):
if b[j] > b[j+1]:
b[j],b[j+1] = b[j+1],b[j]
s[j],s[j+1] = s[j+1],s[j]
print(s)
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
2）n个台阶，最开始在第一节，每次只能上一节或两节，n节有多少种解法
题目描述：
有一楼梯共m级，刚开始在第一级，若每次只能跨上一级或两级，要走上第m级，共有多少走法？
注：规定从一级到一级有0种走法
解题思路：
‘’’
有一楼梯共m级，刚开始在第一级，若每次只能跨上一级或两级，要走上第m级，共有多少种走法？
分析思路：
1、如果m是1，按规定，0种走法
2、如果m是2，从1到2，只能一次跨一级，1种走法
3、如果m是3，从1到3，第一种跨两次一级，第二种一次跨两级，2种走法
4、如果m是4，要到4，有两种方式，一种从3一级到4，另一种是从2两级到4。在第一种的情况下，
到3又有两种方式，第二种情况下，到2有一种方式，所以一共有3种走法
5、如果m是5，要到5，一样有两种方式，一种从4一级到5，另一个是从3两级到5。在第一种的情况下，
到4又有三种方式，第二种情况下，到3有两种方式，所以一共有5种走法
…
其实到这里，就已经感觉到了非常像费波拉契数列，第n种的走法=第(n-1)种的走法 + 第(n-2)种的走法
‘’’
def climbStsirs(n):
if n <= 1:
return n
a = b = 1
for i in range(2, n + 1):
a, b = b, a + b
return b
n = int(input().strip())
print(climbStsirs(n))
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
3）反转单链表
输入一个链表，反转链表后，输出新链表的表头。
示例
输入：{1,2,3}
返回值：{3,2,1}
解题思路：
1）首先定义列表三个变量：pre指针（记录当前节点的前一个节点）、cur指针（指向当前节点），tmp指针（指向当前节点的下一个节点）
2）令单链表首元素指向空（pre的初始值为空）
3）将pre指针指向单链表首元素
4）将下一个节点保存在tmp指针中
5）改变原先链表的指向（首指向末–>末指向首）
6）将pre和cur节点分别向后移动
按上面四个步骤循环，则head指针将会逐渐后移到单链表尾部，再次移动单链表头指针时，为空，此时退出循环，返回pre值，此时由于head指向的是空，所以pre指向的是单链表末尾
class node(object): def __init__(self, elem, next=None): self.elem = elem self.next = next def reserverList(head): pre,cur=None,head ##pre,cur分别指向空节点和头节点 while cur: ##当前节点不为空 tmp=cur.next##保存当前节点的后续节点，保证链表不会断开 cur.next=pre##指针方向 pre=cur##pre指向当前节点 cur=tmp##当前节点指向下一节点 return pre ##当cur为空时停止循环，返回cur的前一个节点，就是pre if __name__ == '__main__': l1 = node(1) l1.next = node(2) l1.next.next = node(3) l = reserverList(l1) print(l.elem, l.next.elem, l.next.next.elem)
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
4）合并两个链表，去重，有序
思路：
1）比较两个链表的头结点
2）如果第一个链表头节点小于等于第二个链表的头节点，当前节点的后继节点指定为l1，combine先l1再l2
3）如果第一个链表头节点大于第二个链表的头节点，当前节点的后继节点指定为l2,combine先l2再l1
# 定义链表类 class ListNode: def __init__(self, x): self.val = x self.next = None # 合并链表 def combine(l1, l2): if l1 is None: return l2 elif l2 is None: return l1 elif l1.val <= l2.val: #如果第一个链表头节点小于等于第二个链表的头节点，当前节点的后继节点指定为l1 l1.next = combine(l1.next, l2) return l1 else: #如果第一个链表头节点大于第二个链表的头节点，当前节点的后继节点指定为l2 l2.next = combine(l1, l2.next) return l2 # 去重 def confict(l): li = [] #li用于存放列表中的节点 h1 = l li.append(h1.val) h2 = l.next while h2: if h2.val in li: h1.next = h2.next else: li.append(h2.val) h1 = h2 h2 = h2.next return l # 打印结果 def printlist(l1): if l1 is None: return print(l1.val) printlist(l1.next) # 生成链表1 x0 = ListNode(1) x1 = ListNode(2) x2 = ListNode(3) x3 = ListNode(4) x0.next = x1 x1.next = x2 x2.next = x3 # 生成链表2 y0 = ListNode(3) y1 = ListNode(4) y2 = ListNode(5) y3 = ListNode(6) y0.next = y1 y1.next = y2 y2.next = y3 #测试 printlist(confict(combine(x0, y0)))
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
