欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

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

 更新時間:2017年04月14日 11:46:41   作者:一線碼農  
這篇文章主要為大家詳細介紹了C#七大經典排序算法系列上篇,冒泡排序,快速排序等,具有一定的參考價值,感興趣的小伙伴們可以參考一下

今天是開篇,得要吹一下算法,算法就好比程序開發(fā)中的利劍,所到之處,刀起頭落。 

針對現(xiàn)實中的排序問題,算法有七把利劍可以助你馬道成功。 

首先排序分為四種:

      交換排序: 包括冒泡排序,快速排序。

      選擇排序: 包括直接選擇排序,堆排序。

      插入排序: 包括直接插入排序,希爾排序。

      合并排序: 合并排序。 

那么今天我們講的就是交換排序,我們都知道,C#類庫提供的排序是快排,為了讓今天玩的有意思點,

我們設計算法來跟類庫提供的快排較量較量。爭取KO對手。 

冒泡排序:

首先我們自己來設計一下“冒泡排序”,這種排序很現(xiàn)實的例子就是:

我抓一把沙仍進水里,那么沙子會立馬沉入水底, 沙子上的灰塵會因為慣性暫時沉入水底,但是又會立馬像氣泡一樣浮出水面,最后也就真相大白咯。 

關于冒泡的思想,我不會說那么官方的理論,也不會貼那些文字上來,我的思想就是看圖說話。

那么我們就上圖.

要達到冒泡的效果,我們就要把一組數(shù)字豎起來看,大家想想,如何冒泡?如何來體會重的沉底,輕的上?。?/p>

第一步:  我們拿40跟20比,發(fā)現(xiàn)40是老大,不用交換。

第二步:  然后向前推一步,就是拿20跟30比,發(fā)現(xiàn)30是老大,就要交換了。

第三步:拿交換后的20跟10比,發(fā)現(xiàn)自己是老大,不用交換。

第四步:拿10跟50交換,發(fā)現(xiàn)50是老大,進行交換。

最后,我們經過一次遍歷,把數(shù)組中最小的數(shù)字送上去了,看看,我們向目標又邁進了一步。 

現(xiàn)在大家思想都知道了,下面我們就強烈要求跟快排較量一下,不是你死就是我活。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;
using System.Threading;

namespace BubbleSort
{
  public class Program
  {
    static void Main(string[] args)
    {
      //五次比較
      for (int i = 1; i <= 5; i++)
      {
        List<int> list = new List<int>();
        //插入2k個隨機數(shù)到數(shù)組中
        for (int j = 0; j < 2000; j++)
        {
          Thread.Sleep(1);
          list.Add(new Random((int)DateTime.Now.Ticks).Next(0, 100000));
        }
        Console.WriteLine("\n第" + i + "次比較:");
        Stopwatch watch = new Stopwatch();
        watch.Start();
        var result = list.OrderBy(single => single).ToList();
        watch.Stop();
        Console.WriteLine("\n快速排序耗費時間:" + watch.ElapsedMilliseconds);
        Console.WriteLine("輸出前是十個數(shù):" + string.Join(",", result.Take(10).ToList()));
        watch.Start();
        result = BubbleSort(list);
        watch.Stop();
        Console.WriteLine("\n冒泡排序耗費時間:" + watch.ElapsedMilliseconds);
        Console.WriteLine("輸出前是十個數(shù):" + string.Join(",", result.Take(10).ToList()));
      }
    }

    //冒泡排序算法
    static List<int> BubbleSort(List<int> list)
    {
      int temp;
      //第一層循環(huán): 表明要比較的次數(shù),比如list.count個數(shù),肯定要比較count-1次
      for (int i = 0; i < list.Count - 1; i++)
      {
        //list.count-1:取數(shù)據(jù)最后一個數(shù)下標,
//j>i: 從后往前的的下標一定大于從前往后的下標,否則就超越了。
        for (int j = list.Count - 1; j > i; j--)
        {
          //如果前面一個數(shù)大于后面一個數(shù)則交換
          if (list[j - 1] > list[j])
          {
            temp = list[j - 1];
            list[j - 1] = list[j];
            list[j] = temp;
          }
        }
      }
      return list;
    }
  }
}

