Bài viết này sẽ giới thiệu cho bạn Radix Sort và cho bạn biết cách triển khai Radix Sort trong C. Các con trỏ sau sẽ được đề cập trong bài viết này,
Vì vậy, hãy để chúng tôi bắt đầu,
Nói một cách dễ hiểu, sắp xếp có nghĩa là sắp xếp các phần tử đã cho theo một thứ tự có hệ thống. Việc sắp xếp được thực hiện trong hầu hết các thuật toán vì nó giúp tìm kiếm dễ dàng hơn, điều này cuối cùng làm cho thuật toán hiệu quả. Trong blog này, chúng ta sẽ hiểu một trong những thuật toán soring thường được sử dụng, tức là sắp xếp theo cơ số.
Sắp xếp theo cơ số là một thuật toán sắp xếp số nguyên không so sánh. Nó phân loại từng chữ số bắt đầu từ chữ số có nghĩa nhỏ nhất (tức là chữ số có ở bên phải) đến chữ số có nghĩa nhất (tức là chữ số ở bên trái). Radix sort sử dụng sắp xếp đếm như một chương trình con để sắp xếp.
Giới hạn dưới cho thuật toán sắp xếp dựa trên So sánh (chẳng hạn như Sắp xếp theo đống, Sắp xếp nhanh, Sắp xếp hợp nhất) là & Omega (nLogn) và chúng không thể được cải thiện ngoài nLogn. Nếu chúng ta nói về sắp xếp đếm, nó là một thuật toán sắp xếp thời gian tuyến tính với độ phức tạp thời gian O (n + k), trong đó phạm vi nằm trong khoảng từ 1 đến k. Bây giờ, vấn đề với sắp xếp đếm là, nó chiếm O (n2) khi các phần tử nằm trong khoảng từ 1 đến n2.
danh sách sự kiện javascript với các ví dụ
Vì vậy, để sắp xếp một mảng có các phần tử nằm trong khoảng từ 1 đến n2 theo thời gian tuyến tính, chúng ta cần sắp xếp theo cơ số. Sắp xếp cơ số sắp xếp chữ số mảng theo chữ số bắt đầu từ chữ số có nghĩa nhỏ nhất đến chữ số có nghĩa nhất. Radix sort sử dụng sắp xếp đếm như một chương trình con để sắp xếp.
Tiếp tục với bài viết này về Chương trình Sắp xếp Radix Trong C,
Thuật toán sắp xếp theo Radix
Thực hiện các bước sau cho tất cả các chữ số bắt đầu từ chữ số có nghĩa nhỏ nhất ở bên phải, chuyển sang chữ số có nghĩa nhất ở bên trái.
Sắp xếp các phần tử bằng cách sử dụng sắp xếp đếm theo chữ số hiện tại.
Thí dụ:
Mảng gốc:
140, 65, 85, 110, 612, 54, 12, 86
Sắp xếp chữ số có nghĩa nhỏ nhất, tức là ở một vị trí, sẽ cho
140, 110, 612, 12, 54, 65, 85, 86
LƯU Ý: Vì 612 xuất hiện trước 12 và việc sắp xếp chỉ được thực hiện cho một chữ số, do đó 612 xuất hiện trước 12 sau lần lặp này.
Sắp xếp theo chữ số tiếp theo, tức là ở vị trí 10 giây, cho:
110, 612, 12, 140, 54, 65, 85, 86
Sắp xếp theo chữ số có nghĩa nhất, tức là có mặt ở vị trí thứ 100, sẽ cho:
012, 054, 065, 085, 086, 110, 140, 612
Tiếp tục với bài viết này về Chương trình Sắp xếp Radix Trong C,
Chương trình sắp xếp Radix trong C
Đầu tiên nhìn vào chức năng sắp xếp Radix
có bao nhiêu từ dành riêng trong java
Chức năng sắp xếp Radix:
void radixsort (int array [], int n) {// Lấy số lớn nhất biết số chữ số tối đa int m = getMax (array, n) int dig // Sắp xếp đếm được thực hiện cho mọi chữ số for (dig = 1 m / dig> 0 dig * = 10) countSort (array, n, dig)}Tiếp tục với bài viết này về Chương trình Sắp xếp Radix Trong C,
Chức năng sắp xếp đếm:
void countSort (int array [], int n, int dig) {int output [n] int i, count [10] = {0} // Lưu trữ số lần xuất hiện trong count [] for (i = 0 i= 0 i--) {output [count [(array [i] / dig)% 10] - 1] = array [i] count [(array [i] / dig)% 10] -} // Sao chép xuất mảng thành arr [], để arr [] bây giờ // chứa các số được sắp xếp theo chữ số hiện tại cho (i = 0 iTrước tiên, hãy viết một chương trình C để triển khai sắp xếp Radix.
Thí dụ:
#include // Hàm tìm Số lớn nhất int getMax (int array [], int n) {int max = array [0] int i for (i = 1 i max) max = array [i] return max} // Hàm for Count sắp xếp void countSort (int array [], int n, int dig) {int output [n] int i, count [10] = {0} // Lưu trữ số lần xuất hiện trong count [] for (i = 0 Tôi= 0 i--) {output [count [(array [i] / dig)% 10] - 1] = array [i] count [(array [i] / dig)% 10] -} // Sao chép xuất mảng thành arr [], để arr [] bây giờ // chứa các số được sắp xếp theo chữ số hiện tại for (i = 0 i 0 dig * = 10) countSort (array, n, dig)} // Hàm in mảng void print (int arr [], int n) {int i for (i = 0 i Đầu ra
Bây giờ sau khi thực hiện chương trình trên, bạn đã hiểu Chương trình sắp xếp theo Radix trong C. Vì vậy, chúng ta đã kết thúc bài viết này về ‘Quicksort trong Java’. Nếu bạn muốn tìm hiểu thêm, hãy xem , một công ty học trực tuyến đáng tin cậy. Khóa học đào tạo và cấp chứng chỉ Java J2EE và SOA của Edureka được thiết kế để đào tạo bạn về cả khái niệm Java cốt lõi và nâng cao cùng với các khung Java khác nhau như Hibernate & Spring.
Có một câu hỏi cho chúng tôi? Vui lòng đề cập đến nó trong phần nhận xét của blog này và chúng tôi sẽ liên hệ lại với bạn trong thời gian sớm nhất.