JS常用的6种数组排序

1，冒泡排序

冒泡排序又称为交换排序。原理是从第一个元素开始，比较相邻元素的大小，若大小顺序有误，则两数对调，再进行下一个元素的比较。如此经过第一次扫描后就可以确保最后一个元素位于正确的顺序。经过第二次扫描可以确保倒数第二个元素位于正确的顺序。由此可知，N个元素经过（N-1）次扫描，就可以完成所有元素的排序。

冒泡排序

// 冒泡排序
function Bubble (arr) {let lengthA = arr.length -1;for(let k = 0;k < lengthA;k++){let done = true;for(let i = 0;i < lengthA - k;i++){let a = arr[i];if(arr[i] > arr[i+1]){arr[i] = arr[i+1]arr[i+1]= a;done = false;};};if(done) break;};return arr;
};

2，快速排序

快速排序又称分割交换排序，是使用 “分而治之” 的方式，先在数据中找到一个虚拟的中间值，并按此中间值将所有的数据分为两部分。其中，小于中间值的数据放在左边，大于中间值的数据放在右边，再以同样的方式分别处理左、右两边的数据，直到排序完为止。

快速排序

// 快速排序
function QuickSort(arr) {if (arr.length <= 1) {return arr;}if (Array.isArray(arr)) {let center = parseInt(arr.length / 2);// 取中间值需要让原数组发生变化let centerNum = arr.splice(center, 1);let left = [];let right = [];for (let i = 0; i < arr.length; i++) {if (arr[i] <= centerNum) {left.push(arr[i]);} else {right.push(arr[i]);};};//使用递归 每次取中间排完再调用两边重新排序return QuickSort(left).concat(centerNum).concat(QuickSort(right));};
}

3，插入排序

插入排序。是将数组中的元素，逐一与已排序好的数据进行比较，前两个元素先排好，再将第三个元素插入适当的位置，所以这三个元素仍然是已排好序的，接着将第四个元素加入，重复此步骤，直到排序完成为止。

插入排序

// 插入排序
function Insert(arr) {if (!Array.isArray(arr)) return false;for (let i = 0; i < arr.length; i++) {var nowNum = arr[i]; // 记录当前的值var prevIndex = i - 1; //前面的索引//对前面进行判断while (prevIndex >= 0 && arr[prevIndex] > nowNum) {//交换位置arr[prevIndex + 1] = arr[prevIndex];prevIndex--;}arr[prevIndex + 1] = nowNum;}return arr;
}

4，选择排序

选择排序，算是枚举法的应用，就是反复从未排序的数列中取出最小的元素，加入到另一个数列中，最后的结果即为已排序的数列。从小到大排序的操作是一开始在所有的数据中挑选一个最小项放在第一个位置，再从第二项开始挑选剩下元素的最小项放在第2个位置，以此反复，直到完成排序为止。

选择排序

// 选择排序
function Select(arr) {if (!Array.isArray(arr)) return false;let temp = null;for (let i = 0; i < arr.length; i++) {//默认记录最小索引let minindex = i;for (let k = i + 1; k < arr.length; k++) {minindex = arr[k] < arr[minindex] ? k : minindex;};//交换位置temp = arr[i];arr[i] = arr[minindex];arr[minindex] = temp;}return arr;
}

5，希尔排序

希尔排序是插入排序的一种，它是针对直接插入排序算法的改进，该方法又称缩小增量排序。希尔排序实质上是一种分组插入方法。它的基本思想是：对于n个待排序的数列，取一个小于n的整数gap(gap被称为步长)将待排序元素分成若干个组子序列，所有距离为gap的倍数的记录放在同一个组中；然后，对各组内的元素进行直接插入排序。这一趟排序完成之后，每一个组的元素都是有序的。然后减小gap的值，并重复执行上述的分组和排序。重复这样的操作，当gap=1时，整个数列就是有序的。

希尔排序

// 希尔排序
function ShellSort(arr) {let len = arr.length,temp,gap = 1;// 动态定义间隔序列，也可以手动定义，如 gap = 5；while (gap < len / 5) {gap = gap * 5 + 1;};for (gap; gap > 0; gap = Math.floor(gap / 5)) {for (var i = gap; i < len; i++) {temp = arr[i];for (var j = i - gap; j >= 0 && arr[j] > temp; j -= gap) {arr[j + gap] = arr[j];}arr[j + gap] = temp;}}return arr;
}

6，归并排序

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
归并排序

// 归并排序function MergeOne(arr) {if (arr.length < 2) {return arr;}//首先将无序数组划分为两个数组let mid = Math.floor(arr.length / 2);let left = arr.slice(0, mid);let right = arr.slice(mid, arr.length);//递归分别对左右两部分数组进行排序合并return this.MergeTwo(this.MergeOne(left), this.MergeOne(right)); },function MergeTwo(left, right) {let 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;}

7，六种方法的集合

<script>let data = [5,6,8,7,3,2,40,100,99,80,10];const Sort = {num:0,// 冒泡排序Bubble (arr) {let lengthA = arr.length -1;for(let k = 0;k < lengthA;k++){let done = true;for(let i = 0;i < lengthA - k;i++){let a = arr[i];if(arr[i] > arr[i+1]){arr[i] = arr[i+1]arr[i+1]= a;done = false;};this.num++;};if(done) break;};return arr;},// 快速排序QuickSort(arr) {if (arr.length <= 1) {return arr;}if (Array.isArray(arr)) {let center = parseInt(arr.length / 2);// 取中间值需要让原数组发生变化let centerNum = arr.splice(center, 1);let left = [];let right = [];for (let i = 0; i < arr.length; i++) {if (arr[i] <= centerNum) {left.push(arr[i]);} else {right.push(arr[i]);};this.num++;};//使用递归 每次取中间排完再调用两边重新排序return this.QuickSort(left).concat(centerNum).concat(this.QuickSort(right));};},// 插入排序Insert(arr) {if (!Array.isArray(arr)) return false;for (let i = 0; i < arr.length; i++) {var nowNum = arr[i]; // 记录当前的值var prevIndex = i - 1; //前面的索引//对前面进行判断while (prevIndex >= 0 && arr[prevIndex] > nowNum) {this.num++;//交换位置arr[prevIndex + 1] = arr[prevIndex];prevIndex--;}arr[prevIndex + 1] = nowNum;}return arr;},// 选择排序Select(arr) {if (!Array.isArray(arr)) return false;let temp = null;for (let i = 0; i < arr.length; i++) {//默认记录最小索引let minindex = i;for (let k = i + 1; k < arr.length; k++) {minindex = arr[k] < arr[minindex] ? k : minindex;this.num++;};//交换位置temp = arr[i];arr[i] = arr[minindex];arr[minindex] = temp;}return arr;},// 希尔排序ShellSort(arr) {let len = arr.length,temp,gap = 1;// 动态定义间隔序列，也可以手动定义，如 gap = 5；while (gap < len / 5) {gap = gap * 5 + 1;};for (gap; gap > 0; gap = Math.floor(gap / 5)) {for (var i = gap; i < len; i++) {temp = arr[i];for (var j = i - gap; j >= 0 && arr[j] > temp; j -= gap) {arr[j + gap] = arr[j];this.num++;}arr[j + gap] = temp;}}return arr;},// 归并排序MergeOne(arr) {if (arr.length < 2) {return arr;}//首先将无序数组划分为两个数组let mid = Math.floor(arr.length / 2);let left = arr.slice(0, mid);let right = arr.slice(mid, arr.length);//递归分别对左右两部分数组进行排序合并return this.MergeTwo(this.MergeOne(left), this.MergeOne(right)); },MergeTwo(left, right) {this.num++;let 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;}};console.log(Sort.Bubble(data), `排序执行了${Sort.num}次`);
</script>