30/09/2018, 18:33
chèn 1 số vào vị trí bất kì trong mảng
- các bác hôm tc em gặp cái bài thế này:
- nhập 1 mảng rồi sắp xếp tăng dần, rồi chèn 1 phần tử bất kì vào 1 vị trí bất kì trong mảng sao cho trật tự không thay đổi.
- em làm thế này:
VD: 1 mảng sắp xếp tăng dần:
1 3 4 5 6 7
em chèn 2 vào cuối cùng rồi sắp xếp lại
1 2 3 4 5 6 7
thế này thầy em bảo sai. các bác giải đáp giúp em vs. em cám ơn!
Bài liên quan
Sau khi sắp xếp mảng, duyệt từ đầu tới cuối để kiểm tra nếu phần tử nằm trong đoạn từ a[i] -> a[i+1] thì chèn vào đó.
Nên dùng tìm kiếm nhị phân để tìm vị trí chèn vào
ý này của bác có vẻ hay!
em không hiểu cách của bác lắm!
bác có thẻ nói rõ cách này hơn không
Đầu tiên bạn tìm vị trí cần chèn. Ví dụ bạn muốn chèn số 4 vào mảng. Vị trí cần chèn sẽ là 2(i tính từ 0).
Khi xác định được vị trí cần chèn rồi, bạn dồn toàn bộ các phần tử về phía sau.(có thể gán a[i+i]=a[i])
Sau khi dồn xong thì chèn số 3 vào vị trí 2 như đã định từ trước.
Các bước này liên quan đến binary insert sort. Bạn có thể tìm hiểu thêm [Wiki] Binary Insert Sort in C