Ý tưởng: Không so sánh mà chia khoảng giá trị

Sắp xếp cơ số là một thuật toán sắp xếp không so sánh, xử lý dữ liệu theo từng bit, tuần tự từ chữ số có nghĩa nhỏ nhất (Chữ số có nghĩa nhỏ nhất, LSD) đến chữ số có nghĩa nhất (Chữ số có nghĩa nhất, MSD) hoặc ngược lại. data.

Tìm hiểu các cơ sở khác với các thuật toán sắp xếp so sánh phổ biến (chẳng hạn như sắp xếp nhanh và sắp xếp hợp nhất), sắp xếp cơ sở dữ liệu không dựa trên so sánh trực tiếp giữa các phần tử mà dựa vào vị trí thông tin của các phần tử tử để sắp xếp. Nghĩa là, giá trị vi phạm phụ thuộc vào mức độ phức tạp.

Ý tưởng cốt lõi của việc sắp xếp cơ số là phân nhóm và hợp nhất: thông tin qua nhiều thao tác phân nhóm, các phần tử được đặt vào nhóm tương ứng theo một bit giá trị nhất được xác định, sau đó hợp nhất theo thứ tự của các nhóm để sắp xếp mảng tăng dần.

Sắp xếp cơ số phân tích đơn giản

Sau đây là quy trình sắp xếp cơ sở LSD đơn giản, dựa trên phân số thập phân:

1. Tìm kiếm số lượng lớn nhất trong mảng và số lượng tối đa chữ số được xác định cụ thể cần xử lý \(d\).
2. Bắt đầu với bit có số lượng thấp nhất, thực hiện các bước sau cho từng bit:
   • Sử dụng các thuật toán sắp xếp ổn định như Sắp xếp bộ đếm để sắp xếp dữ liệu dựa trên bit giá trị hiện tại.
   • Sắp xếp lại mảng theo nhóm thứ tự.

Lý do tại sao phương pháp này có kết quả là dữ liệu được sắp xếp cục bộ mỗi khi nó được nhóm và sắp xếp ổn định sắp xếp từng bit, sắp xếp các bit cao hơn sẽ không thay đổi thứ tự tương đối của các số được sắp xếp thấp hơn. could. Vì mỗi bước chứa thứ tự nguyên của nhóm trước đó nên các thẻ được sắp xếp cuối cùng sẽ được sắp xếp hoàn toàn.

#bao gồm  #bao gồm  #bao gồm  use zero name std; void countSort(vector& arr, int exp) { int n = vectơ kích thước mảng đầu ra(n) ; count(10, 0); // count[i]: Có bao nhiêu số có vị trí thứ i? for (int i = 0; i < n; i++) count[(arr[i] / exp) % 10] ++; cho (int i = 1; i < 10; i++) count[i] += count[ i - 1]; 1; i >= 0; i--) { // [(arr[i] / exp) % 10]--; n; i++) arr[i] = đầu ra[i] } void radixSort(vector& arr) { int maxVal = *max_element(arr.begin(), arr.end()); for (int exp = 1; maxVal / exp > 0; exp *= 10) countSort(arr, exp); vectơ chính() { vectơ arr = {170, 45, 75, 90, 802, 24, 2, 66} cho radixSort(arr); (int num : arr) cout << num << " ";

Bạn có thể nghĩ hàng trăm, hàng và hàng đơn vị là từ khóa thứ nhất, thứ hai và thứ ba theo trình tự và sắp xếp chúng nhiều lần từ khóa quan trọng đến cao. được sắp xếp và bạn chỉ cần sắp xếp chúng theo thứ tự.

Từ đó có thể thấy rằng việc sắp xếp các cơ sở thường xuyên được yêu cầu không gian phụ \(O(n+k)\). (chẳng hạn như số đơn vị hàng, số hàng đơn vị), sắp xếp cơ số ổn định và thứ tự tương thích đối số của các phần tử có cùng khóa giá trị không thay đổi sau khi sắp xếp. thứ tự của cấp độ các phần tử.

Big Endian (MSD) và Little Endian (LSD)

