Bài giảng Giới thiệu các thuật toán sắp xếp

Giới thiệu<br /> Các thuật toán sắp xếp<br /> <br /> 1<br /> <br /> Nội dung trình bày<br /> • Tiếp cận sắp xếp đơn giản<br /> Sắp xếp chọn<br /> Sắp xếp chèn<br /> Sắp xếp nổi bọt<br /> <br /> • Tiếp cận sắp xếp độ phức tạp O(nlog(n))<br /> Sắp xếp theo phân đoạn (Quick sort)<br /> Sắp xếp hòa nhập<br /> Sắp xếp vung đống<br /> <br /> • Một số tiếp cận khác<br /> Sắp xếp theo cơ số<br /> Sắp xếp hòa nhập file lớn<br /> 2<br /> <br /> Sắp xếp đếm - countingsort<br /> • Bài toán<br /> Có n phần tử cần sắp xếp là kiểu nguyên<br /> Các giá trị của phần tử không lớn hơn giá trị k<br /> <br /> • Có cách nào đó xác định được nhanh nhất phần<br /> tử x đầu vào sẽ xác định tại vị trí nào trong danh<br /> sách đầu ra<br /> • Ví dụ:<br /> Nếu kiểm tra được có 17 phần tử bé hơn phần tử x,<br /> vậy x sẽ được bắt đầu tại vị trí 18<br /> Dùng một mảng trung gian để đếm vị trí xuất hiện<br /> của x trong dãy đầu ra<br /> 3<br /> <br /> Sắp xếp đếm - countingsort (t)<br /> Đếm thông qua thống kê số lần xuất hiện của các<br /> phần tử<br /> Cộng dồn để xác định vị trí xuất hiện cuối của phần<br /> tử tiếp theo trong danh sách<br /> <br /> • Phân phối các giá trị theo vị trí đã xác định<br /> <br /> 4<br /> <br /> Sắp xếp đếm – countingsort (t)<br /> • Thuật toán – countingsort (t)<br /> • Input: dãy A[0..N-1] nguyên, miền giá trị [0..k]<br /> • Output: dãy B[0..N] đã được sắp xếp<br /> 1. for(i=0->k)<br /> c[i]=0;<br /> 2. for(i=0->N-1)<br /> c[a[i]]++;<br /> 3. for(i=1->k)<br /> c[i]=c[i-1]+c[i];<br /> 5<br /> <br />