数据结构

Ilingis · 发表于 2023-2-23 10:48

冒泡排序

重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢&#34;浮&#34;到数列的顶端。比较相邻的元素。如果第一个比第二个大，就交换他们两个。对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。针对所有的元素重复以上的步骤，除了最后一个。持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
def bubbleSort(arr):
for i in range(1, len(arr)):
      for j in range(0, len(arr)-i):
         if arr[j] > arr[j+1]:
            arr[j], arr[j+1] = arr[j+1], arr[j]
return arr归并排序

和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是 O(nlogn) 的时间复杂度。代价是需要额外的内存空间。
2. 算法步骤

申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
设定两个指针，最初位置分别为两个已经排序序列的起始位置；
比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
重复步骤 3 直到某一指针达到序列尾；
将另一序列剩下的所有元素直接复制到合并序列尾。

def mergeSort(arr):
if(len(arr)<2):
      return arr
middle = math.floor(len(arr)/2) # 返回小于或等于一个给定数字的最大整数
left, right = arr[0:middle], arr[middle:]
return merge(mergeSort(left), mergeSort(right),)

def merge(left, right):
result = []
while left and right:
      if left[0] <= right[0]:
         result.append(left.pop(0))
      else:
         result.append(right.pop(0));
while left:
      result.append(left.pop(0))
while right:
      result.append(right.pop(0))
return result快速排序

排序效率在同为O(N*logN)的几种排序方法中效率较高，因此经常被采用，再加上快速排序思想----分治法(Divide-and-Conquer Method)
该方法的基本思想是：

1．先从数列中取出一个数作为基准数。
2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
3．再对左右区间重复第二步，直到各区间只有一个数。

以一个数组作为示例，取区间第一个数为基准数。

初始时，i = 0;  j = 9; X = a = 72
由于已经将 a[0] 中的数保存到 X 中，可以理解成在数组 a[0] 上挖了个坑，可以将其它数据填充到这来。
从j开始向前找一个比X小或等于X的数。当j=8，符合条件，将a[8]挖出再填到上一个坑a[0]中。a[0]=a[8]; i++;  这样一个坑a[0]就被搞定了，但又形成了一个新坑a[8]，这怎么办了？简单，再找数字来填a[8]这个坑。这次从i开始向后找一个大于X的数，当i=3，符合条件，将a[3]挖出再填到上一个坑中a[8]=a[3]; j--;
数组变为：

i = 3; j = 7; X=72
再重复上面的步骤，先从后向前找，再从前向后找。
从j开始向前找，当j=5，符合条件，将a[5]挖出填到上一个坑中，a[3] = a[5]; i++;
从i开始向后找，当i=5时，由于i==j退出。
此时，i = j = 5，而a[5]刚好又是上次挖的坑，因此将X填入a[5]。
数组变为：

可以看出a[5]前面的数字都小于它，a[5]后面的数字都大于它。因此再对a[0…4]和a[6…9]这二个子区间重复上述步骤就可以了。
def quick_sort(alist, start, end):
&#34;&#34;&#34;快速排序&#34;&#34;&#34;
if start >= end:  # 递归的退出条件
      return
mid = alist[start]  # 设定起始的基准元素
low = start  # low为序列左边在开始位置的由左向右移动的游标
high = end  # high为序列右边末尾位置的由右向左移动的游标
while low < high:
      # 如果low与high未重合，high(右边)指向的元素大于等于基准元素，则high向左移动
      while low < high and alist[high] >= mid:
         high -= 1
      alist[low] = alist[high]  # 走到此位置时high指向一个比基准元素小的元素,将high指向的元素放到low的位置上,此时high指向的位置空着,接下来移动low找到符合条件的元素放在此处
      # 如果low与high未重合，low指向的元素比基准元素小，则low向右移动
      while low < high and alist[low] < mid:
         low += 1
      alist[high] = alist[low]  # 此时low指向一个比基准元素大的元素,将low指向的元素放到high空着的位置上,此时low指向的位置空着,之后进行下一次循环,将high找到符合条件的元素填到此处

