offerme数据结构排序算法

1. 数据结构--归并排序与基数排序

一、归并排序
归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。将两个或以上的有序表组合成一个新的有序表。
1、2-路归并排序
初始序列含有n个记录，可看成n个有序的子序列，每个子序列的长度为1，然后两两归并，得到[n/2]个长度为2或1的有序子序列，再两两归并，如此重复，直至得到一个长度为n的有序序列为止。
2、举例

上图中的最后一次合并，要将[4,5,7,8]和[1,2,3,6]两个已经有序的子序列，合并为最终序列[1,2,3,4,5,6,7,8]，实现步骤：

Tips：
排序算法的稳定性：保证排序前2个相等的数，在序列中的前后位置顺序和排序后它们两个的前后位置顺序相同。例如，Ai = Aj，Ai排序前位于Aj的前面，排序后Ai还位于Aj的前面。
稳定性的好处：排序算法如果是稳定的，那么从一个键上排序，然后再从另一个键上排序，第一个键排序的结果可以为第二个键排序所用。基数排序就 是这样，先按低位排序，逐次按高位排序，低位相同的元素其顺序再高位也相同时是不会改变的。
排序算法是否为稳定的是由具体算法决定的，不稳定的算法在某种条件下可以变为稳定的算法，而稳定的算法在某种条件下也可以变为不稳定的算法。
例如，对于如下冒泡排序算法，原本是稳定的排序算法，如果将记录交换的条件改成r[j]>=r[j+1]，则两个相等的记录就会交换位置，从而变成不稳定的算法。

堆排序、快速排序、希尔排序、直接选择排序不是稳定的排序算法，而基数排序、冒泡排序、直接插入排序、折半插入排序、归并排序是稳定的排序算法。

一、基数排序
基数排序是一种借助多关键字排序的思想对单逻辑关键字进行排序的方法。
1、什么是多关键字
已知扑克牌中52张牌面的次序关系为：

1、最高位优先于最低位优先

假设有n个记录的序列{R ₁ ，R ₂ ，...R _n }，且每个记录R _i 中含有d个关键字(K _i ¹ ，K _i ² ，...，K _i ^d )，序列{R ₁ ，R ₂ ，...R _n }对关键字(K ¹ ，K ² ，...，K ^d )有序是指：对于序列中任意两个记录R _i 和R _j (1 <= i < j <= n)都满足下列有序关系：(K _i ¹ ，K _i ² ，...，K _i ^d )<(K _j ¹ ，K _j ² ，...，K _j ^d )，其中K ¹ 称为最高位关键字，K ^d 称为最低位关键字。

实现多关键字排序的方法：
A、先对最高位关键字K ¹ 进行排序，间序列分成若干子序列，每个子序列中的记录都具有相同的K ¹ 值，然后分别对每个子序列对关键字K ² 进行排序，按K ² 值不同再分成若干更小的子序列，依次重复，直到对K ^d-1 进行排序后得到的每一子序列中的记录都具有相同的关键字(K ¹ ，K ² ，...，K ^d-1 )，而后每个子序列分别对K ^d 进行排序，最后将所要子序列依次连接在一起成为一个有序序列，这种方法为“最高位优先(MSD)”
B、先从最低位关键字K ^d 进行排序，在对高一位的关键字K ^d-1 进行排序，依次重复，直至对K ¹ 进行排序后便成为一个有序序列。这种方法称为“最低位优先(LSD)”。

三、内部排序方法的比较

结论：
1、表中的“简单排序”指：除希尔排序外的所有插入排序，冒泡排序和简单选择排序，其中之间插入排序最简单，当序列中的记录“基本有序”或n值较小时，它是最佳的排序方法，因此常将他和其他排序方法（快排，归并排序）结合在一起使用。
2、从平均时间性能看，快排最省时间，但他在最坏情况下的时间性能不如堆排序和归并排序。在n较大，归并排序所需时间比堆排序少，但所需的辅助存储量最多。
3、基数排序适用于n值很大且关键字较小的序列。

2. 数据结构中比较各种排序算法 求详解 ，，，，，，，，，，

