Làm cách nào để sắp xếp một chuỗi các chuỗi?

Question

Tôi có một danh sách các từ nhập được phân tách bằng dấu phẩy. Tôi muốn sắp xếp các từ này theo thứ tự chữ cái và độ dài. Làm thế nào tôi có thể làm điều này mà không cần sử dụng các chức năng sắp xếp sẵn có?

Answer 1

Câu hỏi hay !! Phân loại có lẽ là khái niệm quan trọng nhất để học như một nhà khoa học máy tính hiện tại.

Thực tế có rất nhiều thuật toán khác nhau để sắp xếp danh sách.

Khi bạn chia nhỏ tất cả các thuật toán đó xuống, thao tác cơ bản nhất là so sánh hai mục trong danh sách, xác định "thứ tự tự nhiên" của chúng.

Ví dụ, để sắp xếp một danh sách các số nguyên, tôi cần một chức năng mà nói với tôi, đưa ra bất kỳ hai số nguyên X và Y dù X nhỏ hơn, bằng hoặc lớn hơn Y.

Đối với các chuỗi của bạn, bạn sẽ cần một điều tương tự: một hàm cho bạn biết chuỗi nào có giá trị "nhỏ hơn" hoặc "lớn hơn" hoặc chúng có bằng nhau hay không.

Theo truyền thống, những "so sánh" chức năng giống như thế này:

int CompareStrings(String a, String b) { 
    if (a < b) 
     return -1; 
    else if (a > b) 
     return 1; 
    else 
     return 0; 
} 

tôi đã rời ra một số chi tiết (như, làm thế nào để bạn tính toán cho dù a nhỏ hơn hoặc lớn hơn b đầu mối? : lặp qua các ký tự), nhưng đó là bộ xương cơ bản của bất kỳ hàm so sánh nào. Nó trả về một giá trị nhỏ hơn 0 nếu phần tử đầu tiên nhỏ hơn và giá trị lớn hơn 0 nếu phần tử đầu tiên lớn hơn, trả về số không nếu các phần tử có giá trị bằng nhau.

Nhưng điều đó có liên quan gì đến việc sắp xếp?

Định tuyến sắp xếp sẽ gọi hàm đó cho các cặp phần tử trong danh sách của bạn, sử dụng kết quả của hàm để tìm hiểu cách sắp xếp lại các mục vào danh sách được sắp xếp. Hàm so sánh xác định "thứ tự tự nhiên" và "thuật toán sắp xếp" xác định logic để gọi và trả lời kết quả của hàm so sánh.

Mỗi thuật toán giống như một chiến lược hình ảnh lớn để đảm bảo rằng bất kỳ đầu vào nào sẽ được sắp xếp chính xác. Dưới đây là một vài trong số các thuật toán mà có thể bạn sẽ muốn biết về:

Bubble Sort:

Duyệt qua danh sách, gọi hàm so sánh cho tất cả các cặp liền kề của các yếu tố. Bất cứ khi nào bạn nhận được kết quả lớn hơn 0 (có nghĩa là phần tử đầu tiên lớn hơn giá trị thứ hai), hãy hoán đổi hai giá trị. Sau đó chuyển sang cặp tiếp theo. Khi bạn đến cuối danh sách, nếu bạn không phải trao đổi BẤT K pairs cặp nào, thì xin chúc mừng, danh sách được sắp xếp! Nếu bạn DID phải thực hiện bất kỳ giao dịch hoán đổi nào, hãy quay lại phần đầu và bắt đầu lại. Lặp lại quá trình này cho đến khi không có nhiều hoán đổi. LƯU Ý: đây thường không phải là cách rất hiệu quả để sắp xếp danh sách, vì trong trường hợp xấu nhất, nó có thể yêu cầu bạn quét toàn bộ danh sách nhiều lần bằng N lần, với danh sách có phần tử N.

Merge Sắp xếp:

Đây là một trong những thuật toán chia-và-chinh phục phổ biến nhất để phân loại một danh sách. Ý tưởng cơ bản là, nếu bạn có hai danh sách đã được sắp xếp, thật dễ dàng để hợp nhất chúng. Chỉ cần bắt đầu từ đầu mỗi danh sách và xóa phần tử đầu tiên của danh sách bất kỳ có giá trị bắt đầu nhỏ nhất. Lặp lại quá trình này cho đến khi bạn đã tiêu thụ tất cả các mục từ cả hai danh sách và sau đó bạn đã hoàn tất!