# 退出循环后，low与high重合，此时所指位置为基准元素的正确位置,左边的元素都比基准元素小,右边的元素都比基准元素大
alist[low] = mid  # 将基准元素放到该位置,
# 对基准元素左边的子序列进行快速排序
quick_sort(alist, start, low - 1)  # start :0  low -1 原基准元素靠左边一位
# 对基准元素右边的子序列进行快速排序
quick_sort(alist, low + 1, end)  # low+1 : 原基准元素靠右一位  end: 最后

if __name__ == &#39;__main__&#39;:
alist = [54, 26, 93, 17, 77, 31, 44, 55, 20]
quick_sort(alist, 0, len(alist) - 1)
print(alist)常用排序平均最优最坏时间复杂度以及空间复杂度

排序算法的内存消耗
· 原地排序（Sorted in place）：特指空间复杂度为 O(1) 的排序算法
· 算法的内存消耗可以通过空间复杂度来衡量
如何选择合适的排序算法？
对小规模数据进行排序，可以选择时间复杂度是 O(n^2) 的算法
对大规模数据进行排序，时间复杂度是 O(nlogn) 的算法更加高效
为了兼顾任意规模数据的排序，一般都会首选时间复杂度是 O(nlogn) 的排序算法来实现排序函数
如何优化快速排序？
快速排序出现 O(n^2)时间复杂度的主要原因是因为分区节点选择不够合理
最理想的分区节点是：被分区点分开的两个分区中，数据的数量差不多
方法
1、三数取中法（五数取中、十数取中等）：从区间的首、尾、中间，分别取出一个数，然后对比大小，取这 3 个数的中间值作为分区点
2、随机法：每次从要排序的区间中，随机选择一个元素作为分区点

阐述快排和归并的优缺点以及回答为什么排序要稳定？

排序算法的稳定性
稳定的排序算法：指待排序的序列中存在值相等的元素时，经过排序后，相等元素之间原有的先后顺序不变
PS：二者各自的特点。
      快速排序最快的排序算法，缺点是不稳定，不适合对象排序；
      归并排序第二块的算法，缺点是辅存很大，适合对象排序；
快速排序递归堆栈空间的占用：
      最优的情况下空间复杂度为：O(logn)  ；每一次都平分数组的情况
最差的情况下空间复杂度为：O(n )；退化为冒泡排序的情况

归并排序的最坏时间复杂度优于快排，为什么我们还是选择快排？

快速排序和归并排序的时间复杂度都是O(N lgN)，实践证明快速排序的速度比归并排序的速度更快，另外其实这个结论是有限制范围的，当对数组进行排序的时候，这个结论适用。为什么对于链表，却是归并排序的速度优于快速排序呢？快速排序的主要效率来源之一是引用位置，在引用位置，计算机硬件经过优化，因此访问彼此相邻的内存位置往往比访问分散在内存中的内存位置要快。快速排序中的分区步骤通常具有很好的局部性，因为它访问前后附近的连续数组元素。因此，快速排序往往比其他排序算法（如heapsort）的性能要好得多，尽管它通常执行大致相同数量的比较和交换，因为在heapsort的情况下，访问更加分散。
此外，快速排序通常比其他排序算法快得多，因为它可以就地操作，而不需要创建任何辅助数组来保存临时值。与merge-sort相比，这是一个巨大的优势，因为分配和取消分配辅助数组所需的时间是显而易见的。就地操作也提高了quicksort的位置。
在使用链表时，这些优点都不一定适用。因为链表单元常常分散在内存中，所以访问相邻的链表单元并没有局部性奖励。因此，quicksort的一个巨大性能优势被蚕食了。类似地，就地工作的好处不再适用，因为merge-sort的链表算法不需要任何额外的辅助存储空间。
也就是说，快速排序在链表上仍然非常快。合并排序往往更快，因为它更平均地将列表一分为二，而且每次迭代执行合并的工作量比执行分区步骤的工作量要少。

