git

git和svn

• 核心區(qū)別:
  • SVN 是集中式版本控制系統(tǒng)，版本庫是集中放在中央服務器的，而干活的時候，用的都是自己的電腦，所以首先要從中央服務器哪里得到最新的版本，然后干活，干完后，需要把自己做完的活推送到中央服務器。集中式版本控制系統(tǒng)是必須聯(lián)網(wǎng)才能工作，如果在局域網(wǎng)還可以，帶寬夠大，速度夠快，如果在互聯(lián)網(wǎng)下，如果網(wǎng)速慢的話，就納悶了。
  • Git 是分布式版本控制系統(tǒng)，那么它就沒有中央服務器的，每個人的電腦就是一個完整的版本庫，這樣，工作的時候就不需要聯(lián)網(wǎng)了，因為版本都是在自己的電腦上。既然每個人的電腦都有一個完整的版本庫，那多個人如何協(xié)作呢？比如說自己在電腦上改了文件 A，其他人也在電腦上改了文件 A，這時，你們兩之間只需把各自的修改推送給對方，就可以互相看到對方的修改了。
• Git把內容按元數(shù)據(jù)方式存儲，而SVN是按文件：因為,.git目錄是處于你的機器上的一個克隆版的版本庫，它擁有中心版本庫上所有的東西，例如標簽，分支，版本記錄等。.git目錄的體積大小跟.svn比較，你會發(fā)現(xiàn)它們差距很大。
• Git沒有一個全局版本號，而SVN有：目前為止這是跟SVN相比Git缺少的最大的一個特征。
• Git的內容的完整性要優(yōu)于SVN: GIT的內容存儲使用的是SHA-1哈希算法。這能確保代碼內容的完整性，確保在遇到磁盤故障和網(wǎng)絡問題時降低對版本庫的破壞。
• Git下載下來后，在OffLine狀態(tài)下可以看到所有的Log,SVN不可以。
• 剛開始用時，SVN必須先Update才能Commit,忘記了合并時就會出現(xiàn)一些錯誤，git還是比較少的出現(xiàn)這種情況。
• 克隆一份全新的目錄以同樣擁有五個分支來說，SVN是同時復製5個版本的文件,也就是說重復五次同樣的動作。而Git只是獲取文件的每個版本的 元素，然后只載入主要的分支(master)在我的經(jīng)驗,克隆一個擁有將近一萬個提交(commit),五個分支,每個分支有大約1500個文件的 SVN,耗了將近一個小時！而Git只用了區(qū)區(qū)的1分鐘！
• 版本庫（repository):SVN只能有一個指定中央版本庫。當這個中央版本庫有問題時，所有工作成員都一起癱瘓直到版本庫維修完畢或者新的版本庫設立完成。而 Git可以有無限個版本庫?；蛘?，更正確的說法，每一個Git都是一個版本庫，區(qū)別是它們是否擁有活躍目錄（Git Working Tree）。如果主要版本庫（例如：置於GitHub的版本庫）發(fā)生了什麼事，工作成員仍然可以在自己的本地版本庫（local repository）提交，等待主要版本庫恢復即可。工作成員也可以提交到其他的版本庫
• 分支（Branch）在SVN，分支是一個完整的目錄。且這個目錄擁有完整的實際文件。如果工作成員想要開啟新的分支，那將會影響“全世界”！每個人都會擁有和你一樣的分支。如果你的分支是用來進行破壞工作（安檢測試），那將會像傳染病一樣,你改一個分支，還得讓其他人重新切分支重新下載，十分狗血。而 Git，每個工作成員可以任意在自己的本地版本庫開啟無限個分支。舉例：當我想嘗試破壞自己的程序（安檢測試），并且想保留這些被修改的文件供日后使用， 我可以開一個分支，做我喜歡的事。完全不需擔心妨礙其他工作成員。只要我不合并及提交到主要版本庫，沒有一個工作成員會被影響。等到我不需要這個分支時， 我只要把它從我的本地版本庫刪除即可。
• 提交（Commit）在SVN，當你提交你的完成品時，它將直接記錄到中央版本庫。當你發(fā)現(xiàn)你的完成品存在嚴重問題時，你已經(jīng)無法阻止事情的發(fā)生了。如果網(wǎng)路中斷，你根本沒辦法提交！而Git的提交完全屬於本地版本庫的活動。而你只需“推”（git push）到主要版本庫即可。Git的“推”其實是在執(zhí)行“同步”（Sync）

git乘用命令

新建代碼庫

• $ git init 在當前目錄新建一個Git代碼庫
• $ git init [project-name] 新建一個目錄，將其初始化為Git代碼庫
• $ git clone [url] 下載一個項目和它的整個代碼歷史

配置

• 顯示當前的Git配置 $ git config --list
• 編輯Git配置文件 $ git config -e [--global]
• 設置提交代碼時的用戶信息
  • $ git config [--global] user.name "[name]"
  • $ git config [--global] user.email "[email address]"

增加/刪除文件

• 添加指定文件到暫存區(qū) $ git add [file1] [file2] ...
• 添加指定目錄到暫存區(qū)，包括子目錄 $ git add [dir]
• 添加當前目錄的所有文件到暫存區(qū) $ git add .
• 添加每個變化前，都會要求確認
• 對于同一個文件的多處變化，可以實現(xiàn)分次提交 $ git add-p
• 刪除工作區(qū)文件，并且將這次刪除放入暫存區(qū) $ git rm [file1] [file2] ...
• 停止追蹤指定文件，但該文件會保留在工作區(qū) $ git rm --cached [file]
• 改名文件，并且將這個改名放入暫存區(qū) $ git mv [file-original] [file-renamed]

代碼提交

• 提交暫存區(qū)到倉庫區(qū) $ git commit -m [message]
• 提交暫存區(qū)的指定文件到倉庫區(qū) $ git commit [file1] [file2] ... -m [message]
• 提交工作區(qū)自上次commit之后的變化，直接到倉庫區(qū) $ git commit -a
• 提交時顯示所有diff信息 $ git commit -v
• 使用一次新的commit，替代上一次提交
• 如果代碼沒有任何新變化，則用來改寫上一次commit的提交信息 $ git commit --amend -m [message]
• 重做上一次commit，并包括指定文件的新變化 $ git commit --amend [file1] [file2] ...

分支

• 列出所有本地分支 $ git branch
• 列出所有遠程分支 $ git branch -r
• 列出所有本地分支和遠程分支 $ git branch -a
• 新建一個分支，但依然停留在當前分支 $ git branch [branch-name]
• 新建一個分支，并切換到該分支 $ git checkout-b [branch]
• 新建一個分支，指向指定commit $ git branch [branch] [commit]
• 新建一個分支，與指定的遠程分支建立追蹤關系 $ git branch --track [branch] [remote-branch]
• 切換到指定分支，并更新工作區(qū) $ git checkout[branch-name]
• 切換到上一個分支 $ git checkout -
• 建立追蹤關系，在現(xiàn)有分支與指定的遠程分支之間 $ git branch--set-upstream [branch] [remote-branch]
• 合并指定分支到當前分支 $ git merge[branch]
• 選擇一個commit，合并進當前分支 $ git cherry-pick [commit]
• 刪除分支 $ git branch -d [branch-name]
• 刪除遠程分支
  • $ git push origin --delete [branch-name]
  • $ git branch -dr [remote/branch]

