快速排序思想找出中位数

佚名 6年前 (2019-04-18) 随笔 2132人围观抢沙发百度已收录

    class Program
    {


        static void Main(string[] args)
        {


            int[] arr = arrInsert(100000000);
            double mid = medium(arr, arr.Length-1);



            Console.Write(mid);

            Console.ReadKey();
        }

        static  int quick_sort(int[] a ,int left,int right)
        {
            if(left>right)
            {
                return 0;
            }    
            int i,j,t,key;
            key=a[left];
            i=left;
            j=right;
            while(i!=j)
            {
                while(i<j&&a[j]>=key)
                {
                  j--;
                }
       
                while(i<j&&a[i]<=key)
                {
                    i++;
                }
                if(i<j)
                {
                    t=a[i];
                    a[i]=a[j];
                    a[j]=t;
                }
            }
            a[left]=a[i];
            a[i]=key;
            return i;
        }
    static  double medium(int[] a,int n)
    {
        int left=0;
        int right=n;
        int mid=(left+right)/2;
        int num;
        while(true)
        {
            num=quick_sort(a,left,right);
            if(num==mid)
            {
              break;
            }     
            if(num<mid)
            {
              left=num+1;
            }
            if(num>mid)
            {
              right=num-1;
            }     
        }
        return (n%2==0)?a[mid]:(double)(a[mid]+a[mid+1])/2;
    }


    static int[] arrInsert(int count)
    {
        int[] arr = new int[count];
        Random r1 = new Random();
        int i = 0;
        while (i < count)
        {
            int num = r1.Next(0, 10000);
            arr[i] = num;
            i++;
        }
        return arr;
    }

   
    }