简单说一说排序算法

    xiaoxiao2021-03-26  15

    作为一名合格的程序员,还是要懂一些排序算法。

    学习这个话题,通常都会先学冒泡排序,因为它在所有的排序算法中是最简单也是最**的。当然,简单是不会有好结果的。它的性能也是最差的。

    冒泡排序通过比较任何两个相邻的项,如果第一个比第二个打,则交换它们。元素项向上移动至正确的顺序,就好像气泡从水中往上冒一样。冒泡因此得名。

    具体实现代码:

    function bubbleSort(array){ var length = array.length; for(var i = 0 ; i < length ; i++){ for(var j = 0 ; j < length - 1 ; j++){ //for(var j = 0 ; i < length - 1 - j ; j++) if(array[j] > array[j+1]){ var temp = array[j]; array[j] = array[j+1]; array[j+1] = temp; } } } }

    上面代码注释部分是对冒泡算法的优化:通过从内循环中减去外循环中一跑过的轮数,避免内循环中所有不必要的比较。

    第二种算法是选择排序,选择排序算法是一种原址比较排序算法。含义就是找到数据结构中的最小值并将其放置在第一位,接着找到第二小的值并将其放在第二位,以此类推。

    实现代码:

    function selectionSort (array){ var length = array.length, indexMin; for(var i = 0 ; i < length - 1; i++){ indexMin = i; for(var j = i ; i < length ; j++){ if(array[indexMin] > array[j]){ indexMin = j; } } if(i !== indexMin){ var temp = array[i]; array[i] = array[indexMin]; array[indexMin] = temp; } } }

    第三种排序算法是插入排序,插入排序比较好理解,现实生活中比较明显的例子就是插牌。你斗地主的时候,一手牌拿着,然后从第二张开始排列,跟前面的序列进行对比。如果比前面的小则插到前面。 实现代码:

    function insertionSort (array){ var length = array.length, j , temp; for(var i = 1; i < length ; i++){ j = i; temp = array[i]; while(j > 0 && array[j-1] > temp){ array[i] = array[j-1]; j--; } array[j] = temp; } }

    排序小型数组时,此算法比前面两个性能要好。

    第四种排序算法是归并排序,这也是第一个可以被实际使用的排序算法。归并排序是一种分治算法,思路是将原始数组切分成比较小的数组,直到每个小数组只有一个位置,接着将小数组归并成较大的数组,直到最后只有一个排序完毕的大数组。归并排序应用的是递归的方式。

    function mergeSort (array){ array = mergeSortRec(array); } var mergeSortRec = function(array){ var length = array.length; if(length === 1){ return array; } var mid = Math.floor(length / 2), left = array.slice(0 , mid), right = array.slice(mid , length); return merge(mergeSortRec(left) , mergeSortRec(right)); } var merge = function(left , right){ var result = [], il = 0, ir = 0; while(il < left.length && ir < right.length){ if(left[il] < right[ir] && ir < right.length){ if(left[i] < right[ir]){ result.push(left[il++]); }else{ result.push(right[ir++]); } } } while(il < left.length){ result.push(left[il++]); } while(ir < right.length){ result.push(right[ir++]); } return result; }

    可以看到,算法首先将原始数组分割直至只有一个元素的子数组,然后开始归并。

    第五种排序算法是快速排序,也是最常用的排序算法了。同样也是用了分治算法。

    “快速排序”的思想很简单,整个排序过程只需要三步:   (1)在数据集之中,选择一个元素作为”基准”(pivot)。   (2)所有小于”基准”的元素,都移到”基准”的左边;所有大于”基准”的元素,都移到”基准”的右边。   (3)对”基准”左边和右边的两个子集,不断重复第一步和第二步,直到所有子集只剩下一个元素为止。   

    function quickSort (arr) {   if (arr.length <= 1) { return arr; }   var pivotIndex = Math.floor(arr.length / 2);   var pivot = arr.splice(pivotIndex, 1)[0];   var left = [];   var right = [];   for (var i = 0; i < arr.length; i++){     if (arr[i] < pivot) {       left.push(arr[i]);     } else {       right.push(arr[i]);     }   }   return quickSort(left).concat([pivot], quickSort(right)); }

    封装后的源代码

    所有的排序算法就总结到这里,有想法的小伙伴欢迎评论区留言!

    转载请注明原文地址: https://ju.6miu.com/read-500362.html

    最新回复(0)