So sánh 2 manrg và tìm giá trị lớn nhất năm 2024
Sắp xếp mảng là một trong những thao tác phổ biến nhất mà người mới bắt đầu sử dụng Java nên biết cách thực hiện. Mặc dù mảng không phải lúc nào cũng là cách thuận tiện nhất để sắp xếp dữ liệu và điều này chủ yếu áp dụng cho các số nhỏ, nhưng khái niệm đằng sau việc sắp xếp mảng có rất nhiều ứng dụng trong khoa học dữ liệu và phần mềm phức tạp. Trong bài đăng này, chúng ta sẽ xem xét kỹ hơn về sắp xếp chèn là gì. Chúng tôi đã bao gồm một số ví dụ và bài toán thực hành để giúp bạn hoàn toàn nắm bắt được khái niệm này. Show Sắp xếp chèn là gì?Về cơ bản, sắp xếp chèn là một thuật toán mà các nhà phát triển sử dụng để tổ chức các chuỗi số nhỏ. Nó chia tất cả các giá trị thành hai ngăn xếp - một ngăn xếp được sắp xếp và một ngăn xếp chưa được sắp xếp. Lần lượt, các số trong ngăn xếp “chưa sắp xếp” được chọn ra và sắp xếp theo đúng thứ tự. Chúng ta hãy xem xét kỹ hơn đầu vào và đầu ra của sắp xếp chèn:
Có một số cách để sử dụng sắp xếp chèn - đây là những cách phổ biến nhất:
Lưu ý: nếu bạn có một mảng trống hoặc một singleton, chúng được coi là được sắp xếp theo mặc định. Hiểu lý thuyết về sắp xếp chènTrước khi khám phá mã đằng sau sắp xếp chèn, hãy chia nhỏ thuật toán bằng cách sử dụng ngôn ngữ phi kỹ thuật. Bởi vì chúng tôi sẽ hiển thị mã để sắp xếp theo thứ tự tăng dần, nên việc giải thích thuật toán từng bước trong bài đăng này là điều hợp lý. Bước 1. Lặp lại giữa
1và
2ở đâu
3là một giá trị số thường nhỏ hơn 10. Bước 2. So sánh phần tử bạn đã chọn (được gọi là
5phương pháp. Bước 3. Nếu tất cả các phần tử đều nhỏ hơn phần tử kế tiếp, hãy lặp lại phép so sánh cho đến khi bạn tìm thấy giá trị lớn hơn. Bước 4. Hoán đổi giá trị lớn hơn một vị trí so với giá trị nhỏ hơn để tạo một chuỗi có thứ tự. Bước 5. Lặp lại quy trình cho đến khi bạn nhận được chuỗi ký tự đã sắp xếp Sắp xếp mảng nguyên thủyVì thuật toán là một trong những thao tác Java đơn giản nhất nên ngay cả những người mới bắt đầu hoàn chỉnh cũng không gặp nhiều khó khăn khi thực hiện nó. Dưới đây là hướng dẫn từng bước để sắp xếp một mảng 1. Khai báo một mảng để sắp xếpĐể bắt đầu, hãy tạo một chuỗi giá trị mà sau này chúng ta sẽ hiển thị bằng Java. Để sử dụng sắp xếp chèn, bạn cần tạo một mảng. Đối với điều đó, sử dụng
6
2. Sử dụng sort_arr để thực hiện thuật toánPhương thức sort_arr là một trong những cách phổ biến nhất để triển khai sắp xếp chèn. Trong thực tế, nó trông như thế này:
3. Tạo vòng lặp và trình vòng lặpBằng cách sử dụng một vòng lặp trong thuật toán sắp xếp chèn, các nhà phát triển không phải lặp lại logic cho mọi phần tử. Mặc dù việc tạo các vòng lặp có vẻ phức tạp, nhưng nó khá đơn giản - đây là một ví dụ:
Bây giờ bạn đã có một vòng lặp hoạt động, đã đến lúc tạo một trình vòng lặp sẽ sắp xếp tất cả các phần tử theo thứ tự mong muốn. Từ giờ trở đi, chúng ta sẽ gọi iterator là "
7".
4. Tạo "vòng lặp while"Khi nói đến sắp xếp chèn, một vòng lặp "trong khi" là điều cần thiết cho một mảng mới được sắp xếp. Để thiết lập nó cho sắp xếp chèn theo thứ tự tăng dần, nhà phát triển cần tuân thủ hai điều kiện:
Ngay khi cả hai điều kiện trong vòng lặp while đều đúng, giá trị khóa của mảng sẽ bằng chỉ
7mục. 5. Sắp xếp mảngSau khi bạn thiết lập vòng lặp while, các giá trị
7và
8sẽ được hoán đổi cho đến khi một hoặc cả hai điều kiện trong vòng lặp while không thành công. Tương tự, việc sắp xếp sẽ được lặp lại cho mọi giá trị trong vòng lặp for cho đến khi các điều kiện của vòng lặp for cũng không thành công. Đây là cách quá trình sắp xếp chèn hoạt động trong thực tế:
Sắp xếp một ArrayListMặc dù việc hiểu toán học đằng sau sắp xếp chèn là rất quan trọng, nhưng khi nói đến phát triển phần mềm thực tế, bạn sẽ sắp xếp ArrayLists nhiều hơn so với trình tự trong các mảng nguyên thủy. Dưới đây là hướng dẫn từng bước để sắp xếp một ArrayList:
Bài tập thực hành sắp xếp chènBây giờ bạn đã hiểu rõ về thuật toán sắp xếp này, đã đến lúc kiểm tra các kỹ năng lý thuyết và thực hành của bạn. Bài kiểm tra lý thuyết số 1 Bạn được cho một mảng [1, 4, 6, 8] và đang thêm một phần tử mới n = 7 vào mảng đó. Bạn cần thực hiện bao nhiêu phép so sánh để có được một dãy số đã sắp xếp? Cho biết giá trị cuối cùng của chỉ số n trong mảng. Bài kiểm tra lý thuyết số 2 Tại một cuộc phỏng vấn xin việc, trưởng nhóm yêu cầu bạn chứng minh rằng chèn sắp xếp là một phương pháp không hiệu quả. Cho trước một chuỗi số [0, 3, 6, 8, 9], thứ tự của chuỗi đầu vào của bạn sẽ là bao nhiêu để tối đa hóa thời gian chạy cần thiết để sắp xếp? Bài tập thực hành Sắp xếp mảng [0, 1, 4, 5, 2, 3, 7, 9, 8] theo thứ tự tăng dần bằng cách sử dụng sắp xếp chèn cho Java. Phần kết luậnThách thức lớn nhất trong việc nắm bắt sắp xếp chèn là hiểu quy trình hoạt động như thế nào. Khi bạn đã hiểu rõ về nó, việc biến mẫu thành mã là một miếng bánh. Miễn là bạn thực hành và xem lại các vấn đề thực hành có liên quan theo thời gian, bạn sẽ nhanh chóng cải thiện tốc độ sắp xếp chèn của mình. |