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、通過穩定性分類

穩定的排序演算法會依照相等的關鍵（換言之就是值）維持紀錄的相對次序。