黑马程序员技术交流社区

标题: 【广州前端】JavaScript实现十种经典排序算法（1） [打印本页]

作者: 老哥哥 时间: 2018-2-1 14:42
标题: 【广州前端】JavaScript实现十种经典排序算法（1）
本帖最后由老哥哥于 2018-2-1 14:47 编辑

一。冒泡排序算法

冒泡排序（Bubble Sort）是一种简单直观的排序算法。冒泡排序算法的步骤描述如下：

比较相邻的元素。如果第一个比第二个大，就交换他们两个。
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

JavaScript实现冒泡排序算法的代码如下：

[JavaScript] 纯文本查看 复制代码

function bubbleSort(arr) {

    var len = arr.length;

    for (var i = 0; i < len - 1; i++) {

        for (var j = 0; j < len - 1 - i; j++) {

            if (arr[j] > arr[j+1]) {        // 相邻元素两两对比

                var temp = arr[j+1];        // 元素交换

                arr[j+1] = arr[j];

                arr[j] = temp;

            }

        }

    }

    return arr;

}

二。选择排序算法

选择排序是一种简单直观的排序算法，无论什么数据进去都是 O(n²) 的时间复杂度。选择排序算法的步骤描述如下：

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
重复第二步，直到所有元素均排序完毕。

JavaScript实现选择排序算法的代码如下：

[JavaScript] 纯文本查看 复制代码

function selectionSort(arr) {

    var len = arr.length;

    var minIndex, temp;

    for (var i = 0; i < len - 1; i++) {

        minIndex = i;

        for (var j = i + 1; j < len; j++) {

            if (arr[j] < arr[minIndex]) {     // 寻找最小的数

                minIndex = j;                 // 将最小数的索引保存

            }

        }

        temp = arr;

        arr = arr[minIndex];

        arr[minIndex] = temp;

    }

    return arr;

}

三。插入排序算法
插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序算法的步骤描述如下：
将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）

JavaScript实现插入排序算法的代码如下：
[JavaScript] 纯文本查看 复制代码
function insertionSort(arr) {
var len = arr.length;
var preIndex, current;
for (var i = 1; i < len; i++) {
      preIndex = i - 1;
      current = arr;
      while(preIndex >= 0 && arr[preIndex] > current) {
         arr[preIndex+1] = arr[preIndex];
         preIndex--;
      }
      arr[preIndex+1] = current;
}
return arr;
}
四。希尔排序算法
希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。希尔排序算法的步骤描述如下：
选择一个增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；
按增量序列个数 k，对序列进行 k 趟排序；
每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

JavaScript实现希尔排序算法的代码如下：
[JavaScript] 纯文本查看 复制代码
function shellSort(arr) {
var len = arr.length,
      temp,
      gap = 1;
while(gap < len/3) {       //动态定义间隔序列
      gap =gap*3+1;
}
for (gap; gap > 0; gap = Math.floor(gap/3)) {
      for (var i = gap; i < len; i++) {
         temp = arr;
         for (var j = i-gap; j >= 0 && arr[j] > temp; j-=gap) {
            arr[j+gap] = arr[j];
         }
         arr[j+gap] = temp;
      }
}
return arr;
}
五。归并排序算法
归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。归并排序算法的步骤描述如下：
申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
设定两个指针，最初位置分别为两个已经排序序列的起始位置；
比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
重复步骤 3 直到某一指针达到序列尾；
将另一序列剩下的所有元素直接复制到合并序列尾。

JavaScript实现归并排序算法的代码如下：
[JavaScript] 纯文本查看 复制代码
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;
}
点击查看更多精彩前端资源
点击有惊喜

欢迎光临黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2