首页 > 代码库 > [JS]算法总结

[JS]算法总结

技术分享

一、冒泡排序

  1. function bubbleSort(arr){
  2. for(var i=1;i<arr.length;i++){//共需要多少轮
  3. for(var j=0;j<arr.length-i;j++){//每i轮过后,都有最后i个数无需再排序,即第1轮过后,最后一个数最大,第2轮过后,最后两个数最大
  4. if(arr[j]>arr[j+1]){//如果前一个数大于后一个,则交换二者的值
  5. arr[j+1]=[arr[j],arr[j]=arr[j+1]][0];
  6. }
  7. }
  8. }
  9. console.log(arr);
  10. }
  11. sort();

二、快速排序

  1. function quickSort(arr){
  2. if(arr.length<=1){
  3. return arr;
  4. }
  5. var pivotIndex = Math.floor(arr.length/2);//取基准点
  6. var pivot = arr.splice(pivotIndex,1)[0];//从数组中取出基准点所在的数
  7. var left = [];
  8. var right = [];
  9. for(var i=0;i<arr.length;i++){
  10. if(arr[i] < pivot){
  11. left.push(arr[i]);
  12. }else {
  13. right.push(arr[i]);
  14. }
  15. }
  16. return quickSort(left).concat(pivot,quickSort(right));//递归调用
  17. }

三、直接插入排序

  1. function insertionSort(arr){
  2. for (var i = 1; i < arr.length; i++) {//从第2个数开始排序
  3. for (var j = i; j > 0; j--) {//从后往前查找
  4. if (arr[j - 1] > arr[j]) {//如果前一个数大于后一个数,交换二者的值
  5. arr[j]=[arr[j-1],arr[j-1]=arr[j]][0];
  6. } else {
  7. break;
  8. }
  9. }
  10. }
  11. return arr;
  12. }

四、二分查找插入排序

  1. function binaryInsertionSort(array) {
  2. for (var i = 1; i < array.length; i++) {
  3. var key = array[i], left = 0, right = i - 1;
  4. while (left <= right) {
  5. var middle = parseInt((left + right) / 2);
  6. if (key < array[middle]) {
  7. right = middle - 1;
  8. } else {
  9. left = middle + 1;
  10. }
  11. }
  12. for (var j = i - 1; j >= left; j--) {
  13. array[j + 1] = array[j];
  14. }
  15. array[left] = key;
  16. }
  17. return array;
  18. }

五、选择排序

  1. function selectionSort(arr) {
  2. for (var i = 0,len=arr.length; i < len - 1; i++) {//n个数需要n-1次排序
  3. for (var j = i + 1; j < len; j++) {//从i之后的一个数开始遍历
  4. if (arr[j] < arr[i]) {//找到最小的那个数,然后与arr[i]交换值
  5. arr[i]=[arr[j],arr[j]=arr[i]][0];
  6. }
  7. }
  8. }
  9. return arr;
  10. }

参考链接:
http://www.cnblogs.com/beli/p/6297741.html
http://www.cnblogs.com/ywang1724/p/3946339.html

[JS]算法总结