Quảng cáo
2 câu trả lời 990
Thuật toán sắp xếp chọn (Selection Sort) và thuật toán sắp xếp nổi bọt (Bubble Sort) đều là các thuật toán sắp xếp cơ bản, nhưng chúng có một số khác biệt quan trọng:
Phương pháp hoạt động:
Sắp xếp nổi bọt: Bắt đầu từ cuối danh sách, đổi chỗ các cặp phần tử kế cận để đưa phần tử nhỏ hơn trong cặp phần tử đó về đúng vị trí theo thứ tự tăng dần.
Sắp xếp chọn: So sánh các phần tử để đặt các phần tử nhỏ nhất vào vị trí phía trước.
Độ phức tạp thời gian:
Cả hai thuật toán đều có độ phức tạp thời gian làO()
trong trường hợp xấu nhất và trung bình.
Hiệu suất:
Trong điều kiện tốt nhất, khi danh sách đã được sắp xếp trước, thuật toán sắp xếp nổi bọt có hiệu suất tương đương với các thuật toán sắp xếp khác.
Tuy nhiên, cả hai thuật toán này đều không thích hợp sử dụng với các tập dữ liệu lớn
|
Thuật toán
|
Ý tưởng
|
Cách hoạt động
|
Độ phức tạp thời gian
|
Độ phức tạp không gian
|
|
Sắp xếp chọn
|
Lặp lại việc tìm phần tử nhỏ nhất trong mảng và hoán đổi nó với phần tử đầu tiên
|
Duyệt qua mảng, tìm phần tử nhỏ nhất, hoán đổi nó với phần tử đầu tiên, sau đó tiếp tục duyệt phần còn lại của mảng
|
O(n^2)
|
O(1)
|
|
Sắp xếp nổi bọt
|
Lặp lại việc so sánh các phần tử kề nhau và hoán đổi chúng nếu chúng không đúng thứ tự
|
Lặp lại việc so sánh các phần tử kề nhau và hoán đổi chúng nếu chúng không đúng thứ tự
|
O(n^2)
|
O(1)
|
Quảng cáo
Bạn muốn hỏi bài tập?
Câu hỏi hot cùng chủ đề
-
32834
-
Hỏi từ APP VIETJACK25090
