欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

C# 快速排序--二分查找法--拉格朗日插值法

程序员文章站 2022-04-08 11:37:42
1.快速排序 参考自: https://www.cnblogs.com/yundan/p/4022056.html 2.二分查找法 输出: 3.拉格朗日插值法 输出: ......

1.快速排序

 参考自: https://www.cnblogs.com/yundan/p/4022056.html

namespace 快速排序算法
{
    class program
    {
        static void main(string[] args)
        {
            console.writeline("请输入待排序数列以 , 分割");
            string _s = console.readline();
            string[] _sarray = _s.split(",".tochararray());
            int _nlength = _sarray.length;
            int[] _narray = new int[_nlength];
            for (int i = 0; i < _nlength; i++)
            {
                _narray[i] = convert.toint32(_sarray[i]);
            }

            var list = _narray.tolist();
            quicksort(list, 0, _nlength - 1);

            foreach (var i in list)
            {
                console.writeline(i.tostring());
            }
            console.readline();
        }
 
        //left为0,right为数组长度减一,即分别为数组中第一个和最后一个数的索引
        private static int division(list<int> list, int left, int right)   
        {
            while (left < right)
            {
                int num = list[left]; //将首元素作为分割位置
                if (num > list[left + 1]) //前一位 > 后一位
                {
                    list[left] = list[left + 1];  //将两处位置对调
                    list[left + 1] = num;
                    left++;
                }
                else
                {
                    int temp = list[right];
                    list[right] = list[left + 1];
                    list[left + 1] = temp;
                    right--;
                }
                console.writeline(string.join(",", list));
            }
            console.writeline("--------------\n");
            return left; //指向的此时枢轴的位置
        }
        private static void quicksort(list<int> list, int left, int right)
        {
            if (left < right)
            {
                int i = division(list, left, right);
                //对枢轴的左边部分进行排序
                quicksort(list,  i + 1, right);
                //对枢轴的右边部分进行排序
                quicksort(list, left, i - 1);
            }
        }
    }
}

2.二分查找法

namespace 二分查找法
{   
    class program
    {
      // 数组,low=0,high为数组长度减一,key为查找的数字
        public static int binarysearch(int[]arr,int low,int high,int key)
        {
            int mid = (low + high) / 2; //中间数字
            if (low > high)
            {
                return -1;     //查找不到
            }
            else
            {
                if (arr[mid] == key)
                {
                    return mid;
                }
                else if (arr[mid] > key)
                {
                    return binarysearch(arr, low, mid - 1, key);
                }
                else
                {
                    return binarysearch(arr, mid + 1, high, key);
                }
            }
        }
        static void main(string[] args)
        {
            int[] shuzu = { 1, 2, 5, 6, 8,12,16,17,17,19,21,26,28,29,34 }; //先排好大小顺序
            int high = shuzu.length - 1;
            int jieguo = binarysearch(shuzu, 0, high, 16);
            console.writeline("查找数字下标:"+jieguo);
            console.writeline("数组长度:"+shuzu.length );
            console.readline();
        }
    }
}

输出:

C# 快速排序--二分查找法--拉格朗日插值法

 

3.拉格朗日插值法

namespace 拉格朗日插值法
{
    class program
    {
        private static int cha(int[] shuzhu, int key)
        {
            int left = 0;  //数组中起始位置下标
            int right = shuzhu.length - 1; //数组最后一位下标
            int middle = -1;//查找不到
            while (left <= right)
            {
                middle = left + (right - left) * (key - shuzhu[left]) / (shuzhu[right] - shuzhu[left]);
                if (key == shuzhu[middle])
                {
                    return middle;
                }
                else if (key > shuzhu[middle])
                {
                    left = middle + 1;
                }
                else
                {
                    right = middle - 1;
                }
            }
            return -1;
        }
        static void main(string[] args)
        {
            int[] num = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ,45,46,48};
            int a = cha(num, 4);//查找数组中数值为4的下标
            console.writeline(a);
            console.readline();
        }
    }
}

输出:

C# 快速排序--二分查找法--拉格朗日插值法