Mọi lập trình viên ban đầu phải suy nghĩ về sơ đồ/kế hoạch/kiến trúc của công việc trong tương lai, nếu không tất cả sẽ trở nên hỗn loạn, hoàn toàn hỗn loạn. Như với bất kỳ bài đăng nào, ban đầu bạn cần có kế hoạch, hãy bắt đầu.
1) Lấy chủ đề Sắp xếp hợp nhất cho người mới bắt đầu.
2) Chúng tôi sẽ tạo ra một kiến trúc và kế hoạch cho công việc tiếp theo.
3) Chúng tôi sẽ nghiên cứu và mô tả tất cả các phần của kế hoạch.
4) Hãy kiểm tra hiệu suất và chất lượng.
2.1) Sắp xếp hợp nhất là gì.
2.2) Mô tả các chữ ký có thể có.
2.3) Cho ví dụ.
2.4) Mô tả cách triển khai bằng Java bằng một ví dụ.
2.5) Bất cứ điều gì bổ sung.
Hợp nhất - sắp xếp hợp nhất trong Java
Áp dụng nguyên tắc “chia để trị”. Ý tưởng và ý nghĩa của nó là gì?
Sắp xếp.
Ta chia mảng thành nhiều phần cho đến khi nó bằng 1 phần tử. Mỗi 1 phần tử được sắp xếp.
Sáp nhập.
Hợp nhất các phần tử đã được sắp xếp
Dựa trên nguyên tắc hai bộ bài. Chúng tôi đặt 2 bộ bài trên bàn với giá trị của chúng tăng lên và lá bài có giá trị thấp nhất được đặt vào chồng bài thứ ba. Cuối cùng, nếu chúng tôi hết bài trong một bộ bài nhất định, chúng tôi sẽ chuyển từng lá bài một sang bộ bài kết quả. Kết quả sẽ là sự hợp nhất của hai mảng đã được sắp xếp, một mảng mới đã được sắp xếp.
Đây là điều tương tự, chỉ được liên kết với các chỉ mục. Các biến trong đó là:
A=Array= Массив
p, q, r = индексы для массива
p - начало первого массива
q - конец первого массива
q +1- начало второго массива
r - конец второго массива
Nếu những biến này không được mô tả, thì người yêu cầu tự mình thực hiện một hàm như vậy sẽ không biết mình muốn gì. Và bạn sẽ phải lùng sục trên Google để tìm hiểu nó là gì, có thể bạn sẽ tìm thấy nó. Hãy đưa ra một ví dụ về cách sắp xếp của chúng tôi. Có một mảng {6, 1, 3, 5, 2, 4, 7, 8}, nếu độ dài lớn hơn 1 thì ta chia mảng đó thành 2 phần và lấy phần bên trái {6, 1, 3, 5}và phần bên phải {2, 4, 7, 8}. Ta tiếp tục thực hiện chia thành 2 phần cho đến khi độ dài lớn hơn 1. Kết quả ta được một dãy mảng có độ dài 1 phần tử, cụ thể là: {6} {1} {3} {5} {2} {4} {7} {8}. Việc triển khai trong Java giống như thế này:
publicint[]sortArray(int[] arrayA){// sorting Массива который передается в функцию// проверяем не нулевой ли он?if(arrayA ==null){returnnull;}// проверяем не 1 ли элемент в массиве?if(arrayA.length <2){return arrayA;// возврат в рекурсию в строки ниже см комменты.}// копируем левую часть от начала до серединыint[] arrayB =newint[arrayA.length /2];System.arraycopy(arrayA,0, arrayB,0, arrayA.length /2);// копируем правую часть от середины до конца массива, вычитаем из длины первую частьint[] arrayC =newint[arrayA.length - arrayA.length /2];System.arraycopy(arrayA, arrayA.length /2, arrayC,0, arrayA.length - arrayA.length /2);// рекурсией закидываем поделенные обе части обратно в наш метод, он будет крутится до тех пор,// пока не дойдет до 1 element в массиве, после чего вернется в строку и будет искать второй такой же,// точнее правую часть от него и опять вернет его назад
arrayB =sortArray(arrayB);// левая часть возврат из рекурсии строкой return arrayA;
arrayC =sortArray(arrayC);// правая часть возврат из рекурсии строкой return arrayA;// далее опять рекурсия возврата слияния двух отсортированных массивовreturnmergeArray(arrayB, arrayC);}
Tiếp theo bạn cần hợp nhất các mảng này thành 1. Việc này được thực hiện như thế nào? Để tránh phải đi qua từng mảng nhiều lần, hãy nhập chỉ số vị trí cho từng mảng. Sau đó chúng ta sẽ đi qua một vòng lặp một lần, bằng độ dài tổng của hai mảng này. Lấy mảng thứ nhất và mảng thứ hai lấy phần tử thứ nhất, so sánh phần tử số 1 trong mảng thứ nhất và phần tử số 1 trong mảng thứ hai ? Cái nhỏ hơn được đặt trong mảng kết quả. Điều quan trọng ở đây là nếu chúng ta lấy một phần tử từ mảng đầu tiên thì khi vòng lặp đi qua, nó sẽ tham chiếu đến phần tử thứ 2 của mảng đầu tiên và phần tử thứ 1 của mảng thứ hai. Để làm điều này, bạn cần tăng chỉ số của mảng thứ hai lên +1 và khi kiểm tra, hãy trừ nó khỏi số chu kỳ, tương tự như vậy đối với mảng đầu tiên. Có rõ ràng tại sao phải làm điều này? Hay là chẳng có gì rõ ràng cả? :-) Ví dụ có 2 mảng: {1}{4}{8}và {3}{6}{7} Và có một vòng lặp:
for(int i =0; i < arrayA.length + arrayB.length; i++){if(arrayA[i]< arrayB[i]){
arrayC[i]= arrayA[i];}else{
arrayC[i]= arrayB[i];}}
Trong lần đầu tiên vượt qua vòng lặp, hóa ra arrayC[1] = {1}: chúng tôi đã lấy phần tử này từ mảng đầu tiên. Sau đó, khi đi qua vòng lặp thứ hai, chúng ta phải so sánh phần tử {4}và {3}, nhưng để làm được điều này, chúng ta cần tính đến các chỉ số vị trí và độ lệch của cả hai mảng, để làm được điều này, chúng ta nhập chúng.
int positionA =0, positionB =0;for(int i =0; i < arrayA.length + arrayB.length; i++){if(arrayA[i - positionA]< arrayB[i - positionB]){
arrayC[i]= arrayA[i - positionA];
positionB++;}else{
arrayC[i]= arrayB[i - positionB];
positionA++;}}
Nhưng đó chưa phải là tất cả, bạn cần lưu ý rằng một số mảng có thể kết thúc sớm hơn. Ví dụ: có 3 mảng: {1}{3}{5}và {6}{7}{9} Mảng đầu tiên sẽ kết thúc trước khi mảng thứ hai đến, để làm được điều này, bạn cần nhập dấu kiểm và về nguyên tắc, hàm hợp nhất đã sẵn sàng.
Điều khó nhất trong cách sắp xếp này là nguyên tắc chuyển đổi đệ quy. Những thứ kia. Chúng ta ném vế trái vào đệ quy cho đến khi chia hết cho 2 rồi gỡ lại, nói cách khác là rất phức tạp và khó hiểu, nhưng khi bạn thử tưởng tượng mà vẫn chưa rõ ràng thì hoàn toàn là một mớ hỗn độn. Hãy lấy mảng: {2}{1}{4}{3}. Đệ quy sắp xếp thứ nhất sẽ chia thành 2 phần và chạy lại hàm với các phần tử 2-1 , sau đó lại với các phần tử 2 và 1 , trả về lần lượt nên chúng sẽ vào hàm merge trước, và 1-2 sẽ đến out , thì đệ quy sẽ quay trở lại và ném 4-3 vào hợp nhất , sau đó là 4 và 3 , sau đó hợp nhất sẽ trả về 3-4 , và chỉ khi đó đệ quy mới quay trở lại và 1-2 và 3-4 sẽ được đưa vào hợp nhất và mảng đã sắp xếp sẽ được trả về 1-2-3-4 . Vâng, chỉ vậy thôi, việc sắp xếp bao gồm hai chức năng.
sortArray(array);// кладем массив который нужно отсортироватьmergeArray(arrayA, arrayB);// кладем 2 массива которые нужно слить в один
Nếu bạn viết ra một số loại chính, bạn sẽ nhận được một cái gì đó như:
publicstaticvoidmain(String[] args){Merge testMerge =newMerge();int[] result = testMerge.sortArray(newint[]{2,3,1,4});for(int i =0; i < result.length ; i++){System.out.print(result[i]+" ");}}
Đối với tôi, cách sắp xếp này hoàn toàn thất bại, có hàng triệu câu hỏi nhưng không có câu trả lời, tôi tìm khắp Internet, đọc lại, xem rất nhiều video, nhưng như mọi khi, tôi chỉ tự mình tìm ra câu trả lời. Và chỉ khi tôi bắt đầu viết một giải pháp hoàn toàn khác với giải pháp lóe lên khắp nơi) Nhưng cuối cùng nó lại giống với tất cả những giải pháp khác))) Sắp xếp thực sự là đơn giản nhất, điều chính là trình bày nó một cách tương tác trong hành động và mọi thứ sẽ ổn nếu bạn hiểu rõ, tôi sẽ làm một video)))) Cho đến nay, đó là tất cả những gì tôi có đủ: Hợp nhất sắp xếp Hợp nhất -sắp xếp Điều quan trọng nhất là luôn lập kế hoạch từ sự bắt đầu. Tốt hơn là bạn nên đợi một chút và suy nghĩ trước khi bắt đầu làm bất cứ điều gì. Có thể mất nhiều thời gian hơn, nhưng sự hiểu biết và giải pháp sẽ xuất hiện thay vì phải viết lại vài lần rồi tìm ra cách chống nạng. Cảm ơn tất cả các bạn đã dành thời gian, chúc may mắn và tâm trạng tốt. ) PS: Những lời phê bình, tốt và xấu, cũng như các câu hỏi đều rất đáng hoan nghênh. )))
GO TO FULL VERSION