[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 1 năm 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 1 năm trước
2 0
Bài viết liên quan
White
70 8
Tăng sức mạnh cho javascript với lodash Lần này mình sẽ giới thiệu 1 thư viện javascript vô cùng bá đạo có tên là "lodash]1]", có thể nói nó là LI...
Huy Hoàng Phạm viết gần 5 năm trước
70 8
White
10 1
_Có mấy chia sẻ nhỏ, mình muốn đưa ra để mọi người cùng thảo luận góp ý. Thread này không tập trung vào Technical nữa mà discuss về Coding Style & ...
Hùng Phong viết gần 2 năm trước
10 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á!