我們知道程序由數據結構和算法組成的。其中，數據結構表示數據的組織形式，基本的數據結構包括數組、鏈表、棧、隊列、樹、哈希表、圖、堆等。而算法表示對數據結構中的數據進行處理的方式或過程，換句話說，就是解決問題的方法。它們倆之間的關系：數據結構為算法服務，很多算法依賴于特定的數據結構，但不是全部算法，算法可以和數據結構沒有關系。本期我們就來聊一聊算法。

學習算法的重要性

在介紹具體算法之前，我先談一下個人對學習算法的初心。我的初心無非有兩點：一，BAT等互聯網公司招聘面試時要問算法知識，如果想要進入互聯網公司，我就必須學好算法；二，通過學習算法提升個人開發的基本功，這樣一來，對于不同場景我就可以正確選擇對應的數據結構和算法，使得程序更健壯，提高程序的運行效率。

應用領域

目前計算機各個細分領域涉及到不同的算法。比如說搜索引擎，平時我們使用google、百度等瀏覽器，只要我們輸入一個關鍵字，瀏覽器就會快速地返回相關的集合，這個集合的背后就隱藏著許多算法。如果沒有這些算法，我們是不可能這么快速地得到想要的結果。再比如說人工智能，通過計算模型算法實現人體識別、語音識別等各應用場景。

算法分析

上文我們已經介紹到算法就是解決問題的方法，而對于同一個問題，可能存在不同的解決方法。因此，為了衡量一個算法的優劣，提出了時間復雜度與空間復雜度這兩個概念。

時間復雜度

一般情況下，算法中基本操作重復執行的次數是問題規模n的某個函數f(n)，算法的時間度量記為 T(n) = O(f(n))，它表示隨問題規模n的增大，算法執行時間的增長率和f(n)的增長率相同，稱作算法的漸近時間復雜度，簡稱時間復雜度。

空間復雜度

空間復雜度是對一個算法在運行過程中臨時占用存儲空間大小的量度，記做S(n)=O(f(n))。一個算法的優劣主要從算法的執行時間和所需要占用的存儲空間兩個方面衡量。

排序算法

根據時間復雜度我們大體可以將排序算法分為兩類，一類是以選擇排序為代表的O(n^2)的算法，另一類是以快速排序為代表的O(nlogn)的算法。看到這里我們不禁會問：既然有O(nlogn)的排序算法，那些O(n^2)的算法還有存在的必要嗎？要回答這個問題，先來看下O(n^2)的排序算法的特點：首先，它相對是比較基礎的，編碼簡單，易于實現，在一些特定場景下O(n^2)更適合 ，譬如在機器語言中O(n^2)更容易實現；其次，簡單的排序算法思路衍生出復雜的排序算法，比如說希爾排序是對插入排序的優化；最后，對于一些簡單的算法，由于它們本身的一些性質，可以被用作改進更復雜排序算法的子過程中。基于此，本文O(n^2)排序算法中兩個代表性的算法即選擇算法和插入算法。

選擇排序

思想：在整個待排序數組里找到最小的值，然后和待排序中的第一個元素進行交換，接著在剩下的元素里找到最小的元素，接著將它和待排序中的第一個元素進行交換，以此類推。為了加深大家的理解，舉個具體例子，對8、6、2、3、1、5、7、4進行升序排序。

選擇排序的Java語言實現如下：

/*** 思路：每次從待選數組中選擇一個最小元素，然后和對應位置交換位置* @param arr* @param n*/public void sort(int[] arr, int n) {for(int i=0;i<n;i++) {// 1. 尋找[i,n)區間里的最小元素int minIndex = i;for(int j=i+1;j<n;j++ ) {if (arr[j] < arr[minIndex]) {minIndex = j;}}// 2. 交換位置this.swap(arr,i,minIndex);}} 復制代碼

插入排序

思路：插入排序是在一個已經有序的小序列的基礎上，一次插入一個元素。當然，剛開始這個有序的小序列只有1個元素，就是第一個元素。比較是從有序序列的末尾開始，也就是想要插入的元素和已經有序的最大者開始比起，如果比它大則直接插入在其后面，否則一直往前找直到找到它該插入的位置。如果碰見一個和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后順序沒有改變，從原無序序列出去的順序就是排好序后的順序，所以插入排序是穩定的。

插入排序的Java語言實現如下：

public void sort(Comparable[] arr){int n = arr.length;for (int i = 0; i < n; i++) {// 尋找元素arr[i]合適的插入位置for( int j = i; j > 0 && arr[j].compareTo(arr[j-1]) < 0 ; j--)swap(arr, j, j-1);}} 復制代碼

通過比較選擇排序和插入排序的代碼實現，我們可以發現一旦有部分排序好之后，新插入一個數如果比排好序最大值還要大，則不用再和其他數字比較，減少了比較次數。但是，我們應該注意到插入排序在每次遍歷的時候都需要進行交換操作，這個交換操作包含三次賦值操作，導致插入排序的時間要比選擇排序的時間更長。針對這個問題，我們的先輩們想到了一個方法：先將待比較元素復制一份，然后依次和有序數組中的元素進行比較，如果比有序數組中的元素小，則將有序數組中的元素覆蓋待比較元素，以此類推。如下圖所示，首先我們將元素6復制一份，接著驗證元素6是否應當放在當前位置，通過比較6和它之前的元素大小，發現元素8應該放在元素6的位置上，因此將元素8覆蓋元素6，然后我們考查元素6是否應該放在前一個元素位置上，此時，由于元素8在第0個位置上我們就不用比較直接覆蓋。它的Java代碼實現如下：

for (int i = 0; i < n; i++) {// 尋找元素arr[i]合適的插入位置Comparable e = arr[i];int j = i;for( ; j > 0 && arr[j-1].compareTo(e) > 0 ; j--)arr[j] = arr[j-1];arr[j] = e;} 復制代碼

這樣一來，內循環只需要進行一次賦值操作，效率得到了大大優化，不僅超過了選擇排序，而且在待排序數組是有序的情況下，時間復雜度可以達到O(n)。

---

歡迎關注微信公眾號：木可大大，所有文章都將同步在公眾號上。

總結

以上是生活随笔為你收集整理的算法初体验的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。