2.24早，沒事干，先自學一會

關于之前說過的創(chuàng)建對象：

第一種方式：

var person = new Object();

person.name = "孫悟空";

person.age = 18;

console.log(person);

第二種方式：

var person = {

? ? name: "孫悟空",

? ? age: 18

};

console.log(person);

這里引用的話就用對象.屬性名這樣的格式來寫

obj數(shù)據(jù)加上基本數(shù)據(jù)類型，一共6種，這里梳理一下所有的數(shù)據(jù)類型：

基本數(shù)據(jù)類型

JavaScript中的變量可能包含兩種不同數(shù)據(jù)類型的值：基本數(shù)據(jù)類型和引用數(shù)據(jù)類型。

JavaScript中一共有5種基本數(shù)據(jù)類型：String、Number、 Boolean、Undefined、Null

基本數(shù)據(jù)類型的值是無法修改的，是不可變的。

基本數(shù)據(jù)類型的比較是值的比較，也就是只要兩個變量的值相等，我們就認為這兩個變量相等。

引用數(shù)據(jù)類型

引用類型的值是保存在內(nèi)存中的對象。

當一個變量是一個對象時，實際上變量中保存的并不是對象本身，而是對象的引用。當從一個變量向另一個變量復制引用類型的值時，會將對象的引用復制到變量中，并不是創(chuàng)建一個新的對象。這時，兩個變量指向的是同一個對象。因此，改變其中一個變量會影響另一個

ok，完了就是今天最重要的內(nèi)容，排序算法?。。。。。。。。。?！

排序分為兩大類

比較排序，時間復雜度為O(nlogn) ~ O(n^2)，主要有：冒泡排序，選擇排序，插入排序，歸并排序，堆排序，快速排序等

非比較排序，時間復雜度可以達到O(n)，主要有：計數(shù)排序，基數(shù)排序，桶排序等

排序的定義

對一序列對象根據(jù)某個關鍵字進行排序。

穩(wěn)定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面；

不穩(wěn)定：如果a原本在b的前面，而a=b，排序之后a可能會出現(xiàn)在b的后面；

內(nèi)排序：所有排序操作都在內(nèi)存中完成；

外排序：由于數(shù)據(jù)太大，因此把數(shù)據(jù)放在磁盤中，而排序通過磁盤和內(nèi)存的數(shù)據(jù)傳輸才能進行；

時間復雜度：一個算法執(zhí)行所耗費的時間。

空間復雜度：運行完一個程序所需內(nèi)存的大小。

n: 數(shù)據(jù)規(guī)模

k: “桶”的個數(shù)

In-place: 占用常數(shù)內(nèi)存，不占用額外內(nèi)存

Out-place: 占用額外內(nèi)存

1、冒泡排序（Bubble Sort）

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

1.比較相鄰的元素。如果第一個比第二個大，就交換它們兩個；

2.對每一對相鄰元素作同樣的工作，從開始第一對到結(jié)尾的最后一對，這樣在最后的元素應該會是最大的數(shù)；

3.針對所有的元素重復以上的步驟，除了最后一個；

4.重復步驟1~3，直到排序完成。

?var arr = [20,63,50,40,10]

? ? ? ? var len = arr.length;

? ? ? ? ? ? for (var i = 0; i < len; i++) {

? ? ? ? ? ? ? ? for (var j = 0; j < len - 1 - i; j++) {

? ? ? ? ? ? ? ? ? ? if (arr[j] > arr[j + 1]) { ? ? ? //相鄰元素兩兩對比

? ? ? ? ? ? ? ? ? ? var temp = arr[j + 1]; ? ? ? //元素交換

? ? ? ? ? ? ? ? ? ? arr[j + 1] = arr[j];

? ? ? ? ? ? ? ? ? ? arr[j] = temp;

? ? ? ? ? ? ? ? ? ? }

? ? ? ? ? ? ? ? }

? ? ? ? ? ? }

? ? ? ? console.log(arr);

2、選擇排序（Selection Sort）

表現(xiàn)最穩(wěn)定的排序算法之一，因為無論什么數(shù)據(jù)進去都是O(n2)的時間復雜度，所以用到它的時候，數(shù)據(jù)規(guī)模越小越好。唯一的好處可能就是不占用額外的內(nèi)存空間了吧。理論上講，選擇排序可能也是平時排序一般人想到的最多的排序方法了吧。

選擇排序(Selection-sort)是一種簡單直觀的排序算法。它的工作原理：

1.在未排序序列中找到最?。ù螅┰?，存放到排序序列的起始位置，

2.再從剩余未排序元素中繼續(xù)尋找最?。ù螅┰?，

3.放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。

var arr = [20,63,50,40,10];

? ? ? ? var len = arr.length;

? ? ? ? var minIndex, temp;

? ? ? ? for (var i = 0; i < len - 1; i++) {

? ? ? ? ? ? minIndex = i;

? ? ? ? ? ? for (var j = i + 1; j < len; j++) {

? ? ? ? ? ? ? ? if (arr[j] < arr[minIndex]) { ? ?//尋找最小的數(shù)

? ? ? ? ? ? ? ? ? ? minIndex = j; ? ? ? ? ? ? ? ?//將最小數(shù)的索引保存

? ? ? ? ? ? ? ? }

? ? ? ? ? ? }

? ? ? ? ? ? temp = arr[i];

? ? ? ? ? ? arr[i] = arr[minIndex];

? ? ? ? ? ? arr[minIndex] = temp;

? ? ? ? }

? ? ? ? console.log(arr);

3、插入排序（Insertion Sort）

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

