Sắp xếp
Sắp xếp các phần tử
- Sắp xếp sắp xếp một danh sách theo thứ tự, thường là từ nhỏ đến lớn.
- Hành động chính là một lần hoán đổi: trao đổi hai phần tử.
- Trong Python:
a[i], a[j] = a[j], a[i]hoán đổi hai phần tử của danh sách trong một dòng mã.
Sắp xếp nổi bọt
- So sánh từng cặp kẻ cạnh; hoán đổi chúng nếu chúng không đúng thứ tự.
- Sau một lượt duyệt hoàn chỉnh, phần tử lớn nhất đã "nổi" lên cuối cùng.
- Lặp lại các lượt duyệt. Sau
n − 1lượt duyệt, danh sách chắc chắn đã được sắp xếp; bạn có thể dừng sớm hơn nếu một lượt duyệt không thực hiện hoán đổi nào.
data = [3, 1, 2]
n = len(data)
for i in range(n - 1):
for j in range(n - 1 - i):
if data[j] > data[j + 1]:
data[j], data[j + 1] = data[j + 1], data[j]
print(data)
Sắp xếp chèn
- Coi phần bên trái của danh sách là đã được sắp xếp rồi.
- Lấy phần tử tiếp theo và trượt nó sang trái cho đến khi nó vào đúng vị trí.
- Giống như việc sắp xếp các lá bài trong tay, từng lá một.
data = [3, 1, 2]
for i in range(1, len(data)):
key = data[i]
j = i - 1
while j >= 0 and data[j] > key:
data[j + 1] = data[j]
j = j - 1
data[j + 1] = key
print(data)
So sánh chúng
- Cả hai đều kiểm tra khoảng
n × ncặp, nên cả hai đều chậm trên danh sách lớn. - Sắp xếp chèn nhanh khi danh sách gần như đã được sắp xếp sẵn.
- Có các phương pháp nhanh hơn, nhưng sắp xếp nổi bọt và sắp xếp chèn dễ hiểu hơn.
Trong pseudocode Cambridge
- Sắp xếp nổi bọt với biến
tempđể hoán đổi, trên mảnglist[1:n].
FOR i ← 1 TO n - 1
FOR j ← 1 TO n - i
IF list[j] > list[j + 1] THEN
temp ← list[j]
list[j] ← list[j + 1]
list[j + 1] ← temp
ENDIF
NEXT j
NEXT i
Lỗi thường gặp
- Cả sắp xếp nổi bọt và sắp xếp chèn đều có độ phức tạp O(n²).
- Vẽ thử một danh sách nhỏ bằng tay để kiểm tra thuật toán sắp xếp của bạn có hoạt động không.
Bây giờ bạn thử
- Mỗi nhiệm vụ thay đổi danh sách ngay tại chỗ — không cần trả về nó.
- Nhấn Check answer (Kiểm tra câu trả lời) để thử mã của bạn.
Xem quá trình sắp xếp chạy
Sắp xếp liên tục so sánh và hoán đổi cho đến khi mọi thứ đều đúng thứ tự.
Độ 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 swap(items, i, j) hoán đổi các phần tử tại chỉ số i và chỉ số j trong danh sách. Thay đổi danh sách ngay tại chỗ (không return).
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 bubble_sort(items) sắp xếp danh sách theo thứ tự tăng dần dùng bubble sort. Thay đổi danh sách ngay tại chỗ.
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 insertion_sort(items) sắp xếp danh sách theo thứ tự tăng dần dùng insertion sort. Thay đổi danh sách ngay tại chỗ.
Nhấn Chạy để xem kết quả ở đây.