標簽

• 列出所有tag $ git tag
• 新建一個tag在當前commit $ git tag [tag]
• 新建一個tag在指定commit $ git tag [tag] [commit]
• 刪除本地tag $ git tag -d [tag]
• 刪除遠程tag $ git push origin :refs/tags/[tagName]
• 查看tag信息 $ git show [tag]
• 提交指定tag $ git push [remote] [tag]
• 提交所有tag $ git push [remote] --tags
• 新建一個分支，指向某個tag $ git checkout -b [branch] [tag]

查看信息

• 顯示有變更的文件 $ git status
• 顯示當前分支的版本歷史 $ git log
• 顯示commit歷史，以及每次commit發(fā)生變更的件$ git log --stat
• 搜索提交歷史，根據(jù)關鍵詞 $ git log-S [keyword]
• 顯示某個commit之后的所有變動，每個commi占據(jù)一行 $ git log[tag] HEAD --pretty=format:%s
• 顯示某個commit之后的所有變動，其"提交說明"必須符合搜索條件 $ git log[tag] HEAD --grep feature
• 顯示某個文件的版本歷史，包括文件改名
  • $ git log--follow [file]
  • $ git whatchanged [file]
• 顯示指定文件相關的每一次diff $ git log -p [file]
• 顯示過去5次提交 $ git log-5 --pretty --oneline
• 顯示所有提交過的用戶，按提交次數(shù)排序 $ git shortlog-sn
• 顯示指定文件是什么人在什么時間修改過 $ git blame[file]
• 顯示暫存區(qū)和工作區(qū)的差異 $ git diff
• 顯示暫存區(qū)和上一個commit的差異 $ git diff--cached [file]
• 顯示工作區(qū)與當前分支最新commit之間的差異 $ git diff HEAD
• 顯示兩次提交之間的差異 $ git diff[first-branch]...[second-branch]
• 顯示今天你寫了多少行代碼 $ git diff--shortstat "@{0 day ago}"
• 顯示某次提交的元數(shù)據(jù)和內容變化 $ git show[commit]
• 顯示某次提交發(fā)生變化的文件 $ git show--name-only [commit]
• 顯示某次提交時，某個文件的內容 $ git show[commit]:[filename]
• 顯示當前分支的最近幾次提交 $ git reflog

遠程同步

• 下載遠程倉庫的所有變動 $ git fetch[remote]
• 顯示所有遠程倉庫 $ git remote-v
• 顯示某個遠程倉庫的信息 $ git remote show[remote]
• 增加一個新的遠程倉庫，并命名 $ git remote add[shortname] [url]
• 取回遠程倉庫的變化，并與本地分支合并 $ git pull[remote] [branch]
• 上傳本地指定分支到遠程倉庫 $ git push [remote] [branch]
• 強行推送當前分支到遠程倉庫，即使有沖突 $ git push[remote] --force
• 推送所有分支到遠程倉庫 $ git push[remote] –all

撤銷

• 恢復暫存區(qū)的指定文件到工作區(qū) $ git checkout[file]
• 恢復某個commit的指定文件到暫存區(qū)和工作區(qū) $ git checkout[commit] [file]
• 恢復暫存區(qū)的所有文件到工作區(qū) $ git checkout .
• 重置暫存區(qū)的指定文件，與上一次commit保持一致，但工作區(qū)不變 $ git reset [file]
• 重置暫存區(qū)與工作區(qū)，與上一次commit保持一致 $ git reset --hard
• 重置當前分支的指針為指定commit，同時重置暫存區(qū)，但工作區(qū)不變 $ git reset[commit]
• 重置當前分支的HEAD為指定commit，同時重置暫存區(qū)和工作區(qū)，與指定commit一致 $ git reset --hard [commit]
• 重置當前HEAD為指定commit，但保持暫存區(qū)和工作區(qū)不變 $ git reset --keep [commit]
• 新建一個commit，用來撤銷指定commit
• 后者的所有變化都將被前者抵消，并且應用到當前分支 $ git revert[commit]
• 暫時將未提交的變化移除，稍后再移入 git stash pop

常見的攻擊

xss

Xss 跨站腳本攻擊,例如攻擊者向form表單輸入了惡意的html代碼,當用戶訪問列表頁面時,這段html代碼會自動執(zhí)行,達到攻擊效果,我們也遇到過一次,他在form中input輸入了js代碼,創(chuàng)建了html節(jié)點,創(chuàng)建了一個超鏈接標簽,使網(wǎng)頁跳轉到惡意的菠菜網(wǎng)站. 防止:使用正則過濾,使用htmlentites函數(shù)實現(xiàn)html標簽的實體化

sql注入

Sql注入沒有過濾傳入的參數(shù),篡改sql語句,達到攻擊效果,比如賬號輸入完成后使用單引號加井號完成了免密碼登錄,通過#吧#后面的數(shù)據(jù)過濾 防止 通過pdo防止首先將 sql 語句模板發(fā)送給Mysql Server，隨后將綁定的字符變量再發(fā)送給Mysql server，這里的轉義是在Mysql Server做的，它是根據(jù)你在連接PDO的時候，在charset里指定的編碼格式來轉換的。

csrf

Csrf跨站請求攻擊, 全稱是“跨站請求偽造”，而 XSS 的全稱是“跨站腳本”?？雌饋碛悬c相似，它們都是屬于跨站攻擊——不攻擊服務器端而攻擊正常訪問網(wǎng)站的用戶 防止:通過存儲在cookie中token來防止;

Rabbitmq

參考鏈接

• https://blog.csdn.net/yojhon/article/details/82868860
• https://blog.csdn.net/cowbin2012/article/details/89791340

簡介

RabbitMQ是實現(xiàn)了高級消息隊列協(xié)議（AMQP）的開源消息代理軟件（亦稱面向消息的中間件）。RabbitMQ服務器是用[Erlang]語言編寫的，而群集和故障轉移是構建在[開放電信平臺]框架上的。所有主要的編程語言均有與代理接口通訊的客戶端[庫]。用于在分布式系統(tǒng)中存儲轉發(fā)消息，在易用性、擴展性、高可用性等方面表現(xiàn)不俗。

注:

• AMQP，即Advanced Message Queuing Protocol，高級消息隊列協(xié)議，是應用層協(xié)議的一個開放標準，為面向消息的[中間件]設計。消息中間件主要用于組件之間的解耦，消息的發(fā)送者無需知道消息使用者的存在，反之亦然。\
• AMQP的主要特征是面向消息、隊列、路由（包括點對點和發(fā)布/訂閱）、可靠性、安全。
• Erlang是一種通用的面向[并發(fā)]的編程語言, 在[編程范型]上，Erlang屬于多重范型編程語言，涵蓋函數(shù)式、并發(fā)式及[分布式]。順序執(zhí)行的Erlang是一個及早求值, 單次賦值和動態(tài)類型的函數(shù)式編程語言。Erlang是一個結構化，動態(tài)類型編程語言，內建并行計算支持。
• 消息隊列是“”消費-生產(chǎn)者模型“”的一個典型的代表，一端往消息隊列中不斷寫入消息，而另一端則可以讀取或者訂閱隊列中的消息。

項目的使用

