首页 > 代码库 > JavaScript实现常用的排序算法

JavaScript实现常用的排序算法

▓▓▓▓▓▓ 大致介绍

  由于最近要考试复习,所以学习js的时间少了 -_-||,考试完还会继续的努力学习,这次用原生的JavaScript实现以前学习的常用的排序算法,有冒泡排序、快速排序、直接插入排序、希尔排序、直接选择排序

 

▓▓▓▓▓▓ 交换排序

  交换排序是一类在排序过程中借助于交换操作来完成排序的方法,基本思想是两两比较排序记录的关键字,如果发现两个关键字逆序,则将两个记录位置互换,重复此过程,直到该排序列中所有关键字都有序为止,接下来介绍交换排序中常见的冒泡排序快速排序

 

▓▓▓▓▓▓ 冒泡排序

  冒泡排序的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端,故名

  冒泡排序算法的运作如下:(从后往前)
  1、比较相邻的元素。如果第一个比第二个大,就交换他们两个。
    2、对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。
  3、针对所有的元素重复以上的步骤,除了最后一个。
  4、持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

  冒泡排序的时间复杂度是 O(n^2)

  代码:

 1         // 冒泡排序
 2         function bubbleSort(arr){
 3 
 4             for(var i=0;i<arr.length;i++){
 5                 for(var j=0;j<arr.length-i-1;j++){
 6                     if(arr[j] > arr[j+1]){
 7                         var arrMax = arr[j+1];
 8                         arr[j+1] = arr[j];
 9                         arr[j] = arrMax;
10                     }
11                 }
12             }
13 
14             return arr;
15         }

 

▓▓▓▓▓▓ 快速排序 

  快速排序(Quicksort)是对冒泡排序的一种改进。
 
  快速排序由C. A. R. Hoare在1962年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数       据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
 
  一趟快速排序的算法是:
  1)设置两个变量i、j,排序开始的时候:i=0,j=N-1;
  2)以第一个数组元素作为关键数据,赋值给key,即key=A[0];
  3)从j开始向前搜索,即由后开始向前搜索(j--),找到第一个小于key的值A[j],将A[j]和A[i]互换;
  4)从i开始向后搜索,即由前开始向后搜索(i++),找到第一个大于key的A[i],将A[i]和A[j]互换;
  5)重复第3、4步,直到i=j; (3,4步中,没找到符合条件的值,即3中A[j]不小于key,4中A[i]不大于key的时候改变j、i的值,使得j=j-1,i=i+1,直至找到为              止。找到符合条件的值,进行交换的时候i, j指针位置不变。另外,i==j这一过程一定正好是i+或j-完成的时候,此时令循环结束)。
 
  快速排序的时间复杂度是O(n*logn)
 
  代码:
 1         // 快速排序
 2         function quickSort(arr){
 3             // 结束递归条件
 4             if(arr.length <= 1){
 5                 return arr;
 6             }
 7 
 8             var left = [];
 9             var right = [];
10             var key = arr[0];
11 
12             // 分组
13             for(var i=1;i<arr.length;i++){
14                 if(arr[i] < key){
15                     left.push(arr[i]);
16                 }else{
17                     right.push(arr[i]);
18                 }
19             }
20 
21             // 递归分组
22             return quickSort(left).concat(key,quickSort(right));
23         }

 

 

▓▓▓▓▓▓ 插入排序

  插入排序的基本思想是:每次将一个待排序的记录,按其关键字大小插入到前面已经排序的序列中的适当位置,直到全部记录插入完成为止,接下来介绍两种常用的插入排序方法:直接插入排序希尔排序

 

▓▓▓▓▓▓ 直接插入排序

  直接插入排序(straight insertion sort)的做法是:
  每次从无序表中取出第一个元素,把它插入到有序表的合适位置,使有序表仍然有序。第一趟比较前两个数,然后把第二个数按大小插入到有序表中; 第二趟把第         三个数据与前两个数从后向前扫描,把第三个数按大小插入到有序表中;依次进行下去,进行了(n-1)趟扫描以后就完成了整个排序过程。
  
  直接插入排序的时间复杂度为技术分享
  
  代码:
 1         // 直接插入排序
 2         function insertSort(arr){
 3             // 默认第一个元素是有序的
 4             for(var i=1;i<arr.length;i++){
 5 
 6                 if(arr[i] < arr[i-1]){
 7                     var guard = arr[i];
 8                     var j = i - 1;
 9                     // 将有序数组扩大一位
10                     arr[i] = arr[j];
11 
12                     //遍历有序组,找到自己的位置
13                     while(j >= 0 && guard < arr[j]){
14                         arr[j+1] = arr[j];
15                         j--;
16                     }
17 
18                     // 插入检查的元素
19                     arr[j+1] = guard;
20                 }
21             }
22             return arr;
23         }

 

▓▓▓▓▓▓ 希尔排序

  希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序,是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因DL.Shell于1959年提出      而得名。  

  希尔排序属于插入类排序,是将整个有序序列分割成若干小的子序列分别进行插入排序。
  排序过程:先取一个正整数d1<n,把所有序号相隔d1的数组元素放一组,组内进行直接插入排序;然后取d2<d1,重复上述分组和排序操作;直至di=1,即所有       记录放进一 个组中排序为止。
 
  希尔排序的时间复杂度为时间复杂度O(n*logn)
 
  代码:
 1         // 希尔排序
 2         function shellSort(arr){
 3             var len = arr.length;
 4             var stepLen = 1;
 5             // 确定首次遍历的步长
 6             while(stepLen < len/3){
 7                 stepLen = 3*stepLen + 1;
 8             }
 9             // 开始遍历
10             while(stepLen >= 1){
11                 for(var i=stepLen;i<len;i++){
12                     for(var j=i;j>=stepLen && arr[j] < arr[j-stepLen];j-=stepLen){
13                         swap(arr,j,j-stepLen);
14                     }
15                 }
16                 stepLen = (stepLen - 1)/3;
17             }
18 
19             return arr;
20         }
21 
22         function swap(arr,i,j){
23             var temp = arr[j];
24             arr[j] = arr[i];
25             arr[i] = temp;
26         }

 

▓▓▓▓▓▓ 选择排序

  选择排序的基本思想是:每一趟排序在n-i+1个带排序记录中选出关键字最小的记录,作为有序序列的第i个记录,直到全部记录排序完毕。常用的排序方法有直接选择排序堆排序(由于js不能很好的体现堆排序的特点就不写了)

  

▓▓▓▓▓▓ 直接选择排序

  基本思想是:第一次从R[0]~R[n-1]中选取最小值,与R[0]交换,第二次从R[1]~R[n-1]中选取最小值,与R[1]交换,....,第i次从R[i-1]~R[n-1]中选取最小值,与R[i-1]交换,.....,第n-1次从R[n-2]~R[n-1]中选取最小值,与R[n-2]交换,总共通过n-1次,得到一个按排序码从小到大排列的有序序列

  直接选择排序的时间复杂度:O(n^2)

  代码:

 1         // 直接选择排序
 2         function straightSelectSort(arr){
 3             // 默认第一个元素是最小的
 4             var min;
 5             var k;
 6             var lArr = [];
 7             for(var i=0;i<arr.length-1;i++){
 8                 min = arr[i];
 9                 k = i;
10                 for(var j=i+1;j<arr.length;j++){
11                     if(arr[j] < min){
12                         min = arr[j];
13                         k = j;
14                     }
15                 }
16                 if(k != i){
17                     arr[k] = arr[i];
18                     arr[i] = min;
19                 }
20             }
21             return arr;
22         }

 

JavaScript实现常用的排序算法