1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function sort(arr) {
  var temp; //存放临时变量
  for(var i = 1; i < arr.length; i ++ ) {
    // 要插入的元素小于之前排序好的最后一个值
    if(arr[i] < arr[i-1]) {
      temp = arr[i];
      arr[i] = arr[i-1];// 先移动最后一个
      // 倒序处理，将temp放置入合适的位置
      for(var j = i-2; j >= 0 && arr[j] > temp; j-- ) {
        arr[j+1] = arr[j];
      }
      arr[j+1] = temp; 
    }
  }
}
复制代码

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
// dis为距离增量 
function sort(arr, dis) {
  var temp; //存放临时变量
  for(var i = dis; i < arr.length; i += dis ) {
    // 要插入的元素小于之前排序好的最后一个值
    if(arr[i] < arr[i-dis]) {
      temp = arr[i];
      arr[i] = arr[i-dis];// 先移动最后一个
      // 倒序处理，将temp放置入合适的位置
      for(var j = i-dis; j >= 0 && arr[j] > temp; j-=dis ) {
        arr[j+dis] = arr[j];
      }
      arr[j+dis] = temp; 
    }
  }
}
// [5, 4, 2, 1, 3, 6, 7, 9, 2, 0];
// dis取3，第一轮排序后
// [0, 4, 2, 1, 3, 6, 5, 9, 2, 7]

// t为要进行多少次子排序
function sheelSort(arr, t) {
  var dis;
  var len = arr.length; // 间隔默认数组长度
  for(var i = 0; i < t; i++) {
    //  每次取得不同的间隔
    len = Math.floor(len / 3) + 1;
    sort(arr, len);// 对不同的子序列进行直接插入排序，最后一次len为1，做最后的整理
  }
}
复制代码

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
40
41
42
43
44
function partion(arr, left, right) {
  let base = arr[left]; //基准值，默认取数组第一个元素
  while (left < right) {
    while(left < right && arr[right] >= base) {
      right --;
    }
    if(left < right) {
      swap(arr, left, right);
    }
    while(left<right && arr[left] <= base) {
      left ++;
    }
    if(left < right) {
      swap(arr, left, right);
    }
  }
  arr[left] = base;
  return left;
}

// 快速排序
function quickSort(arr, left, right) {
  let dp;
  if(left < right) {
    dp = partion(arr, left, right); // 第一步： 定位第一个基值，左侧的小，右侧的大
    quickSort(arr, left, dp-1); // 第二步： 排序左侧的
    quickSort(arr, dp+1, right); // 第三步： 排序右侧的
  }
}
// 交换数组中的两个值
function swap(array, left, right) {
  let rightValue = array[right]
  array[right] = array[left]
  array[left] = rightValue
}


var arr = [5, 4, 2, 1, 3, 6, 7, 9, 2, 0];

quickSort(arr, 0, arr.length-1);

console.log(arr);

复制代码

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
function sort(arr) {
  for(var i = 0 ; i < arr.length; i++) {
    var min = i;
    // 从往后部分找出最小
    for(var j = i+1 ; j< arr.length; j ++) {
      if(arr[j] < arr[min]) {
        min = j;
      }
    }
    if(i != min) {
      swap(arr, i, min);
    }
  }
}
// 交换数组中的两个值
function swap(array, left, right) {
  let rightValue = array[right]
  array[right] = array[left]
  array[left] = rightValue
}

var arr = [5, 4, 2, 1, 3, 6, 7, 9, 2, 0];

sort(arr);

console.log(arr);
复制代码

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
function merge(arr,  L, mid, R) {
  var temp = new Array(R - L + 1);
  var i = 0;
  var p1 = L;
  var p2 = mid + 1;
  // 比较左右两部分的元素，哪个小，把那个元素填入temp中
  while(p1 <= mid && p2 <= R) {
      temp[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
  }
  // 上面的循环退出后，把剩余的元素依次填入到temp中
  // 以下两个while只有一个会执行
  while(p1 <= mid) {
      temp[i++] = arr[p1++];
  }
  while(p2 <= R) {
      temp[i++] = arr[p2++];
  }
  // 把最终的排序的结果复制给原数组
  for(i = 0; i < temp.length; i++) {
      arr[L + i] = temp[i];
  }
}
function sort(arr, L, R) {
    if(L == R) {
        return;
    }
    var mid = parseInt(( R + L)/2);
    sort(arr, L, mid);
    sort(arr, mid + 1, R);
    merge(arr, L, mid, R);
}
var arr = [5, 4, 2, 1, 3, 6, 7, 9, 2, 0];

sort(arr, 0, arr.length-1);

console.log(arr);
复制代码

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
// v为待查找值
function find(arr, v) {
    var low = 0;
    var high = arr.length - 1;
    var mid;
    // 循环条件必须为low <= high
    while(low <= high) {
        mid = low + parseInt((high - low) / 2); // js除法后不是整数，所以需要转为整数
        if(arr[mid] == v) {
            return arr[mid]; // 函数结束条件
        } else {
            // 到左侧查找
            if(arr[mid] > v) {
                high = mid-1;
            }
            // 右侧查找
            if(arr[mid] < v) {
                low = mid + 1;
            }
        }
    }
    // 没找到返回-1
    return -1;
}

var arr = [];

for(var i = 0; i < 1000; i ++) {
   arr[i] = i;
}



console.log(find(arr, 25));
console.log(find(arr, 500));
console.log(find(arr, 28));
复制代码

1
2
3
4
5
1、首先，遍历数组肯定就能知道某个数字的个数，此时的时间复杂度O(n)。
2、首先这里是排好序的数组，而且是查找问题，那么我们是不是可以使用二分查找呢，通过二分查找到一个目标，然后向两侧查找，然后就能找到所有的目标数，但是这样复杂度其实还是O(n)。
3、如果我们知道了第一个3和最后一个3出现的位置，那么其实也就知道了个数，那么我们能否在第一次使用二分查找之后，继续使用二分法，找到两端的3？当然可以，只是这样的二分查找就要跟上面的有点不一样了
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
function getFirst(arr, length, k, start, end) {
  if(start > end) {
    return -1;
  }
  var mid = start + parseInt((end - start) / 2);
  var midData = arr[mid];

  if(midData == k ) {
    if((mid > 0 && arr[mid - 1] != k) || midData == 0) {
      return mid;
    } else {
      end = mid - 1;
    }
  } else {
    if(midData > k) {
      end = mid - 1;
    }
    if(midData < k ) {
      start = mid + 1;
    }
  }
  return getFirst(arr, length, k, start, end);
}

function getLast(arr, length, k, start, end) {
  if(start > end)
    return -1;

  var mid = start + parseInt((end - start) / 2);
  var midData = arr[mid];

  if(midData == k) {
    if((mid < length-1 && arr[mid + 1] != k) || midData == length-1) {
      return mid;
    } else {
      start = mid + 1;
    }
  } else {
    if(midData > k) {
      end = mid - 1;
    }
    if(midData < k ) {
      start = mid + 1;
    }
  }
  return getLast(arr, length, k, start, end);
}

function getNumber(data, k) {
  var num = 0;
  var length = data.length;
  var first = getFirst(data, length, k, 0, length - 1); // 获取第一次出现的位置
  var last = getLast(data, length, k, 0, length - 1); // 获取最后一次出现的位置
  if(first > -1 && last > -1)
    num = last - first + 1;
  console.log(num, first, last);
}

var arr = [1,2,2,3,4,4,4,4,5,6,8,9];

getNumber(arr, 4);
复制代码