THUẬT TOÁN SẮP XẾP BẰNG TRÁO ĐỔI
Chắc hẳn ngồi bên trên ghế giảng đường đại học thì người nào cũng sẽ được gia công quen cùng với thuật toán. Nghe thì thật là trừu tượng và mơ hồ, tuy vậy để tối ưu hóa những bài xích toán đề ra thì bắt buộc chúng ta phải học mang lại nó. Mình xin chia sẻ 1 chút lí thuyết mà mình học tập được về các thuật toán sắp xếp đơn giản, mong là hoàn toàn có thể giúp các bạn áp dụng vào bài bác toán thực tiễn của mình!
Sắp xếp nổi bọt ( bubble sort)Ý tưởng
Đây có lẽ rằng là các loại sắp xếp thân thuộc nhất với đa số người. Ý tưởng của thuật toán thu xếp nổi bọt như sau: mang lại chỉ số i chạy trường đoản cú 0, 1, ..., n-1, nếu như hai phần tử kề nhau ko đúng trật tự, có nghĩa là A.key > A.key thì ta tráo đổi hai thành phần A với A. Cứ thường xuyên làm bởi thế thì ta vẫn đẩy dữ liệu có khóa lớn nhất lên vị trí sau cùng là A
Bạn đang xem: Thuật toán sắp xếp bằng tráo đổi
Ví dụ
Giả sử ta có mảng số nguyên A<0..4> = (7, 2, 8, 4, 6). Kết quả thực hiện vấn đề tráo đổi đã được tiến hành trong bảng sau:
7 | 2 | 8 | 4 | 6 | Vì 7 > 2, tráo thay đổi A<0> với A<1> |
2 | 7 | 8 | 4 | 6 | Vì 8 > 4, tráo đổi A<2> cùng với A<3> |
2 | 7 | 4 | 8 | 6 | Vì 8 > 6, tráo đổi A<3> cùng với A<4> |
2 | 7 | 4 | 6 | 8 |
Lặp lại quy trình trên với mảng A<0, ..., n-2> để đẩy bộ phận lớn tốt nhất lên địa điểm A
Xem thêm:
void BubbleSort (int A<>, int n) for (int i = n-1; i > 0; i--) bool kiểm tra = true;for (int k = 0; k i; k++) if (A Ok vậy là bài xích toán rất có thể giải quyết nhanh gọn lẹ Ý tưởng
Ý tưởng của thuật toán này cũng dễ dàng và đơn giản không kém sắp xếp nổi bọt:Giả sử ta chọn lựa được thành phần có khóa nhỏ nhất trên mảng là AA<0>A<1>A<2>A<3>A<4>ik 7 2 8 4 6 0 1 2 7 8 4 6 1 3 2 4 8 7 6 2 4 2 4 6 7 8
Thuật toán
1void SelectionSort(int A<>, int n) 2 for (int i = 0; i n - 1; i++) 3 int k = i;4 for (int j = i + 1; j n; j++) 5 if (A
Xem thêm: Điện Thoại Sony Mới Nhất 2021 Cập Nhật Mỗi Ngày &Ndash; Digiphone
Sắp xếp xen vào (insertion sort)
Đây là thuật toán cuối cùng mà bản thân sẽ trình làng ở bài bác ngày hôm nay.
Ý tưởng
Cái thương hiệu của thuật toán cũng góp mình hình dung được phần nào ý tưởng của thuật toán. đưa sử đoạn đầu của mảng A<0..i-1> (với i >= 1) đã được chuẩn bị xếp, tức là ta đã tất cả A<0>.key
Đến đây thì ta gồm k = 2, A<2>
Lúc này k = 1 với A<1> >= A<0> bắt buộc ta dừng lại và ta đã bao gồm đoạn đầu A<0..3> được sắp đến xếpLặp lại công việc trên cùng với i = 4, 5 ta sẽ được mảng thu xếp tăng dần
Thuật toán
Hàm bố trí xen vào được viết như sau:
void InsertionSort(A<>, int n) for (int i = 1; i n-1; i++) for (int k = i; k > 0; k--) if (A