常见的排序算法

发表于 | 更新于 | 分类于 | 评论数： | 阅读次数：

排序在面试中经常会遇到，但是不用就忘了，这里小记一番。

冒泡排序

思想：

依次比较相邻两项的大小，顺序有误则交换，每遍历一次，最大的数就会冒到最后，遍历n-1次可得到顺序的数组

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function bubbleSort(arr) {
  var temp;
  //比较n-1轮即可
  for (var i = 0; i < arr.length - 1; i++) {
    // 经过i轮，数组最后i个数是有序的
    for (var j = 1; j < arr.length - i; j++) {
      //相邻两个数乱序则交换
      if (arr[j] < arr[j-1]) {
        temp = arr[j];
        arr[j] = arr[j-1];
        arr[j-1] = temp;
      }
    };
  }
  return arr;
}

选择排序

思想：

选择待排序列中最小的一项，放在序列的起始位置，然后缩短序列的长度，直到序列的长度为1

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function selectSort(arr) {
  for (var i = 0; i < arr.length - 1; i++) {
    var temp = arr[i];
    // 最小数的下标
    var min_index = i;  
    // 找到待排序的序列中最小的数
    for (var j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[min_index]) {
        min_index = j;
      }
    }
    // 将最小数与队首的数交换
    if (min_index != i) {
      arr[i] = arr[min_index];
      arr[min_index] = temp;
    }
  };
  return arr;
}

插入排序

思想：

构建有序序列，对未排序的数，在已排序的序列中，从后向前扫描，找到相应位置并插入

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function insertSort(arr) {
  var item,index;
  for (var i = 1; i < arr.length; i++) {
    item = arr[i];   //待排序元素
    index = i - 1;   //扫描起始位置
    //向前扫描，序列从后到前向后移一位，直到找出合适位置
    while(item < arr[index] && index >= 0) {
      arr[index + 1] = arr[index];
      index--;
    }
    //在合适位置插入元素
    arr[index + 1] = item;
  };
  return arr;
}

希尔排序

思想：

把数组按下标进行一定的增量分组，对分组进行插入排序，减小增量，再次排序，直到增量为0
如增量为2，则arr[0]，arr[2]，arr[4]…为一组，arr[1]，arr[3]，arr[5]…为一组

代码：

以初始增量为n/2为例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function shellSort(arr) {
  // 初始增量
  var grep = Math.floor(arr.length/2);
  while(grep >= 1) {
    //插入排序
    for (var i = grep; i < arr.length; i++) {
      var temp = arr[i];
      var j = i - grep;
      while(arr[i] < arr[j] && j >= 0) {
        arr[j + grep] = arr[j];
        j = j - grep;
      }
      arr[j + grep] = temp;
    };
    // 缩小增量
    grep = Math.floor(grep/2);
  }
  return arr;
}

归并排序

思想：

分而治之，我们会把两个有序的数组合成一个有序数组，所以可以把一个乱序的数组，分解为若干有序数组，再依次合并成一个有序数组

代码：

