Giải thuật sắp xếp trong lâp trình

Rate this post

Bữa nay tôi muốn đề cập đến một vài thuật toán bất li thân của IT chúng ta, đó là các 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 mà 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ó thời cơ được đăng bài này.

XEM thêm : Magento marketplace

Giới thiệu về bản thân một tíngày nay tôi đang học tập tại Việt Nam(tại nguồn cội page này từ USA) nên phải giới thiệu kĩ càng và mới hoàn tất xong năm nhất.Tôi thích giới thiệu tận tường  tôi cảm nhận trang web này khá tốt, nên tôi muốn nguồn tri thức đưa ra phải đạt một chuẩn nào đó. hy vọng là sắp tới mấy anh admin của izwebz sẽ có thể giới thiệu kĩ, và thật về hiện tại của phiên bản thân. Tôi thấy trang web 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: sắp xếp nổi bọt

Ý tưởng thuật toán: Đúng như tên gọi của nó những 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ử lớn 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 đầu tiên với $i=0 sẽ thực hành vòng lặp for thứ hai từ vị trí thứ 9 xuống vị trí thứ 0 của mảng trên, và bắt đầu so sánh nếu số trước lớn hơn số sau thì hoạn hai số đó. ví 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 hiện hoạ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 nghĩa 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: tuyển lựa 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ử đầu tiên và giả thử nó là ốm nhất, sau đó qua sử lí ta sẽ tìm ra phần tử nhỏ nhất thực thụ của mảng và hoán vị nó với phần tử vừa giá sử là gầy nhất.

những thao tác nhìn có vẻ tương tự bubble sort nhưng 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ử  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ố nhỏ xíu nhất thực sự của mảng cho biến $min. Và thực hành hoán vị $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à gầy hơn giá trị của $a[$i]). Chỉ vậy thôi. Đó là Selection Sort

Insertion Sort: nguyên lý chèn

Code for Insertion Sort.

 

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

ý nghĩ thuật toángiảng giải rễ hiểu nhất cho thuật toán này là khi cả nhà chời bài tiến lên(ngoài băc mình hay gọi là chơi bài nam). cả nhà 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 không đú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 ko phải 5 mà lại 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ác bạn là nhìn lướt cục bộ các quân bài có trên tay và lấy con 5 cơ đặt đúng địa điểm sau 4 cơ. Đó cũng chính là bí quyết mà insertion sort làm việc đó các bạn.

giảng giải code: Ở vòng lặp trước 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 tức thì 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 hoán vị $b[$j+1] = $b[$j]; Nếu không 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ác bạn thích setting them các 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 tới lập trình vận dụng nha  mình chưa có khả năng 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.

Chú ý: Trong những đoạn code trên tôi viết chỉ để mô phỏng những thuật toán trên thôi chưa tính tới 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ích và xây dựng giải thuật,  nó khong tối ưu về thời gian, 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ả nhà có thể khám phá làm sao để tối ưu nhé, code các bạn sẽ public trên izwebz hen, nhớ setting 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ả nhà yêu izwebz . Good luck !!!!

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *