Binsort桶排序实例

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
{
    classCell
    {
        publicint Value;
        public Cell Next = null;
        // Constructors.
        publicCell(int value)
        {
            Value = value;
        }
        publicCell()
        {
        }
    }
    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(1000).ToArray();
            sortButton.Enabled = true;
        }
 
        // Sort the items.
        privatevoid sortButton_Click(object sender, EventArgs e)
        {
            itemsListBox.DataSource = null;
            int numBuckets = int.Parse(numBucketsTextBox.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(1000).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;
                }
            }
        }
 
        // Use insertionsort to sort the list.
        private Cell Insertionsort(Cell input)
        {
            // Make a sentinel for the sorted list.
            Cell sentinel = new Cell();
            sentinel.Next = null;
 
            // Skip the input list's sentinel.
            // Commented out because this list doesn't have a sentinel.
            //input = input.Next;
 
            // Repeat until we have inserted all of the items in the new list.
            while (input != null)
            {
                // Get the next cell to add to the list.
                Cell nextCell = input;
 
                // Move input to input.Next for the next trip through the loop.
                input = input.Next;
 
                // See where to add the next item in the sorted list.
                Cell afterMe = sentinel;
                while ((afterMe.Next != null) &&
                      (afterMe.Next.Value < nextCell.Value))
                {
                    afterMe = afterMe.Next;
                }
 
                // Insert the item in the sorted list.
                nextCell.Next = afterMe.Next;
                afterMe.Next = nextCell;
            }
 
            // Return the sorted list.
            // Skip the sentinel for this program.
            return sentinel.Next;
        }
    }
}
 
namespace Bucketsort
{
    staticclassProgram
    {
        ///<summary>
        /// The main entry point for the application.
        ///</summary>
        [STAThread]
        staticvoid Main()
        {
            Application.EnableVisualStyles();
            Application.SetCompatibleTextRenderingDefault(false);
            Application.Run(new Form1());
        }
    }
}

效果图:

在实际应用中数据项与桶数的比例不能大,否则算法效率不高。

Tags: , , , ,

IT技术

Add comment

  Country flag

biuquote
微笑得意调皮害羞酷大笑惊讶发呆喜欢可怜尴尬闭嘴噘嘴皱眉伤心抓狂呕吐坏笑漫骂发怒
Loading