posted at 2022.1.10 12:05 by Administrator
Binsort桶排序算法（bucketsort algorithm）的工作原理是将数据项装入桶进行排序的算法，桶可以是堆栈、链表、队列、数组或者任何其他合适的数据结构。
C#实例如下：
<supportedRuntimeversion="v4.0"sku=".NETFramework,Version=v4.5" />
using System.Data;using System.Drawing;using System.Linq;using System.Text;using System.Threading.Tasks;using System.Windows.Forms; using System.Diagnostics; namespace Bucketsort{ publicpartialclassForm1 : Form { publicForm1() { InitializeComponent(); } // The items. privateint[] Items; // The largest item in the array. privateint MaxValue; // Make random items. privatevoid generateButton_Click(object sender, EventArgs e) { itemsListBox.DataSource = null; int numItems = int.Parse(numItemsTextBox.Text); Items = newint[numItems]; Random rand = new Random(); MaxValue = int.Parse(maxItemTextBox.Text); for (int i = 0; i < numItems; i++) Items[i] = rand.Next(0, MaxValue + 1); itemsListBox.DataSource = Items.Take(numItems).ToArray(); sortButton.Enabled = true; } // Sort the items. privatevoid sortButton_Click(object sender, EventArgs e) { itemsListBox.DataSource = null; int numBuckets = int.Parse(numBucketsTextBox.Text); int numItems = int.Parse(numItemsTextBox.Text); // Sort. DateTime startTime = DateTime.Now; Bucketsort(Items, MaxValue, numBuckets); DateTime stopTime = DateTime.Now; TimeSpan elapsed = stopTime - startTime; Console.WriteLine(elapsed.TotalSeconds.ToString("0.00") + " seconds"); // Validate the sort. for (int i = 1; i < Items.Length; i++) Debug.Assert(Items[i] >= Items[i - 1]); itemsListBox.DataSource = Items.Take(numItems).ToArray(); } // Use bucketsort to sort the array. privatevoid Bucketsort(int[] values, int max, int numBuckets) { // Make buckets. Cell[] buckets = new Cell[numBuckets]; // Create bucket sentinels. for (int i = 0; i < numBuckets; i++) buckets[i] = new Cell(); // Calculate the number of values per bucket. float itemsPerBucket = (max + 1f) / numBuckets; // Distribute. for (int i = 0; i < values.Length; i++) { // Calculate the bucket number. int value = values[i]; int num = (int)(value / itemsPerBucket); // Insert the item in this bucket. Cell afterMe = buckets[num]; while ((afterMe.Next != null) && (afterMe.Next.Value < value)) afterMe = afterMe.Next; Cell cell = new Cell(value); cell.Next = afterMe.Next; afterMe.Next = cell; } // Gather the values back into the array. int index = 0; for (int i = 0; i < numBuckets; i++) { // Copy the values in bucket i into the array (skipping the sentinel). Cell cell = buckets[i].Next; while (cell != null) { values[index] = cell.Value; index++; cell = cell.Next; } } } } classCell { publicint Value; public Cell Next = null; // Constructors. publicCell(int value) { Value = value; } publicCell() { } } } namespace Bucketsort{ staticclassProgram { ///<summary> /// The main entry point for the application. ///</summary> [STAThread] staticvoid Main() { Application.EnableVisualStyles(); Application.SetCompatibleTextRenderingDefault(false); Application.Run(new Form1()); } }}
效果图：
在实际应用中数据项与桶数的比例不能大，否则算法效率不高。
4244c799-6f4b-40fd-85df-a44f5eaa190a|0|.0|96d5b379-7e1d-4dac-a6ba-1e50db561b04
Tags: app, C#, 数据, 数据结构, 算法
IT技术
