js中数组排序常用的几种方法

一、选择排序

所谓“选择”，就是每次遍历时，选择一个最小的交换到已排好序列的后面。

思路：

每次找到最小的数放在最开始的位置，

详细解释：

1、找到最小的数，放在第一个位置（和第一个位置上的数交换）
2、找到次小的数，放在第二个位置（和第二个位置上的数交换）（在剩下数中，找到最小的数，放在第一个位置）

以此类推

举例说明：

假如一组数：9 6 8 2 5 1 3

//第一轮 i=0 // 从第一个位置(下标为0)朝最后一个数，找最小数(的下标)，和第一个位置(下标为0)上的数交换 1 6 8 2 5 9 3

//第二轮 i=1 // 从第二个位置(下标为1)朝最后一个数，找最小数(的下标)，和第二个位置(下标为1)上的数交换 1 2 8 6 5 9 3

//第三轮 i=2 // 从第三个位置(下标为2)朝最后一个数，找最小数(的下标)，和第三个位置(下标为2)上的数交换 1 2 3 6 5 9 8

以此类推,一共做6轮

代码：

1、var arr1=[100,1,2,8,56,45,12];
2、function selectionSort(arr){//完成从小到大排序
3、    var len = arr.length;//数组长度
4、    var minIndex, templ//minIndex最小值对应的下标，临时变量
5、	for(var i=0; i<len-1; i++){
6、            minIndex = i;
7、            for(var j=i+1; j<len; j++){
8、		if(arr[j]<arr[minIndex]){//寻找最小的数
9、                    minIndex=j;//将最小数的索引保存
10、		}
11、            }
12、            temp=arr[i];
13、           arr[i]=arr[minIndex];
14、            arr[minIndex]=temp;
15、	}
16、	return arr;
17、}
18、selectionSort(arr1);
19、document.write(selectionSort(arr1));
复制代码
复制代码

二、冒泡排序

说明

对数组进行冒泡排序算是比较简单的，冒泡排序也是容易理解的一种排序算法了，在面试的时候，很可能就会问到。

实现原理

数组中有 n 个数，比较每相邻两个数，如果前者大于后者，就把两个数交换位置；这样一来，第一轮就可以选出一个最大的数放在最后面；那么经过 n-1（数组的 length – 1）轮，就完成了所有数的排序。

好的，我们先来实现找数组中的最大数，并把他放到数组最后。

1、var arr = [3,4,1,2];
2、// 遍历数组，次数就是arr.length - 1
3、for (var i = 0; i < arr.length - 1; i++) {
4、    // 如果前一个数 大于 后一个数 就交换两数位置
5、    if (arr[i] > arr[i + 1]) {
6、        var temp = arr[i];
7、       arr[i] = arr[i + 1];
8、        arr[i + 1] = temp;
9、    }
10、}
11、console.log(arr)  // [3, 1, 2, 4]
复制代码
复制代码

我们能找到数组中最大的数，放到最后，这样重复 arr.length – 1 次，便可以实现数组按从小到大的顺序排好了。

1、var arr = [3,4,1,2];
2、// 遍历数组，次数就是arr.length - 1
3、for (var j = 0; j < arr.length - 1; j++) {
4、    // 这里 i < arr.length - 1 ，要思考思考合适吗？我们下面继续说
5、    for (var i = 0; i < arr.length - 1; i++) {
6、        if (arr[i] > arr[i + 1]) {
7、            var temp = arr[i];
8、            arr[i] = arr[i + 1];
9、            arr[i + 1] = temp;
10、        }
11、    }
12、}
13、console.log(arr)  // [1,2,3,4]
复制代码
复制代码

虽然上面的代码已经实现冒泡排序了，但就像注释中提到的，内层 for 循环的次数写成，i < arr.length – 1 ，是不是合适呢？
我们想一下，当第一次，找到最大数，放到最后，那么下一次，遍历的时候，是不是就不能把最后一个数算上了呢？因为他就是最大的了，不会出现，前一个数比后一个数大，要交换位置的情况，所以内层 for 循环的次数，改成 **i < arr.length – 1 -j ** ，才合适，看下面的代码。