1  4  8  10  
    2  5 7  9 
------------ becomes ------------> 
1 2 4 5 7 8 9 10 

Nhưng nếu bạn không có hai danh sách được sắp xếp thì sao? Điều gì sẽ xảy ra nếu bạn chỉ có một danh sách và các thành phần của nó theo thứ tự ngẫu nhiên?

Đó là điều thông minh về sắp xếp hợp nhất. Bạn có thể chia nhỏ bất kỳ danh sách nào thành các phần nhỏ hơn, mỗi danh sách hoặc là một danh sách chưa được sắp xếp, một danh sách được sắp xếp hoặc một phần tử duy nhất (nếu bạn quan tâm đến nó, thực sự là một danh sách được sắp xếp, với độ dài = 1). Vì vậy, bước đầu tiên trong thuật toán sắp xếp hợp nhất là chia danh sách tổng thể của bạn thành các danh sách phụ nhỏ hơn và nhỏ hơn, Ở cấp độ nhỏ nhất (trong đó mỗi danh sách chỉ có một hoặc hai phần tử), chúng rất dễ sắp xếp. Và một khi được sắp xếp, thật dễ dàng để hợp nhất bất kỳ hai danh sách được sắp xếp liền kề nào thành một danh sách được sắp xếp lớn hơn chứa tất cả các phần tử của hai danh sách phụ.

LƯU Ý: Thuật toán này là nhiều tốt hơn phương pháp sắp xếp bong bóng, được mô tả ở trên, về hiệu quả trường hợp xấu nhất. Tôi sẽ không đi vào một lời giải thích chi tiết (liên quan đến một số thuật toán khá tầm thường, nhưng sẽ mất chút thời gian để giải thích), nhưng lý do nhanh chóng cho hiệu quả tăng lên là thuật toán này phá vỡ vấn đề của nó thành các khối có kích thước lý tưởng và sau đó hợp nhất kết quả của những khối đó. Thuật toán sắp xếp bong bóng giải quyết toàn bộ vấn đề cùng một lúc, vì vậy nó không nhận được lợi ích của "phân chia và chinh phục".

---

Những người chỉ là hai thuật toán để phân loại một danh sách, nhưng có rất nhiều các kỹ thuật thú vị khác, đều có ưu và nhược điểm riêng của nó: Sắp xếp nhanh, Radix Sắp xếp, Selection Sort, Heap Sort, Shell Sắp xếp, và Sắp xếp nhóm.

Internet đang tràn đầy thông tin thú vị về sắp xếp. Đây là một nơi tốt để bắt đầu:

http://en.wikipedia.org/wiki/Sorting_algorithms

Answer 2

Có toàn bộ khu vực nghiên cứu được xây dựng xung quanh sorting algorithms. Bạn có thể muốn chọn một đơn giản và thực hiện nó.

Mặc dù nó sẽ không có hiệu suất cao nhất, nhưng bạn không nên mất quá nhiều thời gian để triển khai bubble sort.

Answer 3

Tạo ứng dụng bảng điều khiển và dán ứng dụng này vào Program.cs làm phần thân của lớp.

public static void Main(string[] args) 
{ 
    string [] strList = "a,b,c,d,e,f,a,a,b".Split(new [] { ',' }, StringSplitOptions.RemoveEmptyEntries); 

    foreach(string s in strList.Sort()) 
     Console.WriteLine(s); 
} 

public static string [] Sort(this string [] strList) 
{ 
    return strList.OrderBy(i => i).ToArray(); 
} 

Lưu ý rằng tôi sử dụng phương pháp tích hợp, OrderBy. Như câu trả lời khác chỉ ra có rất nhiều thuật toán sắp xếp khác nhau mà bạn có thể triển khai ở đó và tôi nghĩ đoạn mã của tôi sẽ làm mọi thứ cho bạn ngoại trừ thuật toán sắp xếp thực tế.

Some C# specific sorting tutorials

Answer 4

Nếu bạn không muốn sử dụng xây dựng trong chức năng, bạn phải tạo từng người tự của bạn. Tôi sẽ giới thiệu Sắp xếp bong bóng hoặc một số thuật toán tương tự. Phân loại bong bóng không phải là thuật toán hiệu quả, nhưng nó hoàn thành công việc và dễ hiểu.

