c#实现最简洁的快速排序(你绝对可以看懂)

前言

算法对于程序员的重要性不言而喻,今天我和大家分享算法中的一个基础算法,快速排序。作为一名程序员,相信大家都不陌生,但是要大家徒手一次性写出来,我估计还是有难度的。那么废话不多少,我先简单减少一下概念。

快速排序算法说明:

原始数组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现在这么火,代码真的简单。但是最为程序员,我们始终要记住,语言只是工具,我们才是语言的主宰。了解代码背后的思想才是王道!

总结

以上就是这篇文章的全部内容了,希望本文的内容对大家的学习或者工作具有一定的参考学习价值,谢谢大家对我们的支持。

(0)

相关推荐

  • 逐步讲解快速排序算法及C#版的实现示例

    算法思想 快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序.它采用了一种分治的策略,通常称其为分治法(Divide-and-ConquerMethod). 该方法的基本思想是: 1.先从数列中取出一个数作为基准数. 2.分区过程,将比这个数大的数全放到它的右边,小于或等于它的数全放到它的左边. 3.再对左右区间重复第二步,直到各区间只有一个数. 虽然快速排序称为分治法,但分治法这三个字显然无法很好的概括快速排序的全部步骤.因此我的对快速排序作了进一步的说明:挖坑填数+分治法:

  • C#实现冒泡排序算法的代码示例

    1.原理:从数组的第一个位置开始两两比较array[index]和array[index+1],如果array[index]大于array[index+1]则交换array[index]和array[index+1]的位置,止到数组结束; 从数组的第一个位置开始,重复上面的动作,止到数组长度减一个位置结束; 从数组的第一个位置开始,重复上面的动作,止到数组长度减二个位置结束; .... 2.时间复杂度:O(N²),进行了(n-1)*(n-2)....=n*(n-1)/2次比较和约比较次数一半的交

  • C#七大经典排序算法系列(上)

    今天是开篇,得要吹一下算法,算法就好比程序开发中的利剑,所到之处,刀起头落. 针对现实中的排序问题,算法有七把利剑可以助你马道成功. 首先排序分为四种: 交换排序: 包括冒泡排序,快速排序. 选择排序: 包括直接选择排序,堆排序. 插入排序: 包括直接插入排序,希尔排序. 合并排序: 合并排序. 那么今天我们讲的就是交换排序,我们都知道,C#类库提供的排序是快排,为了让今天玩的有意思点, 我们设计算法来跟类库提供的快排较量较量.争取KO对手. 冒泡排序: 首先我们自己来设计一下"冒泡排序&quo

  • C#排序算法之快速排序

    快速排序实现: 复制代码 代码如下: namespace QuickSort { class QuickSort { public static void Sort(int[] array) { DoSort(array,0, array.Length-1); } private static void DoSort( int[] array, int start, int end) { if( start < end) { int temp = Partition(array, start,

  • C# 排序算法之堆排序

    一.基本概念 堆:这里是指一种数据结构,而不是我们在C#中提到的用于存储引用类型对象的地方.它可以被当成一棵完全二叉树.  为了将堆用数组来存放,这里对每个节点标上顺序.事实上,我们可以用简单的计算公式得出父节点,左孩子,右孩子的索引: parent(i) = left(i) = 2i right(i)=2i + 1 最大堆和最小堆: 最大堆是指所有父节点的值都大于其孩子节点的堆,即满足以下公式: A[parent[i]]A[i](A是指存放该堆的数组) 最小堆相反. 最大堆和最小堆是堆排序的关

  • C#中使用基数排序算法对字符串进行排序的示例

    开始之前 假设最长字符串的长度是L,以L作为输入的长度, 然后假定所有的字符串都"补齐"到此长度,这个补齐只是逻辑上的,我们可以假想有一种"空字符", 它小于任何其它字符,用此字符补齐所有长度不足的字符串.例如:最长的字符串长度为9,有一个字符串A长度为6, 那么当比较第7位字符的时候,我们让A[7]为"空字符". 如果要包含所有的字符似乎并不容易,我们先定义一个字符集, 待排序字符串中的所有字符都包含在这个字符集里 //字符集 private

  • c# 快速排序算法

    快速排序使用分治法(Divide and conquer)策略来把一个串行(list)分为两个子串行(sub-lists). 步骤为: 1.从数列中挑出一个元素,称为 "基准"(pivot), 2.重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边).在这个分区退出之后,该基准就处于数列的中间位置.这个称为分区(partition)操作. 3.递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序. 递归

  • c# 冒泡排序算法(Bubble Sort) 附实例代码

    冒泡排序(Bubble Sort) 冒泡排序算法的运作如下: 1.比较相邻的元素.如果第一个比第二个大,就交换他们两个.2.对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对.在这一点,最后的元素应该会是最大的数.3.针对所有的元素重复以上的步骤,除了最后一个.4.持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较. 平均时间复杂度 复制代码 代码如下: /// <summary> /// 冒泡排序 /// </summary> /// <param

  • C#几种排序算法

    作者:Sabine [导读]本文介绍了C#的四种排序算法:冒泡排序.选择排序.插入排序和希尔排序 冒泡排序 using System: namespace BubbleSorter { public class BubbleSorter { public void Sort(int [] list) { int i,j,temp: bool done=false: j=1: while((j<list.Length)&&(!done)) { done=true: for(i=0:i&

  • C#实现的二维数组排序算法示例

    本文实例讲述了C#实现的二维数组排序算法.分享给大家供大家参考,具体如下: class Order { /// <summary> /// 对二维数组排序 /// </summary> /// <param name="values">排序的二维数组</param> /// <param name="orderColumnsIndexs">排序根据的列的索引号数组</param> /// <

随机推荐