Rabbitmq 的隊列容量可以認為是無限的，根據(jù)內存有關。 可以設置隊列最大長度，當達到長度的時候，最先入隊的消息將被丟棄。
流量削峰一般在秒殺活動中應用廣泛

場景

秒殺活動，一般會因為流量過大，導致應用掛掉,為了解決這個問題，一般在應用前端加入消息隊列。

作用:

• 可以控制活動人數(shù)，超過此一定閥值的訂單直接丟棄，先顯示一個排隊中，后端在處理，可能成功可能失敗。
• 可以緩解短時間的高流量壓垮應用(應用程序按自己的最大處理能力獲取訂單)

為什么選擇rabbitmq

• Rabbit mq 是一個高級消息隊列，在分布式的場景下，擁有高性能。，對負載均衡也有很好的支持。
• 擁有持久化的機制，進程消息，隊列中的信息也可以保存下來。
• 實現(xiàn)消費者和生產(chǎn)者之間的解耦。
• 對于高并發(fā)場景下，利用消息隊列可以使得同步訪問變?yōu)榇性L問達到一定量的限流，利于數(shù)據(jù)庫的操作。
• 可以使用消息隊列達到異步下單的效果，排隊中，后臺進行邏輯下單。

AMQP，即Advanced Message Queuing Protocol，高級消息隊列協(xié)議，是應用層協(xié)議的一個開放標準，為面向消息的中間件設計。消息中間件主要用于組件之間的解耦，消息的發(fā)送者無需知道消息使用者的存在

rabbitMQ的優(yōu)點（適用范圍）

• 基于erlang語言開發(fā)具有高可用高并發(fā)的優(yōu)點，適合集群服務器。
• 健壯、穩(wěn)定、易用、跨平臺、支持多種語言、文檔齊全。
• 有消息確認機制和持久化機制，可靠性高。
• 開源

使用場景

• 跨系統(tǒng)的異步通信，所有需要異步交互的地方都可以使用消息隊列。就像我們除了打電話（同步）以外，還需要發(fā)短信，發(fā)電子郵件（異步）的通訊方式。
• 多個應用之間的耦合，由于消息是平臺無關和語言無關的，而且語義上也不再是函數(shù)調用，因此更適合作為多個應用之間的松耦合的接口?；谙㈥犃械鸟詈希恍枰l(fā)送方和接收方同時在線。在企業(yè)應用集成（EAI）中，文件傳輸，共享數(shù)據(jù)庫，消息隊列，遠程過程調用都可以作為集成的方法。
• 應用內的同步變異步，比如訂單處理，就可以由前端應用將訂單信息放到隊列，后端應用從隊列里依次獲得消息處理，高峰時的大量訂單可以積壓在隊列里慢慢處理掉。由于同步通常意味著阻塞，而大量線程的阻塞會降低計算機的性能。
• 消息驅動的架構（EDA），系統(tǒng)分解為消息隊列，和消息制造者和消息消費者，一個處理流程可以根據(jù)需要拆成多個階段（Stage），階段之間用隊列連接起來，前一個階段處理的結果放入隊列，后一個階段從隊列中獲取消息繼續(xù)處理。
• 應用需要更靈活的耦合方式，如發(fā)布訂閱，比如可以指定路由規(guī)則。
• 跨局域網(wǎng)，甚至跨城市的通訊（CDN行業(yè)），比如北京機房與廣州機房的應用程序的通信。

rabbitmq 三個主要角色

• 生產(chǎn)者：消息的創(chuàng)建者，負責創(chuàng)建和推送數(shù)據(jù)到消息服務器；
• 消費者：消息的接收方，用于處理數(shù)據(jù)和確認消息；
• 代理：就是 RabbitMQ 本身，用于扮演“快遞”的角色，本身不生產(chǎn)消息，只是扮演“快遞”的角色。

消息發(fā)送流程

• 首先客戶端必須連接到 RabbitMQ 服務器才能發(fā)布和消費消息，客戶端和 rabbit server 之間會創(chuàng)建一個 tcp 連接，一旦 tcp 打開并通過了認證（認證就是你發(fā)送給 rabbit 服務器的用戶名和密碼），你的客戶端和 RabbitMQ 就創(chuàng)建了一條 amqp 信道（channel），信道是創(chuàng)建在“真實” tcp 上的虛擬連接，amqp 命令都是通過信道發(fā)送出去的，每個信道都會有一個唯一的 id，不論是發(fā)布消息，訂閱隊列都是通過這個信道完成的。
• 生產(chǎn)者通過網(wǎng)絡將消息發(fā)送給消費者，在中間會有一個應用RabbitMQ(轉發(fā)和存儲的功能)，這時RabbitMQ收到消息后，根據(jù)消息指定的exchange(交換機)來查找綁定然后根據(jù)規(guī)則分發(fā)到不同的Queue（隊列），queue將消息轉發(fā)到具體的消費者。
• 消費者收到消息后，會根據(jù)自己對消息的處理對RabbitMQ進行返回，如果返回ack，就表示已經(jīng)確認這條消息，RabbitMQ會對這條消息進行處理（一般是刪除）。
• 如果消費者接收到消息后處理不了，就可能不對RabbitMQ進行處理，或者拒絕對消息處理，返回reject。

ACK消息確認機制

• ACK消息確認機制, 保證數(shù)據(jù)能被正確處理而不僅僅是被Consumer(接收端)收到，我們就不能采用no-ack或者auto-ack，我們需要手動ack(manual-ack)。在數(shù)據(jù)處理完成后手動發(fā)送ack，這個時候Server才將Message刪除。
• ACK機制可以起到限流的作用，比如在消費者處理后，sleep一段時間，然后再ACK，這可以幫助消費者負載均衡。
• 當然，除了ACK，有兩個比較重要的參數(shù)也在控制著consumer(接收端)的load-balance，即prefetch和concurrency

Broker(消息隊列服務器實體)

接收和分發(fā)消息的應用，RabbitMQ Server就是Message Broker。

Virtual host(虛擬消息服務器)

出于多租戶和安全因素設計的，把AMQP的基本組件劃分到一個虛擬的分組中，類似于網(wǎng)絡中的namespace概念。當多個不同的用戶使用同一個RabbitMQ server提供的服務時，可以劃分出多個vhost，每個用戶在自己的vhost創(chuàng)建exchange／queue等

Connection(TCP連接)

publisher(發(fā)送端)／consumer(接收端)和broker(消息隊列服務器實體)之間的TCP連接。斷開連接的操作只會在client端進行，Broker(消息隊列服務器實體)不會斷開連接，除非出現(xiàn)網(wǎng)絡故障或broker(消息隊列服務器實體)服務出現(xiàn)問題。

Channel(connection內部建立的邏輯連接)

如果每一次訪問RabbitMQ都建立一個Connection，在消息量大的時候建立TCP Connection的開銷將是巨大的，效率也較低。Channel是在connection內部建立的邏輯連接，如果應用程序支持多線程，通常每個thread創(chuàng)建單獨的channel進行通訊，AMQP method包含了channel id幫助客戶端和message broker識別channel，所以channel之間是完全隔離的。Channel作為輕量級的Connection極大減少了操作系統(tǒng)建立TCP connection的開銷。

Exchange(交換機)

message到達broker(消息隊列服務器實體)的第一站，根據(jù)分發(fā)規(guī)則，匹配查詢表中的routing key，分發(fā)消息到queue中去。

