[Thuật toán]Quick Sort JavaScript

Mô tả

Quick Sort là một thuật toán sắp xếp hiệu quả dựa trên việc phân chia mảng thành các nhóm phần tử nhỏ hơn. Giải thuật sắp xếp nhanh chia mảng thành 2 phần bằng nhau bằng cách so sánh từng phần tử của mảng với một phần tử được gọi là chốt.
Một mảng bao gồm các phần tử nhỏ hơn hoặc bằng chốt và một mảng các phần tử lớn hơn phần tử chốt.
Quá trình phân chia này diễn ra cho đến khi độ dài của các mảng con đều bằng 1. Với phương pháp đệ quy ta có thể sắp xếp nhanh các mảng con sau khi kết thúc chương trình ta được một mảng đã sắp xếp hoàn chỉnh. Giải thuật sắp xếp nhanh tỏ ra khá hiệu quả với các tập dữ liệu lớn khi mà độ phức tạp là O(nlogn).

Ý tưởng thuật toán

1.Chọn một phần tử để so sánh, tôi gọi đây là phần tử Key hoặc Pivot tùy vào mỗi người, từ trong mảng đầu tiên của chúng ta.
2.Sau đó phân vùng và sort mảng con của sau phân vùng của chúng ta làm sao cho các phần tử lớn hơn phần tử Key nằm sau(bên phải) và các phần tử bé hơn phần tử Key nằm trước(bên trái). Đây được gọi là quá trình phân vùng.
3.Cuối cùng là đệ quy sử dụng các bước trên cho các mảng với phần tử bé hơn và phân tách với các phần tử lớn hơn sau khi phân vùng.

Giải thuật (JavaScript)

$(function () {
Array.prototype.quickSort = function () {
var r = this;
if (this.length <= 1) {
return this;
}
var less = [],
greater = [];

    var pivot = r.splice(Math.floor(r.length / 2), 1);

    for (var i = r.length - 1; i >= 0; i--) {
        if (r[i] <= pivot) {
            less.push(r[i]);
        } else {
            greater.push(r[i]);
        }
    }
    var c = [];
    return c.concat(less.quickSort(), pivot, greater.quickSort());
};

}

Bình luận


White
{{ comment.user.name }}
Bỏ hay Hay
{{comment.like_count}}
Male avatar
{{ comment_error }}
Hủy
   

Hiển thị thử

Chỉnh sửa

White

Dần Huỳnh

3 bài viết.
2 người follow
Kipalog
{{userFollowed ? 'Following' : 'Follow'}}
Cùng một tác giả
White
3 0
Chào các bạn, hôm nay mình sẽ giới thiệu tool khá nổi tiếng dùng để tạo ra API document: Swagger UI. Swagger UI là một tool cho phép bất cứ ai cũn...
Dần Huỳnh viết 12 ngày trước
3 0
White
2 0
Tăng dung lượng ổ cứng Box Vagrant Cách tăng dung lượng ổ cứng của box vagrant một cách đơn giản nhất Trước khi khi chạy lệnh vagrant up provisio...
Dần Huỳnh viết 11 ngày trước
2 0
Bài viết liên quan
White
7 0
Gần đây, tôi có đọc được cách sử dụng ba hàm call, apply và bind trong JavaScript. Đọc xong thấy khó hiểu quá nên tôi quyết định viết một bài so sá...
Lam Pham viết hơn 1 năm trước
7 0
White
4 1
Tl;dr lưu ý một chút về cách trình bày: .propname tức là public property có tên là "propname" của một đối tượng Bắt đầu với Object, Function v...
Đức Trung viết hơn 1 năm trước
4 1
{{like_count}}

kipalog

{{ comment_count }}

bình luận

{{liked ? "Đã kipalog" : "Kipalog"}}


White
{{userFollowed ? 'Following' : 'Follow'}}
3 bài viết.
2 người follow

 Đầu mục bài viết

Vẫn còn nữa! x

Kipalog vẫn còn rất nhiều bài viết hay và chủ đề thú vị chờ bạn khám phá!