7 thuật toán sắp xếp thường được sử dụng.

7 thuật toán sắp xếp thường được sử dụng

Khi viết các chiến lược, không thể tránh khỏi các tình huống trong mã chương trình đòi hỏi phải sắp xếp dữ liệu, vậy làm thế nào chúng ta có thể thiết kế một chương trình khoa học với chi phí hệ thống tối thiểu (thời gian, tài nguyên hệ thống)?

• 1. Xác định nhanh

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

• 2. Tóm lại và sắp xếp

  Những người khác: Merge sort là một thuật toán sắp xếp hiệu quả được xây dựng dựa trên các hoạt động sắp xếp; thuật toán này là một ứng dụng rất điển hình của phương pháp chia và chinh phục. Các bước: Gọi không gian để 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ữ các chuỗi đã được hợp nhất Thiết lập hai con trỏ, vị trí khởi đầu của hai chuỗi đã được sắp xếp So sánh các phần tử được chỉ ra bởi hai con trỏ, chọn phần tử tương đối nhỏ để đặt vào không gian hợp nhất và di chuyển con trỏ đến vị trí tiếp theo Lặp lại bước 3 cho đến khi một trong các chỉ số đạt đến cuối chuỗi Sao chép trực tiếp tất cả các phần tử còn lại của chuỗi khác vào cuối chuỗi kết hợp Hình thức sắp xếp:

• 3. sắp xếp hàng loạt

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

• 4. Chọn thứ tự

  Những người khác: Chọn sắp xếp (Selection sort) 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 phần tử nhỏ nhất trong chuỗi không sắp xếp, lưu trữ đến vị trí bắt đầu của chuỗi sắp xếp, sau đó, tiếp tục tìm phần tử nhỏ nhất từ các phần tử không sắp xếp còn lại và đặt vào cuối chuỗi sắp xếp. Và tiếp tục như vậy cho đến khi tất cả các phần tử được sắp xếp hoàn tất. Hình thức sắp xếp:

• 5. Xổ bột

  Những người khác: Bubble Sort là một thuật toán sắp xếp đơn giản. Nó truy cập nhiều lần vào các hàng số để sắp xếp, so sánh hai phần tử một lần và thay đổi chúng nếu thứ tự của chúng sai. Công việc tìm kiếm các hàng lặp đi lặp lại cho đến khi không cần phải thay thế nữa, nghĩa là hàng đã được sắp xếp hoàn thành. Các bước: 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 thay hai phần tử đó. Làm tương tự với mỗi cặp các yếu tố lân cận, từ đầu tiên đến cuối cùng. Ở điểm này, các yếu tố cuối cùng sẽ là số lớn nhất. Lặp lại các bước trên cho tất cả các yếu tố, ngoại trừ phần cuối cùng. Tiếp tục lặp lại các bước trên cho từng phần tử càng ít cho đến khi không có cặp số nào cần so sánh. Hình thức sắp xếp:

• 6. Nhập sắp xếp

  Những người khác: 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 sắp xếp, cho dữ liệu không sắp xếp, quét về phía sau trong chuỗi đã sắp xếp, tìm vị trí tương ứng và cài đặt. Các bước: 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 phần tử tiếp theo và quét về phía sau trong chuỗi các 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 vị trí của các phần tử được sắp xếp nhỏ hơn hoặc bằng các phần tử mới Đặt các yếu tố mới vào vị trí đó Lặp lại bước 2 Hình thức sắp xếp: (không có)

• 7. Hill sắp xếp

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

Tôi thường sử dụng cách pha (đơn giản nhất), và bạn?