This is the 7th day of my participation in the August Gwen Challenge.

The sorting

Bubble sort

Average time complexity: O(n^2)


function bubbleSort (arr) {
    if (arr.length <= 1) return arr;
    const n = arr.length;
    for (let i = 0; i < n; i++) {
        let flag = false;

        for (let j = 0; j <= n - i - 1; j++) {
            if (arr[j] > arr[j+1]) {
                / / exchange
                const tmp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = tmp;
                flag = true; }}if(! flag)break;
    }
    return arr;

}

Copy the code

Insertion sort

Time complexity: O(n^2)

How it works: First, we divide the data in the array into two intervals, sorted and unsorted. The initial sorted interval has only one element, the first element of the array. The core idea of insertion algorithm is to take the elements in the unsorted interval, find the appropriate insertion position in the sorted interval, and ensure that the sorted interval data is always in order. This process is repeated until the unsorted interval is empty and the algorithm ends.

Important: Involves the movement of data

Insert sort on linked lists

/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */
/ * * *@param {ListNode} head
 * @return {ListNode}* /
var insertionSortList = function(head) {
    if (head == null) return;
    let dummyHead = new ListNode(0);
    dummyHead.next = head;

    let lastSort = head; // The last element of the new list
    let cur = head.next;

    
    while(cur ! =null) {
        if (cur.val >= lastSort.val) {
            lastSort = lastSort.next;
        } else {
            let prev = dummyHead;
            while (prev.next.val <= cur.val) {
                prev = prev.next;
            }
            lastSort.next = cur.next;
            cur.next = prev.next;
            prev.next = cur;
        }
        cur = lastSort.next;
    }
    return dummyHead.next;
};
Copy the code

Selection sort

Time complexity: O(n^2)

Key points: data location exchange

Selection sort is an unstable sorting algorithm, inferior to bubble sort and insertion sort

Principle: Find the largest (or smallest) in the unsorted sequence and place it at the end of the sorted sequence (if it is empty, place it at the beginning). Repeat the operation until all data has been put into the sorted sequence

Find the unsorted part of the array, find the minimum value, and then, at the end of the sorted array, swap

function selectionSort (arr) {
    if (arr.length <= 1) {returnarr; }const length = arr.length;
    for (let index = 0; index < arr.length - 1; index++) {
        const element = arr[index];
        let minIndex = index;
        // Find the minimum value in the unsorted array
        for (let j = i; j < length; j++) {
            if(arr[minIndex] > arr[j]) { minIndex = j; }}if(i ! == minIndex) {consttmp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = tmp; }}return arr;
}
Copy the code

The resources

Mp.weixin.qq.com/s/N_6vAyZYd…