必备知识架构-算法

[toc]

稳定与不稳定：如果a原本在b的前面并且a=b，排序之后a仍然在b的前面那就是稳定排序，如果排序之后a可能会出现在b的后面则是不稳定排序。所以冒泡排序是稳定的。选择排序可能不稳定。

空间复杂度：是指算法在计算机内执行时所需的存储空间与n的规模之间的关系。

时间复杂度：排序的的总操作次数，与n的规模之间的关系。

以下是我们在面试中要问的主要问题：

1.数据结构：
a、 链表
b、 堆叠
c、 排队
d、 二叉树
e、 哈希表

2.算法：
a、 排序（像快速排序和归并排序），二分搜索法，贪婪算法。
b、 二叉树（比如遍历、构造、操作…）

iOS 开发中常用的排序（冒泡、选择、快速、插入、希尔、归并、基数）算法

排序算法 平均时间复杂度 其他时间复杂度 平均空间复杂度 是否是稳定性的
冒泡排序 O(n^2) 最好：O(n)，已是有序的
最坏：O(n^2)，是逆序的		 O(1) 稳定
选择排序 O(n^2) —— O(1) 不稳定
快速排序 O(nlogn) 最好：O(nlogn)，每次划分都非常平衡时
最坏：O(n^2)，每次划分非常不均匀时		 O(nlogn) 不稳定
不稳定发生在交换的时刻；
归并排序 O(nlogn) —— O(n) 稳定

因为冒泡和选择排序都是原地排序算法，不需要额外的存储空间。所以其空间复杂度都是O(1)。

归并排序需要额外的空间来存储合并过程中的临时数组，其空间复杂度O(n)。

11.5.3 快速排序为什么快

在Object-C中学习数据结构与算法之排序算法

二分搜索法，是一种【在有序数组中】查找某一特定元素的搜索算法。

iOS查找算法之二分查找

漫画：五分钟学会贪心算法

有一个背包，最多能承载150斤的重量，现在有7个物品，
重量分别为[35, 30, 60, 50, 40, 10, 25]，
价值分别为[10, 40, 30, 50, 35, 40, 30]，
应该如何选择才能使得我们的背包背走最多价值的物品？

局部最优解

1、每次都尽量选择当前【价值最高】的物品
重量分别为[35, 30🚗, 60, 50🚗, 40🚗, 10🚗, 25]， 130
价值分别为[10, 40②✅, 30, 50①✅, 35④✅, 40③✅, 30]， 165

2、每次都尽量选择当前【重量最小】的物品
重量分别为[35④, 30③, 60, 50, 40⑤, 10①, 25②]， 140
价值分别为[10✅,40✅, 30, 50, 35✅, 40✅, 30✅]， 155

3、每次都尽量选择当前【价值密度最高】的物品
重量分别为[35🚗, 30🚗, 60, 50🚗, 40, 10🚗, 25🚗]， 150
价值分别为[10✅, 40✅, 30, 50✅, 35, 40✅, 30✅]， 170
价值密度 [0.285⑤, 1.333②, 0.5, 1.0④, 0.875, 4.0①, 1.2③]

想象一下下列场景：

  1. 从通讯录中寻找某个联系人
  2. 从一大堆文件中寻找某个文件
  3. 到了影厅之后，寻找电影票上指定的座位

如果以上情况中，联系人、文件、影厅座位这些“数据”没有按照需要的顺序组织，如何找到想要的特定“数据”呢？会非常麻烦！所以说，对于需要搜索的数据，往往应该先排个序！

排序比较 & 对比归并排序与快速排序

image-20240902163103782

前言

1
2
3
4
5
6
// 交换数组中的两个元素
void swap(NSMutableArray *array, NSInteger i, NSInteger j) {
    NSNumber *temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}

算法图解

《034-Data-AlgorithmCollect-iOS》

Data-AlgorithmCollect-1

一、冒泡排序

实现一个冒泡排序或者快速排序

从小到大排序：

1
2
3
4
5
6
7
8
9
10
11
12
13
假设45132，按从小到大排序
i = 0 的时候，j的相邻两个位置都要比较排一下位置：
         j = 0 的时候：arr_M = 45132(a[0]和a[1]比得到的结果)
         j = 1 的时候：arr_M = 41532(a[1]和a[2]比得到的结果)
         j = 2 的时候：arr_M = 41352(a[2]和a[3]比得到的结果)
         j = 3 的时候：arr_M = 41325(a[3]和a[4]比得到的结果)
i=0已经将第一个最大的值放到最后了。

i = 1 的时候，j的相邻两个位置都要比较排一下位置：
         j = 0 的时候：arr_M = 14325
         j = 1 的时候：arr_M = 13425
         j = 2 的时候：arr_M = 13245
i=1已经将第二个最大的值放到最后了。

冒泡排序代码实现

二、选择排序

从数组的第a[i+1]个元素开始到第n个元素，寻找最小的元素(的位置)。（具体过程为:先设最小位置为i=0，从该位置往后逐一比较，若遇到比之小的则记下该最小值的位置，结束后交换）；

先为a[0]取到最小值，再为a[1]取到最小值，再继续…..

从小到大排序：

1
2
3
4
5
6
7
8
9
10
11
12
13
假设45132，按从小到大排序
i = 0 的时候，j的相邻两个位置都要比较排一下位置：
     j = i+1=1 的时候：arr_M = 45132(此时a[0]的4和a[1]的5比较：得到的结果)
         j = 2 的时候：arr_M = 15432(此时a[0]的4和a[2]的1比较：得到的结果)
         j = 3 的时候：arr_M = 15432(此时a[0]的1和a[3]的3比较：得到的结果)
         j = 4 的时候：arr_M = 15432(此时a[0]的1和a[4]的2比较：得到的结果)