Trên đây là một ví dụ về LSD, thực tế thì việc đi từ cao xuống thấp cũng khả thi và dễ hiểu hơn. Sắp xếp cơ số MSD sắp xếp các số bắt đầu từ chữ số cao nhất, nhóm các số vào các nhóm khác nhau (chẳng hạn như theo hàng nghìn). Mỗi nhóm được sắp xếp đệ quy và được xử lý dần dần về phía các bit thấp hơn. Sau mỗi vòng sắp xếp, nội dung của các nhóm sẽ được hợp nhất theo thứ tự. Ví dụ: thư có thể được phân loại theo thứ bậc theo thành phố, tỉnh và đường phố. Đầu tiên, nó được chia theo thành phố, sau đó theo tỉnh ở mỗi thành phố và cuối cùng là theo đường phố ở mỗi tỉnh. Phân loại cấp cao trước tiên xác định phạm vi rộng và phân chia đệ quy đảm bảo rằng mọi chi tiết đều chính xác.

void msdRadixSortUtil(vector& arr, int left, int right, int exp) { if (left >= right || exp == 0) return vector<>> Bucks(10); phần tử vào các nhóm tương ứng dựa trên chữ số có nghĩa hiện tại for (int i = left; i <= right; i++) { int dig = (arr[i] / exp) % 10; Bucks[digit].push_back(arr[i]); } // Hợp nhất các nhóm lại thành mảng int index = left; for (int i = 0; i < 10; i++) { for (int num : Bucks[i] ) { arr[index++] = num; } } // Sắp xếp đệ quy từng nhóm không trống index = left; for (int i = 0; i < 10; i++) { if (!buckets[i].empty()) { int BucksSize = Bucks[i].size(); msdRadixSortUtil(arr, index, index + BucketSize - 1, exp / 10); chỉ mục += BuckSize; msdRadixSort(vector& arr) { if (arr.empty()) return; // Tìm giá trị lớn nhất để xác định số lượng chữ số int maxVal = *max_element(arr.begin(), arr.end()); int maxExp = pow(10, static_cast(log10(maxVal)) // Bắt đầu sắp xếp cơ số MSD từ chữ số có nghĩa cao nhất msdRadixSortUtil(arr, 0, arr.size() - 1, maxExp }

Việc sắp xếp ở cấp độ cao (MSD) bắt đầu với bit quan trọng nhất, sắp xếp đệ quy các mảng con và tinh chỉnh dần dần đến kết quả được sắp xếp cuối cùng, thường yêu cầu đệ quy. Phương pháp MSD thường được sử dụng để sắp xếp chuỗi vì nó có thể xác định trước các danh mục khác nhau.

Việc sắp xếp theo đầu cuối nhỏ (LSD) bắt đầu với bit có trọng số thấp nhất và tiến tới bit có trọng số cao nhất. Phạm vi sắp xếp của mỗi thao tác là toàn bộ mảng và mỗi lần sắp xếp không phá hủy thứ tự trước đó (sự ổn định). Vì vậy, để sắp xếp số nguyên, phương pháp LSD được sử dụng phổ biến hơn.

Cả hai phương pháp đều khả thi, nhưng việc sắp xếp cấp thấp dễ thực hiện và có thể áp dụng trực tiếp cho các con số nên nó phổ biến hơn trong thực tế.

Sắp xếp cơ số nhị phân

Dữ liệu trong máy tính được lưu trữ dưới dạng hệ nhị phân (hoặc thập lục phân) sẽ dẫn đến việc sử dụng không đủ từng bit thông tin và yêu cầu các phép toán modulo 10 không hiệu quả, rất kém hiệu quả.

Giả sử chỉ là số dương, đối với số nguyên 32 bit không dấu, nó có thể được chia thành các nhóm theo bit nhị phân. Ví dụ: 8 bit được xử lý cùng một lúc (được chia thành 4 nhóm). Phương pháp xử lý này vẫn duy trì ý tưởng sắp xếp cơ số nhưng sử dụng phương pháp gần với các phép toán bit phần cứng hơn, hiệu quả hơn nhiều so với số thập phân và có hiệu quả xử lý cao.

void radixSortBinary(vector& arr) { const int BITS = 32; const int RADIX = 256; // Xử lý 8 bit mỗi lần const int MASK = RADIX - 1 vector buffer(arr.size() ) ; // Bốn vòng lặp, xử lý 0 - 7, 8 - 15, 16 - 23, 24 - 32 bit. Kích thước số đếm cũng được tăng lên 256 for (int shift = 0; shift < BITS; shift += 8) { array count = {0}; for (uint32_t num : arr) count[(num >> shift) & MASK]++; for (int i = 1; i < RADIX; i++) count[i] += count[i - 1]; for (int i = arr.size() - 1; i >= 0; i--) { uint32_t xô = (arr[i] >> shift) & MASK; buffer[--count[bucket]] = arr[i] } arr.swap(buffer); int main() { vector mảng = {170, 45, 75, 90, 802, 24, 2, 66}; radixSortBinary(arr); cho (uint32_t num : arr) cout << num << " }

Tổng các chữ số được xử lý mỗi lần

Ví dụ trên xử lý các số nguyên 32 bit và sắp xếp chúng bốn lần, tám bit một lần. Gọi độ rộng bit của nó là 8. Trên thực tế, bạn cũng có thể chọn sắp xếp 16 bit cùng một lúc và sắp xếp hai lần, điều này có thể giảm một nửa số vòng. Tuy nhiên, việc tạo 65536 nhóm có thể gây ra áp lực bộ nhớ và hiệu quả giảm khi các nhóm được phân bổ không đều: nếu việc phân phối dữ liệu tập trung cao độ, một số Nhóm có thể lớn, gây ra hoạt động không đồng đều. Nếu độ rộng bit chỉ là 4 thì phạm vi phân nhóm nhỏ, quá trình phân nhóm và hợp nhất tương đối nhanh, nhưng số lần sắp xếp quá nhiều, phù hợp với các mảng quy mô nhỏ hoặc các tình huống có bộ nhớ hạn chế.

Open width architecture

Sắp xếp cơ số và sắp xếp nhanh

Sắp xếp cơ số và sắp xếp nhanh là hai thuật toán sắp xếp cổ điển, phù hợp với các tình huống khác nhau. Sắp xếp cơ số là một thuật toán sắp xếp không so sánh dựa trên đặc điểm chữ số của các số. Nó đạt được thứ tự theo cách nhóm và sắp xếp bit. Nó phù hợp để xử lý số hoặc chuỗi có độ dài cố định và có độ phức tạp thời gian tuyến tính \(O(n \cdot). d) \) (trong đó \(d\) là số chữ số). Nó hoạt động tốt với dữ liệu có kích thước dữ liệu lớn hơn và phạm vi giá trị nhỏ hơn nhưng cần thêm không gian để lưu trữ các nhóm. Ngược lại, sắp xếp nhanh là thuật toán chia để trị dựa trên so sánh cổ điển nhất. Nó chia mảng thành hai phần để sắp xếp đệ quy bằng cách chọn một giá trị trục (pivot). N)\ ). Quicksort cực kỳ hiệu quả trong hầu hết các trường hợp, hoạt động tốt với các loại dữ liệu phổ biến và cần ít không gian bổ sung hơn để sắp xếp tại chỗ, nhưng hiệu suất của nó có thể bị suy giảm do lựa chọn điểm chuẩn kém. Nói tóm lại, sắp xếp cơ số phù hợp với dữ liệu có cấu trúc cụ thể (chẳng hạn như số nguyên hoặc chuỗi), trong khi sắp xếp nhanh thì tổng quát hơn và phù hợp với nhiều loại và kích cỡ dữ liệu đầu vào khác nhau.