Queue(隊列)

消息最終被送到這里等待consumer(接收端)取走。一個message可以被同時拷貝到多個queue中。

Binding(交換機和隊列之間的虛擬連接)

exchange和queue之間的虛擬連接，binding中可以包含routing key。Binding信息被保存到exchange中的查詢表中，用于message的分發(fā)依據(jù)。

發(fā)送/接收信息

Send.py(發(fā)送信息)

• 權限驗證
• 鏈接參數(shù): virtual_host, 在多租戶系統(tǒng)中隔離exchange, queue
• 建立鏈接
• 從鏈接中獲得信道
• 聲明交換機
• consumer(接收端)創(chuàng)建隊列, 如果沒有就創(chuàng)建
  • 隊列一旦被創(chuàng)建, 再進行的重復創(chuàng)建會簡單的失效, 所以建議在producer(發(fā)送端)和consumer同時創(chuàng)建隊列, 避免隊列創(chuàng)建失敗
  • 創(chuàng)建隊列回調函數(shù), callback.
  • auto_delete=True, 如果queue失去了最后一個subscriber會自動刪除, 隊列中的message也會失效.
  • 默認auto_delete=False, 沒有subscriber的隊列會cache message, subscriber出現(xiàn)后將緩存的message發(fā)送.
• delivery_mode=2表示讓消息持久化, 重啟RabbitMQ也不丟失. 考慮成本, 開啟此功能, 建議把消息存儲到SSD上.
• 發(fā)布消息到exchange
• 關閉鏈接

receive.py(接收信息)

• 權限驗證
• 鏈接參數(shù): virtual_host, 在多租戶系統(tǒng)中隔離exchange, queue
• 建立鏈接
• 從鏈接中獲得信道
• 聲明交換機, 直連方式, 后面將會創(chuàng)建binding將exchange和queue綁定在一起
• consumer(接收端)創(chuàng)建隊列, 如果沒有就創(chuàng)建
  • 隊列一旦被創(chuàng)建, 再進行的重復創(chuàng)建會簡單的失效, 所以建議在producer(發(fā)送端)和consumer(接收端)同時創(chuàng)建隊列, 避免隊列創(chuàng)建失敗
  • 創(chuàng)建隊列回調函數(shù), callback.
  • auto_delete=True, 如果queue失去了最后一個subscriber會自動刪除, 隊列中的message也會失效.
  • 默認auto_delete=False, 沒有subscriber的隊列會cache message, subscriber出現(xiàn)后將緩存的message發(fā)送.
• 通過binding將隊列queue和交換機exchange綁定
• 處理接收到的消息的回調函數(shù),method_frame攜帶了投遞標記, header_frame表示AMQP信息頭的對象
• 訂閱隊列, 我們設置了不進行ACK, 而把ACK交給了回調函數(shù)來完成
• 關閉連接

如何確保消息正確地發(fā)送至RabbitMQ

• RabbitMQ使用發(fā)送方確認模式，確保消息正確地發(fā)送到RabbitMQ。
• 發(fā)送方確認模式：將信道設置成confirm模式（發(fā)送方確認模式），則所有在信道上發(fā)布的消息都會被指派一個唯一的ID。一旦消息被投遞到目的隊列后，或者消息被寫入磁盤后（可持久化的消息），信道會發(fā)送一個確認給生產(chǎn)者（包含消息唯一ID）。如果RabbitMQ發(fā)生內部錯誤從而導致消息丟失，會發(fā)送一條nack（not acknowledged，未確認）消息。
• 發(fā)送方確認模式是異步的，生產(chǎn)者應用程序在等待確認的同時，可以繼續(xù)發(fā)送消息。當確認消息到達生產(chǎn)者應用程序，生產(chǎn)者應用程序的回調方法就會被觸發(fā)來處理確認消息。

如何確保消息接收方消費了消息

• 接收方消息確認機制：消費者接收每一條消息后都必須進行確認（消息接收和消息確認是兩個不同操作）。只有消費者確認了消息，RabbitMQ才能安全地把消息從隊列中刪除。
• 這里并沒有用到超時機制，RabbitMQ僅通過Consumer的連接中斷來確認是否需要重新發(fā)送消息。也就是說，只要連接不中斷，RabbitMQ給了Consumer足夠長的時間來處理消息。

下面羅列幾種特殊情況：

• 如果消費者接收到消息，在確認之前斷開了連接或取消訂閱，RabbitMQ會認為消息沒有被分發(fā)，然后重新分發(fā)給下一個訂閱的消費者。（可能存在消息重復消費的隱患，需要根據(jù)bizId去重）
• 如果消費者接收到消息卻沒有確認消息，連接也未斷開，則RabbitMQ認為該消費者繁忙，將不會給該消費者分發(fā)更多的消息。

避免消息重復投遞或重復消費

在消息生產(chǎn)時，MQ內部針對每條生產(chǎn)者發(fā)送的消息生成一個inner-msg-id，作為去重和冪等的依據(jù)（消息投遞失敗并重傳），避免重復的消息進入隊列；在消息消費時，要求消息體中必須要有一個bizId（對于同一業(yè)務全局唯一，如支付ID、訂單ID、帖子ID等）作為去重和冪等的依據(jù)，避免同一條消息被重復消費。

消息基于什么傳輸

由于TCP連接的創(chuàng)建和銷毀開銷較大，且并發(fā)數(shù)受系統(tǒng)資源限制，會造成性能瓶頸。RabbitMQ使用信道的方式來傳輸數(shù)據(jù)。信道是建立在真實的TCP連接內的虛擬連接，且每條TCP連接上的信道數(shù)量沒有限制。

消息如何分發(fā)

若該隊列至少有一個消費者訂閱，消息將以循環(huán)（round-robin）的方式發(fā)送給消費者。每條消息只會分發(fā)給一個訂閱的消費者（前提是消費者能夠正常處理消息并進行確認）。

消息怎么路由

從概念上來說，消息路由必須有三部分：交換器、路由、綁定。生產(chǎn)者把消息發(fā)布到交換器上；綁定決定了消息如何從路由器路由到特定的隊列；消息最終到達隊列，并被消費者接收。

• 1. 消息發(fā)布到交換器時，消息將擁有一個路由鍵（routing key），在消息創(chuàng)建時設定。
• 2. 通過隊列路由鍵，可以把隊列綁定到交換器上。
• 3. 消息到達交換器后，RabbitMQ會將消息的路由鍵與隊列的路由鍵進行匹配（針對不同的交換器有不同的路由規(guī)則）。如果能夠匹配到隊列，則消息會投遞到相應隊列中；如果不能匹配到任何隊列，消息將進入 “黑洞”。

常用的交換器主要分為一下三種：

• direct：如果路由鍵完全匹配，消息就被投遞到相應的隊列
• fanout：如果交換器收到消息，將會廣播到所有綁定的隊列上
• topic：可以使來自不同源頭的消息能夠到達同一個隊列。 使用topic交換器時，可以使用通配符，比如：“ * ” 匹配特定位置的任意文本， “ . ” 把路由鍵分為了幾部分，“#” 匹配所有規(guī)則等。特別注意：發(fā)往topic交換器的消息不能隨意的設置選擇鍵（routing_key），必須是由"."隔開的一系列的標識符組成。

