欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

学习JavaScript算法之常用的排序算法讲解

程序员文章站 2022-07-05 17:26:06
学习常用的排序算法 一、冒泡排序 优点: 所有排序中最简单的,易于理解; 缺点: 时间复杂度o(n^2),平均来说是最差的一种排序方式; 因为在默认情况下,对于已经排好序的部分,此排序任然会进行比较...

学习常用的排序算法

一、冒泡排序

优点:

所有排序中最简单的,易于理解;

缺点:

时间复杂度o(n^2),平均来说是最差的一种排序方式;

因为在默认情况下,对于已经排好序的部分,此排序任然会进行比较(当然可以进行改进优化)

算法步骤:

比较相邻的元素,如果第一个比第二个大,就交换他们两个。

对每一对相邻元素作同样的工作,从开始第一对一直到结尾的最后一对,如此将最大的数放在后面。

对所有的元素重复以上的步骤,除了最后一个。

持续每次对元素重复上面的步骤,直到排序完成。

原理分析:

通过比较两个相邻的项,(由大到小排序)如果第一个比的二个大,则交换它们的位置元素项向上移动至正确的顺序,就好像气泡升至表面,冒泡也因此得名。

const bubblesort = (arr) => {
    const length= arr.length;
    for (let i = 0; i arr[j+1]){
                let swap = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = swap;
            }
        }
    }
}

改进优化:

默认上述代码,对于第一轮之后的循环任然会进行和全部元素的比较,但其实之前的循环已经将器排序正确了,所以可以从内循环中减去外循环已经进行过的轮数,从而避免不必要的比较

const bubblesort = (arr) => {
        const length= arr.length;
        for (let i = 0; i arr[j+1]){
                    let swap = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = swap;
                }
            }
        }
    }

学习JavaScript算法之常用的排序算法讲解

二、选择排序

原理:

进行原地址比较,找到数据结构中最小值并放在第一位,接着在剩下的中找到第二个最小值放在第二位,依次类推;

代码实现:

function selectionsort(arr) {
    var length= arr.length;
    var minindex;
    for (var i = 0; i < length - 1; i++) {
        minindex = i;
        for (var j = i + 1; j < length; j++) {
            if (arr[j] < arr[minindex]) {     // 寻找最小的数
                minindex = j;                 // 将最小数的索引保存
            }
        }
        if(i != minindex){
            var temp = arr[i];
            arr[i] = arr[minindex];
            arr[minindex] = temp;  
        }
        
    }
    return arr;
}

学习JavaScript算法之常用的排序算法讲解

三、插入排序

原理:

通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。

排序步骤:

将第一待排序序列第一个元素看做一个有序序列,把第二个元素到最后一个元素当成是未排序序。

从头到尾依次扫描未排序序列,将扫描到的每个元素插入有序序列的适当位置。(如果待插入的元素与有序序列中的某个元素相等,则将待插入元素插入到相等元素的后面。)

代码实现

function insertionsort(arr) {
    var len = arr.length;
    var preindex, current;
    for (var i = 1; i < len; i++) {
        preindex = i - 1;
        current = arr[i];
        while(preindex >= 0 && arr[preindex] > current) {
            arr[preindex+1] = arr[preindex];
            preindex--;
        }
        arr[preindex+1] = current;
    }
    return arr;
}

原理图

学习JavaScript算法之常用的排序算法讲解

四、归并排序

原理:

归并是一种分治算法,即将原始数组切分成较小的数组,直到每个小数组只有一个位置,接着将小数组归并成较大的数组,每次归并时进行排序,直到最后只有一个排序完毕的大数组。

代码实现(递归):

function mergesort(arr) {  // 采用自上而下的递归方法,数组拆分
    var len = arr.length;
    if(len < 2) {
        return arr;
    }
    var middle = math.floor(len / 2),
        left = arr.slice(0, middle),
        right = arr.slice(middle);
    return merge(mergesort(left), mergesort(right));
}
//合并数组,并进行排序
function merge(left, right)
{
    var result = [];

    while (left.length && right.length) {
        if (left[0] <= right[0]) {
            result.push(left.shift());
        } else {
            result.push(right.shift());
        }
    }

    while (left.length)
        result.push(left.shift());

    while (right.length)
        result.push(right.shift());

    return result;
}

原理图

学习JavaScript算法之常用的排序算法讲解

五、快速排序

原理:

快速排序使用分治法(divide and conquer)策略来把一个串行(list)分为两个子串行(sub-lists)。

排序步骤:

首先,从数组中选择中间一项作基数;

然后,创建两个指针,左边一个指向数组的第一项,右边一个指向数组的最后一项;

移动左指针直到找到一个比基数大的元素,移动右指针,直到找到一个比基数小的元素;然后交换它们;

重复以上步骤,直到左指针超过了右指针;(这个过程将使得比基数小的树都在基数的前面,较大的数都在基数的后面)

最后,对划分后的小数组(比基数小的值组成的子数组,以及比基数大的值组成是子数组)重复之前的两个步骤,直到数组已经完全排序。

代码实现

function quicksort(arr, left, right) {
    var len = arr.length,
        partitionindex,
        left = typeof left != 'number' ? 0 : left,
        right = typeof right != 'number' ? len - 1 : right;

    if (left < right) {
        partitionindex = partition(arr, left, right);
        quicksort(arr, left, partitionindex-1);
        quicksort(arr, partitionindex+1, right);
    }
    return arr;
}

function partition(arr, left ,right) {     // 分区操作
    var pivot = left,                      // 设定基准值(pivot)
        index = pivot + 1;
    for (var i = index; i <= right; i++) {
        if (arr[i] < arr[pivot]) {
            swap(arr, i, index);
            index++;
        }        
    }
    swap(arr, pivot, index - 1);
    return index-1;
}

function swap(arr, i, j) {
    var temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}
function partition2(arr, low, high) {
  let pivot = arr[low];
  while (low < high) {
    while (low < high && arr[high] > pivot) {
      --high;
    }
    arr[low] = arr[high];
    while (low < high && arr[low] <= pivot) {
      ++low;
    }
    arr[high] = arr[low];
  }
  arr[low] = pivot;
  return low;
}

function quicksort2(arr, low, high) {
  if (low < high) {
    let pivot = partition2(arr, low, high);
    quicksort2(arr, low, pivot - 1);
    quicksort2(arr, pivot + 1, high);
  }
  return arr;
}

原理图

学习JavaScript算法之常用的排序算法讲解