1
2
3
4
5
6
7
8
9
10
11
12
function mergeSort(arr) {
  // 少于两个元素就不用分了
  if(arr.length < 2) {
    return arr;
  }
  var index = arr.length/2;
  // 分成左右两个有序数组
  var left = mergeSort(arr.slice(0,index));
  var right = mergeSort(arr.slice(index));
  // 合并两个有序数组
  return mergeArr(left,right);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 合并数组
function mergeArr(arr1,arr2) {
  var res = [];
  // index1,index2分别为两个数组的下标
  var index1 = 0;
  var index2 = 0;
  // 比较两个数组，将较小的数依次添加到res中
  while(index1 != arr1.length && index2 != arr2.length) {
    if (arr1[index1] <= arr2[index2]) {
      res.push(arr1[index1++]);
    } else {
      res.push(arr2[index2++]);
    }
  }
  // 处理数组剩余部分
  res = res.concat(arr2.slice(index2));
  res = res.concat(arr1.slice(index1));
  return res;
}

快速排序

思想：

以一个数为基准，把比之小的数放在左边，比之大的数放在右边，然后对左右区间进行递归操作，直到区间只有一个数。

代码：

1
2
3
4
5
6
function quickSort(arr) {
  return qSort(arr,0,arr.length-1);
}
function qsort(arr, start, end) {
  ...
}

方法一步骤

1.每次取第一个元素为基准为例，配合两个下标，左下标，右下标，记录初始值
2.先从后到前扫描，扫描到比基准小的数后，左下标对应的值替换为此数（最开始，左下标对应的数就是基准）
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
function qSort(arr,start,end) {
  if(start >= end) return arr;
  var key = arr[start];
  var st = start;
  var ed = end;
  while(st < ed) {
  	 // 这里注意扫描的顺序，得先从后扫描，再从前扫描，这样才能保证最后的相遇点的值比基准值小
    // 从后向前扫描，找到乱序元素
    while (arr[ed] >= key && ed > st) {
   		ed--;
    }
    // 拷贝为左下标的元素
    arr[st] = arr[ed];
    // 从前往后扫描，找到乱序元素
    while(arr[st] <= key && st < ed) {
      st++;
    }
    // 拷贝为右下标的元素
    arr[ed] = arr[st];
  }
  // 汇合处替换为基准
  arr[st] = key;
  // 左右区间递归操作
  arr = qSort(arr,start,st-1);
  arr = qSort(arr,st+1,end);
  return arr;
}

方法二步骤

1.每次取第一个元素为基准为例，配合两个下标，左下标，右下标，记录初始值
2.先从后到前扫描，扫描到比基准小
3.再向从前向后扫描，扫到比基准大
4.交换前后两个不符合顺序的元素
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
function qSort(arr,start,end) {
  if(start >= end) return arr;
  var key = arr[start];
  var st = start;
  var ed = end;
  while(st < ed) {
    // 从后向前扫描
    while (arr[ed] >= key && ed > st) {
      ed--;
    }
    // 从前向后扫描
    while(arr[st] <= key && ed > st) {
      st++;
    }
    // 交换两个乱序的元素
    var temp = arr[ed];
    arr[ed] = arr[st];
    arr[st] = temp;
  }
  // 汇合处替换为基准,st位置的元素一定比基准小
  arr[start] = arr[st]
  arr[st] = key;
  arr = qSort(arr,start,st-1);
  arr = qSort(arr,st+1,end);
  return arr;
}

堆排序

思想：

根据二叉堆的数据结构来实现，将数组构造成最大堆

二叉堆

  • 二叉堆近似为完全二叉树
  • 父节点的值总是大于等于子节点
  • 二叉堆的数组存储
    二叉堆的数组存储

步骤：

1.将数组映射成一棵树，调整数组使之对应一个二叉堆
2.把二叉堆的根元素放在数组最后，将剩余元素重新构造成一个二叉堆
3.重复步骤2，直到顺序都对了

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 调整二叉堆，调整前已保证，根节点的左右子树均为最大堆
function max_heapify(arr,start,end) {
  var parent = start;    		//父节点
  var son = 2 * start + 1;   	//左节点
  while(son < end) {
    // 找到孩子中较大的一个
    if (son + 1 < end && arr[son + 1] > arr[son]) {
      son++;
    }
    if (arr[parent] < arr[son]) {  
      // 父节点和较大子节点的互换
      var temp = arr[son];
      arr[son] = arr[parent];
      arr[parent] = temp;
      // 调整后可能会影响下面的堆，所以对下面的堆进行调整
      parent = son;
      son = 2 * parent + 1;
    } else {
      return arr;
    }
  }
  return arr;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 堆排序
function heapSort(arr) {
  // 从最小的最大堆开始构造，构造成最大堆
  for(var i = Math.floor(arr.length / 2 - 1); i >= 0; i--) {
    arr = max_heapify(arr,i,arr.length);
  }
  // 调整数组为有序数组
   for (var i = arr.length - 1;i > 0;i--) {
   	//堆对应的数组首项是的最大的,和原数组的最后一个元素交换
    var temp = arr[0];
    arr[0] = arr[i];
    arr[i] = temp;
    // 重新构造堆
    arr = max_heapify(arr,0,i);
  };
  return arr;
}

参考资料