確保消息不丟失

息持久化的前提是：將交換器/隊列的durable屬性設置為true，表示交換器/隊列是持久交換器/隊列，在服務器崩潰或重啟之后不需要重新創(chuàng)建交換器/隊列（交換器/隊列會自動創(chuàng)建）。

如果消息想要從Rabbit崩潰中恢復，那么消息必須：

• 在消息發(fā)布前，通過把它的 “投遞模式” 選項設置為2（持久）來把消息標記成持久化
• 將消息發(fā)送到持久交換器
• 消息到達持久隊列

RabbitMQ確保持久性消息能從服務器重啟中恢復的方式是，將它們寫入磁盤上的一個持久化日志文件，當發(fā)布一條持久性消息到持久交換器上時，Rabbit會在消息提交到日志文件后才發(fā)送響應（如果消息路由到了非持久隊列，它會自動從持久化日志中移除）。一旦消費者從持久隊列中消費了一條持久化消息，RabbitMQ會在持久化日志中把這條消息標記為等待垃圾收集。如果持久化消息在被消費之前RabbitMQ重啟，那么Rabbit會自動重建交換器和隊列（以及綁定），并重播持久化日志文件中的消息到合適的隊列或者交換器上。

重要的組件

• ConnectionFactory（連接管理器）：應用程序與Rabbit之間建立連接的管理器，程序代碼中使用。
• Channel（信道）：消息推送使用的通道。
• Exchange（交換器）：用于接受、分配消息。
• Queue（隊列）：用于存儲生產(chǎn)者的消息。
• RoutingKey（路由鍵）：用于把生成者的數(shù)據(jù)分配到交換器上。
• BindingKey（綁定鍵）：用于把交換器的消息綁定到隊列上。

vhost

vhost 可以理解為虛擬 broker ，即 mini-RabbitMQ server。其內部均含有獨立的 queue、exchange 和 binding 等，但最最重要的是，其擁有獨立的權限系統(tǒng)，可以做到 vhost 范圍的用戶控制。當然，從 RabbitMQ 的全局角度，vhost 可以作為不同權限隔離的手段（一個典型的例子就是不同的應用可以跑在不同的 vhost 中）。

保證消息持久化成功的條件

1. 聲明隊列必須設置持久化 durable 設置為 true.
2. 消息推送投遞模式必須設置持久化，deliveryMode 設置為 2（持久）。
3. 消息已經(jīng)到達持久化交換器。
4. 消息已經(jīng)到達持久化隊列。

rabbitmq 持久化有什么缺點

持久化的缺地就是降低了服務器的吞吐量，因為使用的是磁盤而非內存存儲，從而降低了吞吐量?？杀M量使用 ssd 硬盤來緩解吞吐量的問題。

幾種廣播類型

三種廣播模式：

• fanout: 所有bind到此exchange的queue都可以接收消息（純廣播，綁定到RabbitMQ的接受者都能收到消息）；
• direct: 通過routingKey和exchange決定的那個唯一的queue可以接收消息；
• topic:所有符合routingKey(此時可以是一個表達式)的routingKey所bind的queue可以接收消息；

延遲消息隊列實現(xiàn)

1. 通過消息過期后進入死信交換器，再由交換器轉發(fā)到延遲消費隊列，實現(xiàn)延遲功能；
2. 使用 RabbitMQ-delayed-message-exchange 插件實現(xiàn)延遲功能。

集群的作用

• 高可用：某個服務器出現(xiàn)問題，整個 RabbitMQ 還可以繼續(xù)使用；
• 高容量：集群可以承載更多的消息量。

節(jié)點的類型

• 磁盤節(jié)點：消息會存儲到磁盤。
• 內存節(jié)點：消息都存儲在內存中，重啟服務器消息丟失，性能高于磁盤類型。

集群搭建注意問題

• 各節(jié)點之間使用“–link”連接，此屬性不能忽略。
• 各節(jié)點使用的 erlang cookie 值必須相同，此值相當于“秘鑰”的功能，用于各節(jié)點的認證。
• 整個集群中必須包含一個磁盤節(jié)點。

rabbitmq 每個節(jié)點是其他節(jié)點的完整拷貝嗎

不是，原因有以下兩個：

1. 存儲空間的考慮：如果每個節(jié)點都擁有所有隊列的完全拷貝，這樣新增節(jié)點不但沒有新增存儲空間，反而增加了更多的冗余數(shù)據(jù)；
2. 性能的考慮：如果每條消息都需要完整拷貝到每一個集群節(jié)點，那新增節(jié)點并沒有提升處理消息的能力，最多是保持和單節(jié)點相同的性能甚至是更糟。

集群中唯一一個磁盤節(jié)點崩潰了會發(fā)生什么

如果唯一磁盤的磁盤節(jié)點崩潰了，不能進行以下操作：

• 不能創(chuàng)建隊列
• 不能創(chuàng)建交換器
• 不能創(chuàng)建綁定
• 不能添加用戶
• 不能更改權限
• 不能添加和刪除集群節(jié)點

唯一磁盤節(jié)點崩潰了，集群是可以保持運行的，但你不能更改任何東西。

API 接口

接口的規(guī)范

接口規(guī)范采用rustful接口規(guī)范

使用SSL（https）來提供URL

• 首先，使用https可以在數(shù)據(jù)包被抓取時多一層加密。我們現(xiàn)在的APP使用環(huán)境大部分都是在路由器WIFI環(huán)境下，一旦路由器被入侵，那么黑客可以非常容易的抓取到用戶通過路由器傳輸?shù)臄?shù)據(jù)，如果使用http未經(jīng)加密，那么黑客可以很輕松的獲取用戶的信息，甚至是賬戶信息。
• 其次，即使使用https，也要在API數(shù)據(jù)傳輸設計時，正確的采用加密。例如直接將token信息放在URL中的做法，即使你使用了https，黑客抓不到你具體傳輸?shù)臄?shù)據(jù)，但是可以抓到你請求的URL??！因此，使用https進行請求時，要采用POST、PUT或者HEAD的方式傳輸必要的數(shù)據(jù)。

使用GET、POST、PUT、DELETE這幾種請求模式

請求模式也可以說是動作、數(shù)據(jù)傳輸方式，通常我們在web中的form有GET、POST兩種，而在HTTP中，存在下發(fā)這幾種。

GET (選擇)：從服務器上獲取一個具體的資源或者一個資源列表。
POST （創(chuàng)建）： 在服務器上創(chuàng)建一個新的資源。
PUT（更新）：以整體的方式更新服務器上的一個資源。
PATCH （更新）：只更新服務器上一個資源的一個屬性。
DELETE（刪除）：刪除服務器上的一個資源。
HEAD ： 獲取一個資源的元數(shù)據(jù)，如數(shù)據(jù)的哈希值或最后的更新時間。
OPTIONS：獲取客戶端能對資源做什么操作的信息。

在URI中體現(xiàn)資源，而非動作

• 在構建API的URL的時候，URI中應該僅包含資源（對象），而不要加入動作。比如 /user/1/update ，其中update就是一個動作，雖然我們希望通過這個URI來實現(xiàn)用戶ID為1的用戶進行信息更新，但是按照RESTful的規(guī)范，作為動作，應該用上面的PUT來表示，所以請求更新用戶信息，應該使用 PUT /user/1 來表示更新用戶ID為1的用戶信息。
• 如果去對應上面的請求模式，GET表示顯示、列出、展示，POST表示提交、創(chuàng)建，PUT表示更新，DELETE表示刪除。