Sắp xếp cơ số và sắp xếp nhóm

Mặc dù sắp xếp cơ số và sắp xếp nhóm đều là các thuật toán sắp xếp không so sánh dựa trên việc nhóm, nhưng mục tiêu và phương pháp triển khai của chúng là khác nhau và sắp xếp cơ số có thể được coi là một phần mở rộng của sắp xếp nhóm. Sắp xếp nhóm phân phối dữ liệu vào một số nhóm giới hạn, sắp xếp từng nhóm (thường sử dụng phương pháp sắp xếp chèn hoặc các thuật toán khác) và cuối cùng hợp nhất nội dung nhóm để có được kết quả sắp xếp. Nó chủ yếu dựa vào đặc điểm phân phối của dữ liệu. phù hợp với các tình huống trong đó dữ liệu được phân bổ đồng đều và độ phức tạp về thời gian gần bằng \(O(n)\). Về cơ bản, sắp xếp cơ số có thể được coi là nhiều vòng sắp xếp nhóm: khi phạm vi giá trị rất lớn, nó dần dần đạt được thứ tự chung cuối cùng bằng cách chia và sắp xếp nhiều nhóm theo bit (chẳng hạn như hàng đơn vị, hàng chục, v.v.). Ý tưởng cốt lõi của việc sắp xếp cơ số là giải quyết vấn đề một nhóm không thể xử lý dữ liệu nhiều bit bằng cách nhóm nhiều lần. Do đó, có thể hiểu nó là một thiết kế mở rộng của sắp xếp cơ số sang sắp xếp nhóm, được sử dụng để xử lý dữ liệu có tính năng nhiều bit như số và chuỗi có độ dài cố định.

