Sắp xếp nổi bọt
Trang này cần trình duyệt gần đây (hỗ trợ SharedArrayBuffer). Vui lòng cập nhật Chrome, Edge, Firefox hoặc Safari lên phiên bản mới nhất.
Sắp xếp sắp xếp các mục theo thứ tự
- Sắp xếp sắp xếp lại một danh sách theo thứ tự — từ nhỏ đến lớn, ví dụ.
- Sắp xếp bong bóng là phương pháp tiêu chuẩn được nêu trong chương trình học.
- Nó so sánh các phần tử kề nhau và hoán đổi bất kỳ cặp nào đang ở vị trí sai.
Hoán đổi hai giá trị
- Để sắp xếp, bạn phải hoán đổi hai mục.
- Python có thể hoán đổi trong một dòng:
a, b = b, a.
English
a = 5
b = 9
a, b = b, a
print(a, b) # 9 5
Sắp xếp bong bóng: so sánh các phần tử kề nhau
- Duyệt qua danh sách, so sánh từng cặp phần tử kề nhau.
- Nếu phần tử bên trái lớn hơn, hãy hoán đổi chúng — phần tử lớn nhất sẽ "nổi" về cuối.
- Lặp lại các lượt duyệt cho đến khi danh sách được sắp xếp hoàn chỉnh.
English
nums = [5, 1, 4, 2]
for i in range(len(nums) - 1):
for j in range(len(nums) - 1 - i):
if nums[j] > nums[j + 1]:
nums[j], nums[j + 1] = nums[j + 1], nums[j]
print(nums) # [1, 2, 4, 5]
Trong bài thi: sắp xếp bong bóng
- Bài thi viết sắp xếp bong bóng dưới dạng giả mã với vòng lặp lồng nhau và phép hoán đổi.
FOR I ← 1 TO N - 1
FOR J ← 1 TO N - 1
IF List[J] > List[J + 1]
THEN
Temp ← List[J]
List[J] ← List[J + 1]
List[J + 1] ← Temp
ENDIF
NEXT J
NEXT I
Khám phá
Quan sát cách sắp xếp nổi bọt hoạt động
So sánh các phần tử kề nhau và hoán đổi các cặp bị sai thứ tự; phần tử lớn nhất sẽ nổi lên cuối cùng.
Lỗi thường gặp
- Mỗi lượt duyệt đưa giá trị lớn nhất còn lại về cuối danh sách.
- Nếu một lượt duyệt hoàn toàn không thực hiện phép hoán đổi nào, danh sách đã được sắp xếp rồi.
Bây giờ bạn thử
- Hoán đổi hai giá trị, sau đó sắp xếp cả danh sách.
- Nhấn Check answer (Kiểm tra câu trả lời) để thử mã của bạn.
Độ khó 4/5 · 280 xu + phần thưởng nhỏ khi hoàn thành lần đầu tiên hôm nay
Hoán đổi giá trị của a và b, để sau khi thực hiện thì a bằng 9 và b bằng 5.
Nhấn Chạy để xem kết quả ở đây.
Độ khó 4/5 · 280 xu + phần thưởng nhỏ khi hoàn thành lần đầu tiên hôm nay
Sắp xếp danh sách nums theo thứ tự tăng dần (nhỏ trước lớn sau) bằng thuật toán sắp xếp nổi bọt. Kết quả sẽ là [1, 2, 4, 5].
Nhấn Chạy để xem kết quả ở đây.
Độ khó 4/5 · 280 xu + phần thưởng nhỏ khi hoàn thành lần đầu tiên hôm nay
Viết is_sorted(nums) trả về True nếu danh sách đã được sắp xếp theo thứ tự tăng dần, ngược lại trả về False.
Nhấn Chạy để xem kết quả ở đây.