JavaScript排序算法

2021/7/21 22:22:06

本文主要是介绍JavaScript排序算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

冒泡排序

 原理:假设排序顺序为增序,数组长度为 N。数组每相邻两个元素进行比较,大数后移,小数前移,第一轮排序下来就能找到最大的数。也就是比较 A[i] 和 A[i+1] ,将大数后移,随后增加 i 的值,再进行比较。第二轮再对剩余的 N-1 个数进行排序,找出第二大的数,以此类推。同时也可以记录交换次数来进行优化,如果在一层循环之中交换次数为 0,则排序结束。

function bubbleSort(arr){  
    var len = arr.length;  
    for (var i = 0; i < len; i++) {  
        for(var j = 0; j < len - i -1; j++){  
            if(arr[j]>arr[j+1]){  //相邻元素进行对比  
                var temp = arr[j+1];//交换元素  
                arr[j+1] = arr[j];  
                arr[j] = temp;  
            }  
        }  
    }  
    return arr;//返回数组  
}  
  
var arr=[1,45,37,5,48,15,37,26,29,2,46,4,17,50,52];//调用排序算法  
console.log(bubbleSort(arr));//控制台输出结果

选择排序

选择排序算法与冒泡排序算法类似,即每一轮找出一个最大值。但和冒泡排序不同的一点是,冒泡排序是采用不停的交换将最大值(最小值)筛选出来,而选择排序是记录下最大值(最小值)的索引。

  原理:假设排序方式为增序,数组长度为 N。设置最大值索引初始值 index = 0,然后遍历数组,记录下最大值的索引,即比较 A[i] 与 A[index] 的值,若 A[i] > A[index] 则更新 index = i。在每一轮遍历结束后,交换 index 位置和末尾位置的值,即交换 A[index] 和 A[i],这样便保证了末尾值是最大值。随后对剩余的 N-1 个数进行同样的方式排序,以此类推。  

 

 function selectSort (arr) {
      for(var i = 0, length1 = arr.length; i < length1; i ++){
         var index = 0
          for(var j = 0, length2 = length1 - i; j < length2; j ++){
              if(arr[j] > arr[index]){
                  index = j;
             }
         }
         var temp = arr[index];
        arr[index] = arr[length1 - i - 1];
         arr[length1 - i - 1] = temp;
    }
return arr;
}
var arr=[1,45,37,5,48,15,37,26,29,2,46,4,17,50,52];//调用排序算法console.log(bubbleSort(arr));//控制台输出结果

 

插入排序

插入排序的思想是将原始数组划分成两侧,一侧是有序数组,一侧是无序数组。每次取出无序数组的一个元素,将它插入到有序数组的正确位置上,这种方式也会导致有序数组中其插入位置之后的元素全部后移。插入排序的思想类似于我们抓扑克牌。

  原理:假设排序方式为增序,数组长度为 N。初始设 A[0] 为有序数组,A[1] ~ A[N-1] 为无序数组,取出 A[1] 将其插入至有序数组中的正确位置,使得有序数组增大为 A[0] ~ A[1]。继续取 A[2] 将其插入至有序表数组的正确位置,以此类推,直至无序数组取完。

function insertSort (arr) {
 2     for(var i = 0, length1 = arr.length; i < length1; i ++){
 3         for(var j = 0, length2 = i + 1; j < length2; j ++){
 4             if(arr[j] > arr[length2]){
 5                 var temp = arr[length2];
 6                 for(var k = length2; k > j; k --){
 7                     arr[k] = arr[k-1];
 8                 }
 9                 arr[j] = temp;
10             }
11         }
12     }
13 }

快速排序

 快速排序同样也使用了分治法的思想,在实际运用中使用的最多的就是快速排序。快速排序的核心思想是运用递归法,在每轮排序时指定一个基数,将基数移动到正确的位置上,然后再把基数的左右两边拆分出来,并分别进行相同的排序处理,直到其子数组长度为 1。其采用的是自顶向下的处理法。

  原理:在每一轮排序中取一个基数 k , 设 i 和 j 分别为数组的最左端和最右端,i 坐标从起始点向 k 点遍历,若找到一个比 k 大的元素,则停下来等待 j 的遍历。 j 坐标从起始点向 k 点遍历,若找到一个比 k 小的元素,则 i 和 j 坐标的元素互相交换。若有一端提前到达了 k 点,则等待满足条件后与另一端坐标交换。当 i 和 j 碰撞时,则为分治点,此时 i 和 j 相碰撞的坐标元素便是它的最终位置,以碰撞点为中心将数组拆分成两段,并进行相同的递归处理。当 i >= j 时,则为回退点

function quickSort (arr) {
 2     function sort(array, first, last) {
 3         if (first >= last) {
 4             return;
 5         }
 6         var base = Math.floor((first + last) / 2);
 7         var i = first - 1;
 8         var j = last - 1;
 9         var temp;
10         while (j > i) {
11             while (j > i && array[j] > array[base]) {
12                 j--;
13             }
14             while (i < j && array[i] <= array[base]) {
15                 i++;
16             }
17             temp = array[i];
18             array[i] = array[j];
19             array[j] = temp;
20         }
21         temp = array[base];
22         array[base] = array[i];
23         array[i] = temp;
24         sort(array, first, i);
25         sort(array, i + 2, last)
26     }
27     sort(arr, 1, arr.length);
28 }



这篇关于JavaScript排序算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程