JavaScript là loại gì?

Trong bài viết này, tôi sẽ đề cập đến một số thuật toán sắp xếp phổ biến trong khoa học máy tính. Các thuật toán sắp xếp rất quan trọng để nghiên cứu vì chúng thường có thể làm giảm độ phức tạp của một vấn đề. Chúng cũng có các ứng dụng trực tiếp trong thuật toán tìm kiếm, thuật toán cơ sở dữ liệu, v.v.

Các thuật toán sắp xếp chúng ta sẽ tìm hiểu về

• Sắp xếp bong bóng
• Sắp xếp lựa chọn
• Sắp xếp chèn
• Hợp nhất Sắp xếp
• Sắp xếp nhanh chóng
• Sắp xếp theo nhóm

Phương pháp trợ giúp để hoán đổi và so sánh

Chúng ta sẽ hoán đổi các phần tử trong mảng rất nhiều, vì vậy hãy bắt đầu bằng cách viết một phương thức trợ giúp có tên là hoán đổi

function swap(arr, a, b) {
    let temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
}

Chúng ta sẽ so sánh các phần tử rất nhiều nên tôi nghĩ viết một hàm cho mục đích đó là một ý kiến ​​hay

const Compare = {
    LESS_THAN: -1,
    BIGGER_THAN: 1
};

function defaultCompare(a, b) {
    if (a === b) {
        return 0;
    }
    return a < b ? Compare.LESS_THAN : Compare.BIGGER_THAN;
}

Được rồi, bây giờ điều đó đã được giải quyết, hãy chuyển sang phân loại

Tốt. O(N), tệ nhất. O(N^2)

Sắp xếp bong bóng là một điểm khởi đầu tốt vì đây là một trong những thuật toán sắp xếp đơn giản nhất. Nó chủ yếu chỉ tốt cho mục đích giảng dạy vì nó là một trong những thuật toán sắp xếp chậm nhất

Nói tóm lại, thuật toán sắp xếp bong bóng so sánh hai giá trị liền kề và hoán đổi chúng nếu giá trị thứ nhất lớn hơn giá trị thứ hai. Điều này phản ánh tên của nó vì các giá trị có xu hướng di chuyển lên theo đúng thứ tự, giống như bong bóng nổi lên trên bề mặt

function bubbleSort(arr, compare = defaultCompare) {
    const { length } = arr;
    for (let i = 0; i < length; i++) {
        for (let j = 0; j < length - 1 - i; j++) { // refer to note below
            if (compare(arr[j], arr[j + 1]) === Compare.BIGGER_THAN) {
                swap(arr, j, j + 1);
            }
        }
    }
    return arr;
}

Lưu ý rằng giải pháp mà tôi cung cấp là một phiên bản cải tiến một chút của thuật toán sắp xếp bong bóng thông thường vì chúng tôi đang trừ đi số lượt đi từ vòng lặp bên trong để tránh những so sánh không cần thiết. Để hiểu rõ hơn về những gì đang thực sự xảy ra, đây là một sơ đồ với một ví dụ

Tệ nhất. O(N^2)

Ý tưởng cơ bản đằng sau thuật toán sắp xếp lựa chọn là tìm giá trị nhỏ nhất trong cấu trúc dữ liệu, đặt nó ở vị trí đầu tiên, tìm giá trị nhỏ nhất thứ hai, đặt nó ở vị trí thứ hai, v.v.

function selectionSort(arr, compare = defaultCompare) {
    const { length } = arr;
    let minIndex;
    for (let i = 0; i < length - 1; i++) {
        minIndex = i;
        for (let j = i; j < length; j++) {
            if (compare(arr[minIndex], arr[j]) === Compare.BIGGER_THAN) {
                minIndex = j;
            }
        }
        if (i !== minIndex) {
            swap(arr, i, minIndex);
        }
    }
    return arr;
}

Sơ đồ sau hoạt động như một ví dụ về thuật toán sắp xếp lựa chọn đang hoạt động

Tốt. O(N), tệ nhất. O(N^2)

Thuật toán sắp xếp chèn xây dựng mảng được sắp xếp cuối cùng một giá trị tại một thời điểm. Quá trình trông giống như thế này

1. Giả sử phần tử đầu tiên đã được sắp xếp
2. So sánh phần tử thứ nhất và phần tử thứ hai - giá trị thứ hai nên giữ nguyên vị trí của nó hay được chèn vào trước giá trị đầu tiên?
3. Tiếp theo, bạn có thể thực hiện phép so sánh tương tự với giá trị thứ ba - nó nên được chèn vào vị trí thứ nhất, thứ hai hay thứ ba?

function insertionSort(arr, compare = defaultCompare) {
    const { length } = arr;
    let temp;
    for (let i = 1; i < length; i++) {
        let j = i;
        temp = arr[i];
        while (j > 0 && compare(arr[j - 1], temp) === Compare.BIGGER_THAN) {
            arr[j] = arr[j - 1];
            j--;
        }
        arr[j] = temp;
    }
    return arr;
}

Tham khảo sơ đồ này để biết ví dụ về sắp xếp chèn trong hành động

Mặc dù vậy, thuật toán sắp xếp chèn có hiệu suất tốt hơn so với thuật toán sắp xếp lựa chọn và sắp xếp bong bóng khi sắp xếp lại các mảng nhỏ, tôi thực sự không khuyên bạn nên sử dụng nó ngoài mục đích giáo dục

Tệ nhất. O(N Nhật ký N)

Thuật toán sắp xếp hợp nhất là thuật toán chia để trị. Nói cách khác, nó chia mảng ban đầu thành các mảng nhỏ hơn cho đến khi mỗi mảng nhỏ chỉ có một vị trí, sau đó nó hợp nhất các mảng nhỏ hơn thành một mảng lớn hơn được sắp xếp

