C#典范排序算法的图文代码详解（上）【C#.Net教程】,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 pision(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 = pision(list, left, right);

        //对“基准标号“左边的一组数值举行递归的切割，以至于将这些数值完全的排序
        QuickSort(list, left, i - 1);

        //对“基准标号“右边的一组数值举行递归的切割，以至于将这些数值完全的排序
        QuickSort(list, i + 1, right);
      }
    }
  }
}