c#完成最简疾速排序,你相对能够看懂

2019年7月2日10:56:09c#完成最简疾速排序,你相对能够看懂已关闭评论 1,092

原创文章,转载请申明出处

 算法关于程序员的重要性显而易见,本日我和人人分享算法中的一个基础算法,疾速排序。作为一位程序员,置信人人都不生疏,然则要人人徒手一次性写出来,我预计照样有难度的。那末空话不若干,我先简朴削减一下观点。

疾速排序算法申明:

原始数组L1,从中恣意挑选一个基准数F(一样平常挑选第1个),小于F的数据放在F的左侧记为数组minList,大于F的数据放在F的右侧记为数组maxList。那末

L1=minList+F+maxList

然后对minList和maxList再做如许的操纵,直到minList和maxList中的元素个数为1或许0的时刻住手

一、C#网上如今最简约的完成体式格局:

  如今就是要举行算法的完成了,很明显,这里要用到一个叫递归的头脑。我们晓得编程言语学问东西,算法才是中心,然则分歧的编程言语完成算法却有很大的分歧(简约水平)。如今网上关于c#的完成疾速排序的体式格局有许多,简朴查阅了一下,发明一样平常都要100行代码摆布(c和c++的代码行数要少一些)。千找万找,终究找到了一个,贴出以下:

        static void QuickSort(ref List<int> nums, int left, int right)
        {
            if (left < right)
            {
                int i = left;
                int j = right;
                int middle = nums[(left + right) / 2];
                while (true)
                {
                    while (i < right && nums[i] < middle) { i++; };
                    while (j > 0 && nums[j] > middle) { j--; };
                    if (i == j) break;
                    int temp = nums[i];
                    nums[i] = nums[j];
                    nums[j] = temp;
                    if (nums[i] == nums[j]) j--;
                }
                QuickSort(ref nums, left, i);
                QuickSort(ref nums, i + 1, right);
            }
        }

然则说真的,很难读懂,真要在考场上写出这个代码,难保能一次写对。

 

二、python的完成体式格局:

python我也有打仗,以是当我用python写出这个算法的代码的时刻,真的有种觉得,真是太TM简朴了吧,有编程履历的同砚应当也能看懂下面的python代码

def quicksort(array):   
    if len(array) < 2:     
        return array  ------基线前提:为空或只包罗一个元素的数组是“有序”的   
    else:     
        pivot = array[0]  ------递归前提
        less = [i for i in array[1:] if i <= pivot]  ------由一切小于基准值的元素构成的子数组     
        greater = [i for i in array[1:] if i > pivot]  ------由一切大于基准值的元素构成的子数组     
    return quicksort(less) + [pivot] + quicksort(greater) 
print quicksort([10, 5, 2, 3])

短短几行代码,清楚清楚明了。重要的代码就是数组能够直接相加运算:quicksort(less) + [pivot] + quicksort(greater) 

 

三、C#本身完成最浅易体式格局

那岂非我们c#就只能写出难明又多的代码能力完成吗?终究让我也找到了,下面贴出我本身写的c#代码:

    public class Extend :List<int>
    {
        public static Extend operator +(Extend L1, Extend L2)
        {
            L1.AddRange(L2);
            return L1;
        }
    }

        static Extend QuickSort2(Extend nums)
        {
            if (nums.Count < 2)
            {
                return nums;
            }
            else
            {
                Extend minList = new Extend();//小于基准数的鸠合
                Extend maxList = new Extend();//大于基准数的鸠合
                int f = nums[0];
                for (int i = 1; i < nums.Count; i++)
                {
                    if (nums[i] <= f) minList.Add(nums[i]);
                    else maxList.Add(nums[i]);
                }
                return QuickSort2(minList) + new Extend() { f} + QuickSort2(maxList);//递归,而且运用+运算符
            }
        }

实际上就只要两步操纵,就完成了和python一样的简约!

第一:新建一个Extend 类继续于List<int>

第二:重写了+运算符

有同砚对Extend类中的AddRange要领提出了内存上的质疑,我也举行了复兴,算法是对时间复杂度的考核,也就是对历程的考核。内存斲丧依据分歧的代码肯定会有所分歧,然则不影响算法。固然我也对Extend举行了革新,由于实际上终究的加法运算中,minList和maxList都只要一个元素,或许没有元素。

    public class Extend :List<int>
    {
        private static Extend k = new Extend();
        
        public static Extend operator +(Extend L1, Extend L2)
        {
            if (L1.Count == 1) k.Add(L1[0]);
            if (L2.Count == 1) k.Add(L2[0]);
            return k;
            //L1.AddRange(L2);
            //return L1;
        }
    }

 

其他的和python的代码基础一致,代码清楚清楚明了。

据我视察,c#经由过程我这类体式格局完成的,如今独此一份,收好不谢!末了我照样要吐槽一句,怪不得python如今这么火,代码真的简朴。然则最为程序员,我们一直要记着,言语只是东西,我们才是言语的主宰。相识代码背地的头脑才是霸道!

 

avatar