form1.cs

求第k个最小值问题

using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Text;
using System.Windows.Forms;

namespace 求第k个最小值
{
    public partial class Form1 : Form
    {
        public Form1()
        {
            InitializeComponent();
        }

        private void button1_Click(object sender, EventArgs e)
        {
            //初始化输入数组%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
            //this.listBox1.Items.Clear();
            if (textBox2.Text == "" || textBox1.Text == "")
                MessageBox.Show("输入数据和第k个最小元素的值不能为空，请输入值");

            //char sss = Convert.ToChar(textBox2.Text.ToString());
            char ss = Convert.ToChar(textBox2.Text.ToString());
            if (ss < '0' || ss > '9')
                MessageBox.Show("第k个最小元素的值必须是数字，请重新输入");

            string str = textBox1.Text.ToString();
            int k = Convert.ToInt32(textBox2.Text.ToString());//找第k个最小元素
            str = str.Replace(" ", "#");
            string[] str1 = str.Split('#');
            string[] s = new string[str1.Length];
            int x;//结果

            int n = 0;
            for (int i = 0; i < str1.Length; i++)
            {
                if (str1[i] != "")
                {
                    s[n] = str1[i];
                    n++;
                }

                //if (str1[i] == ""&&str1[i+1]!="")
                //{
                //    s[n] = str1[i + 1];
                //    n++;
                //}

            }
            int[] a = new int[n + 1];
            for (int i = 0; i < n; i++)
            {
                int j = int.Parse(s[i].Trim());
                a[i] = j;
                // listBox1.Items.Add(a[i].ToString());
            }
            //找一个随机分界点r，并以其为界线做快速排序
            if (n < k)
                MessageBox.Show("输入值的个数不超过k个，不存在第k个最小数");
            if (n == k && k == 1)
                MessageBox.Show("输入值的个数只有1个，只存在1个最小数");
            if (n > 1)
            {
                x = H(a, 0, n, k);
                this.textBox3.Text = x.ToString();
                //int seed = n;
                //Random ra = new Random();
                //int r = ra.Next(0, seed);
                //listBox1.Items.Add(r.ToString());

                //if (k == r + 1)//要求的数的位置等于分界点则返回该位置的数值，如果小于分界点，则在左边找，否则在右边找
                //{ }
            }

        }

        private void button2_Click(object sender, EventArgs e)
        {
            this.Close();
        }

        private int H(int[] a, int p, int q, int k)
        {
            // int i=rand(a,p,q,k);
            //int j = i - p + 1;
            //if (k <= j) 
            //    return rand(a, p, i - 1, k);
            //else 
            //    return rand(a, i + 1, q, k - j);
            int r = partition(a, p, q, k);
            while (true)
            {
                if (r == k)
                {
                    return a[k];
                }
                else
                {
                    if (r < k)
                    {
                        p = r + 1;
                    }
                    else
                    {
                        q = r - 1;
                    }
                    r = partition(a, p, q, k);
                }
            }

        }

        private void swap(int[] a, int p, int r)
        {
            int temp = a[p];
            a[p] = a[r];
            a[r] = temp;
        }

        private int partition(int[] a, int p, int q, int k)
        {
            int i = p, j = q + 1;
            int x = a[p];
            // 将< x的元素交换到左边区域
            // 将> x的元素交换到右边区域
            while (true)
            {
                while (a[++i] < x && i < q) ;
                while (a[--j] > x) ;
                if (i >= j) break;
                swap(a, i, j);
            }
            a[p] = a[j];
            a[j] = x;
            return j;

        }
    }
}