Bạn sẽ tìm thấy nhiều bài đọc hay trên wikipedia.

Answer 5

Tôi khuyên bạn nên thực hiện wiki cho quicksort.

Vẫn không chắc chắn lý do tại sao bạn không muốn sử dụng loại được tích hợp sẵn?

Answer 6

Sắp xếp bong bóng làm hỏng não.

Sắp xếp chèn ít nhất là đơn giản để hiểu và mã, và thực sự hữu ích trong thực tế (đối với các tập dữ liệu rất nhỏ và dữ liệu gần như được sắp xếp). Nó hoạt động như thế này:

Giả sử rằng n mục đầu tiên đã sẵn sàng (bạn có thể bắt đầu với n = 1, vì rõ ràng là một điều riêng của nó là "theo đúng thứ tự").

Lấy mục (n + 1) trong mảng của bạn. Gọi đây là "trục". Bắt đầu với mục thứ n và làm việc:
    - nếu nó lớn hơn trục xoay, hãy di chuyển một khoảng trống sang phải (để tạo "khoảng trống" ở bên trái của nó).
    - nếu không, hãy để nguyên vị trí, đặt "trục" một không gian bên phải (nghĩa là, trong "khoảng trống" nếu bạn di chuyển bất kỳ thứ gì hoặc vị trí bắt đầu nếu bạn không chuyển gì) và dừng .

Bây giờ, mục n + 1 đầu tiên trong mảng theo thứ tự, bởi vì trục nằm ở bên phải của mọi thứ nhỏ hơn nó, và bên trái của mọi thứ lớn hơn nó. Kể từ khi bạn bắt đầu với n mục theo thứ tự, đó là tiến bộ.

Lặp lại, với n tăng 1 ở mỗi bước, cho đến khi bạn xử lý toàn bộ danh sách.

Điều này tương ứng với một cách mà bạn có thể đặt một loạt các thư mục vào một tủ hồ sơ theo thứ tự: đặt một trong; sau đó đặt một vị trí khác vào đúng vị trí của nó bằng cách đẩy mọi thứ thuộc về nó sau một khoảng trống để nhường chỗ; lặp lại cho đến khi kết thúc. Không ai bao giờ phân loại các vật thể bằng cách sắp xếp bong bóng, do đó, nó là một bí ẩn đối với tôi tại sao nó được coi là "đơn giản".

Tất cả những gì còn lại bây giờ là bạn cần có khả năng làm việc, với hai chuỗi, cho dù đầu tiên có lớn hơn giây hay không. Tôi không hoàn toàn chắc chắn những gì bạn có nghĩa là "chữ cái và chiều dài": thứ tự chữ cái được thực hiện bằng cách so sánh một nhân vật tại một thời điểm từ mỗi chuỗi. Nếu không có cùng, đó là đơn đặt hàng của bạn. Nếu chúng giống nhau, hãy xem phần tiếp theo, trừ khi bạn không có các ký tự trong một trong các chuỗi, trong trường hợp đó là chữ "nhỏ hơn".

Answer 7

Sử dụng NSort

Tôi chạy ngang qua thư viện NSort một vài năm trước đây trong cuốn sách Windows Developer Power Tools. Thư viện NSort thực hiện một số thuật toán sắp xếp. Ưu điểm chính để sử dụng một cái gì đó như NSort trên văn bản phân loại của riêng bạn là đó là đã được thử nghiệm và tối ưu hóa.

Answer 8

viết bài liên kết đến chuỗi nhanh sort code trong C#:

http://www.codeproject.com/KB/cs/fast_string_sort.aspx

điểm khác: Các so sánh gợi ý ở trên không được khuyến khích cho các ngôn ngữ không phải tiếng Anh:

int CompareStrings (String một, Chuỗi b) {
nếu (a < b) trả lại -1;
người khác nếu (a> b)
trả lại 1; else
trả lại 0; }

Thanh toán liên kết này cho loại ngôn ngữ không phải tiếng Anh:

http://msdn.microsoft.com/en-us/goglobal/bb688122

Và như đã đề cập, sử dụng nsort cho mảng thực sự khổng lồ mà không phù hợp trong bộ nhớ.