排序，搜索，算法模式，算法復雜度 | 數據結構與算法綜合筆記
圖 樹 字典,散列表 集合 鏈表 隊列 棧
冒泡排序，選擇排序，插入排序，歸并排序，快速排序，堆排序，順序搜索，二分搜索算法
排序算法
先創(chuàng)建一個數組來表示待排序和搜索的數據結構
function ArrayList(){
var array = []; //將項存儲在數組中
this.insert = function(item){ //插入方法來向數據結構中添加元素
array.push(item);
};
this.toString = function(){ //來拼接數組中的所有元素至一個單一的字符串
return array.join();
};
}
// join方法拼接數組元素至一個字符串，并返回該字符串
冒泡排序
冒泡排序在運行時間的角度來看，是最差的。
原理：
冒泡排序比較任何兩個相鄰的項，如果第一個比第二個大，則交換它們。元素項向上移動到正確的順序，就像氣泡升至表面一樣，冒泡排序因此得名。
實現冒泡排序：
this.bubbleSort = function(){
var length = array.length; // 用來存儲數組的長度
for (var i=0; i<length; i++){
// 會從數組的第一位迭代至最后一位，它控制了在數組中經過多少輪排序
// 應該是數組中每項都經過一輪，輪數和數組長度一致
for (var j=0; j<length-1; j++ ){
//內循環(huán)將從第一位迭代至倒數第二位
//內循環(huán)實際上進行當前項和下一項的比較
if (array[j] > array[j+1]){
swap(array, j, j+1); //{5}
}
}
}
};
// 聲明swap函數
// 一個私有函數
var swap = function(array, index1, index2){
var aux = array[index1];
array[index1] = array[index2];
array[index2] = aux;
};
// 我們用一個中間值來存儲某一交換項的值
ES6寫法：
[array[index1], array[index2]] = [array[index2], array[index1]];
從內循環(huán)減去外循環(huán)中已跑過的輪數
進階冒泡排序：
this.modifiedBubbleSort = function(){
var length = array.length;
for (var i=0; i<length; i++){
for (var j=0; j<length-1-i; j++ ){ //避免內循環(huán)中所有不必要的比較
if (array[j] > array[j+1]){
swap(j, j+1);
}
}
}
};
選擇排序(一種原址比較排序算法)
原理：找到數據結構中的最小值并將其放置在第一位，接著找到第二小的值并將其放在第二位，以此類推
示例：
this.selectionSort = function(){
var length = array.length, indexMin;
for (var i=0; i<length-1; i++){
indexMin = i;
for (var j=i; j<length; j++){
if(array[indexMin]>array[j]){
indexMin = j;
}
}
if (i !== indexMin){
swap(i, indexMin);
}
}
};
插入排序
插入排序每次排一個數組項，以此方式構建最后的排序數組
示例：
this.insertionSort = function(){
var length = array.length, j, temp;
for (var i=1; i<length; i++){
j = i;
temp = array[i];
while (j>0 && array[j-1] > temp){
array[j] = array[j-1];
j--;
}
array[j] = temp;
}
};
歸并排序
歸并排序是第一個可以被實際使用的排序算法
原理：
將原始數組切分成較小的數組，直到每個小數組只有一個位置，接著將小數組歸并成較大的數組，直到最后只有一個排序完畢的大數組。
歸并排序是一種分治算法 歸并排序也是遞歸的
this.mergeSort = function(){
array = mergeSortRec(array);
};
遞歸函數
// 歸并排序將一個大數組轉化為多個小數組直到只有一個項
var mergeSortRec = function(array){
var length = array.length;
if(length === 1) { //判斷數組的長度是否為1
return array; //返回這個長度為1的數組
}
var mid = Math.floor(length / 2), //如果數組長度比1大，那么我們得將其分成小數組
left = array.slice(0, mid),
//left數組由索引0至中間索引的元素組成
right = array.slice(mid, length);
//right數組由中間索引至原始數組最后一個位置的元素組成
return merge(mergeSortRec(left), mergeSortRec(right)); //將數組分成兩個小數組
};
示例：
// merge函數接受兩個數組作為參數
// 并將它們歸并至一個大數組
var merge = function(left, right){
var result = [], // 聲明歸并過程要創(chuàng)建的新數組
il = 0,
ir = 0;
while(il < left.length && ir < right.length) { // 迭代兩個數組
// 比較來自left數組的項是否比來自right數組的項小
if(left[il] < right[ir]) {
result.push(left[il++]);
// 將該項從left數組添加至歸并結果數組，并遞增迭代數組的控制變量
} else{
result.push(right[ir++]);
// 從right數組添加項并遞增相應的迭代數組的控制變量
}
}
while (il < left.length){ // {11}
result.push(left[il++]);
}
while (ir < right.length){ // {12}
result.push(right[ir++]);
}
return result; // {13}
};
快速排序
從數組中選擇中間一項作為主元 創(chuàng)建兩個指針，左邊一個指向數組第一個項，右邊一個指向數組最后一個項 移動左指針直到我們找到一個比主元大的元素 移動右指針直到找到一個比主元小的元素
示例：
this.quickSort = function(){
quick(array, 0, array.length - 1);
};
示例：
var quick = function(array, left, right){
var index; //該變量能幫助我們將子數組分離為較小值數組和較大值數組
if (array.length > 1) { //因為只有一個元素的數組必然是已排序了的
index = partition(array, left, right); //。partition函數返回值將賦值給index
if (left < index - 1) { //如果子數組存在較小值的元素
quick(array, left, index - 1); //對該數組重復這個過程
}
if (index < right) { //對存在較大值的子數組 如果存在子數組存在較大值
quick(array, index, right); //對該數組重復這個過程
}
}
};
劃分過程
1.選擇主元
劃分過程：
var partition = function(array, left, right) {
var pivot = array[Math.floor((right + left) / 2)], //選擇中間項作為主元
i = left, //初始化兩個指針 初始化為數組第一個元素
j = right; //初始化兩個指針 初始化為數組最后一個元素
while (i <= j) { //只要left和right指針沒有相互交錯就執(zhí)行劃分操作
while (array[i] < pivot) { //移動left指針直到找到一個元素比主元大
i++;
}
while (array[j] > pivot) { //移動right指針直到我們找到一個元素比主元小
j--;
}
if (i <= j) { //當左指針指向的元素比主元大且右指針指向的元素比主元小
// 左指針索引沒有右指針索引大 左項比右項大
swap(array, i, j); //交換它們，然后移動兩個指針
i++;
j--;
}
}
return i;
};
展示圖：
下面的示意圖展示了對有較小值的子數組執(zhí)行的劃分操作
繼續(xù)創(chuàng)建子數組，請看下圖
繼續(xù)進行劃分
繼續(xù)進行劃分
堆排序
一種很高效的算法 把數組當作二叉樹來排序而得名
1.索引0是樹的根節(jié)點；
2.除根節(jié)點外，任意節(jié)點N的父節(jié)點是N/2；
3.節(jié)點L的左子節(jié)點是2*L；
4.節(jié)點R的右子節(jié)點是2*R+1
數組[3, 5, 1, 6, 4, 7, 2]想象成下面的樹
示例：
this.heapSort = function() {
var heapSize = array.length;
buildHeap(array); //構造一個滿足array[parent(i)] ≥ array[i]的堆結構
while (heapSize > 1) {
heapSize--;
swap(array, 0, heapSize); //交換堆里第一個元素和最后一個元素的位置
heapify(array, heapSize, 0);
//找到當前堆的根節(jié)點（較小的值），重新放到樹的底部
}
};
buildHeap函數實現如下
var buildHeap = function(array){
var heapSize = array.length;
for (var i = Math.floor(array.length / 2); i >= 0; i--) {
heapify(array, heapSize, i);
}
};
堆的構建過程如下：(調用buildHeap函數)
數組[3, 5, 1, 6, 4, 7, 2]
var heapify = function(array, heapSize, i){
var left = i * 2 + 1,
right = i * 2 + 2,
largest = i;
if (left < heapSize && array[left] > array[largest]) {
largest = left;
}
if (right < heapSize && array[right] > array[largest]) {
largest = right;
}
if (largest !== i) {
swap(array, i, largest);
heapify(array, heapSize, largest);
}
};
排序(分布式排序)
1.計數排序
2.桶排序
3.基數排序
最著名的分布式算法有計數排序、桶排序和基數排序
搜索算法-順序搜索
順序或線性搜索是最基本的搜索算法 將每一個數據結構中的元素和我們要找的元素做比較
示例：
this.sequentialSearch = function(item){
for (var i=0; i<array.length; i++){ //順序搜索迭代整個數組
if (item === array[i]) //將每個數組元素和搜索項作比較
return i; //搜索成功
// 返回值可以是該搜索項本身，或是true，又或是搜索項的索引
}
}
return -1; //沒有找到該項，則返回-1 表示該索引不存在
};
搜索算法-二分搜索
游戲示例：一個1到100的數字游戲。我們每回應一個數字，那個人就會說這個數字是高了、低了還是對了。
示例：
this.binarySearch = function(item){
this.quickSort(); //需要先將數組排序
var low = 0, // 在數組排序之后，我們設置low和high指針
high = array.length - 1,
mid, element;
while (low <= high){ //當low比high小時
mid = Math.floor((low + high) / 2);
element = array[mid];
if (element < item) {
//比較選中項的值和搜索值
low = mid + 1;
} else if (element > item) {
high = mid - 1;
} else {
return mid;
}
}
return -1; //我們計算得到中間項索引并取得中間項的值
//此處如果low比high大，則意思是該待搜索值不存在并返回-1
};
執(zhí)行的步驟：
冒泡、選擇、插入、歸并、快速以及堆排序算法，順序搜索和二分搜索
算法模式
遞歸 動態(tài)規(guī)劃 貪心算法
示例:
function recursiveFunction(someParam){
recursiveFunction(someParam);
};
function recursiveFunction1(someParam){
recursiveFunction2(someParam);
};
function recursiveFunction2(someParam){
recursiveFunction1(someParam);
};
它會一直執(zhí)行下去(棧溢出錯誤)。(需要一個不再遞歸調用的條件)
JavaScript 調用棧大小的限制
示例：
var i = 0;
function recursiveFn () {
i++;
recursiveFn();
}
try {
recursiveFn();
} catch (ex) {
alert('i = ' + i + ' error: ' + ex);
// 超限錯誤：超過最大調用棧大小
// 內部錯誤：遞歸次數過多
}
es6尾調用優(yōu)化
斐波那契數列
1和2的斐波那契數是 1 n（n>2）的斐波那契數是(n?1)的斐波那契數加上(n?2)的斐波那契數
示例：
// 邊界條件是已知的，1和2的斐波那契數是1
function fibonacci(num){
if (num === 1 || num === 2){ //{1}
return 1;
}
}
function fibonacci(num){
if (num === 1 || num === 2){
return 1;
}
return fibonacci(num - 1) + fibonacci(num - 2);
}
// 當n大于2時，Fibonacci(n)等于Fibonacci(n-1)+Fibonacci(n-2)
用非遞歸的方式實現斐波那契函數：
function fib(num){
var n1 = 1,
n2 = 1,
n = 1;
for (var i = 3; i<=num; i++){
n = n1 + n2;
n1 = n2;
n2 = n;
}
return n;
}
動態(tài)規(guī)劃
一些著名的問題如下:
背包問題 最長公共子序列 矩陣鏈相乘 硬幣找零 圖的全源最短路徑
函數式編程簡介
函數式編程是借助ES6的能力，JavaScript也能夠進行函數式編程
用命令式編程，聲明的函數如下：
var printArray = function(array) {
for (var i = 0; i < array.length; i++) {
console.log(array[i]);
}
};
printArray([1, 2, 3, 4, 5]);
函數式編程:(重點是需要描述什么，而不是如何描述)
var forEach = function(array, action) {
for (var i = 0; i < array.length; i++) {
action(array[i]);
}
};
var logItem = function (item) {
console.log(item);
};
forEach([1, 2, 3, 4, 5], logItem);
1.目標是描述數據，以及要對數據應用的轉換
2.程序執(zhí)行順序的重要性很低，而在命令式編程中，步驟和順序是非常重要的
3.函數和數據集合是函數式編程的核心
4.在函數式編程中，我們可以使用和濫用函數和遞歸，而在命令式編程中，則使用循環(huán)、 賦值、條件和函數
map
把一個數據集合轉換或映射成另一個數據集合
filter
使用filter函數過濾一個集合的值
reduce
把一個集合歸約成一個特定的值
算法復雜度
著名的大O表示法 和NP完全理論
大 O 表示法
當討論大O表示法時，一般考慮的是CPU（時間）占用
O(1)
// 函數的復雜度是O(1)
// 和參數無關，increment函數的性能都一樣
function increment(num){
return ++num;
}
O(n)
// 時間復雜度是O(n)
// n是（輸入）數組的大小
function sequentialSearch(array, item){
for (var i=0; i<array.length; i++){
if (item === array[i]){ //{1}
return i;
}
}
return -1;
}
時間復雜度比較
常用數據結構的時間復雜度:
圖的時間復雜度:
排序算法的時間復雜度:
搜索算法的時間復雜度：
NP 完全理論
NP（nondeterministic polynomial，非確定性多項式）算法對于給定的問題，如果存在多項式算法，則計為 P（polynomial，多項式）如果一個問題可以在多項式時間內驗證解是否正確，則計為 NPNP問題中最難的是NP完全問題
1.是NP問題，也就是說，可以在多項式時間內驗證解，但還沒有找到多項式算法
2.所有的NP問題都能在多項式時間內歸約為它
P、NP、NP完全和NP困難 問題 圖：
推薦：NP完全性理論簡介
??關注+點贊+收藏+評論+轉發(fā)??，原創(chuàng)不易，鼓勵筆者創(chuàng)作更好的文章
點贊、收藏和評論
我是Jeskson(達達前端)，感謝各位人才的：點贊、收藏和評論，我們下期見！(如本文內容有地方講解有誤，歡迎指出?謝謝，一起學習了)
我們下期見！
文章持續(xù)更新，可以微信搜一搜「 程序員哆啦A夢 」第一時間閱讀，回復【資料】有我準備的一線大廠資料，本文 http://www.dadaqianduan.cn/#/ 已經收錄
github收錄，歡迎Star：https://github.com/webVueBlog/WebFamily
關注數：10億+ 文章數：10億+
粉絲量：10億+ 點擊量：10億+
微信群管理員請掃描這里
微信群管理員請掃描這里
喜歡本文的朋友，歡迎關注公眾號 程序員哆啦A夢，收看更多精彩內容
點個[在看]，是對小達最大的支持！
如果覺得這篇文章還不錯，來個【分享、點贊、在看】三連吧，讓更多的人也看
評論
圖片
表情