前言

算法對(duì)于程序員的重要性不言而喻，今天我和大家分享算法中的一個(gè)基礎(chǔ)算法，快速排序。作為一名程序員，相信大家都不陌生，但是要大家徒手一次性寫(xiě)出來(lái)，我估計(jì)還是有難度的。那么廢話不多少，我先簡(jiǎn)單減少一下概念。

快速排序算法說(shuō)明：

原始數(shù)組L1，從中任意選擇一個(gè)基準(zhǔn)數(shù)F（一般選擇第1個(gè)），小于F的數(shù)據(jù)放在F的左邊記為數(shù)組minList，大于F的數(shù)據(jù)放在F的右邊記為數(shù)組maxList。那么

L1=minList+F+maxList

然后對(duì)minList和maxList再做這樣的操作，直到minList和maxList中的元素個(gè)數(shù)為1或者0的時(shí)候停止

一、C#網(wǎng)上目前最簡(jiǎn)潔的實(shí)現(xiàn)方式：

現(xiàn)在就是要進(jìn)行算法的實(shí)現(xiàn)了，很明顯，這里要用到一個(gè)叫遞歸的思想。我們知道編程語(yǔ)言知識(shí)工具，算法才是核心，但是不同的編程語(yǔ)言實(shí)現(xiàn)算法卻有很大的不同（簡(jiǎn)潔程度）。目前網(wǎng)上對(duì)于c#的實(shí)現(xiàn)快速排序的方式有很多，簡(jiǎn)單查閱了一下，發(fā)現(xiàn)一般都要100行代碼左右（c和c++的代碼行數(shù)要少一些）。千找萬(wàn)找，終于找到了一個(gè)，貼出如下：

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);
  }
 }

但是說(shuō)真的，很難讀懂，真要在考場(chǎng)上寫(xiě)出這個(gè)代碼，難保能一次寫(xiě)對(duì)。

二、python的實(shí)現(xiàn)方式：

python我也有接觸，所以當(dāng)我用python寫(xiě)出這個(gè)算法的代碼的時(shí)候，真的有種感覺(jué)，真是太TM簡(jiǎn)單了吧，有編程經(jīng)驗(yàn)的同學(xué)應(yīng)該也能看懂下面的python代碼

def quicksort(array): 
 if len(array) < 2:  
  return array ------基線條件：為空或只包含一個(gè)元素的數(shù)組是“有序”的 
 else:  
  pivot = array[0] ------遞歸條件
  less = [i for i in array[1:] if i <= pivot] ------由所有小于基準(zhǔn)值的元素組成的子數(shù)組  
  greater = [i for i in array[1:] if i > pivot] ------由所有大于基準(zhǔn)值的元素組成的子數(shù)組  
 return quicksort(less) + [pivot] + quicksort(greater) 
print quicksort([10, 5, 2, 3])

短短幾行代碼，清晰明了。主要的代碼就是數(shù)組可以直接相加運(yùn)算：quicksort(less) + [pivot] + quicksort(greater)

三、C#自己實(shí)現(xiàn)最簡(jiǎn)易方式

那難道我們c#就只能寫(xiě)出難懂又多的代碼才能實(shí)現(xiàn)嗎？終于讓我也找到了，下面貼出我自己寫(xiě)的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();//小于基準(zhǔn)數(shù)的集合
    Extend maxList = new Extend();//大于基準(zhǔn)數(shù)的集合
    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);//遞歸，并且使用+運(yùn)算符
   }
  }

實(shí)際上就只有兩步操作，就實(shí)現(xiàn)了和python一樣的簡(jiǎn)潔！

第一：新建一個(gè)Extend 類繼承于List<int>

第二：重寫(xiě)了+運(yùn)算符

有同學(xué)對(duì)Extend類中的AddRange方法提出了內(nèi)存上的質(zhì)疑，我也進(jìn)行了回復(fù)，算法是對(duì)時(shí)間復(fù)雜度的考察，也就是對(duì)過(guò)程的考察。內(nèi)存消耗根據(jù)不同的代碼肯定會(huì)有所不同，但是不影響算法。當(dāng)然我也對(duì)Extend進(jìn)行了改進(jìn)，因?yàn)閷?shí)際上最終的加法運(yùn)算中，minList和maxList都只有一個(gè)元素，或者沒(méi)有元素。

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的代碼基本一致，代碼清晰明了。

據(jù)我觀察，c#通過(guò)我這種方式實(shí)現(xiàn)的，目前獨(dú)此一份，收好不謝！最后我還是要吐槽一句，怪不得python現(xiàn)在這么火，代碼真的簡(jiǎn)單。但是最為程序員，我們始終要記住，語(yǔ)言只是工具，我們才是語(yǔ)言的主宰。了解代碼背后的思想才是王道！

總結(jié)

以上就是這篇文章的全部?jī)?nèi)容了，希望本文的內(nèi)容對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，謝謝大家對(duì)腳本之家的支持。

最新評(píng)論