版本

• API的開發(fā)直接關系了APP是否可以正常使用，如果原本運行正常的API，突然改動，那么之前使用這個API的APP可能無法正常運行。APP是不可能強迫用戶主動升級的，因此，通過API版本來解決這個問題。也就是說，API的多個版本是同時運行的，而且都要保證可以正常使用。
• 按照RESTful的規(guī)范，不同的版本也應該用相同的API URL，通過header信息來判斷版本，再調用不同版本的程序進行處理。但是這明顯會給開發(fā)帶來巨大的成本。解決辦法有兩種：1.新版本兼容舊版本，所有舊版本的動作、字段、操作，都在新版本中可以被實現(xiàn)，但明顯這樣的維護成本很大；2.不同的版本，用不同的URL來提供服務，比如再URL中通過v1、v2來區(qū)分版本號，我則更喜歡采用子域名的方式，比如v2.api.xxx.com/user的方式。

HTTP響應碼
在用戶發(fā)出請求，服務端對請求進行響應時，給予正確的HTTP響應狀態(tài)碼，有利于讓客戶端正確區(qū)分遇到的情況。

• 200 OK - [GET]：服務器成功返回用戶請求的數(shù)據(jù)，該操作是冪等的（Idempotent）。
• 201 CREATED - [POST/PUT/PATCH]：用戶新建或修改數(shù)據(jù)成功。
• 202 Accepted - [* ] ：表示一個請求已經(jīng)進入后臺排隊（異步任務）
• 204 NO CONTENT - [DELETE]：用戶刪除數(shù)據(jù)成功。
• 400 INVALID REQUEST - [POST/PUT/PATCH]：用戶發(fā)出的請求有錯誤，服務器沒有進行新建或修改數(shù)據(jù)的操作，該操作是冪等的。
• 401 Unauthorized - [* ]：表示用戶沒有權限（令牌、用戶名、密碼錯誤）。
• 403 Forbidden - [* ] 表示用戶得到授權（與401錯誤相對），但是訪問是被禁止的。
• 404 NOT FOUND - [* ]：用戶發(fā)出的請求針對的是不存在的記錄，服務器沒有進行操作，該操作是冪等的。
• 406 Not Acceptable - [GET]：用戶請求的格式不可得（比如用戶請求JSON格式，但是只有XML格式）。
• 410 Gone -[GET]：用戶請求的資源被永久刪除，且不會再得到的
• 422 Unprocesable entity - [POST/PUT/PATCH] 當創(chuàng)建一個對象時，發(fā)生一個驗證錯誤。
• 500 INTERNAL SERVER ERROR - [* ]：服務器發(fā)生錯誤，用戶將無法判斷發(fā)出的請求是否成功。

返回值結構

用JSON進行返回，而非xml。

原因：

1. JSON可以很好的被很多程序支持，javascript的ajax可以直接將JSON轉換為對象。
2. 2. JSON的格式在容量上比xml小很多，可以減低寬帶占用，提高傳輸效率。

那么，返回值應該怎么去部署呢？

• 首先，字段的合理返回，數(shù)據(jù)的包裹。因為返回值中，我們常常要對數(shù)據(jù)進行區(qū)分分組，或者按照從屬關系打包，所以，我們再返回時，最好有包裹的思想，把數(shù)據(jù)存放在不同的包裹中進行返回。可以使用data來作為數(shù)據(jù)包，將所有數(shù)據(jù)統(tǒng)一以這個字段進行包裹。除了data，也可以用list等其他形式的包裹，命名都是自己來根據(jù)自己的需要確定的。
• 總之，不要不分包，直接把所有數(shù)據(jù)和一些你想返回的全局數(shù)據(jù)混在一起進行返回。
• 其次，錯誤碼。錯誤碼的作用是方便查找錯誤原因，通常情況下，我喜歡用error_code來表示，當error_code=0時，表示沒有發(fā)生錯誤，當error_code>0時，發(fā)生了錯誤，并且提供較為詳細的文檔，告訴客戶端對應的error_code值所產(chǎn)生的錯誤的原因和位置。
• 最后，空白壓縮和字符轉換。也就是返回的JSON結果不要換行和空格，用一行返回結果，使整個結果文本容量最小。同時，中文等字符或結果中有引號，都進行字符轉換，防止結果無法被正確識別。

鑒權

• 其實也就是客戶端的權限控制。一般而言，我會采用給客戶端分發(fā)一個token來確定該客戶端的唯一身份。客戶端在請求時，通過這個token，判斷發(fā)出請求的客戶端所對應的用戶，及其相關信息和權限。
• token信息不是用來進行處理的數(shù)據(jù)，雖然可以通過POST、PUT等進行數(shù)據(jù)提交或傳輸，但是從RESTful規(guī)范來講，它不屬于操作數(shù)據(jù)，在服務端進行處理時，僅是利用token進行鑒權處理，所以，我的建議是通過header來發(fā)送token。
• 國內大部分API對PUT、DELETE請求進行了閹割，更不用提HEAD、PACTH、OPTIONS請求。實際上，國內大部分開放API僅支持GET和POST兩種，部分API支持將app key信息通過header進行發(fā)送。在面對這種情況下，我們不得不拋棄標準的RESTful規(guī)范，在url中加入get、add、update、delete等動作詞匯，以補充由于請求支持不完善帶來的動作區(qū)分問題。如果僅支持GET和POST，那么所有需要保密的數(shù)據(jù)，絕對不可以用GET來進行請求，而必須用POST。

接口的安全

保證接口的可用性

接口的效率

接口的版本控制

算法

時間復雜度

**算法分析 **

• 同一問題可用不同算法解決,而一個算法的質量優(yōu)劣將影響到算法乃至程序的效率.算法分析的目的在 于選擇合適算法和改進算法.一個算法的評價主要從時間復雜度和空間復雜度來考慮.
• 計算機科學中，算法的時間復雜度是一個函數(shù)，它定性描述了該算法的運行時間。這是一個關于代 表算法輸入值的字符串的長度的函數(shù)。時間復雜度常用大O符號表述，不包括這個函數(shù)的低階項和首 項系數(shù)。使用這種方式時，時間復雜度可被稱為是漸近的，它考察當輸入值大小趨近無窮時的情況

**時間復雜度 **

在計算機科學中，算法的時間復雜度是一個函數(shù)，它定性描述了該算法的運行時間。這是一個關于 代表算法輸入值的字符串的長度的函數(shù)。時間復雜度常用大O符號表述，不包括這個函數(shù)的低階項和 首項系數(shù)。

**計算方法 **

1.一般情況下，算法中基本操作重復執(zhí)行的次數(shù)是問題規(guī)模n的某個函數(shù)，用T(n)表示，若有某個輔 助函數(shù)f(n)，使得T(n)/f(n)的極限值（當n趨近于無窮大時）為不等于零的常數(shù)，則稱f(n)是T(n)的同 數(shù)量級函數(shù)。記作T(n)=O(f(n))，稱O(f(n)) 為算法的漸進時間復雜度，簡稱時間復雜度。 分析：隨著模塊n的增大，算法執(zhí)行的時間的增長率和 f(n) 的增長率成正比，所以 f(n) 越小，算法的 時間復雜度越低，算法的效率越高。

