88-排序

发表于 | 分类于 |

选择排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
var arr=[1,2,4,5,6,4,3,2]

function fn(arr){
  for(let i=0;i<arr.length;i++){
    var minIndex=i
    for(let j=i+1;j<arr.length;j++){
      if(arr[minIndex]>arr[j]){
        minIndex=j
      }
    }
    [arr[i],arr[minIndex]]=[arr[minIndex],arr[i]]
  }
  return arr
}
console.log(fn(arr));

插入排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function fn(arr){
  for (let i = 1; i < arr.length; i++) {
    for (let j = i; j > 0; j--) {
      if(arr[j]<arr[j-1]){
        [arr[j-1],arr[j]]=[arr[j],arr[j-1]]
      }else{
        break
      }
    }
  }
  return arr
}

console.log(fn([9,1,4,2,7,4]));

二分查找

// 非递归算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function binary_search(arr, key) {
    var low = 0,
        high = arr.length - 1;
    while(low <= high){
        var mid = parseInt((high + low) / 2);
        if(key == arr[mid]){
            return  mid;
        }else if(key > arr[mid]){
            low = mid + 1;
        }else if(key < arr[mid]){
            high = mid -1;
        }else{
            return -1;
        }
    }
};
var arr = [1,2,3,4,5,6,7,8,9,10,11,23,44,86];
var result = binary_search(arr,10);
alert(result); // 9 返回目标元素的索引值

希尔排序

希尔排序其实大体思路很简单,就是将数组(长度为len)分成间隔为t1的若干数组.进行插入排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
let arr = [2,5,10,7,10,32,90,9,11,1,0,10];

function fn(arr){
  for(let gap=Math.floor(arr.length/2);gap>0;gap=Math.floor(gap/2)){
    for (let i = gap; i < arr.length; i++) {
      for (let j = i; j >0; j-=gap) {
        if(arr[j]<arr[j-gap]){
          [arr[j-gap],arr[j]]=[arr[j],arr[j-gap]]
        }else{
          break;
        }
      }
    }
  }
  return arr
}

console.log(fn(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
function 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));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

堆排序

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
function heapSort(arr){
  var len=arr.length
  buildMaxHeap(arr,len)

  for(var i=arr.length-1;i>0;i--){
    [arr[0],arr[i]]=[arr[i],arr[0]]
    len--;
    heapify(arr,0,len)
  }
  
  return arr
}

// 建立大根堆
function buildMaxHeap(arr,len){
  for (var i = Math.floor(len/2); i >= 0; i--) {
    heapify(arr, i,len);
  }
}

// 堆调整
function heapify(arr,i,len){
  var left=2*i+1;
  var right=2*i+2;
  var largest=i;

  if(left<len && arr[left]>arr[largest]){
    largest=left
  }

  if(right<len && arr[right]>arr[largest]){
    largest=right
  }

  if(largest!=i){
    [arr[i],arr[largest]]=[arr[largest],arr[i]]
    heapify(arr,largest,len)
  }
}

var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(heapSort(arr));