嗚嗚,看著這兩種排序體檢報告,心都涼了,冒泡被快排KO了,真慘,難怪人家說冒泡效率低,原來真低。

快速排序:

既然能把冒泡KO掉,馬上就激起我們的興趣,tnd快排咋這么快,一定要好好研究一下。

首先上圖:   

從圖中我們可以看到:

left指針,right指針,base參照數(shù)。

其實思想是蠻簡單的,就是通過第一遍的遍歷(讓left和right指針重合)來找到數(shù)組的切割點。

第一步:首先我們從數(shù)組的left位置取出該數(shù)(20)作為基準(base)參照物。

第二步:從數(shù)組的right位置向前找,一直找到比(base)小的數(shù),

            如果找到,將此數(shù)賦給left位置(也就是將10賦給20),

            此時數(shù)組為:10,40,50,10,60,

            left和right指針分別為前后的10。

第三步:從數(shù)組的left位置向后找,一直找到比(base)大的數(shù),

             如果找到,將此數(shù)賦給right的位置(也就是40賦給10),

             此時數(shù)組為:10,40,50,40,60,

             left和right指針分別為前后的40。

第四步:重復“第二,第三“步驟,直到left和right指針重合,

             最后將(base)插入到40的位置,

             此時數(shù)組值為: 10,20,50,40,60,至此完成一次排序。

第五步:此時20已經潛入到數(shù)組的內部,20的左側一組數(shù)都比20小,20的右側作為一組數(shù)都比20大,

            以20為切入點對左右兩邊數(shù)按照"第一,第二,第三,第四"步驟進行,最終快排大功告成。 

同樣,我們把自己設計的快排跟類庫提供的快拍比較一下。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading;
using System.Diagnostics;

namespace QuickSort
{
  public class Program
  {
    static void Main(string[] args)
    {
      //5次比較
      for (int i = 1; i <= 5; i++)
      {
        List<int> list = new List<int>();

        //插入200個隨機數(shù)到數(shù)組中
        for (int j = 0; j < 200; j++)
        {
          Thread.Sleep(1);
          list.Add(new Random((int)DateTime.Now.Ticks).Next(0, 10000));
        }

        Console.WriteLine("\n第" + i + "次比較:");

        Stopwatch watch = new Stopwatch();

        watch.Start();
        var result = list.OrderBy(single => single).ToList();
        watch.Stop();

        Console.WriteLine("\n系統(tǒng)定義的快速排序耗費時間:" + watch.ElapsedMilliseconds);
        Console.WriteLine("輸出前是十個數(shù):" + string.Join(",", result.Take(10).ToList()));

        watch.Start();
        new QuickSortClass().QuickSort(list, 0, list.Count - 1);
        watch.Stop();

        Console.WriteLine("\n俺自己寫的快速排序耗費時間:" + watch.ElapsedMilliseconds);
        Console.WriteLine("輸出前是十個數(shù):" + string.Join(",", list.Take(10).ToList()));

      }
    }
  }

  public class QuickSortClass
  {

    ///<summary>
/// 分割函數(shù)
///</summary>
///<param name="list">待排序的數(shù)組</param>
///<param name="left">數(shù)組的左下標</param>
///<param name="right"></param>
///<returns></returns>
    public int Division(List<int> list, int left, int right)
    {
      //首先挑選一個基準元素
      int baseNum = list[left];

      while (left < right)
      {
        //從數(shù)組的右端開始向前找,一直找到比base小的數(shù)字為止(包括base同等數(shù))
        while (left < right && list[right] >= baseNum)
          right = right - 1;

        //最終找到了比baseNum小的元素,要做的事情就是此元素放到base的位置
        list[left] = list[right];

        //從數(shù)組的左端開始向后找,一直找到比base大的數(shù)字為止(包括base同等數(shù))
        while (left < right && list[left] <= baseNum)
          left = left + 1;


        //最終找到了比baseNum大的元素,要做的事情就是將此元素放到最后的位置
        list[right] = list[left];
      }
      //最后就是把baseNum放到該left的位置
      list[left] = baseNum;

      //最終,我們發(fā)現(xiàn)left位置的左側數(shù)值部分比left小,left位置右側數(shù)值比left大
//至此,我們完成了第一篇排序
      return left;
    }

