js实现常用排序算法

本文为大家分享了js实现常用排序算法,具体内容如下

1.冒泡排序

 var bubbleSort = function (arr) {
 var flag = true;
 var len = arr.length;
 for (var i = 0; i < len - 1; i++) {
  flag = true;
  for (var j = 0; j < len - 1 - i; j++) {
   if (arr[j] > arr[j + 1]) {
    var temp = arr[j+1];
    arr[j+1] = arr[j];
    arr[j] = temp;
    flag = false;
   }
  }
  if (flag) {
   break;
  }
 }
};

2.选择排序

 var selectSort = function (arr) {
 var min;
 for (var i = 0; i < arr.length-1; i++) {
  min = i;
  for (var j = i + 1; j < arr.length; j++) {
   if (arr[min] > arr[j]) {
    min = j;
   }
  }
  if (i != min) {
   swap(arr, i, min);
  }
 }
};
function swap(arr, index1, index2) {
 var temp = arr[index1];
 arr[index1] = arr[index2];
 arr[index2] = temp;
}; 

 3.插入排序

 var insertSort = function (arr) {
 var len = arr.length, key;
 for (var i = 1; i < len; i++) {
  var j = i;
  key = arr[j];
  while (--j > -1) {
   if (arr[j] > key) {
    arr[j + 1] = arr[j];
   } else {
    break;
   }
  }
  arr[j + 1] = key;
 }
};

4.希尔排序

 var shellSort = function (arr) {
 var gaps = [5, 3, 1];
 for (var g = 0; g < gaps.length; ++g) {
  for (var i = gaps[g]; i < arr.length; ++i) {
   var temp = arr[i];
   for (var j = i; j >= gaps[g] && arr[j - gaps[g]] > temp; j -= gaps[g]) {
    arr[j] = arr[j - gaps[g]];
   }
   arr[j] = temp;
  }
 }
};

5.归并排序

 function mergeSort(arr) {
 if (arr.length < 2) {
  return;
 }
 var step = 1;
 var left, right;
 while (step < arr.length) {
  left = 0;
  right = step;
  while (right + step <= arr.length) {
   mergeArrays(arr, left, left + step, right, right + step);
   left = right + step;
   right = left + step;
  }
  if (right < arr.length) {
   mergeArrays(arr, left, left + step, right, arr.length);
  }
  step *= 2;
 }
}
function mergeArrays(arr, startLeft, stopLeft, startRight, stopRight) {
 var rightArr = new Array(stopRight - startRight + 1);
 var leftArr = new Array(stopLeft - startLeft + 1);
 k = startRight;
 for (var i = 0; i < (rightArr.length - 1); ++i) {
  rightArr[i] = arr[k];
  ++k;
 }
 k = startLeft;
 for (var i = 0; i < (leftArr.length - 1); ++i) {
  leftArr[i] = arr[k];
  ++k;
 }
 rightArr[rightArr.length - 1] = Infinity; // 哨兵值
 leftArr[leftArr.length - 1] = Infinity; // 哨兵值
 var m = 0;
 var n = 0;
 for (var k = startLeft; k < stopRight; ++k) {
  if (leftArr[m] <= rightArr[n]) {
   arr[k] = leftArr[m];
   m++;
  }
  else {
   arr[k] = rightArr[n];
   n++;
  }
 }
}

6.快速排序

 var quickSort = function(arr, left, right) {
 var i, j, t, pivot;
 if (left >= right) {
  return;
 }
 pivot = arr[left];
 i = left;
 j = right;
 while (i != j) {
  while (arr[j] >= pivot && i < j) {
   j--;
  }
  while (arr[i] <= pivot && i < j) {
   i++;
  }
  if (i < j) {
   t = arr[i];
   arr[i] = arr[j];
   arr[j] = t;
  }
 }
 arr[left] = arr[j];
 arr[j] = pivot;
 quickSort(arr, left, i - 1);
 quickSort(arr, i + 1, right);
}

总结:算法效率比较:

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持我们。

(0)

