算法-简单了解一下

算法

伪代码流程图

从正整数组 a 中找出最小的数字，打印出来

a <- {
    '0': 23
    '1': 43
    '2': 239
    '3': 1321
    '4': 90
    'length': 5
}
min <-  a['0']
index <- 1
while index < a['length']
    if a[index] < min
        min <- a[index]
    end
    index <- index + 1
end
print min

相关链接

1. 排序算法列表 https://zh.wikipedia.org/wiki/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95#排序算法列表
2. 冒泡排序 http://bubkoo.com/2014/01/12/sort-algorithm/bubble-sort/
3. 插入排序 http://bubkoo.com/2014/01/14/sort-algorithm/insertion-sort/
4. 桶排序 http://bubkoo.com/2014/01/15/sort-algorithm/bucket-sort/
5. 其他排序：http://bubkoo.com/tags/algorithm/

什么是算法

以下是高德纳在他的著作《计算机程序设计艺术》里对算法的特征归纳

1. 输入：一个算法必须有零个或以上输入量。
2. 输出：一个算法应有一个或以上输出量，输出量是算法计算的结果。
3. 明确性：算法的描述必须无歧义，以保证算法的实际执行结果是精确地匹配要求或期望，通常要求实际运行结果是确定的。
4. 有限性：依据图灵的定义，一个算法是能够被任何图灵完备系统模拟的一串运算，而图灵机只有有限个状态、有限个输入符号和有限个转移函数（指令）。而一些定义更规定算法必须在有限个步骤内完成任务。
5. 有效性：又称可行性。能够实现，算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现。

什么是数据结构

就是数据的结构。

一般来说是这样的：

1. 我们要解决一个跟数据相关的问题
2. 分析这个问题，想出对应的数据结构
3. 分析数据结构，想出算法

大分类

1. 分治法：把一个问题分区成互相独立的多个部分分别求解的思路。这种求解思路带来的好处之一是便于进行并行计算。
2. 动态规划法：当问题的整体最优解就是由局部最优解组成的时候，经常采用的一种方法。
3. 贪婪算法：常见的近似求解思路。当问题的整体最优解不是（或无法证明是）由局部最优解组成，且对解的最优性没有要求的时候，可以采用的一种方法。
4. 线性规划法：见词条。
5. 简并法：把一个问题通过逻辑或数学推理，简化成与之等价或者近似的、相对简单的模型，进而求解的方法。
6. 我们前端主要使用分治法——分而治之。

排序算法

中国学生学不好排序算法主要是因为这些算法的名字是外国人取的

1. 体育委员两两摸头法（冒泡排序）
2. 体育老师一指禅法（选择排序）
3. 起扑克牌法（插入排序）
4. 强迫症收扑克牌法（基数排序）
5. 快排
6. 归并排序
7. 堆排序

排序可视化：https://visualgo.net/bn/sorting

伪代码：

a <- {
    '0':4,
    '1':6,
    '2':3,
    '3':2,
    '4':1,
    'length': 5
}
轮数 = 1
左手指向的下标 

while(轮数 < a['length'])
    左手指向的下标 = 0
    while(左手指向的下标 <= a['length'] - 1 - 轮数)
        if a[左手指向的下标] < a[左手指向的下标+1]
            // 什么也不做
        else
            // 交换左右的位置
            t <- a[左手指向的下标]
            a[左手指向的下标] <- a[左手指向的下标+1]
            a[左手指向的下标+1] <- t
        end
        左手指向的下标 <- 左手指向的下标+1
    end
    轮数 <- 轮数 + 1
end
print a
/////////

轮数  左手指向的下标最大值（从0开始）
1        3
2       2
3       1
4       0

冒泡

function bubbleSort(array) {
   var length = array.length,
       i,
       j,
       temp;
   for (i = length - 1; 0 < i; i--) {
       for (j = 0; j < i; j++) {
           if (array[j] > array[j + 1]) {
               temp = array[j];
               array[j] = array[j + 1];
               array[j + 1] = temp;
           }
       }
   }
   return array;
}

插入排序

function insertionSort(array) {
  function swap(array, i, j) {
    var temp = array[i];
    array[i] = array[j];
    array[j] = temp;
  }
  var length = array.length,
      i,
      j;
  for (i = 1; i < length; i++) {
    for (j = i; j > 0; j--) {
      if (array[j - 1] > array[j]) {
        swap(array, j - 1, j);
      } else {
        break;
      }
    }
  }
  return array;
}

②减少次数

function insertionSort(array) {
  var length = array.length,
    i,
    j,
    temp;
  for (i = 1; i < length; i++) {
    temp = array[i];
    for (j = i; j >= 0; j--) {
      if (array[j - 1] > temp) {
        array[j] = array[j - 1];
      } else {
        array[j] = temp;
        break;
      }
    }
  }
  return array;
}