一般來說，插入排序都采用in-place在數(shù)組上實現(xiàn)。具體算法描述如下：

1.從第一個元素開始，該元素可以認為已經(jīng)被排序；

2.取出下一個元素，在已經(jīng)排序的元素序列中從后向前掃描；

3.如果該元素（已排序）大于新元素，將該元素移到下一位置；

4.重復步驟3，直到找到已排序的元素小于或者等于新元素的位置；

5.將新元素插入到該位置后；

6.重復步驟2~5。

? ????? var arr3 = [63,20,10,15,30];

? ? ? ? var len = arr3.length;

? ? ? ? var preIndex, current;

? ? ? ? for (var i = 1; i < len; i++) {

? ? ? ? ? ? preIndex = i - 1;

? ? ? ? ? ? current = arr3[i]; ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?//創(chuàng)立一個值用來保存需要插入的值

? ? ? ? ? ? while(preIndex >= 0 && arr3[preIndex] > current) { ?//用插入值與前值比較，若前者大于后者進入排序

? ? ? ? ? ? ? ? arr3[preIndex+1] = arr3[preIndex]; ? ? ? ? ? ? ?//該處相當于將前者向后移動一位，給插入值留出“空位”

? ? ? ? ? ? ? ? preIndex--; ?

? ? ? ? ? ? ? ? // console.log(arr3)

? ? ? ? ? ? } ?

? ? ? ? ? ? arr3[preIndex+1] = current; ? ? ? ? ? ? ? ? ? ? ? ? //若前者數(shù)值小于插入值時，跳出循環(huán)，將插入值插進“空位”

? ? ? ? ? ? // console.log(arr3)

? ? ? ? }

?4、歸并排序（Merge Sort）

和選擇排序一樣，歸并排序的性能不受輸入數(shù)據(jù)的影響，但表現(xiàn)比選擇排序好的多，因為始終都是O(n log n）的時間復雜度。代價是需要額外的內(nèi)存空間。

歸并排序是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法（Divide and Conquer）的一個非常典型的應用。歸并排序是一種穩(wěn)定的排序方法。將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合并成一個有序表，稱為2-路歸并。

1.把長度為n的輸入序列分成兩個長度為n/2的子序列；

2.對這兩個子序列分別采用歸并排序；

3.將兩個排序好的子序列合并成一個最終的排序序列。

該方法需要使用函數(shù)，所以這里暫且記一下，學完函數(shù)后回來補充。

5、快速排序（Quick Sort）

快速排序的基本思想：通過一趟排序?qū)⒋庞涗浄指舫瑟毩⒌膬刹糠郑渲幸徊糠钟涗浀年P鍵字均比另一部分的關鍵字小，則可分別對這兩部分記錄繼續(xù)進行排序，以達到整個序列有序。

1.從數(shù)列中挑出一個元素，稱為 “基準”（pivot）；

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

3.遞歸地（recursive）把小于基準值元素的子數(shù)列和大于基準值元素的子數(shù)列排序

6、計數(shù)排序（Counting Sort）

計數(shù)排序的核心在于將輸入的數(shù)據(jù)值轉(zhuǎn)化為鍵存儲在額外開辟的數(shù)組空間中。 作為一種線性時間復雜度的排序，計數(shù)排序要求輸入的數(shù)據(jù)必須是有確定范圍的整數(shù)。

計數(shù)排序(Counting sort)是一種穩(wěn)定的排序算法。計數(shù)排序使用一個額外的數(shù)組C，其中第i個元素是待排序數(shù)組A中值等于i的元素的個數(shù)。然后根據(jù)數(shù)組C來將A中的元素排到正確的位置。它只能對整數(shù)進行排序。

1.找出待排序的數(shù)組中最大和最小的元素；

2.統(tǒng)計數(shù)組中每個值為i的元素出現(xiàn)的次數(shù)，存入數(shù)組C的第i項；

3.對所有的計數(shù)累加（從C中的第一個元素開始，每一項和前一項相加）；

4.反向填充目標數(shù)組：將每個元素i放在新數(shù)組的第C(i)項，每放一個元素就將C(i)減去1。

? var bucket =new Array(maxValue+1),

? ? ? ? sortedIndex = 0;

? ? ? ? arrLen = arr.length,

? ? ? ? bucketLen = maxValue + 1;

? ? for (var i = 0; i < arrLen; i++) {

? ? ? ? if (!bucket[arr[i]]) {

? ? ? ? ? ? bucket[arr[i]] = 0;

? ? ? ? }

? ? ? ? bucket[arr[i]]++;

? ? }

? ? for (var j = 0; j < bucketLen; j++) {

? ? ? ? while(bucket[j] > 0) {

? ? ? ? ? ? arr[sortedIndex++] = j;

? ? ? ? ? ? bucket[j]--;

? ? ? ? }

? ? }

這里記錄一個大佬的帖子https://blog.csdn.net/lpfasd123/article/details/81199885?spm=1001.2101.3001.6650.2&utm_medium=distribute.pc_relevant.none-task-blog-2%7Edefault%7ECTRLIST%7ERate-2.pc_relevant_aa&depth_1-utm_source=distribute.pc_relevant.none-task-blog-2%7Edefault%7ECTRLIST%7ERate-2.pc_relevant_aa&utm_relevant_index=2

作者是CSDN博主「lpfasd123」

我基本上都是看他的才看懂，該文中多出也是摘他的

最后放一張我自己看著都想笑的圖，是我實在不理解算法時隨手畫的，這件事也證明了我實在不適合畫畫。。。