Quicksort – Algorithm

· Uncategorized

Quicksort is a divide and conquer algorithm. Quicksort first divides a large list into two smaller sub-lists: the low elements and the high elements. Quicksort can then recursively sort the sub-lists.

Sắp xếp nhanh là một thuật toán phân chia và chinh phục (chiến thắng). Sắp xếp nhanh đầu tiên chia một danh sách lớn thành hai danh sách nhỏ hơn: các phần tử thấp và các phần tử cao. Sắp xếp nhanh sau đó có thể sắp xếp đệ quy các danh sách nhỏ hơn.

The steps are:

  1. Pick an element, called a pivot, from the list.
  2. Reorder the list so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation.
  3. Recursively apply the above steps to the sub-list of elements with smaller values and separately the sub-list of elements with greater values.

Chọn một phần tử, được gọi là một chốt (trục, xoay quanh trục), từ danh sách.

Sắp xếp lại danh sách để tất cả các phần tử có giá trị nhỏ hơn chốt đến trước chốt, trong khi tất cả các phần tử có giá trị lớn hơn so với trục đến sau nó (giá trị tương đương có thể đi một trong hai cách). Sau quá trình phân vùng này, chốt ở vị trí cuối cùng của nó. Này được gọi là hành động phân vùng.

The base case of the recursion are lists of size zero or one, which never need to be sorted.

Trường hợp cơ sở của đệ quy là danh sách các kích thước là không hoặc một, mà không bao giờ cần phải được sắp xếp.

 

Gửi phản hồi

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s

%d bloggers like this: