2019 iOS面試題大全---全方面剖析面試
2018 iOS面試題---算法相關(guān)
1、七種常見的數(shù)組排序算法整理(C語(yǔ)言版本)
2组贺、2019 算法面試相關(guān)(leetcode)--數(shù)組和鏈表
3、2019 算法面試相關(guān)(leetcode)--字符串
4祖娘、2019 算法面試相關(guān)(leetcode)--棧和隊(duì)列
5失尖、2019 算法面試相關(guān)(leetcode)--優(yōu)先隊(duì)列
6、2019 算法面試相關(guān)(leetcode)--哈希表
7、2019 算法面試相關(guān)(leetcode)--樹雹仿、二叉樹增热、二叉搜索樹
8、2019 算法面試相關(guān)(leetcode)--遞歸與分治
9胧辽、2019 算法面試相關(guān)(leetcode)--貪心算法
10峻仇、2019 算法面試相關(guān)(leetcode)--動(dòng)態(tài)規(guī)劃(Dynamic Programming)
11、2019 算法面試相關(guān)(leetcode)--動(dòng)態(tài)規(guī)劃之背包問題
～～～C語(yǔ)言版本～～～
- 冒泡排序
- 選擇排序
- 直接插入排序
- 二分插入排序
- 希爾排序
- 快速排序
- 堆排序
#define EXCHANGE(num1, num2) { num1 = num1 ^ num2;\
num2 = num1 ^ num2;\
num1 = num1 ^ num2;}
排序算法是否穩(wěn)定:相同元素的相對(duì)在排序前后是否會(huì)發(fā)生改變邑商，如果會(huì)摄咆，就是不穩(wěn)定的，否則就是穩(wěn)定的人断。
一.冒泡排序
冒泡排序原理很容易理解吭从，就是重復(fù)地走訪過要排序的元素列，依次比較兩個(gè)相鄰的元素恶迈，順序不對(duì)就交換涩金，直至沒有相鄰元素需要交換，也就是排序完成暇仲。
這個(gè)算法的名字由來(lái)是因?yàn)樵酱蟮脑貢?huì)經(jīng)由交換慢慢“浮”到數(shù)列的頂端（升序或降序排列）步做，就如同碳酸飲料中二氧化碳的氣泡最終會(huì)上浮到頂端一樣，故名“冒泡排序”奈附。
- 冒泡排序是一種穩(wěn)定排序算法全度。
- 時(shí)間復(fù)雜度:最好情況(初始情況就是正序)下是o(n),平均情況是o(n2)
void buddleSort(int num[],int count)
{
for (int i = 0; i < count - 1; i++) {
for (int j = 0; j < count - i - 1; j++) {
if (num[j] > num[j + 1]) EXCHANGE(num[j], num[j + 1])
}
}
}
二、選擇排序
選擇排序（Selection sort）是一種簡(jiǎn)單直觀的排序算法斥滤。它的工作原理是每一次從待排序的數(shù)據(jù)元素中選出最薪摇（或最大）的一個(gè)元素，存放在序列的起始位置佑颇，然后顶掉，再?gòu)氖Ｓ辔磁判蛟刂欣^續(xù)尋找最小（大）元素漩符，然后放到已排序序列的末尾一喘。以此類推驱还，直到全部待排序的數(shù)據(jù)元素排完嗜暴。
選擇排序的交換操作介于 0 和 (n - 1） 次之間。選擇排序的比較操作為 n (n - 1） / 2 次之間议蟆。選擇排序的賦值操作介于 0 和 3 (n - 1） 次之間闷沥。
比較次數(shù)O(n2），比較次數(shù)與關(guān)鍵字的初始狀態(tài)無(wú)關(guān)咐容，總的比較次數(shù)N=(n-1）+(n-2）+...+1=n*(n-1）/2舆逃。交換次數(shù)O(n），最好情況是，已經(jīng)有序路狮，交換0次虫啥；最壞情況交換n-1次，逆序交換n/2次奄妨。交換次數(shù)比冒泡排序少多了涂籽，由于交換所需CPU時(shí)間比比較所需的CPU時(shí)間多，n值較小時(shí)砸抛，選擇排序比冒泡排序快
- 選擇排序是不穩(wěn)定的排序方法评雌。
- 時(shí)間復(fù)雜度：最好和平均情況下都是O(n2）
void selectSort(int num[],int count)
{
for (int i = 0; i < count; i++) {
int min = i;
for (int j = i; j < count; j++) {
if (num[j] < num[min]) min = j;
}
if (i != min) EXCHANGE(num[i], num[min]);//可以看出，最多交換count - 1次
}
}
三直焙、直接插入排序
插入排序的基本操作就是將一個(gè)數(shù)據(jù)插入到已經(jīng)排好序的有序數(shù)據(jù)中景东，從而得到一個(gè)新的、個(gè)數(shù)加一的有序數(shù)據(jù)奔誓，算法適用于少量數(shù)據(jù)的排序斤吐，
插入排序的基本思想是：每步將一個(gè)待排序的記錄，按其關(guān)鍵碼值的大小插入前面已經(jīng)排序的文件中適當(dāng)位置上厨喂，直到全部插入完為止
- 直接插入排序是穩(wěn)定的排序算法曲初。
- 時(shí)間復(fù)雜度：最好情況(初始情況就是正序)下是o(n),平均情況是o(n2)
void insertSort2(int num[],int count)
{
int i,j;
for (i = 1; i < count; i++) {
if (num[i] < num[i - 1]) {
int temp = num[i];
for (j = i; j > 0; j--) {
if (num[j - 1] > temp) num[j] = num[j - 1];
else break;
}
num[j] = temp;
}
}
}
四、二分插入排序
由于在插入排序過程中杯聚，待插入數(shù)據(jù)左邊的序列總是有序的臼婆，針對(duì)有序序列，就可以用二分法去插入數(shù)據(jù)了幌绍，也就是二分插入排序法颁褂。適用于數(shù)據(jù)量比較大的情況。
二分插入排序的算法思想：
算法的基本過程：
（1）計(jì)算 0 ~ i-1 的中間點(diǎn)傀广，用 i 索引處的元素與中間值進(jìn)行比較颁独，如果 i 索引處的元素大，說明要插入的這個(gè)元素應(yīng)該在中間值和剛加入i索引之間伪冰，反之誓酒，就是在剛開始的位置 到中間值的位置，這樣很簡(jiǎn)單的完成了折半贮聂；
（2）在相應(yīng)的半個(gè)范圍里面找插入的位置時(shí)靠柑，不斷的用（1）步驟縮小范圍，不停的折半吓懈，范圍依次縮小為 1/2 1/4 1/8 .......快速的確定出第 i 個(gè)元素要插在什么地方歼冰；
（3）確定位置之后，將整個(gè)序列后移耻警，并將元素插入到相應(yīng)位置隔嫡。
- 二分插入排序是穩(wěn)定的排序算法甸怕。
- 時(shí)間復(fù)雜度：最好情況(剛好插入位置為二分位置)下是O(log?n),平均情況和最壞情況是o(n2)
void insertSortBinary(int num[],int count)
{
int i,j;
for (i = 1; i < count; i++) {
if (num[i] < num[i - 1]) {
int temp = num[i];
int left = 0,right = i - 1;
while (left <= right) {
int mid = (left + right)/2;
if (num[mid] < temp) left = mid + 1;
else right = mid - 1;
}
//只是比較次數(shù)變少了，交換次數(shù)還是一樣的
for (j = i; j > left; j--) {
num[j] = num[j - 1];
}
num[left] = temp;
}
}
}
五腮恩、希爾(插入)排序
希爾排序(Shell's Sort)是插入排序的一種又稱“縮小增量排序”（Diminishing Increment Sort）梢杭，是直接插入排序算法的一種更高效的改進(jìn)版本。
希爾排序是把記錄按下標(biāo)的一定增量分組秸滴，對(duì)每組使用直接插入排序算法排序式曲；隨著增量逐漸減少，每組包含的關(guān)鍵詞越來(lái)越多缸榛，當(dāng)增量減至1時(shí)吝羞，整個(gè)文件恰被分成一組，排序完成内颗。
- 希爾排序是非穩(wěn)定排序算法钧排。
- 時(shí)間復(fù)雜度：O(n^（1.3—2）)
void shellSort(int num[],int count)
{
int shellNum = 2;
int gap = round(count/shellNum);
while (gap > 0) {
for (int i = gap; i < count; i++) {
int temp = num[i];
int j = i;
while (j >= gap && num[j - gap] > temp) {
num[j] = num[j - gap];
j = j - gap;
}
num[j] = temp;
}
gap = round(gap/shellNum);
}
}
六、快速排序
快速排序（Quicksort）是對(duì)冒泡排序的一種改進(jìn)均澳。
它的基本思想是：通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分恨溜，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序找前，整個(gè)排序過程可以遞歸進(jìn)行糟袁，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列。
- 快速排序是非穩(wěn)定的排序算法
- 時(shí)間復(fù)雜度：最差為O(n^2)躺盛，平均為O(nlogn)项戴，最好為O(nlogn)
void quickSort(int num[],int count,int left,int right)
{
if (left >= right){
return ;
}
int key = num[left];
int lp = left; //左指針
int rp = right; //右指針
while (lp < rp) {
if (num[rp] < key) {
int temp = num[rp];
for (int i = rp - 1; i >= lp; i--) {
num[i + 1] = num[i];
}
num[lp] = temp;
lp ++;
rp ++;
}
rp --;
}
quickSort(num,count,left,lp - 1);
quickSort(num,count,rp + 1,right);
}
七、堆排序
是指利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計(jì)的一種排序算法槽惫。堆是一個(gè)近似完全二叉樹的結(jié)構(gòu)周叮，并同時(shí)滿足堆積的性質(zhì)：即子結(jié)點(diǎn)的鍵值或索引總是小于（或者大于）它的父節(jié)點(diǎn)
在堆的數(shù)據(jù)結(jié)構(gòu)中，堆中的最大值總是位于根節(jié)點(diǎn)（在優(yōu)先隊(duì)列中使用堆的話堆中的最小值位于根節(jié)點(diǎn)）界斜。堆中定義以下幾種操作：
最大堆調(diào)整（Max Heapify）：將堆的末端子節(jié)點(diǎn)作調(diào)整仿耽，使得子節(jié)點(diǎn)永遠(yuǎn)小于父節(jié)點(diǎn)
創(chuàng)建最大堆（Build Max Heap）：將堆中的所有數(shù)據(jù)重新排序
堆排序（HeapSort）：移除位在第一個(gè)數(shù)據(jù)的根節(jié)點(diǎn)，并做最大堆調(diào)整的遞歸運(yùn)算
- 堆排序是一個(gè)非穩(wěn)定的排序算法各薇。
- 時(shí)間復(fù)雜度：O(nlogn)
void maxHeapify(int num[], int start, int end) {
//建立父節(jié)點(diǎn)指標(biāo)和子節(jié)點(diǎn)指標(biāo)
int dad = start;
int son = dad * 2 + 1;
while (son <= end) { //若子節(jié)點(diǎn)指標(biāo)在范圍內(nèi)才做比較
if (son + 1 <= end && num[son] < num[son + 1]) //先比較兩個(gè)子節(jié)點(diǎn)大小项贺，選擇最大的
son++;
if (num[dad] > num[son]) //如果父節(jié)點(diǎn)大於子節(jié)點(diǎn)代表調(diào)整完畢，直接跳出函數(shù)
return;
else { //否則交換父子內(nèi)容再繼續(xù)子節(jié)點(diǎn)和孫節(jié)點(diǎn)比較
EXCHANGE(num[dad], num[son])
dad = son;
son = dad * 2 + 1;
}
}
}
void heapSort(int num[], int count) {
int i;
//初始化峭判，i從最後一個(gè)父節(jié)點(diǎn)開始調(diào)整
for (i = count / 2 - 1; i >= 0; i--)
maxHeapify(num, i, count - 1);
//先將第一個(gè)元素和已排好元素前一位做交換开缎，再重新調(diào)整，直到排序完畢
for (i = count - 1; i > 0; i--) {
EXCHANGE(num[0], num[i])
maxHeapify(num, 0, i - 1);
}
}