i=0已经将第一个最小的值放到第一位了。

i = 1 的时候，j的相邻两个位置都要比较排一下位置：
         j = 2 的时候：arr_M = 14532(a[1]和a[2]比得到的结果)
         j = 3 的时候：arr_M = 13542(a[1]和a[3]比得到的结果)
         j = 4 的时候：arr_M = 12543(a[1]和a[4]比得到的结果)
i=1已经将第二个最小的值放到最第二位了。

选择排序代码实现

三、快速排序

漫画：什么是快速排序？（完整版）

快速排序（Quicksort）是对冒泡排序的一种改进。

同冒泡排序一样，快速排序也属于交换排序，通过元素之间的比较和交换位置来达到排序的目的。

不同的是，冒泡排序在每一轮只把一个元素冒泡到数列的一端，而快速排序在每一轮挑选一个基准元素，并让其他比它大的元素移动到数列一边，比它小的元素移动到数列的另一边，从而把数列拆解成了两个部分。这种思路就叫做分治法。

1
2
3
4
5
6
7
8
// 快速排序函数 quickSort(array, 0, [array count] - 1);
void quickSort(NSMutableArray *array, NSInteger left, NSInteger right) {
    if (left < right) {
        NSInteger pivotIndex = partition(array, left, right);
        quickSort(array, left, pivotIndex - 1);
        quickSort(array, pivotIndex + 1, right);
    }
}

快速排序代码实现

1、排序原理：

设要排序的数组是A[0]……A[N-1]，首先任意选取一个数据（通常选用数组的第一个数）作为关键数据，

快排图快排图

然后将所有比它小的数都放到它左边，所有比它大的数都放到它右边，这个过程称为一趟快速排序。

2、排序流程

快速排序算法通过多次比较和交换来实现排序，其排序流程如下：

(1)首先设定一个分界值，通过该分界值将数组分成左右两部分。

(2)将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值。

(3)然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。

(4)重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。

四、归并排序

Hello 算法 11.6 归并排序

图解排序算法(四)之归并排序

1、划分阶段：通过递归不断地将数组从中点处分开（以把序列分成元素尽可能相等的两半），将长数组的排序问题转换为短数组的排序问题。当子数组长度为 1 时终止划分，开始合并。

归并排序

归并排序思路简单，速度仅次于快速排序，为稳定排序算法，一般用于对总体无序，但是各子项相对有序的数列。

2、合并阶段：持续地将左右两个较短的有序数组合并为一个较长的有序数组，直至结束。

归并排序的合并过程如下：

  1. 初始化：创建两个指针，分别指向两个已排序数组的起始位置。
  2. 比较元素：比较两个指针所指向的元素。
  3. 选择较小元素：将较小的元素放入临时数组，并移动该元素所在数组的指针。
  4. 重复比较：重复步骤2和3，直到其中一个数组的所有元素都被比较过。
  5. 复制剩余元素：如果一个数组的所有元素都已经被比较并复制到临时数组中，将另一个数组中剩余的元素直接复制到临时数组的末尾。
  6. 返回临时数组：临时数组现在是一个合并后的有序数组。

示例：要将[4,5,7,8]和[1,2,3,6]两个已经有序的子序列，合并为最终序列[1,2,3,4,5,6,7,8]，来看下实现步骤。

img

附：深度优先遍历(DFS)和广度优先遍历(BFS)

深度优先遍历(Depth First Search, 简称 DFS)

img

广度优先遍历（Breath First Search, 简称 BFS） 也叫层序遍历，指的是从图的一个未遍历的节点出发，先遍历这个节点的相邻节点，再依次遍历每个相邻节点的相邻节点。

BFS 一般是解决最短路径问题。

img

iOS算法篇-leetcode题目记录

附：排序算法代码

1、冒泡排序代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
- (void)methodMaopao {
  int array[5] = {4, 5, 1, 3, 2};
    
  for (int i = 0; i < 5-1; i++) { //需要比较几遍
      for(int j = 0; j < 5-1-i; j++) { //每一遍都从0开始到倒数第-i个
          if (array[j] > array [j + 1]){
              int temp = array[j];
              array[j] = array[j + 1];
              array[j + 1] = temp;
          }
      }
  }

  for(int i = 0; i < 5; i++) {
      printf("%d\n",array[i]);
  }
}

2、选择排序代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func sort(items: Array<Int>) -> Array<Int> {
    var list = items
    for i in 0..<list.count {
    		//记录当前最小的数，比较i+1后更大的数进行记录
        var minIndex = i
        for j in i+1..<list.count {
            if list[j] < list[minIndex] {
                minIndex = j
            }
        }
        // 交换
        let temp = list[minIndex]
        list[minIndex] = list[i]
        list[i] = temp
    }
    return list
}

3、快速排序代码实现

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
//单趟 快速排序挖坑法
int PartSort2(int* a, int left, int right)
{
	if (left >= right) return left;
 
  int begin = left;
	int end = right;
	int key = a[left]; //保存要排序的值
	while (begin < end) //当左右指针相遇时结束
	{
    // begin是坑，从后往前找比key小的值填到坑里
		while (begin < end && a[end] >= key) {
			end--;
		}
		a[begin] = a[end];
    
    // 此时end位置是坑，从前往后比key大的值填到坑中
		while (begin < end && a[begin] <= key) {
			begin++;
		}
		a[end] = a[begin];
	}
 
	//begin和end相遇的地方是key对应的位置
	a[end] = key;
	return end; //返回排好位置的元素的下标
}

END

< 返回目录