经典排序算法 js 实现
使用JavaScript实现排序算法
1. 冒泡排序
冒泡排序是我记得最牢的了，可能是因为它的思想最简单，重复走过要排序的序列，一次比较两个元素，如果顺序错误就把它们调整过来（升序）。一直重复工作，知道把最大的元素一步步下沉到数组的尾部function BubbleSort(arr) {
for(var i=0;i<arr.length;i++){
for(var j=0;j<arr.length-1-i;j++){//因为每次循环都会有一个数被下沉，随着x增大下沉的元素就增加了
if(arr[j]>arr[j+1]){
let temp = arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp
}
}
}
return arr;
}
2. 选择排序
选择排序对我来说也很好理解,首先在未排序的数组中找到最小（最大）元素，存放到排序序列的起始位置，然后在从生育未排序元素中继续寻找最小（最大）的元素，然后放到已排序序列的尾部，以此类推，直到所有元素排序完毕
function quickSort(arr) {
for(var i=0;i<arr.length;i++){
for(var j=i+1;j<arr.length;j++){
if(arr[j]<arr[i]){
let temp = arr[j];
arr[j] = arr[i];
arr[i] = temp
}
}
}
return arr;
}
3. 插入排序
原理是，对于未排序数据，在一排序序列中从后向前扫描，为其找到相应的位置并插入。从后向前扫描的过程中需要对元素进行向后移位操作
function insertSort(arr) {
for(var i=1;i<arr.length;i++){
var preIndex =i-1;
var current = arr[i];
while(preIndex>=0&¤t<arr[preIndex]){
arr[preIndex+1]=arr[preIndex];
preIndex--;
}
arr[preIndex+1]=current;
}
return arr;
}
4. 希尔排序
据说是第一个突破O(n^2)的排序操作，可以说是简单插入排序的改进版。它与插入排序的不同在于，它会优先比较距离较远的元素。所以又叫缩小增量排序。核心在于间隔序列的设定，好的间隔序列的设定能够很大程度上的降低排序的时间复杂度。这次我采用的增量是数组长度的一半，然后依次折半。当增量减至1时候，数组被分为了一组，算法停止。
我们来看下希尔排序的基本步骤，在此我们选择增量gap=length/2，缩小增量继续以gap = gap/2的方式，这种增量选择我们可以用一个序列来表示，{n/2,(n/2)/2...1}，称为增量序列
function ShellSort(arr) {
var len = arr.length;
for (var gap = Math.floor(arr.length/2); gap>0;gap=Math.floor(gap/2)){
for(var i=0;i<gap;i++){//i表示被分成了几组
var j = i;
while(j<arr.length-gap){
var k = j;
while(arr[k+gap]<arr[k]&&k>=0){
var temp = arr[k+gap];
arr[k+gap] = arr[k];
arr[k] = temp;
k=k-gap;
}
j=j+gap;
}
}
}
return arr
}
5. 归并排序
和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是O(n log n）的时间复杂度。代价是需要额外的内存空间。
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。归并排序是一种稳定的排序方法。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。
核心思想：分治。
主题流程：先将一个序列分成很多个不能再分割的子序列，将各个子序列分别排序后再将子序列合并。其实就是重复两个步骤：【1】分【2】合并。
首先是第一个小问题，怎么分?
比如说一个序列:12 ,23,1,44,233,10,9,8。我们先分成两段：12 ,23,1,44 和 233,10,9,8，
发现还能再分成4段：12 ,23 和 1,44------233,10 和 9,8。
再分成8段：12--23--1--44 和233--10--9--8。
这时候开始把子序列进行排序合并，一个元素就是有序的。所以不用排序。
合并成2个一组排序得到：12，23----1，44---10，233---8，9。
再合并成4个一组排序得到：1，12，23，44---8，9，10，233。
最后合并得到最终结果：1，8，9，10，12，23，44，233
我觉得归并排序在实现上就可以分为两个函数，一个负责分段，一个负责合并（因为分割后的每个子序列都是有序的，合并就是两个有序数组合并的过程）
function merge(arr) {
if(arr.length<2){
return arr;
}
var mid = Math.floor(arr.length/2);
//floor 向下取值；ceil向上取值，around 正常的四舍五入
var left = arr.slice(0,mid);
var right = arr.slice(mid);
return sort(merge(left),merge(right));
}
function sort(left,right) {
var result=[];
var i=0;var j=0;
while(i<left.length&&j<right.length){
if(left[i]<right[j]){
result.push(left[i]);
i++
}
else{
result.push(right[j]);
j++
}
}
if(i==left.length){
result=result.concat(right.slice(j));
}
if(j==right.length){
result=result.concat(left.slice(i));
}
return result;
}
6. 堆排序
https://www.cnblogs.com/chengxiao/p/6129630.html
这篇文章讲的太好了，我就是按照它的讲解步骤理解了整个过程，将代码写出来了。
堆是具有以下性质的完全二叉树：每个节点的值都大于或者等于其左右节点的值，称为大顶堆；每个节点的值都小于或者等于其左右孩子节点的值，称为小顶堆。如下图
有几个公式比较重要：
大顶堆：arr[i]>=arr[2i+1]&&arr[i]>=arr[ai+2];
小顶堆：arr[i]<=arr[2i+1]&&arr[i]<=arr[2i+2];
第一个非叶子节点：arr.length/2-1
再简单总结下堆排序的基本思路：
a.将无需序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆;
b.将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端;
c.重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。
function HeapSort(arr) {
for(var k=Math.floor(arr.length/2)-1;k>=0;k--){
arr = HightHeap(arr,k,arr.length);
}
for(var j= arr.length-1;j>0;j--){
//重新对堆顶进行调整
var temp = arr[j];
arr[j] = arr[0];
arr[0] = temp;
//调整后进行堆调整
for(var f = Math.floor(j/2)-1;f>=0;f--)
arr = HightHeap(arr,f,j);
}
return arr
}
function HightHeap(arr,i,length) {
var current = arr[i];
if(i*2+2<length&&arr[i*2+1]<arr[i*2+2]){
if(arr[i*2+2]>arr[i]){
arr[i]= arr[i*2+2];
arr[i*2+2] =current
}
}
else {
if(arr[i*2+1]>arr[i]){
arr[i]= arr[i*2+1];
arr[i*2+1] =current
}
}
return arr
}
7. 快速排序（https://blog.****.net/adusts/article/details/80882649原理带图）
快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序
function sort(arr,left,right) {//第一次调用的时候left=0，right=arr.length-1
var standard = arr[left];
var i=left;
var j=right;
if(left>=right)return arr;
while(i<j){
while(arr[j]>=standard&&j>i)j--;
while (arr[i]<=standard&&i<j)i++;
if(i<j){
var temp= arr[j];
arr[j] = arr[i];
arr[i] = temp;
}
}
arr[left] = arr[j];
arr[j]=standard;
sort(arr,left,i-1);
sort(arr,i+1,right);
return arr;
}
二分查找
二分查找又称为折半查找，仅适用于事先已经排好序的顺序表。其查找的基本思路：首先将给定值K，与表中中间位置元素的关键字比较，若相等，返回该元素的存储位置；若不等，这所需查找的元素只能在中间数据以外的前半部分或后半部分中。然后在缩小的范围中继续进行同样的查找。如此反复直到找到为止。算法如下：
（1）递归方法
1 function binarySearch(data,item,start,end){
2 var end=end || data.length-1;
3 var start=start || 0;
4 var m=Math.floor((start+end)/2);
5 if(item==data[m]){
6 return m;
7 }else if(item<data[m]){
8 return binarySearch(data,item,start,m-1) //递归调用
9 }else{
10 return binarySearch(data,item,m+1,end);
11 }
12 return false;
13 }
14
15 var arr=[34,12,5,123,2,745,32,4];
16
17 binary(arr,5);
（2）非递归方法
function binarySearch(data, item){
2 var h = data.length - 1,
3 l = 0;
4 while(l <= h){
5 var m = Math.floor((h + l) / 2);
6 if(data[m] == item){
7 return m;
8 }
9 if(item > data[m]){
10 l = m + 1;
11 }else{
12 h = m - 1;
13 }
14 }
15
16 return false;
17 }
18 var arr=[34,12,5,123,2,745,32,4];
19 binarySearch(arr,5);