资讯专栏INFORMATION COLUMN

学习经典算法—JavaScript篇(一)排序算法

Rindia / 3236人阅读

摘要:对每一对相邻元素作同样的工作,从开始第一对一直到结尾的最后一对,如此将最大的数放在后面。持续每次对元素重复上面的步骤,直到排序完成。排序步骤将第一待排序序列第一个元素看做一个有序序列,把第二个元素到最后一个元素当成是未排序序。

前端攻城狮——学习常用的排序算法 一、冒泡排序

优点:

所有排序中最简单的,易于理解;

缺点:

时间复杂度O(n^2),平均来说是最差的一种排序方式;

因为在默认情况下,对于已经排好序的部分,此排序任然会进行比较(当然可以进行改进优化)

算法步骤:

比较相邻的元素,如果第一个比第二个大,就交换他们两个。

对每一对相邻元素作同样的工作,从开始第一对一直到结尾的最后一对,如此将最大的数放在后面。

对所有的元素重复以上的步骤,除了最后一个。

持续每次对元素重复上面的步骤,直到排序完成。

原理分析:

通过比较两个相邻的项,(由小到大排序)如果第一个比的二个大,则交换它们的位置元素项向上移动至正确的顺序,就好像气泡升至表面,冒泡也因此得名。

</>复制代码

  1. const bubbleSort = (arr) => {
  2. const length= arr.length;
  3. for (let i = 0; i arr[j+1]){
  4. let swap = arr[j];
  5. arr[j] = arr[j+1];
  6. arr[j+1] = swap;
  7. }
  8. }
  9. }
  10. }

改进优化:

默认上述代码,对于第一轮之后的循环任然会进行和全部元素的比较,但其实之前的循环已经将器排序正确了,所以可以从内循环中减去外循环已经进行过的轮数,从而避免不必要的比较

</>复制代码

  1. const bubbleSort = (arr) => {
  2. const length= arr.length;
  3. for (let i = 0; i arr[j+1]){
  4. let swap = arr[j];
  5. arr[j] = arr[j+1];
  6. arr[j+1] = swap;
  7. }
  8. }
  9. }
  10. }

二、选择排序

原理:

进行原地址比较,找到数据结构中最小值并放在第一位,接着在剩下的中找到第二个最小值放在第二位,依次类推;

代码实现:

</>复制代码

  1. function selectionSort(arr) {
  2. var length= arr.length;
  3. var minIndex;
  4. for (var i = 0; i < length - 1; i++) {
  5. minIndex = i;
  6. for (var j = i + 1; j < length; j++) {
  7. if (arr[j] < arr[minIndex]) { // 寻找最小的数
  8. minIndex = j; // 将最小数的索引保存
  9. }
  10. }
  11. if(i != minIndex){
  12. var temp = arr[i];
  13. arr[i] = arr[minIndex];
  14. arr[minIndex] = temp;
  15. }
  16. }
  17. return arr;
  18. }

三、插入排序

原理:

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

排序步骤:

将第一待排序序列第一个元素看做一个有序序列,把第二个元素到最后一个元素当成是未排序序。

从头到尾依次扫描未排序序列,将扫描到的每个元素插入有序序列的适当位置。(如果待插入的元素与有序序列中的某个元素相等,则将待插入元素插入到相等元素的后面。)

代码实现

</>复制代码

  1. function insertionSort(arr) {
  2. var len = arr.length;
  3. var preIndex, current;
  4. for (var i = 1; i < len; i++) {
  5. preIndex = i - 1;
  6. current = arr[i];
  7. while(preIndex >= 0 && arr[preIndex] > current) {
  8. arr[preIndex+1] = arr[preIndex];
  9. preIndex--;
  10. }
  11. arr[preIndex+1] = current;
  12. }
  13. return arr;
  14. }

原理图

四、归并排序

原理:

归并是一种分治算法,即将原始数组切分成较小的数组,直到每个小数组只有一个位置,接着将小数组归并成较大的数组,每次归并时进行排序,直到最后只有一个排序完毕的大数组。

代码实现(递归):

</>复制代码

  1. function mergeSort(arr) { // 采用自上而下的递归方法,数组拆分
  2. var len = arr.length;
  3. if(len < 2) {
  4. return arr;
  5. }
  6. var middle = Math.floor(len / 2),
  7. left = arr.slice(0, middle),
  8. right = arr.slice(middle);
  9. return merge(mergeSort(left), mergeSort(right));
  10. }
  11. //合并数组,并进行排序
  12. function merge(left, right)
  13. {
  14. var result = [];
  15. while (left.length && right.length) {
  16. if (left[0] <= right[0]) {
  17. result.push(left.shift());
  18. } else {
  19. result.push(right.shift());
  20. }
  21. }
  22. while (left.length)
  23. result.push(left.shift());
  24. while (right.length)
  25. result.push(right.shift());
  26. return result;
  27. }

原理图

五、快速排序

原理:

快速排序使用分治法(Divide and conquer)策略来把一个串行(list)分为两个子串行(sub-lists)。

