程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> .NET網頁編程 >> C# >> C#入門知識 >> C#七大經典排序算法系列(上)

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

編輯:C#入門知識

C#七大經典排序算法系列(上)。本站提示廣大學習愛好者:(C#七大經典排序算法系列(上))文章只能為提供參考,不一定能成為您想要的結果。以下是C#七大經典排序算法系列(上)正文


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

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

首先排序分為四種:

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

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

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

合並排序: 合並排序。 

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

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

冒泡排序:

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

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

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

那麼我們就上圖.

要達到冒泡的效果,我們就要把一組數字豎起來看,大家想想,如何冒泡?如何來體會重的沉底,輕的上浮?

第一步:  我們拿40跟20比,發現40是老大,不用交換。

第二步:  然後向前推一步,就是拿20跟30比,發現30是老大,就要交換了。

第三步:拿交換後的20跟10比,發現自己是老大,不用交換。

第四步:拿10跟50交換,發現50是老大,進行交換。

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

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

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個隨機數到數組中
        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("輸出前是十個數:" + string.Join(",", result.Take(10).ToList()));
        watch.Start();
        result = BubbleSort(list);
        watch.Stop();
        Console.WriteLine("\n冒泡排序耗費時間:" + watch.ElapsedMilliseconds);
        Console.WriteLine("輸出前是十個數:" + string.Join(",", result.Take(10).ToList()));
      }
    }

    //冒泡排序算法
    static List<int> BubbleSort(List<int> list)
    {
      int temp;
      //第一層循環: 表明要比較的次數,比如list.count個數,肯定要比較count-1次
      for (int i = 0; i < list.Count - 1; i++)
      {
        //list.count-1:取數據最後一個數下標,
//j>i: 從後往前的的下標一定大於從前往後的下標,否則就超越了。
        for (int j = list.Count - 1; j > i; j--)
        {
          //如果前面一個數大於後面一個數則交換
          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參照數。

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

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

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

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

  此時數組為:10,40,50,10,60,

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

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

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

   此時數組為:10,40,50,40,60,

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

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

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

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

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

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

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

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個隨機數到數組中
        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系統定義的快速排序耗費時間:" + watch.ElapsedMilliseconds);
        Console.WriteLine("輸出前是十個數:" + 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("輸出前是十個數:" + string.Join(",", list.Take(10).ToList()));

      }
    }
  }

  public class QuickSortClass
  {

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

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

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

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


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

      //最終,我們發現left位置的左側數值部分比left小,left位置右側數值比left大
//至此,我們完成了第一篇排序
      return left;
    }

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

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

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

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

嗯,最後要分享下:

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

快排的時間復雜度為:

    平均復雜度:N(logN)

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

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

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved