Articles
13
Tags
8
Categories
1
Home
Archives
Tags
Categories
Catalog
  1. 1. 排序算法
    1. 1.1. 选择排序 Selection Sort
    2. 1.2. 冒泡排序 Bubble Sort
    3. 1.3. 插入排序 Insertion Sort
    4. 1.4. 快速排序 Quick Sort
  2. 2. 查询算法
    1. 2.1. 顺序查找 Inorder Search
    2. 2.2. 二分查找 Binary Search）
    3. 2.3. 插值查找 Interpolation Search
算法之排序和查找
|前端
Post View:

排序算法

排序算法没有优劣之分，在不同的场景中，不同的排序算法执行效率不同。

选择排序 Selection Sort

一次选择排序，可以将某个区间的最小值排列到该区域的第一位，具体的方式是：

1) 找出该区域的最小值
2) 将该值与该区域第一个值交换
3) 对下一个区域重复上述过程，直到排序完成

1
2
3
4
5
6
7
8
/**
 * 辅助函数  用于交换位置
 */
function swap(arr, i1, i2) {
  let temp = arr[i1]
  arr[i1] = arr[i2]
  arr[i2] = temp
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * 选择排序
 */
function SelectionSort(arr) {
  //第一次循环，找出第一圈最小的放在第一位。第二次，放在第二位。以此类推。。
  for (let i = 0; i < arr.length - 1; i++) {
    let min = arr[i],  //假设第一位最小
        index = i      //记录最小的下标
    for (let j = i + 1; j < arr.length ; j++) {
      if (arr[j] < min) {
        min = arr[j]
        index = j
      }
      swap(arr,i, index)
    }
  }
}
var a = [4, 2, 3, 1, 8, 5]
SelectionSort(a)
console.log(a)

冒泡排序 Bubble Sort

一次冒泡排序，可以将某个区域序列的最大值排序到该区域的最后一位，具体的方式是：

1) 将第1位和第2位比较，如果前者比后者大则交换
2) 将第2位和第3位比较，如果前者比后者大则交换
3) 依次类推，直到比较到该区域的最后两位
4) 重复上述过程，直到序列排序完成

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 * 冒泡排序
 */
function BubbleSort(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    //每次循环确定最大的一位放在末尾。下一次循环只循环到length - 1 - i位。
    for (let j = 0; j < arr.length - 1 - i; j++) {
      if(arr[j] > arr[j + 1]) {
        swap(arr, j, j + 1)
      }
    }
  }
}

var a = [4, 2, 3, 1, 8, 5]
BubbleSort(a)
console.log(a)

插入排序 Insertion Sort

将序列分为两个部分，一部分是有序的，一部分是无序的，现在要做的是，就是不断的从无序的部分取出数据，加入到有序的部分，直到整个排序完成

例如：序列[5, 7, 2, 3, 6]

1) 分为有序的序列和无序的序列 (5) (7 2 3 6)
2) 不断的扩充有序序列 (5 7) (2 3 6)
3) 不断的扩充有序序列 (2 5 7) (3 6)
4) 不断的扩充有序序列 (2 3 5 7) (6)
5) 不断的扩充有序序列 (2 3 5 6 7)
6) 排序完成

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * 插入排序
 */
function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    //如果i项小于i - 1项，循环i项之前的数组，找到比i项小的值。放入i项
    if (arr[i] < arr[i - 1]) {
      let temp = arr[i]
      for (let j = i; j >= 0; j--) {
        //j-1比i大，每一项往后移
        if (j > 0 && arr[j - 1] > temp) {
          arr[j] = arr[j - 1]
        }
        else {
          arr[j] = temp
          break
        }
      }
    }
  }
}
var a = [4, 2, 3, 1, 8, 5]
insertionSort(a)
console.log(a)

快速排序 Quick Sort

选择一个数（比如序列的最后一位）作为基准数，将整个序列排序成两部分，一部分比该数小，另一部分比该数大，基准数在中间，然后对剩余的序列做同样的事情，直到排序完成

例如：序列[5, 7, 2, 3, 6, 4]