排序算法包括：插入排序、交换排序、选择排序以及合并排序。

其中插入排序包括直接插入排序和Shell排序，交换排序包括冒泡排序和分化交换排序，选择排序包括直接选择排序和堆排序。

这些排序算法中，直接插入排序、冒泡排序和直接选择排序这三种排序的算法平均时间复杂度是O(n的平方)；分化交换排序、堆排序和合并排序这三种排序的算法平均时间复杂度是

3. 数据结构的排序方法有哪些

冒泡排序，快速排序，堆排序。

4. iOS开发面试拿offer攻略之数据结构与算法篇附加安全加密

集合结构 线性结构 树形结构 图形结构

1.1、集合结构 说白了就是一个集合，就是一个圆圈中有很多个元素，元素与元素之间没有任何关系 这个很简单

1.2、线性结构 说白了就是一个条线上站着很多个人。 这条线不一定是直的。也可以是弯的。也可以是值的 相当于一条线被分成了好几段的样子 （发挥你的想象力）。 线性结构是一对一的关系

1.3、树形结构 说白了 做开发的肯定或多或少的知道 xml 解析 树形结构跟他非常类似。也可以想象成一个金字塔。树形结构是一对多的关系

1.4、图形结构 这个就比较复杂了。他呢 无穷。无边 无向（没有方向）图形机构 你可以理解为多对多 类似于我们人的交集关系

数据结构的存储

数据结构的存储一般常用的有两种 顺序存储结构 和 链式存储结构

2.1 顺序存储结构

发挥想象力啊。 举个列子。数组。1-2-3-4-5-6-7-8-9-10。这个就是一个顺序存储结构 ，存储是按顺序的 举例说明啊。 栈，做开发的都熟悉。栈是先进后出 ，后进先出的形式 对不对 ？

他的你可以这样理解， hello world 在栈里面从栈底到栈顶的逻辑依次为 h-e-l-l-o-w-o-r-l-d 这就是顺序存储，再比如队列 ，队列是先进先出的对吧，从头到尾 h-e-l-l-o-w-o-r-l-d 就是这样排对的

2.2 链式存储结构

再次发挥想象力 这个稍微复杂一点 这个图片我一直弄好 ，回头找美工问问，再贴上 例如 还是一个数组 1-2-3-4-5-6-7-8-9-10 链式存储就不一样了 1(地址)-2(地址)-7(地址)-4(地址)-5(地址)-9(地址)-8(地址)-3(地址)-6(地址)-10(地址)。每个数字后面跟着一个地址 而且存储形式不再是顺序 ，也就说顺序乱了，1（地址） 1 后面跟着的这个地址指向的是 2，2 后面的地址指向的是 3，3 后面的地址指向是谁你应该清楚了吧。他执行的时候是 1(地址)-2(地址)-3(地址)-4(地址)-5(地址)-6(地址)-7(地址)-8(地址)-9(地址)-10(地址)，但是存储的时候就是完全随机的。明白了？

单向链表双向链表循环链表

还是举例子。理解最重要。不要去死记硬背 哪些什么。定义啊。逻辑啊。理解才是最重要滴

3.1 单向链表

A->B->C->D->E->F->G->H . 这就是单向链表 H 是头 A 是尾 像一个只有一个头的火车一样 只能一个头拉着跑

3.2 双向链表

数组和链表区别：

数组：数组元素在内存上连续存放，可以通过下标查找元素；插入、删除需要移动大量元素，比较适用元素很少变化的情况

链表：链表中的元素在内存中不是顺序存储的，查找慢，插入、删除只需要对元素指针重新赋值，效率高

3.3 循环链表

循环链表是与单向链表一样，是一种链式的存储结构，所不同的是，循环链表的最后一个结点的指针是指向该循环链表的第一个结点或者表头结点，从而构成一个环形的链。发挥想象力 A->B->C->D->E->F->G->H->A . 绕成一个圈。就像蛇吃自己的这就是循环 不需要去死记硬背哪些理论知识。

二叉树／平衡二叉树

4.1 什么是二叉树