Việc triển khai ở đây là đệ quy và bao gồm hai hàm, một để chia mảng thành các mảng nhỏ hơn và một để thực hiện sắp xếp

function mergeSort(arr, compare = defaultCompare) {
    if (arr.length > 1) {
        const { length } = arr;
        const middle = Math.floor(length / 2);
        const left = mergeSort(arr.slice(0, middle), compare);
        const right = mergeSort(arr.slice(middle, length), compare);
        arr = merge(left, right, compare);
    }
    return arr;
}

function merge(left, right, compare) {
    let i = 0;
    let j = 0;
    const result = [];
    while (i < left.length && j < right.length) {
        result.push(compare(left[i], right[j]) === Compare.LESS_THAN ? left[i++] : right[j++]);
    }
    return result.concat(i < left.length ? left.slice(i) : right.slice(j));
}

Đây là một sơ đồ để hình dung quá trình

Tốt nhất/Trung bình. O(N Log N), Xấu nhất. O(N^2)

Thuật toán sắp xếp nhanh là một trong những thuật toán sắp xếp được sử dụng nhiều nhất. Tương tự như sắp xếp hợp nhất, sắp xếp nhanh cũng sử dụng phương pháp chia để trị. Hãy chia nhỏ quy trình thành các bước để hiểu rõ hơn một chút vì nó phức tạp hơn một chút so với các loại trước đây mà chúng tôi đã đề cập

1. Chọn một giá trị từ mảng mà chúng ta sẽ gọi là trục, thường là giá trị ở giữa mảng
2. Thực hiện thao tác phân vùng sẽ dẫn đến một mảng có giá trị nhỏ hơn trục ở bên trái và lớn hơn ở bên phải
3. Lặp lại hai bước đầu tiên cho mỗi mảng con (trái và phải) cho đến khi các mảng được sắp xếp hoàn toàn

function quickSort(arr, compare = defaultCompare) {
    return quick(arr, 0, arr.length - 1, compare);
}

function quick(arr, left, right, compare) {
    let i;
    if (arr.length > 1) {
        i = partition(arr, left, right, compare);
        if (left < i - 1) {
            quick(arr, left, i - 1, compare);
        }
        if (i < right) {
            quick(arr, i, right, compare);
        }
    }
    return arr;
}

function partition(arr, left, right, compare) {
    const pivot = arr[Math.floor((right, left) / 2)];
    let i = left;
    let j = right;

    while (i <= j) {
        while (compare(arr[i], pivot) === Compare.LESS_THAN) {
            i++;
        }
        while (compare(arr[j], pivot) === Compare.BIGGER_THAN) {
            j--;
        }
        if (i <= j) {
            swap(arr, i, j);
            i++;
            j--;
        }
    }
    return i;
}

Tốt nhất/Trung bình. O(N + k), Xấu nhất. O(N^2)

Thuật toán sắp xếp nhóm là một thuật toán sắp xếp phân tán, tách các phần tử thành các nhóm khác nhau hoặc các mảng nhỏ hơn, sau đó sử dụng thuật toán sắp xếp đơn giản hơn phù hợp để sắp xếp các mảng nhỏ, chẳng hạn như sắp xếp chèn, để sắp xếp từng nhóm

function bucketSort(arr, bucketSize) {
    if (arr.length < 2) {
        return arr;
    }
    // create buckets and distribute the elements
    const buckets = createBuckets(arr, bucketSize);
    // sort the buckets using insertion sort and add all bucket elements to sorted result 
    return sortBuckets(buckets);
}

function createBuckets(arr, bucketSize) {
    // determine the bucket count
    let min = arr[0];
    let max = arr[0];
    for (let i = 1; i < arr.length; i++) {
        if (arr[i] < min) {
            min = arr[i];
        } else if (arr[i] > max) {
            max = arr[i];
        }
    }
    const bucketCount = Math.floor((max - min) / bucketSize) + 1;

    // initialize each bucket (a multidimensional array)
    const buckets = [];
    for (let i = 0; i < bucketCount; i++) {
        buckets[i] = [];
    }

    // distribute elements into buckets
    for (let i = 0; i < arr.length; i++) {
        const bucketIndex = Math.floor((arr[i] - min) / bucketSize);
        buckets[bucketIndex].push(arr[i]);
    }
    return buckets;
}

function sortBuckets(buckets) {
    const sortedArr = [];
    for (let i = 0; i < buckets.length; i++) {
        if (buckets[i] != null) {
            insertionSort(buckets[i]); // quick sort is another good option
            sortedArr.push(...buckets[i]);
        }
    }
    return sortedArr;
}

Lưu ý rằng sắp xếp nhóm hoạt động tốt nhất khi các phần tử có thể được phân phối đồng đều vào các nhóm. Nếu các phần tử phần lớn thưa thớt, thì sử dụng nhiều nhóm hơn sẽ tốt hơn và ngược lại

Sơ đồ sau đây minh họa thuật toán sắp xếp nhóm đang hoạt động

Chúng tôi đã đề cập đến một số thuật toán sắp xếp phổ biến nhất. Còn rất nhiều thuật toán sắp xếp nữa mà mình chưa nói hết trong bài viết này, nếu bạn muốn mình viết tiếp phần 2 thì hãy cho mình biết nhé. Dù bằng cách nào, tôi dự định sẽ sớm viết về các thuật toán tìm kiếm, vì vậy hãy chú ý theo dõi

Sắp xếp JavaScript có phải là sắp xếp bong bóng không?

JavaScript có sắp xếp QuickSort không?

Loại sắp xếp nào là sắp xếp mảng JavaScript?

Sắp xếp JavaScript là đồng bộ hay không đồng bộ?