相关推荐

  • js的各种排序算法实现(总结)

    如下所示: // ---------- 一些排序算法 var Sort = {} Sort.prototype = { // 利用sort进行排序 systemSort:function(array){ return array.sort(function(a, b){ return a - b; }); }, // 冒泡排序 bubbleSort:function(array){ var i = 0, len = array.length, j, d; for(; i<len; i++){ f

  • js常用排序实现代码

    复制代码 代码如下: <script> Array.prototype.swap = function(i, j) { var temp = this[i]; this[i] = this[j]; this[j] = temp; } Array.prototype.bubbleSort = function() { for (var i = this.length - 1; i > 0; --i) { for (var j = 0; j < i; ++j) { if (this[j

  • js快速排序的实现代码

    但是有不少的书本讲得并不是很清楚,而且不同的教材的实现方式也不尽相同,我这里将最简单的快速排序的思路写出来供大家参考. 希望不管是使用什么语言都能从这个简单的代码里很方便的掌握快排思路与编写方式 复制代码 代码如下: function quick_sort(list, start, end) {        if (start < end) {          var pivotpos = partition(list, start, end);   //找出快排的基数          q

  • js函数排序的实例代码

    复制代码 代码如下: var as = [1,2,11,3434,3,4545,33,55,0];as.sort(); //这个排序是按照字典排序//自定义按照数字排序function sortByNum(a,b){return parseInt(a) - parseInt(b);}as.sort(sortByNum);//按照对象来排序//定义一个person对象function Person(name.age){this.name=name;this.age=age;}var p1 = ne

  • js排序与重组的实例讲解

    前几天同学发给我一个问题,思路想整理一下,也供大家参考.实际上这道题本质就是考察的是去重与排序的问题.好了闲话少说,上题. function input(req){ if(req<=100){ var arr=[],arr1=[]; for(var i=0;i<req;i++){ var num=parseInt(Math.random()*(1000-1)+1); arr.push(num); if(arr1.indexOf(arr[i])==-1) arr1.push(arr[i]); }

  • js实现常用排序算法

    本文为大家分享了js实现常用排序算法,具体内容如下 1.冒泡排序 var bubbleSort = function (arr) { var flag = true; var len = arr.length; for (var i = 0; i < len - 1; i++) { flag = true; for (var j = 0; j < len - 1 - i; j++) { if (arr[j] > arr[j + 1]) { var temp = arr[j+1]; arr

  • C/C++ 常用排序算法整理汇总分享

    (伪)冒泡排序算法: 相邻的两个元素之间,如果反序则交换数值,直到没有反序的记录为止. #include <stdio.h> void BubbleSort(int Array[], int ArraySize) { int x, y, temporary; for (x = 0; x < ArraySize - 1; x++) { for (y = x + 1; y < ArraySize; y++) { if (Array[x] > Array[y]) { tempora

  • Java常用排序算法及性能测试集合

    现在再回过头理解,结合自己的体会, 选用最佳的方式描述这些算法,以方便理解它们的工作原理和程序设计技巧.本文适合做java面试准备的材料阅读. 先附上一个测试报告: Array length: 20000bubbleSort : 766 msbubbleSortAdvanced : 662 msbubbleSortAdvanced2 : 647 msselectSort : 252 msinsertSort : 218 msinsertSortAdvanced : 127 msinsertSor

  • PHP常用排序算法实例小结【基本排序,冒泡排序,快速排序,插入排序】

    php三种基础算法:冒泡,插入和快速排序法 $array = array(2,3,5,6,9,8,1); //冒泡排序思想,前后元素比较 function sort_bulldle($array){ $num = count($array); for($i=0; $i<$num; $i++){ $tmp = $array[$i]; for ($j=$i-1; $j>=0; $j--) { if ($tmp < $array[$j]) { $arr[$j+1] = $arr[$j]; $a

  • 视觉直观感受若干常用排序算法

    直观感受几种常用排序算法,具体内容如下 1 快速排序 介绍: 快速排序是由东尼·霍尔所发展的一种排序算法.在平均状况下,排序 n 个项目要Ο(n log n)次比较.在最坏状况下则需要Ο(n2)次比较,但这种状况并不常见.事实上,快速排序通常明显比其他Ο(n log n) 算法更快,因为它的内部循环(inner loop)可以在大部分的架构上很有效率地被实现出来,且在大部分真实世界的数据,可以决定设计的选择,减少所需时间的二次方项之可能性. 步骤: 从数列中挑出一个元素,称为 "基准"

  • Java数组常用排序算法实例小结

    本文实例讲述了Java数组常用排序算法.分享给大家供大家参考,具体如下: 1.冒泡排序法 SortArray_01.java public class SortArray_01 { public static void main(String args[]) { int[] array = { 14, 5, 86, 4, 12, 3, 21, 13, 11, 2, 55, 66, 22 }; // 创建一个初始化的一维数组array System.out.println("未排序的数组:&quo

  • PHP实现常用排序算法的方法

    本文主要介绍了一些常用的排序算法,以及PHP的代码实现等,希望对您能有所帮助. 本文来自于awaimai.com,由火龙果软件Luca编辑推荐. 作为phper,一般接触算法的编程不多. 但基本的排序算法还是应该掌握. 毕竟算法作为程序的核心,算法的好坏决定了程序的质量. 本文将依次介绍一些常用的排序算法,以及PHP实现. 1 快速排序 快速排序是由东尼·霍尔发展的一种排序算法. 在平均状况下,排序 n 个项目要Ο(n log n)次比较. 在最坏状况下则需要Ο(n2)次比较,但这种状况并不常见

  • 10个python3常用排序算法详细说明与实例(快速排序,冒泡排序,桶排序,基数排序,堆排序,希尔排序,归并排序,计数排序)

    我简单的绘制了一下排序算法的分类,蓝色字体的排序算法是我们用python3实现的,也是比较常用的排序算法. Python3常用排序算法 1.Python3冒泡排序--交换类排序 冒泡排序(Bubble Sort)也是一种简单直观的排序算法. 它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来. 走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成.这个算法的名字由来是因为越小的元素会经由交换慢慢"浮"到数列的顶端. 作为最简单的排序算法

  • c语言实现的几种常用排序算法

    概述 最近重新回顾了一下数据结构和算法的一些基本知识,对几种排序算法有了更多的理解,也趁此机会通过博客做一个总结. 1.选择排序-简单选择排序 选择排序是最简单的一种基于O(n2)时间复杂度的排序算法,基本思想是从i=0位置开始到i=n-1每次通过内循环找出i位置到n-1位置的最小(大)值. 算法实现: void selectSort(int arr[], int n) { int i, j , minValue, tmp; for(i = 0; i < n-1; i++) { minValue

随机推荐