跟随Google大佬的脚步。。。(一如既往的跟不上)
突然看到《数据结构与算法之美》,突然买,突然看,突然继续看,突然反复看。。。
什么是数据结构?什么是算法?
1、从广义上讲,数据结构就是指一组数据的存储结构。算法就是操作数据的一组方法。
举例:
图书馆储藏书籍你肯定见过吧?为了方便查找,图书管理员一般会将书籍分门别类进行“存储”。按照一定规律编号,就是书籍这种“数据”的存储结构。
那我们如何来查找一本书呢?有很多种办法,你当然可以一本一本地找,也可以先根据书籍类别的编号,是人文,还是科学、计算机,来定位书架,然后再依次查找。笼统地说,这些查找方法都
是算法。
2、从狭义上讲,是指某些著名的数据结构和算法,比如队列、栈、堆、二分查找、动态规划等。这些都是前人智慧的结晶,都是前人从很多实际操作场景中抽象出来的,经过非常多的求证和检验,
可以高效地帮助我们解决很多实际的开发问题。
数据结构和算法有什么关系?
数据结构是为算法服务的,算法要作用在特定的数据结构之上。
举例:
数组具有随机访问的特点,常用的二分查找算法需要用数组来存储数据。但如果我们选择链表这种数据结构,二分查找算法就无法工作了,因为链表并不支持随机访问。
数据结构是静态的,它只是组织数据的一种方式。如果不在它的基础上操作、构建算法,孤立存在的数据结构就是没用的。
我们怎么选用合适的数据结构和算法?有什么衡量标准吗?
衡量的标准(metric)—时间复杂度和空间复杂度,也就是数据结构与算法中最重要的概念——复杂度分析。数据结构和算法解决的是如何更省、更快地存储和处理数据的问题,因此,我们就需要
一个考量效率和资源消耗的方法,这就是复杂度分析方法,知道怎么去分析复杂度,才能得出正确的判断。
几种常见时间复杂度实例分析
虽然代码千差万别,但是常见的复杂度量级并不多。我稍微总结了一下,这些复杂度量级几乎涵盖了了你今后可以接触的所有代码的复杂度量级。
可以粗略地分为两类,多项式量级和非多项式量级,其中,非多项式量级只有两个:O(2n) 和 O(n!)。
当数据规模n越来越大时,非多项式量级的算法的执行时间会急剧增加,求解决问题的执行时间会无限增长,所以非多项式时间复杂度的算法其实是非常低效的算法。
多项式时间复杂度
1、O(1)
O(1)只是常量级时间复杂度的一种表示方法,并不是指只执行了一行代码,比如这段代码,即便有三行,它的时间复杂度也是O(1),而不是O(3)。1
2
3int i = 8;
int j = 6;
int sum = i + j;
总结:只要代码的执行时间不随着n的增大而增大,这样代码的时间复杂度我们都记作O(1)。或者说,一般情况下,只要算法中不存在循环语句,递归语句,即使有成千上万行的代码,其时间复杂度也是O(1)。
2、O(logn)、O(nlogn)
对数阶时间复杂度非常常见,同时也是最难分析的一种时间复杂度1
2
3
4i=1;
while (i <= n) {
i = i * 2;
}
根据复杂度分析方法,第三行代码是循环执行次数最多的,所以,只要能计算出这行代码被执行了多少次,就能知道整段代码的时间复杂度。
从代码中可以看出,变量 i 的值从 1 开始取,每循环一次就乘以 2。当大于 n 时,循环结束。还记得我们高中学过的等比数列吗?实际上,变量 i 的取值就是一个等比数列。
如果把它一个一个列出来,就应该是这个样子的:
所以,只要知道 x 值是多少,就知道这行代码执行的次数了。通过 2x=n 求解 x。所以,这段代码的时间复杂度就是 O(log2n)。
现在,把代码稍微改下,再看看,这段代码的时间复杂度是多少?1
2
3
4i=1;
while (i <= n) {
i = i * 3;
}
根据刚刚的思路,很简单就能看出来,这段代码的时间复杂度为 O(log3n)。实际上,不管是以 2 为底、以 3 为底,还是以 10 为底。我们可以把所有对数阶的时间复杂度都记
为 O(logn)。为什么呢?
我们知道,对数之间是可以互相转换的,log3n 就等于 log32 log2n,所以 O(log3n) = O(C log2n),其中 C=log32 是一个常量。基于我们前面的一个理论:在采用大
O标记复杂度的时候,可以忽略系数,即 O(Cf(n)) = O(f(n))。所以,O(log2n) 就等于 O(log3n)。因此,在对数阶时间复杂度的表示方法里,我们忽略对数的“底”,统一表示为 O(logn)。
十个经典的排序算法
看java算法教程时候的截图笔记~~~~
1、冒泡排序
两两比较相邻的数字,左边比右边大就做交换1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18function bubble(arr,n){
let temp=null;
for(let i=0;i<n-1;i++){
if(arr[i]>arr[i+1]){
temp=arr[i];
arr[i]=arr[i+1];
arr[i+1]=temp;
}
}
}//走一遍冒泡
function sortBble(arr,n){
for(let i = n;i>=1;i--){
bubble(arr,i)
}
}//走一组冒泡
let arr=[1,3,2,7,5,6,4,9,8,0]
sortBble(arr,arr.length)
console.log(arr)
有一个骚操作是可以提高冒泡排序的性能,降低时间复杂度的,也是刚get的新技能,那就是亦或,也就是这个东西^,举个栗子,封装一个冒泡排序,普通操作1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17function sortFunc(arr){
for(let i = 0; i < arr.length; i++){
for(let j = 0; j <= arr.length - i - 1; j++){
if(arr[j]>arr[j+1]){
//普通操作
//let wap = arr[j];
//arr[j] = arr[j+1];
//arr[j+1] = wap;
//亦或操作
arr[j] = arr[j]^arr[j+1];
arr[j+1] = arr[j]^arr[j+1];
arr[j] = arr[j]^arr[j+1];
}
}
}
}
2、 选择排序
每次走一遍数组,找到最大的数字,然后和最后一个做交换1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21function getMaxIndex(arr,n){
let max=arr[0];
for(let i=0;i<n;i++){
if (arr[i]>max) {
max=arr[i]
}
}
return arr.indexOf(max)
}
function selectionSort(arr,n){
let maxIndex,temp;
for(let j=n;j>0;j--){
maxIndex=getMaxIndex(arr,j)
temp=arr[maxIndex];
arr[maxIndex]=arr[j-1];
arr[j-1]=temp;
}
return arr
}
let arr=[1,3,2,7,5,6,4,9,8,0]
console.log(selectionSort(arr,arr.length))
3、插入排序
将一条记录插入到已排好的有序表中,从而得到一个新的、记录数量增1的有序表。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19function insert(arr,n){
let key=arr[n]
let i=n
for(i;arr[i-1]>key;i--){
if(i<=0){
return
}
arr[i]=arr[i-1];
}
return arr[i]=key;
}
function insertSort(arr,n){
for(let i=0;i<n;i++){
insert(arr,i)
}
return arr
}
let arr=[1,3,2,7,5,6,4,9,8,0]
console.log(insertSort(arr,arr.length))
4、希尔排序
插入排序的一种又称“缩小增量排序”(Diminishing Increment Sort),是直接插入排序算法的一种更高效的改进版本。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20function shellSort(arr) {
var len = arr.length,
temp,
gap = 1;
while(gap < len/5) {
gap =gap*5+1;
}
for (gap; gap > 0; gap = Math.floor(gap/5)) {
for (var i = gap; i < len; i++) {
temp = arr[i];
for (var j = i-gap; j >= 0 && arr[j] > temp; j-=gap) {
arr[j+gap] = arr[j];
}
arr[j+gap] = temp;
}
}
return arr;
}
var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(shellSort(arr));
5、归并排序
将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31function mergeSort(arr) { //采用自上而下的递归方法
var len = arr.length;
if(len < 2) {
return arr;
}
var middle = Math.floor(len / 2),
left = arr.slice(0, middle),
right = arr.slice(middle);
return merge(mergeSort(left), mergeSort(right));
}
function merge(left, right){
var result = [];
while (left.length && right.length) {
if (left[0] <= right[0]) {
result.push(left.shift());
} else {
result.push(right.shift());
}
}
while (left.length){
result.push(left.shift());
}
while (right.length){
result.push(right.shift());
}
return result;
}
var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(mergeSort(arr));
6、快速排序
通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,
以此达到整个数据变成有序序列1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23function quickSort(array, left, right) {
if (left < right) {
var x = array[right], i = left - 1, temp;
for (var j = left; j <= right; j++) {
if (array[j] <= x) {
i++;
temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
console.log(array) ;
console.log(left,i) ;
quickSort(array, left, i - 1);
console.log(array)
console.log(i,right)
quickSort(array, i + 1, right);
}
console.log(array)
return array;
}
var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(quickSort(arr,0,arr.length-1));
7、堆排序
Heapsort是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33function heapSort(array) {
var heapSize = array.length, temp;
for (var i = Math.floor(heapSize / 2) - 1; i >= 0; i--) {
heapify(array, i, heapSize);
}
//堆排序
for (var j = heapSize - 1; j >= 1; j--) {
temp = array[0];
array[0] = array[j];
array[j] = temp;
console.log(array)
heapify(array, 0, --heapSize);
}
return array;
}
function heapify(arr, x, len) {
var l = 2 * x + 1, r = 2 * x + 2, largest = x, temp;
if (l < len && arr[l] > arr[largest]) {
largest = l;
}
if (r < len && arr[r] > arr[largest]) {
largest = r;
}
if (largest != x) {
temp = arr[x];
arr[x] = arr[largest];
arr[largest] = temp;
console.log(arr)
heapify(arr, largest, len);
}
}
var arr=[91,60,96,13,35,65,46,65,10,30,20,31,77,81,22];
console.log(heapSort(arr));
8、计数排序
对于给定的输入序列中的每一个元素x,确定该序列中值小于x的元素的个数(此处并非比较各元素的大小,而是通过对元素值的计数和计数值的累加来确定)。一旦有了这个信息,就可以将x直
接存放到最终的输出序列的正确位置上。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24function countingSort(array) {
var len = array.length,
B = [],
C = [],
min = max = array[0];
for (var i = 0; i < len; i++) {
min = min <= array[i] ? min : array[i];
max = max >= array[i] ? max : array[i];
C[array[i]] = C[array[i]] ? C[array[i]] + 1 : 1;
console.log(C)
}
for (var j = min; j < max; j++) {
C[j + 1] = (C[j + 1] || 0) + (C[j] || 0);
console.log(C)
}
for (var k = len - 1; k >= 0; k--) {
B[C[array[k]] - 1] = array[k];
C[array[k]]--;
console.log(B)
}
return B;
}
var arr = [2, 2, 3, 8, 7, 1, 2, 2, 2, 7, 3, 9, 8, 2, 1, 4, 2, 4, 6, 9, 2];
console.log(countingSort(arr));
9、桶排序
将数组分到有限数量的桶子里。每个桶子再个别排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序)。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40function bucketSort(array, num) {
if (array.length <= 1) {
return array;
}
var len = array.length, buckets = [], result = [], min = max = array[0], space, n = 0;
var index = Math.floor(len / num) ;
while(index<2){
num--;
index = Math.floor(len / num) ;
}
for (var i = 1; i < len; i++) {
min = min <= array[i] ? min : array[i];
max = max >= array[i] ? max : array[i];
}
space = (max - min + 1) / num; //步长
for (var j = 0; j < len; j++) {
var index = Math.floor((array[j] - min) / space);
if (buckets[index]) { // 非空桶,插入排序
var k = buckets[index].length - 1;
while (k >= 0 && buckets[index][k] > array[j]) {
buckets[index][k + 1] = buckets[index][k];
k--;
}
buckets[index][k + 1] = array[j];
} else { //空桶,初始化
buckets[index] = [];
buckets[index].push(array[j]);
}
}
while (n < num) {
result = result.concat(buckets[n]);
n++;
}
return result;
}
var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(bucketSort(arr,4));
10、基数排序
透过键值的部份资讯,将要排序的元素分配至某些“桶”中,藉以达到排序的作用,基数排序法是属于稳定性的排序,其时间复杂度为O (nlog(r)m)
,其中r为所采取的基数,而m为堆数,在某些时候,基数排序法的效率高于其它的稳定性排序法。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26function radixSort(arr, maxDigit) {
var mod = 10;
var dev = 1;
var counter = [];
for (var i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
for(var j = 0; j < arr.length; j++) {
var bucket = parseInt((arr[j] % mod) / dev);
if(counter[bucket]== null) {
counter[bucket] = [];
}
counter[bucket].push(arr[j]);
}
var pos = 0;
for(var j = 0; j < counter.length; j++) {
var value = null;
if(counter[j]!=null) {
while ((value = counter[j].shift()) != null) {
arr[pos++] = value;
}
}
}
}
return arr;
}
var arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
console.log(radixSort(arr,2));