Home » Thuật toán » [Thuật toán] Thuật toán sắp xếp (Phần 5)

[Thuật toán] Thuật toán sắp xếp (Phần 5)

Hôm nay mình xin giới thiệu với các bạn thuật toán sắp xếp được coi như nhanh nhất trong tất cả các thuật toán sắp xếp. Couting sort.

Các bạn có thể xem lại các thuật toán sắp xếp khác tại đây [bsbutton text=”Phần 1″ link=”http://motoo.in/lap-trinh-cc-cac-thuat-toan-sap-xep/” target=”This page” style=”default” theme=”default” size=”normal”] [bsbutton text=”Phần 2″ link=”http://motoo.in/lap-trinh-cc-cac-thuat-toan-sap-xep-phan-2/” target=”This page” style=”default” theme=”default” size=”normal”] [bsbutton text=”Phần 3″ link=”http://motoo.in/thuat-toan-thuat-toan-sap-xep-phan-3/” target=”This page” style=”default” theme=”default” size=”normal”][bsbutton text=”Phần 4″ link=”http://motoo.in/thuat-toan-thuat-toan-sap-xep-phan-4/” target=”This page” style=”default” theme=”default” size=”normal”]

XI./ COUNTING SORT

  • Ý tưởng

Counting Sort là thuật toán đếm số lần xuất hiện của các giá trị khác nhau trong mảng ban đầu. Và gán giá trị vừa đếm vào vị trí tương ứng của 1 mảng có độ dài là giá trị lớn nhất của mảng.

  • Giải thuật

Bước 1: Tìm MAX = max(Array[]);

Bước 2: Tạo mảng động *Soluong có độ dài = MAX và Soluong[i] = 0;

int *Soluong = new (int *)calloc(MAX, sizeof(int));

Bước 3: Đếm số lần xuất hiện của các giá trị khác nhau trong mảng ban đầu. Và gán giá trị vào vị trí tương ứng ở mảng Soluong.

Bước 4: Sắp xếp lại mảng ban đầu bằng cách duyệt mảng Soluong.

  • Cài đặt Code C/C++

  • Đánh giá thuật toán

Trường hợp Độ phức tạp
Tốt nhất O(n)
Xấu nhất O(n)

 Độ phức tạp trung bình  = O(n)

 

Share
Share
Free WordPress Themes - Download High-quality Templates