7 thuật toán sắp xếp phổ biến

Khi viết chiến lược, mã của chương trình sẽ gặp phải những tình huống cần sắp xếp dữ liệu, vậy làm thế nào chúng ta có thể thiết kế chương trình khoa học với chi phí hệ thống ít nhất (thời gian, tài nguyên hệ thống)?

• ### 1. Sắp xếp nhanh

Hình ảnh: Lưu trữ nhanh là một thuật toán sắp xếp được phát triển bởi Tony Hall. Trong trường hợp trung bình, sắp xếp n dự án cần O (n log n) lần so sánh. Trong trường hợp xấu nhất, cần O (n) lần so sánh, nhưng điều này không phổ biến. Trong thực tế, lưu trữ nhanh thường nhanh hơn nhiều so với các thuật toán khác, vì vòng lặp nội bộ của nó có thể được thực hiện trên hầu hết các cấu trúc một cách hiệu quả và trên hầu hết dữ liệu trong thế giới thực, có thể quyết định lựa chọn thiết kế, giảm khả năng của các yếu tố thứ hai cần thiết. Bước 3: Một phần tử được chọn từ hàng, được gọi là pivot (pivot) Sắp xếp lại số lượng, tất cả các phần tử nhỏ hơn so với giá trị chuẩn được đặt ở phía trước của chuẩn, tất cả các phần tử lớn hơn so với giá trị chuẩn được đặt ở phía sau của chuẩn ((tương đương số lượng có thể đi đến bất kỳ bên nào)). Sau khi thoát khỏi phân vùng này, chuẩn nằm ở vị trí trung tâm của số lượng. Điều này được gọi là phân vùng ((partition) hoạt động. Trình thu hồi ((recursive) sắp xếp các tiểu số nhỏ hơn các phần tử chuẩn và các tiểu số lớn hơn các phần tử chuẩn. Hiệu ứng sắp xếp:

• ### 2. Phân tích và sắp xếp

Hình ảnh: Phân loại kết hợp (tiếng Anh: Merge sort) là một thuật toán sắp xếp hiệu quả dựa trên hoạt động kết hợp. Đây là một ứng dụng điển hình của phương pháp phân chia và chinh phục. Bước 3: Không gian yêu cầu, làm cho nó có kích thước là tổng của hai chuỗi đã được sắp xếp, không gian này được sử dụng để lưu trữ chuỗi đã được hợp nhất Thiết lập hai con trỏ với vị trí ban đầu là hai vị trí ban đầu của chuỗi đã được sắp xếp So sánh hai phần tử mà con trỏ chỉ, chọn phần tử tương đối nhỏ để đưa vào không gian kết hợp và di chuyển con trỏ đến vị trí tiếp theo Lặp lại bước 3 cho đến khi một con trỏ đến cuối chuỗi Sao chép tất cả các phần tử còn lại của chuỗi khác trực tiếp vào cuối chuỗi kết hợp Hiệu ứng sắp xếp:

• ### 3. Sắp xếp

Hình ảnh: Heapsort là một loại thuật toán sắp xếp được thiết kế sử dụng cấu trúc dữ liệu như Heapsort. Heapsort là một cấu trúc gần như là cây nhị phân hoàn toàn, đồng thời đáp ứng tính chất của Heapsort: giá trị khóa hoặc chỉ mục của các node con luôn nhỏ hơn hoặc lớn hơn các node cha của nó. Bước 3: (Thật phức tạp, hãy tự tìm kiếm trên mạng) Hiệu ứng sắp xếp:

• ### 4. Lựa chọn thứ tự

Hình ảnh: Sort chọn là một thuật toán sắp xếp đơn giản và trực quan. Nó hoạt động như sau. Đầu tiên, tìm kiếm các phần tử nhỏ nhất trong chuỗi không được sắp xếp, lưu trữ đến vị trí bắt đầu của chuỗi, sau đó tìm kiếm các phần tử nhỏ nhất trong số các phần tử còn lại, và sau đó đặt vào cuối chuỗi. Hiệu ứng sắp xếp:

• ### 5. Sắp xếp hình bọt

Hình ảnh: Bubble Sort là một thuật toán sắp xếp đơn giản. Nó lặp đi lặp lại các số đã được sắp xếp, so sánh hai phần tử một lần và trao đổi chúng nếu thứ tự của chúng sai. Việc truy cập vào hàng là lặp đi lặp lại cho đến khi không còn cần trao đổi, nghĩa là hàng đã được sắp xếp. Tên của thuật toán này xuất phát từ việc các phần tử nhỏ hơn sẽ được trao đổi và dần dần trôi dạt lên đỉnh hàng. Bước 3: So sánh các phần tử lân cận. Nếu phần tử đầu tiên lớn hơn phần tử thứ hai, hãy trao đổi hai phần tử đó. Làm tương tự cho mỗi cặp các phần tử lân cận, bắt đầu từ cặp đầu tiên cho đến cặp cuối cùng. Tại thời điểm này, phần tử cuối cùng sẽ là số lượng lớn nhất. Lặp lại các bước trên cho tất cả các phần tử, ngoại trừ phần cuối. Tiếp tục lặp lại các bước trên cho các phần tử ít hơn và ít hơn, cho đến khi không có bất kỳ cặp số nào cần được so sánh. Hiệu ứng sắp xếp:

• ### 6. Chèn thứ tự

Hình ảnh: Insertion Sort là một thuật toán sắp xếp đơn giản và trực quan. Nó hoạt động bằng cách xây dựng một chuỗi có trình tự, quét từ phía sau về phía trước trong chuỗi được sắp xếp, tìm vị trí tương ứng và chèn. Sort chèn thường được thực hiện bằng cách sắp xếp in-place (tức là chỉ cần sử dụng O (1) không gian thêm), do đó trong quá trình quét từ phía sau về phía trước, cần phải di chuyển các phần tử đã được sắp xếp từng bước về phía sau, để cung cấp không gian chèn cho các phần tử mới nhất. Bước 3: Bắt đầu từ phần tử đầu tiên, phần tử này có thể được coi là đã được sắp xếp Lấy một phần tử, quét từ phía sau về phía trước trong chuỗi phần tử đã được sắp xếp Nếu phần tử ((đã được sắp xếp) lớn hơn phần tử mới, di chuyển phần tử đó đến vị trí tiếp theo Lặp lại bước 3 cho đến khi tìm thấy các yếu tố được sắp xếp nhỏ hơn hoặc bằng các yếu tố mới Chèn các phần tử mới vào vị trí Lặp lại bước 2 Hiệu ứng sắp xếp: (Không có)

• ### 7. Phong cách của Hill

Hình ảnh: Phân loại Hill, còn được gọi là thuật toán phân loại gia tăng giảm, là một phiên bản cải tiến nhanh và ổn định của phân loại chèn. Phong cách sắp xếp của Hill được đề xuất dựa trên hai đặc tính sau của sắp xếp nhúng: 1, sắp xếp nhúng có hiệu quả cao khi xử lý dữ liệu gần như đã được sắp xếp, tức là có thể đạt được hiệu quả sắp xếp tuyến tính 2/ Tuy nhiên, chèn phân loại thường kém hiệu quả, vì mỗi lần chèn phân loại chỉ có thể di chuyển dữ liệu một người.

Tôi thường sử dụng phương pháp phun nước (đơn giản nhất), còn bạn thì sao?