基礎演算法(一） 純干貨！！ 排序及二分演算法
碼了7天，手殘黨也能看懂！！
手殘第一篇：第一章 基礎演算法（一）
提示：你的三連是作者輸出下去的動力哦！！真的真的！！！（小聲嗶嗶：趕緊收藏！！內容持續更新中，，，）
文章目錄【演算法篇】
- 基礎演算法(一） 純干貨！！ 排序及二分演算法
- 前言
- 一、排序
- 1.快速排序 quick_sort
- 2.歸并排序 merge_sort
- 二、二分演算法
- 1、整數二分演算法
- 2、浮點數二分演算法
- 彩蛋，彩蛋！！
前言
- 已經斷更一周了，深感愧疚！突然在思考一個問題，是衣服穿得少比較冷還是褲子穿得少比較冷？我這衣服穿三件卻沒穿秋褲的老年人冷的直哆嗦，哈哈哈哈廢話不多說，以下是我學習演算法的一些心得筆記，全是模板干貨，感謝各位大佬，小伙伴的支持，以后一周一更，希望對各位有所幫助，話不多說直接上干貨！！
不懂的問題歡迎下方評論區留言哦，一定一定盡量回答
一、排序
1.快速排序 quick_sort
- 快速排序由于排序效率在同為O(N*logN)的幾種排序方法中效率較高，因此經常被采用，再加上快速排序思想----分治法也確實實用，因此很多軟體公司的筆試面試，包括像騰訊，微軟等知名IT公司都喜歡考這個，還有大大小的程式方面的考試如軟考，考研中也常常出現快速排序的身影，
- 下面是作者自己總結的想法，幫助大家快速理解： 原理：首先定義一個基準值(為了防止邊界問題，這里推薦取中點x)，以及指標 i ,p，指標i為起始位小于基準值向右移，指標p為終點位大于基準向左移，不符條件時指標停止，兩指標進行交換（即swap），進行下次回圈重新定義基點，最終變成有序序列，
圖解如下：
代碼如下（示例）：
void quick_sort(int q[],int i,int p)
{
if(i>=p) return;
int x =(i+p)<<1,g=i-1,u=p+1;
while(i<p)
{
do g++ ; while(q[g]<x);
do u--; while(q[u]>x);
if(i<j) swap(q[g],[u]);
quick_sort(q,i,g),quick_sort(q,g+1,p);
}
}
2.歸并排序 merge_sort
- 歸并排序（Merge sort）是建立在歸并操作上的一種有效的排序演算法，該演算法是采用分治法（Divide and
Conquer）的一個非常典型的應用，時間復雜度同為O(N*logN)，許多小伙伴一眼看去肯定是懵的吧（和我當初一樣哈哈哈，苦逼專研4小時），先將經驗總結如下： - 原理：將陣列以遞回的方式分為n個元素即時間復雜度為logN，再進行整合（此程序也是在遞回的程序中完成）此程序時間復雜度為n，整合的程序中比較，因此就完成了歸并排序，主要思想還是先分后合，可以看著代碼將思想代入無限遞回的最后一層，會幫助你清晰很多！
圖解如下：
代碼如下（示例）：
void merge_sort(int q[],int i,int p)
{
if(i>=p) return;
int mid = (i+p)>>1;
merge_sort(q,l,mid),merge_sort(q,mid+1,p);
int k = 0, l = i,r = mid + 1;
while(i>=p)
if(q[l]<q[p]) tmp[k++] = q[l++];
else tmp[k++] = q[p--];
while(l<=mid) tmp(k++) = q[l++];
while(r>=p) tmp(k++) = q[p--];
for(int r = 0,l = i;r <= p;i++,k++) q[i]=tmp[r];
}
二、二分演算法
1、整數二分演算法
- 二分法，即二分搜索法，是通過不斷縮小解可能存在的范圍，從而求得問題最優解的方法，下面兩種任用其一就行，分別求左右臨界點，一般情況下左右臨界點相等，除某些特殊題型需要查找出左邊界和右邊界，如：
起起始位置即左邊界，終止位置即右邊界，
- 圖解：好吧，這個比較簡單，博主就沒找圖啦，直接說原理！
- 其原理就是：先判斷mid的值滿足某種條件，于是可以將邊界點左右倆邊分為滿足此條件和不滿足此條件，如果mid的值滿足此條件說明查找值在不滿足此條件的值的那邊，為了更好的理解，舉個例子：猜數字玩過吧，比如這0-1000這個數字，第一次猜測為500，對方如果反饋數字大了，則說明要猜測的數字在0-499之間，如果反饋猜小了，那么說明要猜測的數字就在501-999之間，
還沒看懂的小可愛可以結合代碼理解哦
代碼如下（示例）：
bool cheak(int x) {/****/}//檢驗x是否滿足某種性質
// 區間[l, r]被劃分成[l, mid]和[mid + 1, r]時使用：
int binarysearch_1(int l,int r)//向左查找，尋找右臨界點
{
while(l<r)
{
int mid = (l + r) >> 1;
if(cheak(mid)) r = mid;//如果x在mid左邊，則另右端點等于mid
else l = mid + 1;
}
return l;
}
// 區間[l, r]被劃分成[l, mid - 1]和[mid, r]時使用：
int binarysearch_2(int l,int r)//向右查找，尋找左臨界點
{
while(l<r)
{
int mid = (l+r)>>1;
if(cheak(mid)) l=mid;
else r = mid-1;
}
return l;
}
每次取中點，也就相當于分的程序，所以時間復雜度最壞的情況下用O (log n)來完成，
2、浮點數二分演算法
- 和整數一樣本質上也是尋找一個邊界，和整數二分不同的是，浮點數不存在由于（整數）取整導致的邊界問題，每次二磁區間嚴格減半，因此比整數二分簡單的多，每次更新邊界時直接讓r = mid或l = mid即可，當整個區間的長度足夠小的時候（這里取的是10^-6）就可以認定找到了答案，
代碼如下（示例）：
bool cheak(double x) {/****/}//檢驗x是否滿足某種性質
double Fbinarysearch(double l,double r)
{
const double eps = 1e-6;// eps 表示精度，取決于題目對精度的要求
while(r - l > eps)
{
double mid = (l + r) >> 1;
if(cheak(mid)) r = mid;
else l = mid;
}
return l;
}
彩蛋，彩蛋！！
終于碼完了！！！【哭!】
- 都康到這里了，彩蛋就是、就是：今年你肯定是yyds！！！（不是永遠單身）
大佬：就這啊？
我：就這了【哭!】
后面還會持續更新，歡迎下方評論區留言----------------------
作者：還沒想好名字，，，（有推薦的嗎？【狗頭】）
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/274073.html
標籤：python