Thuật toán sắp xếp trong lâp trình

Bữa nay tôi muốn đề cập tới một số thuật toán bất li thân của IT chúng ta, đó là những thuật toán sắp xếp. Ai đã học IT thì chắc đã cài đặt nó trên C hay C++ rồi, nhưng cài trên PHP tuy nó vẫn giống nhưng mà hiện tại trên izwebz chưa có nên tôi có cơ hội được đăng bài này.

Giới thiệu về bản thân một chút, hiện tại tôi đang học tập tại Việt Nam(tại cội nguồn page này từ USA) nên phải giới thiệu tỉ mỉ và mới hoàn thành xong năm nhất.Tôi thích giới thiệu kĩ càng bởi vì tôi cảm nhận website này khá tốt, nên tôi muốn nguồn kiến thức đưa ra phải đạt một chuẩn nào đó. hy vọnggần tới mấy anh admin của izwebz sẽ có thể giới thiệu kĩ, và thật về ngày nay của bản thân. Tôi thấy site của nước ngoài hay thế lắm, tôi cảm thầy rất tin tưởng và chuyên nghiệp nữa. The end introduction …

Bubble Sort: bố trí nổi bọt

Ý tưởng thuật toán: Đúng như tên gọi của nó các phần tử sẽ được bố trí theo kiểu phần tử nào tí hon nhất sẽ nổi lên đầu còn những phần tử béo sẽ chìm xuống cuối.

Code bubble sort:

Output:

0, 1, 2, 3, 4, 5, 6, 7, 8, 9

Giảng giải đoạn code trên

đánh số key cho mảng ở trên (chú ý hen, trong C thì những chỉ số là index nhưng trong PHP lại là key).

9 -> a[0]; 8 -> a[1]; 7-> a[2]; 6->a[3]; 5->a[4]; 4->a[5]; 3->a[6]; 2->a[7]; 1->a[8]; 0->a[9];

Ở vòng for trước tiên với $i=0 sẽ thực hành vòng lặp for thứ hai từ địa điểm thứ 9 xuống vị trí thứ 0 của mảng trên, và khởi đầu so sánh nếu số trước bự hơn số sau thì thiến hai số đó. tỉ dụ giá trị của a[9] =0 và a[8] =1; rõ ràng a[8] =1 (số trước) > a[9]=0 (số sau). Thỏa mãn điều kiện if ở trên nên thực hành thiến hai số này và tiếp tục so sánh như vậy cho đến j=1; như vậy sau giá trị $i=0 và chạy vòng for thứ hai thì phần tử 0 tức là giái trị của a[9] sẽ được đẩy lên đầu. (phần tử nhẹ nhất nổi lên đầu.).Như vậy có thể hiểu ngay sau khi tăng $i lên một thì giá trị =1 trong mảng $a sẽ đứng kế sau giá trị 0 trong mảng $a.

Selection Sort: chọn lọc trực tiếp

Code selection sort

Output: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9

Ý tưởng thuật toán: xét một mảng cần bố trí ta sẽ chọn phần tử trước tiênví thử nó là nhỏ nhất, sau đó qua sử lí ta sẽ tìm ra phần tử nhỏ xíu nhất thực sự của mảng và hoạn nó với phần tử vừa giá sử là gầy nhất.

các thao tác nhìn có vẻ na ná bubble sort nhưng mà nó có thêm biến $min, biến này nhằm mục đích lấy chỉ số (à quên key chứ )của phần tử ốm nhất mà ta vừa giả tỉ và xét đến điều kiện if ($b[$j] < $b[$min]) nếu đúng thì gán lại chỉ số gầy nhất thực sự của mảng cho biến $min. Và thực hiện thiến $a[$i] (là giá trị của biến min mà ta giả sử) cho$a[$min] (giá trị vừa tìm ra và nhỏ xíu hơn giá trị của $a[$i]). Chỉ vậy thôi. Đó là Selection Sort

Insertion Sort: cách thức chèn

Code for Insertion Sort.

Output: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9

ý nghĩ thuật toán: giải thích rễ hiểu nhất cho thuật toán này là khi các bạn chời bài tiến lên(ngoài băc mình hay gọi là chơi bài nam). các bạn sẽ nhìn thầy một nhóm quân bài đã có trật tự nhưng con bài tiếp theo lại ko đúng với thứ tự của nhóm quân bài này (ví dụ nhìn thầy 2 cơ, 3 cơ, 4 cơ A tiếp theo không phải 5 nhưng mà là K cơ. Trong khi đó 5 cơ lại ở đâu đó trong những quân bài cầm trên tay) nhiệm vụ của cả nhà là nhìn lướt tổng thể các quân bài có trên tay và lấy con 5 cơ đặt đúng vị trí sau 4 cơ. Đó cũng chính là phương pháp mà insertion sort làm việc đó các bạn.

giải thích code: Ở vòng lặp đầu tiên khi xét $i=0, và thực hành tất các câu lệnh ở dưới nó khi $i=0 ngay tức khắc là lấy giá trị của nó liền nghĩa là tóm lấy $b[$i]; và so sánh nó với $b[$j]. cả nhà thấy nó ở trong điều kiện vòng lặp for thư hai && đó. Nếu đúng thì sẽthực hiện thiến $b[$j+1] = $b[$j]; Nếu ko thì chính nó là nhỏ xíu hơn số cần so sánh rồi, nó vẫn là chính nó thể hiện qua $b[$j+1]=$x; chỉ vậy thôi

Kết luận

Trong bài viết này tôi chỉ có thể public từng dó thôi, nếu cả nhà thích thiết lập them những thuật toán shellsort, radix sort, merg sort hay binary search thì phải comment(còm men) ở dưới hay một số đòi hỏi về lập trình PHP (chưa nói đến lập trình ứng dụng nha bởi vì mình chưa có bản lĩnh do mới tiếp xúc với PHP). Mình sẽ cố hết sức để viết. Do đây là bài viết đầu tiên nên rất cần thăm dò nhã hứng của các thành viên. Mình thích khen lắm..hi hi hi. Rất vui khi được đóng góp cho izwebz.

Lưu ý: Trong các đoạn code trên tôi viết chỉ để mô phỏng các thuật toán trên thôi chưa tính đến chuyện tối ưu trong tính toán, thí dụ như bubble sort nếu viết như vậy thì các bạn sẽ được điểm kém khi học môn phân táchxây dựng giải thuật, bởi vì nó khong tối ưu về thời kì, rõ rang với code như vậy thì kể cả mảng đã bố trí rồi nó vẫn phải thực sắp như ngần đó đoạn code sở dĩ gần như và câu lệnh if đều không thỏa(vì nó đã sắp xếp rồi). và trong insertion sort cũng như vậy. các bạn có thể tìm hiểu làm sao để tối ưu nhé, code các bạn sẽ public trên izwebz hen, nhớ thiết lập trên PHP. Đang ngồi trên thư viện trường rất thoải mái khi viết bài này. Chào tất cả các bạn yêu izwebz . Good luck !!!!

(Lượt xem: 2, Lượt xem trong ngày: 1)

Bài trước:

Bài sau:

Condotel Vinpearl