js实现高级排序(希尔排序和快速排序)

2020-10-8 22:46:30
学习记录
477

js实现高级排序(希尔排序和快速排序)

数据结构已经学完了,整体对于数据结构有所了解,但是还是处于入门阶段吧,对各种场景下,数据结构的选择和算法实现不能给灵活的运用,主要是对算法的认识不够深刻,关键点把握不够牢固,通过这个文章,记录一下我对高级排序的实现方式,从而对前面所学的内容进行回顾

1.希尔排序

原理

希尔排序是在插入排序的基础上进行的更加深刻的优化,其中也体现出了希尔对插入排序算法的深刻理解。

希尔排序核心思想是通过挑选一定的间隔,来对一组数据进行大小排序,尽可能的使最小的数字距离正确位置更近一些,随着间隔的减小,直到间隔为1,就是简单排序中的插入排序了。

注意要点

  • 希尔排序关键要找出一个合适的间隔,希尔采用的是每次循环间隔大小是N/2。
  • 排序方式使用插入排序

实现代码

function shellSort(arr){ let gap = Math.floor(arr.length/2); while(gap>0){ for(let i=gap;i<arr.length;i++){ let tmp = arr[i]; let k = i;//内层插入初始化变量,注意下面循环查找是从后往前查找并插入的。 while( tmp < arr[k-gap]&&k>0 ){ arr[k] = arr[k-gap]; k -= gap; } arr[k] = tmp; } gap = Math.floor(gap/2); } return arr; }

2. 快速排序

原理

快速排序利用了分而治之的思想,从一堆数中拿出来一个,其他的按照大的放左边,小的放右边,这样就可以确定,拿出来的这个就是正确位置了的,接下来就分别多左边指针和右边指针再次分而治之,直到最后指针大小都一样。

注意要点

  • 快速排序需要用到递归,但是递归的结束条件是传入的开始元素指针必须要大于结束元素
  • 挑选第一个数也比较重要,尽可能挑选到接近中间的数,这样可以让算法更均匀

代码实现

//获取中间数数据,作为第一个被挑出来的 function getMiddle(arr,start,end){ let middle = Math.floor((start+end)/2); let tmp; //下面使用了冒泡排序挑选出最中间的数 if(arr[start]>arr[middle]){ tmp = arr[start]; arr[start] = arr[middle]; arr[middle] = tmp; } if(arr[middle]>arr[end]){ tmp = arr[middle]; arr[middle] = arr[end]; arr[end] = tmp; } if(arr[start]>arr[middle]){ tmp = arr[start]; arr[start] = arr[middle]; arr[middle] = tmp; } return {pivot:middle,arr}; } function quickSort(arr,start=0,end=arr.length-1){ let {pivot,arr:newArr} = getMiddle(arr,start,end); arr = newArr; let left,right,tmp;//定义双指针 tmp = arr[pivot]; arr[pivot] = arr[end-1]; arr[end-1] = tmp; pivot = end-1; left = start; right = pivot; while(left<right){ //因为经getMiddle 已经把两端的位置大小排好了 if(arr[left] > arr[right]){ tmp = arr[left]; arr[left] = arr[right]; arr[right] = tmp; } while(arr[++left]<arr[pivot]){} while(arr[--right]>arr[pivot]){} } if(pivot != left){ tmp = arr[pivot]; arr[pivot] = arr[left]; arr[left] = arr[pivot]; pivot = left; } if(pivot - 1 >start){ arr = quickSort(arr,start,pivot-1); } if(end > pivot+1){ arr = quickSort(arr,pivot+1,end); } return arr; }

js实现高级排序(希尔排序和快速排序)

avatar

Sky(小新)

个人签名: 提升能力,创造价值!

江苏-南京
skylpz@qq.com