数组几种排序方式

2021年4月29日 20点热度 0人点赞 0条评论

在数据结构算法中常见和不常见的排序方式,可分为比较类排序和非比较类排序:

比较类排序,通过比较来决定元素之间的相对次序,它的时间复杂度不能突破O(nlogn),也称之为非线性时间比较类排序。非比较类排序则与之相反。

比较类排序

  1. 冒泡排序
  2. 快速排序
  3. 插入排序
  4. 普通选择排序
  5. 堆排序
  6. 归并排序

非比较类排序

  1. 计数排序
  2. 桶排序
  3. 基数排序

冒泡排序

使用某种规则来比较两个元素,当顺序出错时,就交换两个元素的位置。一直遍历数列,直到不再需要交换元素,也就是该数列已经排序结束了。

/*
 * @fileName: 冒牌排序
 * @Author: duxinyue
 * @Date: 2021-04-28 16:41:00
 * @LastEditors: duxinyue
 * @LastEditTime: 2021-04-28 17:38:58
 * @FilePath: \JavaScript\js\bubbleSort.js
 */
import {arr} from "./array-data.js";
function bubbleSort(array) {
    console.log("排序之前的",array)
    const len = array.length;
    if (len < 1) return array;
    for (let index = 0; index < len; index++) {
       for (let key = 0; key < index; key++) {
          if(array[key]>array[index]){
              const temp = array[key];
              array[key] = array[index];
              array[index] = temp
          } 
       }
    }
console.log("排序后的数列=",array)  
}
bubbleSort(arr);

快速排序

快速排序,走的是一次排序:原理就是把待排序的数列分成两个独立的部分。其中一部分记录的是元素都比另一个部分元素小。在分别对这两部分记录继续进行排序,以到达整个数列有序。

/*
 * @fileName: 快速排序
 * @Author: duxinyue
 * @Date: 2021-04-28 17:47:13
 * @LastEditors: duxinyue
 * @LastEditTime: 2021-04-29 09:09:59
 * @FilePath: \JavaScript\algorithm\quickSort.js
 */

import {
    arr
} from "../js/array-data.js"

function quickSort(arr) {
    const quick = function (arr) {
        const len = arr.length;
        if (len <= 1) return arr;
        const index = Math.floor(len >> 1);
        const pivot = arr.splice(index, 1)[0];
        const left = [];
        const right = [];
        for (let i = 0; i <len; i++) {
            if(arr[i]>pivot){
                right.push(arr[i])
            }            
            if(arr[i]<= pivot){
                left.push(arr[i])
            }
        }
        return  quick(left).concat([pivot],quick(right));
    }

    const result = quick(arr);
    console.log(result)
    return result;
}

quickSort(arr)

插入排序

原理:构建一个有序的数列,对没有排序的数列,在已排序的数列中从后往前扫描,找到对应的位置插入,从而到达排序的效果。

/*
 * @fileName: 插入排序
 * @Author: duxinyue
 * @Date: 2021-04-29 09:35:50
 * @LastEditors: duxinyue
 * @LastEditTime: 2021-04-29 09:55:29
 * @FilePath: \JavaScript\algorithm\insertSort.js
 */

import {
    arr
} from "../js/array-data.js"

function insertSort(arr) {
    const len = arr.length;
    let current, prev;
    for (let index = 1; index < len; index++) {
        current = arr[index];
        prev = index - 1;

        while (prev >= 0 && arr[prev] > current) {
            arr[prev + 1] = arr[prev];
            prev--;
        }
        arr[prev + 1] = current
    }
    console.log("排序后的数组==", arr)
    return arr
}

insertSort(arr)

选择排序

原理:将最小的元素放在序列首位,再从未排序的元素中查找最小元素,放在已排序的元素后面,一直到所有元素排序结束,默认数组首位是最小元素。在用到选择排序的时候,数据规模越小越好。

/*
 * @fileName: 选择排序
 * @Author: duxinyue
 * @Date: 2021-04-29 10:00:20
 * @LastEditors: duxinyue
 * @LastEditTime: 2021-04-29 10:07:34
 * @FilePath: \JavaScript\algorithm\selectSort.js
 */

import {
    arr
} from "../js/array-data.js"

function selectSort(arr) {
    const len = arr.length;
    let temp, minIndex;

    for (let i = 0; i < len - 1; i++) {
        minIndex = i;
        for (let index = i + 1; index < len; index++) {
            if (arr[index] <= arr[minIndex]) {
                minIndex = index
            }
        }

        temp =  arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
    console.log("排序后的数组",arr)
    return  arr
}


selectSort(arr)

堆排序

堆,是完全二叉树,若父节点序号为n,那么叶子节点的序号分别是2n和2n+1。

堆排序就是就是在排序前先建立堆。

子节点键值或者索引总是小于(或者大于)它的父节点。

根节点最大的堆叫做大根堆,根节点最小的堆叫做小根堆,可以根据从大到小或者从小到大来排序,分别建立对应的堆。

/*
 * @fileName: 堆排序
 * @Author: duxinyue
 * @Date: 2021-04-29 10:59:49
 * @LastEditors: duxinyue
 * @LastEditTime: 2021-04-29 11:20:37
 * @FilePath: \JavaScript\algorithm\heapSort.js
 */

import {
    arr
} from "../js/array-data.js"

function heapSort(arr) {
    const len = arr.length;
    const k = 0;

    function swap(i, j) {
        const temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    function max_heapify(start, end) {
        const dad = start;
        let son = dad * 2 + 1;
        if (son >= end) return;
        if (son + 1 < end && arr[son] < arr[son + 1]) {
            son++
        };
        if (arr[dad] <= arr[son]) {
            swap(dad, son);
            max_heapify(son, end);
        }
    }

    for (let index = Math.floor(len / 2) - 1; index >= 0; index--) {
        max_heapify(index, len);
    }

    for (let index = len - 1; index > k; index--) {
        swap(0, index);
        max_heapify(0, index)
    }


    console.log("排序后的数组", arr);
    return arr;
}
heapSort(arr)

归并排序

分治法,

/*
 * @fileName:归并排序
 * @Author: duxinyue
 * @Date: 2021-04-29 11:35:40
 * @LastEditors: duxinyue
 * @LastEditTime: 2021-04-29 11:49:15
 * @FilePath: \JavaScript\algorithm\mergeSort.js
 */

import {
    arr
} from "../js/array-data.js";

function mergeSort(arr) {
    console.log("排序前的数组", arr)
    const merge = (left, right) => {
        const result = [];
        let il = 0;
        let ir = 0;
        while (il < left.length && ir < right.length) {
            if (left[il] < right[ir]) {
                result.push(left[il++])
            } else {
                result.push(right[ir++])
            }
        }

        while (il < left.length) {
            result.push(left[il++])
        }

        while (ir < right.length) {
            result.push(right[ir++])
        }

        return result;
    }
    const mergeSort = (arr) => {
        if (arr.length == 1) return arr;
        const mid = Math.floor(arr.length / 2);
        const left = arr.slice(0, mid);
        const right = arr.slice(mid, arr.length);

        return merge(mergeSort(left), mergeSort(right))
    }
    console.log("排序后的数组", mergeSort(arr))
    return mergeSort(arr)
}

mergeSort(arr);

 

读心悦

读心,读自己!

文章评论