2. 在計算時間復雜度的時候，先找出算法的基本操作，然后根據(jù)相應的各語句確定它的執(zhí)行次數(shù)， 再找出 T(n) 的同數(shù)量級（它的同數(shù)量級有以下：1，log2n，n，n log2n ，n的平方，n的三次方，2 的n次方，n!），找出后，f(n) = 該數(shù)量級，若 T(n)/f(n) 求極限可得到一常數(shù)c，則時間復雜度T(n) = O(f(n))
   3.在pascal中比較容易理解，容易計算的方法是：看看有幾重for循環(huán)，只有一重則時間復雜度為 O(n)，二重則為O(n^2)，依此類推，如果有二分則為O(logn)，二分例如快速冪、二分查找，如果一 個for循環(huán)套一個二分，那么時間復雜度則為O(nlogn)。

**分類 **

• 按數(shù)量級遞增排列，常見的時間復雜度有： 常數(shù)階O(1),對數(shù)階O(log 2的n次方 ),線性階O(n), 線性對數(shù)階O(nlog2n),平方階O(n^{2)，立方階O(n}3),...， k次方階O(n^{k),指數(shù)階O(2}n)。
• 隨著問題規(guī)模n的不斷增大，上述時間復雜度不斷增大，算法的執(zhí)行 效率越低。

理解

• 整個算法的執(zhí)行時間與基本操 作重復執(zhí)行的次數(shù)成正比。
• 基本操作重復執(zhí)行的次數(shù)是問題規(guī)模n的某個函數(shù)f(n)，于是算法的時間量度可以記為：T(n) = O(f(n)) 如果按照這么推斷，T(n)應該表示的是算法的時間量度，也就是算法執(zhí)行的時間。
• 而該頁對“語句頻度”也有定義：指的是該語句重復執(zhí)行的次數(shù)。
• 如果是基本操作所在語句重復執(zhí)行的次數(shù)，那么就該是f(n)。 上邊的n都表示的問題規(guī)模。

總結
時間頻度

一個算法執(zhí)行所耗費的時間,從理論上是不能算出來的,必須上機運行測試才能知道.但我們不可能也沒 有必要對每個算法都上機測試,只需知道哪個算法花費的時間多,哪個算法花費的時間少就可以了.并且 一個算法花費的時間與算法中語句的執(zhí)行次數(shù)成正比例,哪個算法中語句執(zhí)行次數(shù)多,它花費時間就多. 一個算法中的語句執(zhí)行次數(shù)稱為語句頻度或時間頻度.記為T(n).

時間復雜度

• 一般情況下,算法中基本操作重復執(zhí)行的次數(shù)是問題規(guī)模n的某個函數(shù),用T(n)表示,若有某個輔助函數(shù) f(n),使得當n趨近于無窮大時,T（n)/f(n)的極限值為不等于零的常數(shù),則稱f(n)是T(n)的同數(shù)量級函數(shù). 記作T(n)=O(f(n)),稱O(f(n)) 為算法的漸進時間復雜度,簡稱時間復雜度.
• 在各種不同算法中,若算法中語句執(zhí)行次數(shù)為一個常數(shù),則時間復雜度為O(1),另外,在時間頻度不相同 時,時間復雜度有可能相同,如T(n)=n^{2+3n+4與T(n)=4n}2+2n+1它們的頻度不同,但時間復雜度 相同,都為O(n2).
• 按數(shù)量級遞增排列,常見的時間復雜度有： 常數(shù)階O(1),對數(shù)階O(log2n),線性階O(n), 線性對數(shù)階O(nlog2n),平方階O(n2),立方階O(n3),...,
• k次方階O(nk),指數(shù)階O(2n).隨著問題規(guī)模n的不斷增大,上述時間復雜度不斷增大,算法的執(zhí)行效率越 低.

空間復雜度

• 與時間復雜度類似,空間復雜度是指算法在計算機內執(zhí)行時所需存儲空間的度量.記作: S(n)=O(f(n)) 我們一般所討論的是除正常占用內存開銷外的輔助存儲單元規(guī)模.
  • O(1): 表示算法的運行時間為常量
  • O(n): 表示該算法是線性算法
  • O(㏒2n): 二分查找算法
  • O(n2): 對數(shù)組進行排序的各種簡單算法，例如直接插入排序的算法。
  • O(n3): 做兩個n階矩陣的乘法運算
  • O(2n): 求具有n個元素集合的所有子集的算法
  • O(n!): 求具有N個元素的全排列的算法
  • O(n2)表示當n很大的時候，復雜度約等于Cn2，C是某個常數(shù)，簡單說就是當n足夠大的 時候，n的線性增長，復雜度將沿平方增長。
• 一個算法執(zhí)行所耗費的時間，從理論上是不能算出來的，必須上機運行測試才能知道。 但我們不可能也沒有必要對每個算法都上機測試，只需知道哪個算法花費的時間多，哪 個算法花費的時間少就可以了。并且一個算法花費的時間與算法中語句的執(zhí)行次數(shù)成正 比例，哪個算法中語句執(zhí)行次數(shù)多，它花費時間就多。一個算法中的語句執(zhí)行次數(shù)稱為 語句頻度或時間頻度。記為T(n)。
• 一般情況下，算法中基本操作重復執(zhí)行的次數(shù)是問題規(guī)模n的某個函數(shù)，用T(n)表示， 若有某個輔助函數(shù)f(n),使得當n趨近于無窮大時，T（n)/f(n)的極限值為不等于零的常 數(shù)，則稱f(n)是T(n)的同數(shù)量級函數(shù)。記作T(n)=O(f(n)),稱O(f(n))

性能比較

[圖片上傳失敗...(image-8270e-1572255684151)]

排序 算法

交換排序：交換排序的基本思想是，比較兩個記錄鍵值的大小，如果這兩個記錄鍵值的大小出現(xiàn)逆 序，則交換這兩個記錄，這樣將鍵值較小的記錄向序列前部移動，鍵值較大的記錄向序列后部移動。

冒泡排序

冒泡排序（Bubble Sort，臺灣譯為：泡沫排序或氣泡排序）是一種簡單的排序算法。它重復 地走訪過要排序的數(shù)列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。走訪 數(shù)列的工作是重復地進行直到?jīng)]有再需要交換，也就是說該數(shù)列已經(jīng)排序完成。這個算法的 名字由來是因為越小的元素會經(jīng)由交換慢慢“浮”到數(shù)列的頂端。

步驟

1. 比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。
2. 對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最后一對。在這一 點，最后的元素應該會是最大的數(shù)。 3. 針對所有的元素重復以上的步驟，除了最后一個。
3. 持續(xù)每次對越來越少的元素重復上面的步驟，直到?jīng)]有任何一對數(shù)字需要比 較。

冒泡排序理解起來是最簡單，但是時間復雜度（O(n^2)）也是最大的之一

快速排序

快速排序是由東尼?霍爾所發(fā)展的一種排序算法。在平均狀況下，排序 n 個項目要Ο(n log n) 次比較。在最壞狀況下則需要Ο(n2)次比較，但這種狀況并不常見。事實上，快速排序通常明 顯比其他Ο(n log n) 算法更快，因為它的內部循環(huán)（inner loop）可以在大部分的架構上很 有效率地被實現(xiàn)出來，且在大部分真實世界的數(shù)據(jù)，可以決定設計的選擇，減少所需時間的 二次方項之可能性。