树形结构下,两个节点以内 都称之为二叉树 不存在大于 2 的节点 分为左子树 右子树 有顺序 不能颠倒 ，懵逼了吧，你肯定会想这是什么玩意，什么左子树右子树 ，都什么跟什么鬼？ 现在我以普通话再讲一遍，你把二叉树看成一个人 ，人的头呢就是树的根 ，左子树就是左手，右子树就是右手，左右手可以都没有（残疾嘛，声明一下，绝非歧视残疾朋友，勿怪，勿怪就是举个例子， I am very sorry ） , 左右手呢可以有一个，就是不能颠倒。这样讲应该明白了吧

二叉树有五种表现形式

1.空的树（没有节点）可以理解为什么都没 像空气一样

2.只有根节点。 （理解一个人只有一个头 其他的什么都没，说的有点恐怖）

3.只有左子树 （一个头 一个左手 感觉越来越写不下去了）

4.只有右子树

5.左右子树都有

二叉树可以转换成森林 树也可以转换成二叉树。这里就不介绍了 你做项目绝对用不到数据结构大致介绍这么多吧。理解为主, 别死记，死记没什么用

1、不用中间变量,用两种方法交换 A 和 B 的值

2、****求最大公约数

3、模拟栈操作

栈是一种数据结构，特点：先进后出 -

练习：使用全局变量模拟栈的操作

#include <stdio.h>

#include <stdbool.h>

#include <assert.h>

//保护全局变量：在全局变量前加 static 后，这个全局变量就只能在本文件中使用 static int data[1024] ;//栈最多能保存 1024 个数据

static int count = 0 ;//目前已经放了多少个数(相当于栈顶位置)

4、排序算法

选择排序、冒泡排序、插入排序三种排序算法可以总结为如下：

都将数组分为已排序部分和未排序部分。

1.选择排序将已排序部分定义在左端，然后选择未排序部分的最小元素和未排序部分的第一个元素交换。

2.冒泡排序将已排序部分定义在右端，在遍历未排序部分的过程执行交换，将最大元素交换到最右端。

3.插入排序将已排序部分定义在左端，将未排序部分元的第一个元素插入到已排序部分合适的位置。

4.1、选择排序

【选择排序】：最值出现在起始端

第 1 趟：在 n 个数中找到最小(大)数与第一个数交换位置

第 2 趟：在剩下 n-1 个数中找到最小(大)数与第二个数交换位置

重复这样的操作...依次与第三个、第四个...数交换位置

第 n-1 趟，最终可实现数据的升序（降序）排列。

4.2、冒泡排序

【冒泡排序】：相邻元素两两比较，比较完一趟，最值出现在末尾

第 1 趟：依次比较相邻的两个数，不断交换（小数放前，大数放后）逐个推进，最值最后出现在第 n 个元素位置

第 2 趟：依次比较相邻的两个数，不断交换（小数放前，大数放后）逐个推进，最值最后出现在第 n-1 个元素位置

…… ……

第 n-1 趟：依次比较相邻的两个数，不断交换（小数放前，大数放后）逐个推进，最值最后出现在第 2 个元素位置

5、折半查找（二分查找）

折半查找：优化查找时间（不用遍历全部数据） 折半查找的原理：

1.数组必须是有序的

2.必须已知 min 和 max （知道范围）

// 已知一个有序数组, 和一个 key , 要求从数组中找到 key 对应的索引位置

字符串反转

给定字符串 " hello,world ",实现将其反转。输出结果： dlrow , olleh

序数组合并

将有序数组 {1,4,6,7,9} 和 {2,3,5,6,8,9,10,11,12} 合并为{1,2,3,4,5,6,6,7,8,9,9,10,11,12}

HASH 算法

哈希表

例：给定值是字母 a ，对应 ASCII 码值是 97，数组索引下标为 97。

这里的 ASCII 码，就算是一种哈希函数，存储和查找都通过该函数，有效地提高查找效率。

