JavaScript排序算法一（冒泡排序、选择排序、插入排序、希尔排序、归并排序）

[madfour]

十大算法动图演示

常见的内部算法：冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序、基数排序等

1、冒泡排序

function bubbleSort(arr) {
let len = arr.length;
for (let i = 0; i < len; i++) {
for (let j = 0; j < len - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {         //相邻元素两两对比
let temp = arr[j + 1];     // 元素交换
arr[j + 1] = arr[j];
arr[j] = temp
}
}
}
return arr
}

var arr = [133, 23, 4, 90, 55, 6, 0]; bubbleSort(arr)

### 2、选择排序（使用时数据规模越小越好；不占额外内存空间）
```JavaScript
function selectionSort(arr) {
    var len = arr.length;
    var minIndex, temp;
    for (let i = 0; i < len - 1; i++) {
        minIndex = i;
        for (let j = i + 1; j < len; j++) {
            if (arr[j] < arr[minIndex]) {     //寻找最小的数
                minIndex = j;                 //将最小数的索引保存
            }
        }
        temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
    return arr;
}

var arr = [133, 23, 4, 90, 55, 6, 0];
selectionSort(arr)

3、插入排序（像打扑克牌一样，按大小整理牌）

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

function Insertion(arr) {
let len = arr.length;
let preIndex, current;
for (let i = 1; i < len; i++) {
preIndex = i - 1;
current = arr[i];
while (preIndex >= 0 && current < arr[preIndex]) {
arr[preIndex + 1] = arr[preIndex];
preIndex--;
}
arr[preIndex + 1] = current;
}
return arr;
}

var arr = [133, 23, 4, 90, 55, 6, 0]; Insertion(arr); // [0, 4, 6, 23, 55, 90, 133]

### 4、希尔排序(又叫缩小增量排序) #8 
> 希尔排序是插入排序的一种高效率；但是对数列进行了等间隔分组处理，在每一组中做插入排序。
> 希尔排序的核心在于间隔序列的设定。既可以提前设定好间隔序列，也可以动态的定义间隔序列。
```JavaScript
function shellSort(arr) {
  let len = arr.length;
  // gap 即为增量
  for (let gap = Math.floor(len / 2); gap > 0; gap = Math.floor(gap / 2)) {
    for (let i = gap; i < len; i++) {
      let j = i;
      let current = arr[i];
      while(j - gap >= 0 && current < arr[j - gap]) {
        arr[j] = arr[j - gap];
        j = j - gap;
      }
      arr[j] = current;
    }
  }
}

var arr = [133, 23, 4, 90, 55, 6, 0];
shellSort(arr);     // [0, 4, 6, 23, 55, 90, 133]

5、归并排序

(分治法)先使每个子序列有序，再使子序列段间有序。

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 > 0 && right.length > 0) {
    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 = [133, 23, 4, 90, 55, 6, 0]; mergeSort(arr); // [0, 4, 6, 23, 55, 90, 133]

[madfour]

扩展： 希尔排序理解及视图

将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：

• 选择一个增量序列t1，t2，…，tk，其中t1>t2>...，tk=1；

• 按增量序列个数k，对序列进行k 趟排序；

• 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。