Sắp xếp cơ số được áp dụng cho số không nguyên

Trong một số trường hợp, sắp xếp cơ số có thể được mở rộng sang các cấu trúc và số không nguyên (chẳng hạn như số dấu phẩy động), nhưng dữ liệu cần phải được xử lý trước đúng cách để làm cho các đặc tính của nó phù hợp với cơ chế sắp xếp cơ số. Dưới đây là những ý tưởng chính để triển khai các tiện ích mở rộng này:

---

1. Xử lý số dấu phẩy động

Mã bit dấu phẩy động có một thuộc tính đặc biệt: định dạng IEEE 754 đảm bảo rằng đối với các số dương từ nhỏ đến lớn, mẫu bit tăng đơn điệu từ nhỏ đến lớn. Do đó, mẫu bit của số dấu phẩy động có thể được hiểu trực tiếp dưới dạng số nguyên không dấu và sau đó được sắp xếp theo số nguyên. Nói cách khác, nếu dấu không được xem xét thì nó có thể được coi trực tiếp là sắp xếp số nguyên.

void radixSortFloat(vector& arr) { vector bitPattern(arr.size()); // Giải thích các số có dấu phẩy động là số nguyên không dấu, giả sử rằng các số có dấu phẩy động đều là số dương. for (size_t i = 0; i < arr.size(); ++i) { memcpy(&bitPattern[i], &arr[i], sizeof(float)); } // Sắp xếp các số nguyên không dấu radixSort(bitPattern.begin( ), bitPattern.end()); // Sau khi sắp xếp xong, nó được khôi phục về số dấu phẩy động cho (size_t i = 0; i < arr.size(); ++i) { memcpy(&arr[i], &bitPattern[i], sizeof(float));

---

2. Cấu trúc xử lý

Việc sắp xếp cơ số có thể phân chia các từ khóa một cách tự nhiên. Đối với các cấu trúc, bài toán sắp xếp cấu trúc có thể được chuyển thành việc sắp xếp các khóa này bằng cách chọn một hoặc nhiều giá trị khóa (trường) làm cơ sở để sắp xếp.

Ví dụ: đối với một mảng cấu trúc chứa các trường tuổi và mức lương:

struct Nhân viên { int tuổi;

Nếu tuổi là từ khóa đầu tiên và cả hai thuộc tính đều là số dương, bạn có thể trực tiếp chia toàn bộ cấu trúc thành các độ rộng bit và thực hiện sắp xếp cơ số.

Cuối cùng, bài viết giải thích chi tiết về cách sắp xếp cơ số kết thúc ở đây. Nếu bạn muốn biết thêm về lời giải thích chi tiết về cách sắp xếp cơ số, vui lòng tìm kiếm bài viết CFSDN hoặc tiếp tục duyệt các bài viết liên quan. Tôi hy vọng bạn sẽ ủng hộ blog của tôi trong tương lai. ! .