在一个字符串中找到第一个只出现一次的字符。如输入" abaccdeff "，输出' b '字符( char )是一个长度为 8 的数据类型，因此总共有 256 种可能。每个字母根据其 ASCII 码值作为数组下标对应数组种的一个数字。数组中存储的是每个字符出现的次数。

查找两个子视图的共同父视图

思路:分别记录两个子视图的所有父视图并保存到数组中，然后倒序寻找,直至找到第一个不一样的父视图。

求无序数组中的中位数

中位数：当数组个数 n 为奇数时，为 (n + 1)/2 ，即是最中间那个数字；当 n 为偶数时，为 (n/2 + (n/2 + 1))/2 , 即是中间两个数字的平均数。

首先要先去了解一些几种排序算法: iOS 排序算法

思路:

1.排序算法+中位数

首先用冒泡排序、快速排序、堆排序、希尔排序等排序算法将所给数组排序，然后取出其中位数即可。

2.利用快排思想

1、简述 SSL 加密的过程用了哪些加密方法，为何这么作？

SSL 加密的过程之前有些过，此处不再赘述。

SSL 加密，在过程中实际使用了 对称加密 和 非对称加密 的结合。

主要的考虑是先使用 非对称加密 进行连接，这样做是为了避免中间人攻击秘钥被劫持，但是 非对称加密的效率比较低。所以一旦建立了安全的连接之后，就可以使用轻量的 对称加密。

2、RSA 非对称加密

对称加密[算法]在加密和解密时使用的是同一个秘钥；而[非对称加密算法]需要两个[密钥]来进行加密和解密，这两个秘钥是[公开密钥]（ public key ，简称公钥）和私有密钥（ private key ，简称私钥）。

RSA 加密

与对称加密[算法]不同，[非对称加密算法]需要两个[密钥]：[公开密钥]（ publickey ）和私有密钥（ privatekey ）。公开密钥与私有密钥是一对，如果用公开密钥对数据进行加密，只有用对应的私有密钥才能解密；如果用私有密钥对数据进行加密，那么只有用对应的公开密钥才能解密。因为加密和解密使用的是两个不同的[密钥]，所以这种算法叫作[非对称加密算法]。

RSA**** 加密原理

RSA 是常用的加密模式，其加密原理可用以下的例子进行简要的论述。

随机取两个质数

以上就是本篇所整理的，感谢观看！

5. 数据结构的排序算法中，哪些排序是稳定的，哪些排序是不稳定的

一、稳定排序算法

1、冒泡排序

2、鸡尾酒排序

3、插入排序

4、桶排序

5、计数排序

6、合并排序

7、基数排序

8、二叉排序树排序

二、不稳定排序算法

1、选择排序

2、希尔排序

3、组合排序

4、堆排序

5、平滑排序

6、快速排序

排序(Sorting) 是计算机程序设计中的一种重要操作，它的功能是将一个数据元素（或记录）的任意序列，重新排列成一个关键字有序的序列。

一个排序算法是稳定的，就是当有两个相等记录的关键字R和S，且在原本的列表中R出现在S之前，在排序过的列表中R也将会是在S之前。

不稳定排序算法可能会在相等的键值中改变纪录的相对次序，但是稳定排序算法从来不会如此。不稳定排序算法可以被特别地实现为稳定。

做这件事情的一个方式是人工扩充键值的比较，如此在其他方面相同键值的两个对象间之比较，就会被决定使用在原先数据次序中的条目，当作一个同分决赛。然而，要记住这种次序通常牵涉到额外的空间负担。

(5)offerme数据结构排序算法扩展阅读：

排序算法的分类：

1、通过时间复杂度分类

计算的复杂度（最差、平均、和最好性能），依据列表(list)的大小(n)。

一般而言，好的性能是 O(nlogn)，且坏的性能是 O(n^2)。对于一个排序理想的性能是 O(n)。

而仅使用一个抽象关键比较运算的排序算法总平均上总是至少需要 O(nlogn)。

2、通过空间复杂度分类

存储器使用量（空间复杂度）（以及其他电脑资源的使用）

3、通过稳定性分类

稳定的排序算法会依照相等的关键（换言之就是值）维持纪录的相对次序。