    public void QuickSort(List<int> list, int left, int right)
    {
      //左下標一定小于右下標,否則就超越了
      if (left < right)
      {
        //對數(shù)組進行分割,取出下次分割的基準標號
        int i = Division(list, left, right);

        //對“基準標號“左側的一組數(shù)值進行遞歸的切割,以至于將這些數(shù)值完整的排序
        QuickSort(list, left, i - 1);

        //對“基準標號“右側的一組數(shù)值進行遞歸的切割,以至于將這些數(shù)值完整的排序
        QuickSort(list, i + 1, right);
      }
    }
  }
}

不錯,快排就是快,難怪內庫非要用他來作為排序的標準。 

嗯,最后要分享下:

冒泡的時間復雜度為:0(n) - 0(n^2)

快排的時間復雜度為:

    平均復雜度:N(logN)

    最壞復雜度: 0(n^2)

以上就是本文的全部內容,希望對大家的學習有所幫助,也希望大家多多支持腳本之家。

相關文章

  • C#并行編程之Task任務

    C#并行編程之Task任務

    這篇文章介紹了C#并行編程之Task任務,文中通過示例代碼介紹的非常詳細。對大家的學習或工作具有一定的參考借鑒價值,需要的朋友可以參考下
    2022-05-05
  • 聊聊C# 中HashTable與Dictionary的區(qū)別說明

    聊聊C# 中HashTable與Dictionary的區(qū)別說明

    這篇文章主要介紹了聊聊C# 中HashTable與Dictionary的區(qū)別說明,具有很好的參考價值,希望對大家有所幫助。一起跟隨小編過來看看吧
    2021-01-01
  • C#實現(xiàn)的JS操作類實例

    C#實現(xiàn)的JS操作類實例

    這篇文章主要介紹了C#實現(xiàn)的JS操作類,封裝了C#關于javascript的彈出對話框、返回上一頁、跳轉等常用操作,非常具有實用價值,需要的朋友可以參考下
    2015-03-03
  • c#中虛函數(shù)的相關使用方法

    c#中虛函數(shù)的相關使用方法

    若一個實例方法聲明前帶有virtual關鍵字,那么這個方法就是虛方法。
    2013-02-02
  • c# 文件壓縮zip或將zip文件解壓的方法

    c# 文件壓縮zip或將zip文件解壓的方法

    下面小編就為大家分享一篇c# 文件壓縮zip或將zip文件解壓的方法,具有很好的參考價值,希望對大家有所幫助。一起跟隨小編過來看看吧
    2018-03-03
  • C#使用Socket發(fā)送和接收TCP數(shù)據(jù)實例

    C#使用Socket發(fā)送和接收TCP數(shù)據(jù)實例

    這篇文章主要介紹了C#使用Socket發(fā)送和接收TCP數(shù)據(jù)的實現(xiàn)方法,以實例的形式詳細講述了C#實現(xiàn)socket通信的完整實現(xiàn)過程,非常具有實用價值,需要的朋友可以參考下
    2014-10-10
  • 淺析C# 索引器(Indexer)

    淺析C# 索引器(Indexer)

    這篇文章主要介紹了C# 索引器(Indexer)的相關資料,文中示例代碼非常詳細,幫助大家更好的理解和學習,感興趣的朋友可以了解下
    2020-07-07
  • C#基礎教程之IComparable用法,實現(xiàn)List<T>.sort()排序

    C#基礎教程之IComparable用法,實現(xiàn)List<T>.sort()排序

    這篇文章主要介紹了C#的一些基礎知識,主要是IComparable用法,實現(xiàn)List<T>.sort()排序,非常的實用,這里推薦給大家。
    2015-02-02
  • C#使用linq對數(shù)組進行篩選排序的方法

    C#使用linq對數(shù)組進行篩選排序的方法

    這篇文章主要介紹了C#使用linq對數(shù)組進行篩選排序的方法,實例分析了C#實用linq擴展進行數(shù)組排序的技巧,具有一定參考借鑒價值,需要的朋友可以參考下
    2015-04-04
  • 深入分析C#中的異步和多線程

    深入分析C#中的異步和多線程

    這篇文章主要介紹了C#中異步和多線程的相關資料,幫助大家更好的理解和學習c#,感興趣的朋友可以了解下
    2021-01-01

最新評論