排序步骤:

首先,从数组中选择中间一项作基数;

然后,创建两个指针,左边一个指向数组的第一项,右边一个指向数组的最后一项;

移动左指针直到找到一个比基数大的元素,移动右指针,直到找到一个比基数小的元素;然后交换它们;

重复以上步骤,直到左指针超过了右指针;(这个过程将使得比基数小的树都在基数的前面,较大的数都在基数的后面)

最后,对划分后的小数组(比基数小的值组成的子数组,以及比基数大的值组成是子数组)重复之前的两个步骤,直到数组已经完全排序。

代码实现

</>复制代码

  1. function quickSort(arr, left, right) {
  2. var len = arr.length,
  3. partitionIndex,
  4. left = typeof left != "number" ? 0 : left,
  5. right = typeof right != "number" ? len - 1 : right;
  6. if (left < right) {
  7. partitionIndex = partition(arr, left, right);
  8. quickSort(arr, left, partitionIndex-1);
  9. quickSort(arr, partitionIndex+1, right);
  10. }
  11. return arr;
  12. }
  13. function partition(arr, left ,right) { // 分区操作
  14. var pivot = left, // 设定基准值(pivot)
  15. index = pivot + 1;
  16. for (var i = index; i <= right; i++) {
  17. if (arr[i] < arr[pivot]) {
  18. swap(arr, i, index);
  19. index++;
  20. }
  21. }
  22. swap(arr, pivot, index - 1);
  23. return index-1;
  24. }
  25. function swap(arr, i, j) {
  26. var temp = arr[i];
  27. arr[i] = arr[j];
  28. arr[j] = temp;
  29. }
  30. function partition2(arr, low, high) {
  31. let pivot = arr[low];
  32. while (low < high) {
  33. while (low < high && arr[high] > pivot) {
  34. --high;
  35. }
  36. arr[low] = arr[high];
  37. while (low < high && arr[low] <= pivot) {
  38. ++low;
  39. }
  40. arr[high] = arr[low];
  41. }
  42. arr[low] = pivot;
  43. return low;
  44. }
  45. function quickSort2(arr, low, high) {
  46. if (low < high) {
  47. let pivot = partition2(arr, low, high);
  48. quickSort2(arr, low, pivot - 1);
  49. quickSort2(arr, pivot + 1, high);
  50. }
  51. return arr;
  52. }

原理图

</>复制代码

  1. 持续更新中~喜欢留下个赞哦!

往期经典好文推荐——前端JavaScript面试宝典

我的成长日记——我的前端面试日记(1)

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/116732.html

相关文章

  • 学习经典算法JavaScript排序算法

    摘要:对每一对相邻元素作同样的工作,从开始第一对一直到结尾的最后一对,如此将最大的数放在后面。持续每次对元素重复上面的步骤,直到排序完成。排序步骤将第一待排序序列第一个元素看做一个有序序列,把第二个元素到最后一个元素当成是未排序序。 前端攻城狮——学习常用的排序算法 一、冒泡排序 优点: 所有排序中最简单的,易于理解; 缺点: 时间复杂度O(n^2),平均来说是最差的一种排序方式; 因为在...

    remcarpediem 评论0 收藏0
  • 学习经典算法JavaScript排序算法

    摘要:对每一对相邻元素作同样的工作,从开始第一对一直到结尾的最后一对,如此将最大的数放在后面。持续每次对元素重复上面的步骤,直到排序完成。排序步骤将第一待排序序列第一个元素看做一个有序序列,把第二个元素到最后一个元素当成是未排序序。 前端攻城狮——学习常用的排序算法 一、冒泡排序 优点: 所有排序中最简单的,易于理解; 缺点: 时间复杂度O(n^2),平均来说是最差的一种排序方式; 因为在...

    fireflow 评论0 收藏0
  • 十大经典排序算法总结(Javascript描述)

    摘要:算法描述冒泡排序是一种简单的排序算法。算法描述和实现一般来说,插入排序都采用在数组上实现。平均情况希尔排序年发明第一个突破的排序算法是简单插入排序的改进版它与插入排序的不同之处在于,它会优先比较距离较远的元素。 前言 读者自行尝试可以想看源码戳这,博主在github建了个库,读者可以Clone下来本地尝试。此博文配合源码体验更棒哦~~~ 个人博客:Damonare的个人博客 原文地址:...

    Binguner 评论0 收藏0
  • Nicolas讲算法:Computer Science in JavaScript

    摘要:使用来描述算法和数据结构的教程很少,目前市面上用描述算法和数据结构的书屈指可数,并且就我看过的那本而言我只看过数据结构与算法语言描述质量实在堪忧。 使用JavaScript来描述算法和数据结构的教程很少, 目前市面上用JS描述算法和数据结构的书屈指可数,并且就我看过的那本而言(我只看过《数据结构与算法 JavaScript 语言描述》)质量实在堪忧。碰巧有次看到Nicolas博客中的C...

    codergarden 评论0 收藏0

发表评论

0条评论

Rindia

|高级讲师

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<