1、var arr = [3, 4, 1, 2];
2、function bubbleSort (arr) {
3、  for (var j = 0; j < arr.length - 1; j++) {
4、    // 这里要根据外层for循环的 j，逐渐减少内层 for循环的次数
5、    for (var i = 0; i < arr.length - 1 - j; i++) {
6、      if (arr[i] > arr[i + 1]) {
7、        var temp = arr[i];
8、        arr[i] = arr[i + 1];
9、        arr[i + 1] = temp;
10、      }
11、    }
12、  }
13、  return arr;
14、}
15、bubbleSort(arr);
复制代码
复制代码

我们想下这个情况，当原数组是，
arr = [1,2,4,3];
在经过第一轮冒泡排序之后，数组就变成了
arr = [1,2,3,4];
此时，数组已经排序完成了，但是按上面的代码来看，数组还会继续排序，所以我们加一个标志位，如果某次循环完后，没有任何两数进行交换，就将标志位设置为 true，表示排序完成，这样我们就可以减少不必要的排序，提高性能。

完整代码

1、var arr = [3, 4, 1, 2];
2、function bubbleSort (arr) {
3、  var max = arr.length - 1;
4、  for (var j = 0; j < max; j++) {
5、    // 声明一个变量，作为标志位
6、    var done = true;
7、    for (var i = 0; i < max - j; i++) {
8、      if (arr[i] > arr[i + 1]) {
9、        var temp = arr[i];
10、        arr[i] = arr[i + 1];
11、        arr[i + 1] = temp;
12、        done = false;
13、      }
14、    }
15、    if (done) {
16、      break;
17、    }
18、  }
19、  return arr;
20、}
21、bubbleSort(arr);
复制代码
复制代码

三。插入排序

插入排序（Insertion-Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

一般来说，插入排序都采用 in-place 在数组上实现：

1、从第一个元素开始，该元素可以认为已经被排序；
2、取出下一个元素，在已经排序的元素序列中从后向前扫描；
3、如果该元素（已排序）大于新元素，将该元素移到下一位置；
4、重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
5、将新元素插入到该位置后；
6、重复步骤2~5。
复制代码
复制代码

动图演示：

代码实现：

1、function Insertion(arr) {
2、  let len = arr.length;
3、  let preIndex, current;
4、  for (let i = 1; i < len; i++) {
5、    preIndex = i - 1;
6、    current = arr[i];
7、    while (preIndex >= 0 && current < arr[preIndex]) {
8、      arr[preIndex + 1] = arr[preIndex];
9、      preIndex--;
10、    }
11、    arr[preIndex + 1] = current;
12、  }
13、  return arr;
14、}
 
 
15、var arr = [3,5,7,1,4,56,12,78,25,0,9,8,42,37];
16、Insertion(arr);
复制代码
复制代码

思路：

1.默认从 i = 1 开始判断，这样 preIndex 自然是内部循环的游标；

2.current 保存 arr[i]，通过循环来确定 current 的最终位置；

3.每个内循环开始的时候，arr[i] === current === arr[preIndex + 1]，所以在内循环首次时 arr[preIndex + 1] = arr[preIndex] 的时候不必担心 arr[i] 的值丢失；

4.总体思路是，需要排位的元素先额外缓存起来，然后套用内循环，使得需要调整的元素赋值给它后面的一个位置上，形成依次挪位，最后因为内循环在判断条件不生效的时候停止意味着找到了需要排位的元素的正确位置，然后赋值上去，完成排序。

四、堆排序

算法描述

1、将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；
2、将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]；
3、由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。

动图演示

代码实现

1、var len;   // 因为声明的多个函数都需要数据长度，所以把len设置成为全局变量
2、function buildMaxHeap(arr) {  // 建立大顶堆
3、    len = arr.length;
4、    for (var i = Math.floor(len/2); i >= 0; i--) {
5、        heapify(arr, i);
6、    }
7、}
8、 function heapify(arr, i) {    // 堆调整
9、    var left = 2 * i + 1,
10、        right = 2 * i + 2,
11、        largest = i;
12、    if (left < len && arr[left] > arr[largest]) {
13、        largest = left;
14、    }
15、    if (right < len && arr[right] > arr[largest]) {
16、        largest = right;
17、    }
18、    if (largest != i) {
19、        swap(arr, i, largest);
20、        heapify(arr, largest);
21、    }
复制代码

文章版权归作者所有，未经允许请勿转载。

THE END

前端