③利用二分查找法实现的插入排序，二分查找排序：

function insertionSort2(array) {
  function binarySearch(array, start, end, temp) {
    var middle;
    while (start <= end) {
      middle = Math.floor((start + end) / 2);
      if (array[middle] < temp) {
        if (temp <= array[middle + 1]) {
          return middle + 1;
        } else {
          start = middle + 1;
        }
      } else {
        if (end === 0) {
          return 0;
        } else {
          end = middle;
        }
      }
    }
  }
  function binarySort(array) {
    var length = array.length,
        i,
        j,
        k,
        temp;
    for (i = 1; i < length; i++) {
      temp = array[i];
      if (array[i - 1] <= temp) {
        k = i;
      } else {
        k = binarySearch(array, 0, i - 1, temp);
        for (j = i; j > k; j--) {
          array[j] = array[j - 1];
        }
      }
      array[k] = temp;
    }
    return array;
  }
  return binarySort(array);
}

桶排序

桶排序 (Bucket sort)或所谓的箱排序的原理是将数组分到有限数量的桶子里，然后对每个桶子再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序），最后将各个桶中的数据有序的合并起来。

排序过程：

1. 假设待排序的一组数统一的分布在一个范围中，并将这一范围划分成几个子范围，也就是桶
2. 将待排序的一组数，分档规入这些子桶，并将桶中的数据进行排序
3. 将各个桶中的数据有序的合并起来

实现：
首先用最笨的方法，每一个桶只能放相同的数字，最大桶的数量为数组中的正数最大值加上负数最小值的绝对值。

function bucketSort(array) {
    var bucket = [], // 正数桶
        negativeBucket = [], // 负数桶
        result = [],
        l = array.length,
        i,
        j,
        k,
        abs;
    // 入桶
    for (i = 0; i < l; i++) {
        if (array[i] < 0) {
            abs = Math.abs(array[i]);
            if (!negativeBucket[abs]) {
                negativeBucket[abs] = [];
            }
            negativeBucket[abs].push(array[i]);
        } else {
            if (!bucket[array[i]]) {
                bucket[array[i]] = [];
            }
            bucket[array[i]].push(array[i]);
        }
    }
    // 出桶
    l = negativeBucket.length;
    for (i = l - 1; i >= 0; i--) {
        if (negativeBucket[i]) {
            k = negativeBucket[i].length;
            for (j = 0; j < k; j++) {
                result.push(negativeBucket[i][j]);
            }
        }
    }
    l = bucket.length;
    for (i = 0; i < l; i++) {
        if (bucket[i]) {
            k = bucket[i].length;
            for (j = 0; j < k; j++) {
                result.push(bucket[i][j]);
            }
        }
    }
    return result;
}
下面这种方式就是文中举例分析的那样，每个桶存放一定范围的数字，用 step 参数来设置该范围，取 step 为 1 就退化成前一种实现方式。关键部位代码有注释，慢慢看，逻辑稍微有点复杂。

/*
* @array 将要排序的数组
*
* @step 划分桶的步长，比如 step = 5，表示每个桶存放的数字的范围是 5，像 -4<sub>1、0</sub>5、6~11
*/
function bucketSort(array, step) {
    var result = [],
        bucket = [],
        bucketCount,
        l = array.length,
        i,
        j,
        k,
        s,
        max = array[0],
        min = array[0],
        temp;
    for (i = 1; i < l; i++) {
        if (array[i] > max) {
            max = array[i]
        }
        if (array[i] < min) {
            min = array[i];
        }
    }
    min = min - 1;
    bucketCount = Math.ceil((max - min) / step); // 需要桶的数量
    for (i = 0; i < l; i++) {
        temp = array[i];
        for (j = 0; j < bucketCount; j++) {
            if (temp > (min + step * j) && temp <= (min + step * (j + 1))) { // 判断放入哪个桶
                if (!bucket[j]) {
                    bucket[j] = [];
                }
                // 通过插入排序将数字插入到桶中的合适位置
                s = bucket[j].length;
                if (s > 0) {
                    for (k = s - 1; k >= 0; k--) {
                        if (bucket[j][k] > temp) {
                            bucket[j][k + 1] = bucket[j][k];
                        } else {
                            break;
                        }
                    }
                    bucket[j][k + 1] = temp;
                } else {
                    bucket[j].push(temp);
                }
            }
        }
    }
    for (i = 0; i < bucketCount; i++) { // 循环取出桶中数据
        if (bucket[i]) {
            k = bucket[i].length;
            for (j = 0; j < k; j++) {
                result.push(bucket[i][j]);
            }
        }
    }
    return result;
}