步驟

1. 從數(shù)列中挑出一個元素，稱為 “基準”（pivot）
2. 重新排序數(shù)列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大 的擺在基準的后面（相同的數(shù)可以到任一邊）。在這個分區(qū)退出之后，該基準就處于數(shù)列的中間位置。這個稱為分區(qū)（partition）操作。
3. 遞歸地（recursive）把小于基準值元素的子數(shù)列和大于基準值元素的子數(shù)列排 序。

快排也是一個高效的排序算法，它的時間復雜度也是O(nlogn)

選擇排序

• 選擇排序(Selection sort)是一種簡單直觀的排序算法。首先在未排序序 列中找到最小元素，存放到排序序列的起始位置，然后，再從剩余未排序元素中繼續(xù)尋找最 小元素，然后放到排序序列末尾。以此類推，直到所有元素均排序完畢。
• 選擇排序包括兩種，分別是直接選擇排序和堆排序，選擇排序的基本思想是每一次在ni+1（i=1,2,3，...，n-1）個記錄中選取鍵值最小的記錄作為有序序列的第i個記錄

堆排序

堆積排序（Heapsort）是指利用堆這種數(shù)據(jù)結構所設計的一種排序算法。堆是一個近似完全 二叉樹的結構，并同時滿足堆性質：即子結點的鍵值或索引總是小于（或者大于）它的父節(jié) 點。

步驟

堆排序是指利用堆積樹（堆）這種數(shù)據(jù)結構所設計的一種排序算法，利用數(shù)組的特點快速定位指定 索引的元素。堆分為大根堆和小根堆，是完全二叉樹。大根堆的要求是每個節(jié)點的值都不大于其父 節(jié)點的值，即A[PARENT[i]] >= A[i]。在數(shù)組的非降序排序中，需要使用的就是大根堆，因為根據(jù) 大根堆的要求可知，最大的值一定在堆頂。

堆排序是一種高效的排序算法，它的時間復雜度是O(nlogn)。原理是：先把數(shù)組轉為一個最 大堆，然后把第一個元素跟第i元素交換，然后把剩下的i-1個元素轉為最大堆，然后再把第一 個元素與第i-1個元素交換，以此類推

插入排序

插入排序（Insertion Sort）的算法描述是一種簡單直觀的排序算法。它的工作原理是通過構 建有序序列，對于未排序數(shù)據(jù)，在已排序序列中從后向前掃描，找到相應位置并插入。插入 排序在實現(xiàn)上，通常采用in-place排序（即只需用到O(1)的額外空間的排序），因而在從后向 前掃描過程中，需要反復把已排序元素逐步向后挪位，為最新元素提供插入空間。

步驟

1. 從第一個元素開始，該元素可以認為已經(jīng)被排序
2. 取出下一個元素，在已經(jīng)排序的元素序列中從后向前掃描
3. 如果該元素（已排序）大于新元素，將該元素移到下一位置
4. 重復步驟3，直到找到已排序的元素小于或者等于新元素的位置
5. 將新元素插入到該位置中
6. 重復步驟2

插入排序跟冒泡排序有點相似，時間復雜度也是O(n^2)

希爾排序

• 希爾排序，也稱遞減增量排序算法，是插入排序的一種高速而穩(wěn)定的改進版本。 希爾排序是基于插入排序的以下兩點性質而提出改進方法的：
  • 1、插入排序在對幾乎已經(jīng)排好序的數(shù)據(jù)操作時， 效率高， 即可以達到線性排序的效率
  • 2、但插入排序一般來說是低效的， 因為插入排序每次只能將數(shù)據(jù)移動一位>
• 希爾排序其實可以理解是插入排序的一個優(yōu)化版，它的效率跟增量有關，增量要取多 少，根據(jù)不同的數(shù)組是不同的，所以希爾排序是一個不穩(wěn)定的排序算法，它的時間復雜 度為O(nlogn)到O(n^2)之間

歸并排序

歸并排序（Merge sort，臺灣譯作：合并排序）是建立在歸并操作上的一種有效的排序算 法。該算法是采用分治法（pide and Conquer）的一個非常典型的應用

步驟

1. 申請空間，使其大小為兩個已經(jīng)排序序列之和，該空間用來存放合并后的序列
2. 設定兩個指針，最初位置分別為兩個已經(jīng)排序序列的起始位置
3. 比較兩個指針所指向的元素，選擇相對小的元素放入到合并空間，并移動指針 到下一位置
4. 重復步驟3直到某一指針達到序列尾
5. 將另一序列剩下的所有元素直接復制到合并序列尾

歸并排序的時間復雜度也是O(nlogn)。原理是：對于兩個排序好的數(shù)組，分別遍歷這兩 個數(shù)組，獲取較小的元素插入新的數(shù)組中，那么，這么新的數(shù)組也會是排序好的。

順序查找

** 說明**

順序查找適合于存儲結構為順序存儲或鏈接存儲的線性表。

基本思想
順序查找也稱為線形查找，屬于無序查找算法。從數(shù)據(jù)結構線形表的一端開始，順 序掃描，依次將掃描到的結點關鍵字與給定值k相比較，若相等則表示查找成功；若掃描結束仍沒有 找到關鍵字等于k的結點，表示查找失敗。

**復雜度分析 **

查找成功時的平均查找長度為：（假設每個數(shù)據(jù)元素的概率相等） ASL = 1/n(1+2+3+…+n) = (n+1)/2 ? 當查找不成功時，需要n+1次比較，時間復雜度為O(n)?

二分查找

二分搜索（binary search），也稱折半搜索（half-interval search）、對數(shù)搜索（logarithmic search），是一種在有序數(shù)組中查找某一特定元素的搜索算法。搜索過程從數(shù)組的中間元素開始，如果中間元素正好是要查找的元素，則搜索過程結束；如果某一特定元素大于或者小于中間元素，則在數(shù)組大于或小于中間元素的那一半中查找，而且跟開始一樣從中間元素開始比較。如果在某一步驟數(shù)組為空，則代表找不到。這種搜索算法每一次比較都使搜索范圍縮小一半。

思路

• 查找的k可能在數(shù)組下標區(qū)間a,b
• 計算區(qū)間ab的中間點m
• k < tarr[m] 將區(qū)間縮小為a,m繼續(xù)二分查找
• k >arr[m] 將區(qū)間縮小為m，b，繼續(xù)二分查找

** 復雜度分析**

最壞情況下，關鍵詞比較次數(shù)為log2(n+1)，且期望時間復雜度為O(log2n)；

其他鏈接

優(yōu)惠券

優(yōu)惠券業(yè)務設計

鏈接: http://www.itdecent.cn/p/269a54846a9c

技術架構設計：https://blog.csdn.net/HUXU981598436/article/details/78048919

優(yōu)惠券表設計：

https://blog.csdn.net/t_332741160/article/details/86591243

優(yōu)惠券業(yè)務設計

https://blog.csdn.net/egworkspace/article/details/80414953

https://learnku.com/articles/28758#edfe81

原文：https://learnku.com/articles/28772#7b3802