TopK问题详解

在一堆数据里面找到前 K 大（当然也可以是前 K 小）的数。
面对海量数据，我们就可以放分布式的方向去思考了  我们可以将数据分散在多台机器中，然后每台机器并行计算各自的 TopK 数据，最后汇总，再计算得到最终的 TopK 数据  这种数据分片的分布式思想在面试中非常值得一提，在实际项目中也十分常见  四. 利用最经典的方法，一台机器也能处理海量数据  其实提到 Top K 问题，最经典的解法还是利用堆。  维护一个大小为 K 的小顶堆，依次将数据放入堆中，当堆的大小满了的时候，只需要将堆顶元素与下一个数比较：如果大于堆顶元素，则将当前的堆顶元素抛弃，并将该元素插入堆中。遍历完全部数据，Top K 的元素也自然都在堆里面了。  当然，如果是求前 K 个最小的数，只需要改为大顶堆即可

对于海量数据，我们不需要一次性将全部数据取出来，可以一次只取一部分，因为我们只需要将数据一个个拿来与堆顶比较。  另外还有一个优势就是对于动态数组，我们可以一直都维护一个 K 大小的小顶堆，当有数据被添加到集合中时，我们就直接拿它与堆顶的元素对比。这样，无论任何时候需要查询当前的前 K 大数据，我们都可以里立刻返回给他。  整个操作中，遍历数组需要 O(n) 的时间复杂度，一次堆化操作需要 O(logK)，加起来就是 O(nlogK) 的复杂度，换个角度来看，如果 K 远小于 n 的话， O(nlogK) 其实就接近于 O(n) 了，甚至会更快，因此也是十分高效的。
如何判断图里有环？

【算法】如何确定图（Graph）里有没有环（Cycle）？ - 云+社区 - 腾讯云 (tencent.com)

C++中new和malloc的区别

最大的区别：new在申请空间的时候会调用构造函数，malloc不会调用
申请失败返回：new在申请空间失败后返回的是错误码bad_alloc，malloc在申请空间失败后会返回NULL
属性上：new/delete是C++关键字需要编译器支持，maollc是库函数，需要添加头文件
参数：new在申请内存分配时不需要指定内存块大小，编译器会更具类型计算出大小，malloc需要显示的指定所需内存的大小
成功返回类型：new操作符申请内存成功时，返回的是对象类型的指针，类型严格与对象匹配，无需进行类型转换，因此new是类型安全性操作符。malloc申请内存成功则返回void*，需要强制类型转换为我们所需的类型
自定义类型：new会先调operator new函数，申请足够的内存（底层也是malloc实现），然后调用类的构造函数，初始化成员变量，最后返回自定义类型指针。delete先调用析构函数，然后调用operator delete函数来释放内存（底层是通过free实现）。malloc/free是库函数，只能动态的申请和释放内存，无法强制要求其做自定义类型对象构造和析构函数
重载：C++允许重载new/delete操作符，特别的，布局new的就不需要为对象分配内存，而是指定了一个地址作为内存起始区域，new在这段内存上为对象调用构造函数完成初始化工作，并返回地址。malloc不允许重载。

进制计算，搜索，数论。语言C++和Java，Python
重点知识点：字符操作；进制转化；动态规划（这个太爱考了）；搜索（DSP/BSP）;二分搜索；贪心；栈；链表；二叉树简单的（比如前后中缀表达式转换，求个深度广度什么的）；数论（这玩意儿难的可以难死人，建议看一些快速幂，欧几里得给自己心里个底）

树的遍历

排列组合

		自动登录	找回密码
密码			立即注册

数据结构

本帖子中包含更多资源