1) 选择4作为基准数，排序成为：(3, 2) 4 (7, 6, 5)
2) 对于3,2， 继续使用该方式排序，得到： (2, 3) 4 (7,6,5)
3) 对于7,6,5，继续使用该方式排序，得到： (2, 3) 4 (5,6,7)
4) 排序完成

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
/**
 * 快排
 */
function quickSort(arr) {
  function _quickSort(arr, start, end) {
    if (start >= end || start > arr.length - 1) return
    let low = start,//定一个最初的指针
        height = end,//定一个末尾的指针
        key = arr[end]; //选择最后一个值作为基准值
    //把小于基准值的数放左边，大的放右边
    while (low < height) {
      while (low < height && arr[low] <= key) low++
      arr[height] = arr[low]
      while (low < height && arr[height] >= key) height--
      arr[low] = arr[height]
    }
    arr[low] = key //把基准值放中间
    //对左边继续做快排
    _quickSort(arr, start, low - 1)
     //对右边继续做快排
    _quickSort(arr, low + 1, end)
  }
  _quickSort(arr, 0, arr.length - 1)
}

var a = [4, 2, 3, 1, 8, 5]
quickSort(a)
console.log(a)

查询算法

即普通的遍历，属于算法的穷举法。

1
2
3
4
5
6
7
8
9
10
11
12
function inOrderSearch(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) {
      return true
    }
  }
  return false
}

var a = [4, 2, 3, 1, 8, 5]
const result = search(a, 5)
console.log(result)

二分查找 Binary Search）

如果一个序列是一个排序好的序列，则使用二分查找可以极大的缩短查找时间

具体的做法是：

查找该序列中间未知的数据

1) 相等，找到
2) 要找的数据较大，则对后续部分的数据做同样的步骤
3) 要找的数据较小，则对前面部分的数据做同样的步骤

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
function binarySearch(arr, target) {
  if(arr.length === 0 || arr[0] > target || arr[arr.length - 1] < target) return false
  let minIndex = 0, //最小下标
      maxIndex = arr.length - 1//最大下标
  while(minIndex <= maxIndex) {
    let mid = Math.floor((maxIndex + minIndex)/2)//中间下标
    if(arr[mid] === target) {
      return true
    }
    else if(arr[mid] > target) {
      maxIndex = mid - 1
    }
    else {
      minIndex = mid + 1
    }
  }
  return false
}

var a = [1,2,3,4,5,6,7]
const result = binarySearch(a, 7)
console.log(result)

插值查找是对二分查找的进一步改进

如果序列不仅是一个排序好的序列，而且序列的步长大致相同，使用插值查找会更快的找到目标。

插值查找基于如下假设：下标之间的距离比和数据之间的距离比大致相同，即：

(目标下标-最小下标) / (最大下标 - 最小下标) ≈ (目标值 - 最小值) / (最大值 - 最小值)

因此可以算出大致的下标落点：

目标下标 ≈ (目标值 - 最小值) / (最大值 - 最小值) * (最大下标 - 最小下标) + 最小下标

这样就可以计算出大致的下标落点，后续的比较和二分查找一样。

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
function interpolationSearch(arr, target) {
    if (arr.length === 0 || target < arr[0] || target > arr[arr.length - 1]) return false;
    var minIndex = 0; //最小下标
    var maxIndex = arr.length - 1; //最大下标
    while (minIndex <= maxIndex) {
        var mid = (target - arr[minIndex]) / (arr[maxIndex] - arr[minIndex]) * (maxIndex - minIndex) + minIndex;
        if (arr[mid] === target) {
            return true;
        }
        else if (arr[mid] > target) {
            maxIndex = mid - 1;
        }
        else {
            minIndex = mid + 1;
        }
    }
    return false;
}

var arr = new Array(100000);
for (var i = 0; i < arr.length; i++) {
    arr[i] = i + 1;
}

var result = interpolationSearch(arr, 100000)
console.log(result)
算法 排序
Recommend
数据结构和算法概述
算法之线性结构(数组和链表)
繁