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)

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持我们。

(0)

相关推荐

  • C#中使用快速排序按文件创建时间将文件排序的源码

    快速排序类 using System; using System.Data; using System.Configuration; using System.Web; using System.Web.Security; using System.Web.UI; using System.Web.UI.WebControls; using System.Web.UI.WebControls.WebParts; using System.Web.UI.HtmlControls; using Sy

  • 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# 数组查找与排序实现代码

    1. 查找对象 复制代码 代码如下: Person p1 = new Person( " http://www.my400800.cn " , 18 ); Person p2 = new Person( " http://www.my400800.cn " , 19 ); Person p3 = new Person( " http://www.my400800.cn " , 20 ); Person[] persons = ... { p1,

  • C#对DataTable里数据排序的方法

    直接给个实例代码吧 复制代码 代码如下: protected void Page_Load(object sender, EventArgs e)    {        DataTable dt = new DataTable();        dt.Columns.Add("Name");        dt.Columns.Add("Age");//因为是字符串,所以排序不对        dt.Rows.Add("小明", "

  • c#对list排序示例

    复制代码 代码如下: using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace ListSort { class Program { static void Main(string[] args) { List listCustomer = new List(); listCustomer.Add(new Customer { name = "客户1",

  • C#基础教程之IComparable用法,实现List<T>.sort()排序

    List<T>.sort()可以实现对T的排序,比如List<int>.sort()执行后集合会按照int从小到大排序.如果T是一个自定义的Object,可是我们想按照自己的方式来排序,那该怎么办呢,其实可以用过IComparable接口重写CompareTo方法来实现.流程如下: 一.第一步我们申明一个类Person但是要继承IComparable接口: 复制代码 代码如下: using System; using System.Collections.Generic; usin

  • C#基础之数组排序、对象大小比较实现代码

    从个小例子开始: 复制代码 代码如下: int[] intArray = new int[]{2,3,6,1,4,5}; Array.Sort(intArray); Array.ForEach<int>(intArray,(i)=>Console.WriteLine(i)); 这个例子定义了一个int数组,然后使用Array.Sort(arr)静态方法对此数组进行排序,最后输出排序后的数组.以上例子将毫无意外的依次输出1,2,3,4,5,6. 为什么Array的Sort方法可以正确的对i

  • C#数组排序的两种常用方法

    本文实例讲述了C#数组排序的两种常用方法.分享给大家供大家参考.具体如下: 1.第一个例子 定义代码 #region Array数组排序1 public class Pigeon : IComparable<Pigeon> //类元素本身继承比较接口 { int XValue; int YValue; public string BatchNo { get; set; } public int CompareTo(Pigeon other) { if (other == null) throw

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

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

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

    今天跟大家聊聊最后三种排序: 直接插入排序,希尔排序和归并排序. 直接插入排序: 这种排序其实蛮好理解的,很现实的例子就是俺们斗地主,当我们抓到一手乱牌时,我们就要按照大小梳理扑克,30秒后,扑克梳理完毕,4条3,5条s,哇塞...... 回忆一下,俺们当时是怎么梳理的. 最左一张牌是3,第二张牌是5,第三张牌又是3,赶紧插到第一张牌后面去,第四张牌又是3,大喜,赶紧插到第二张后面去,第五张牌又是3,狂喜,哈哈,一门炮就这样产生了. 怎么样,生活中处处都是算法,早已经融入我们的生活和血液. 下面

  • 七大经典排序算法图解

    目录 插入排序 ①直接插入排序 基本思想 动图演示 代码实现 ②希尔排序 基本思想 图示 代码实现 选择排序 ③直接选择排序 基本思想 动图演示 代码实现 ④堆排序 基本思想 建堆需要注意的问题 图示 代码实现 交换排序 ⑤冒泡排序 基本思想 动图演示 代码实现 ⑥快速排序 基本思想 基本框架 Partion函数分析 Partion函数的优化 快速排序代码实现 归并排序 ⑦归并排序 基本思想 动图演示 代码实现 排序算法复杂度及稳定性分析 插入排序 ①直接插入排序 基本思想 每次从一个有序序列开

  • python实现经典排序算法的示例代码

    以下排序算法最终结果都默认为升序排列,实现简单,没有考虑特殊情况,实现仅表达了算法的基本思想. 冒泡排序 内层循环中相邻的元素被依次比较,内层循环第一次结束后会将最大的元素移到序列最右边,第二次结束后会将次大的元素移到最大元素的左边,每次内层循环结束都会将一个元素排好序. def bubble_sort(arr): length = len(arr) for i in range(length): for j in range(length - i - 1): if arr[j] > arr[j

  • Java多种经典排序算法(含动态图)

    算法分析 一个排序算法的好坏,一般是通过下面几个关键信息来分析的,下面先介绍一下这几个关键信息,然后再将常见的排序算法的这些关键信息统计出来. 名词介绍 时间复杂度:指对数据操作的次数(或是简单的理解为某段代码的执行次数).举例:O(1):常数时间复杂度:O(log n):对数时间复杂度:O(n):线性时间复杂度. 空间复杂度:某段代码每次执行时需要开辟的内存大小. 内部排序:不依赖外部的空间,直接在数据内部进行排序: 外部排序:数据的排序,不能通过内部空间来完成,需要依赖外部空间. 稳定排序:

  • Python 数据结构之十大经典排序算法一文通关

    目录 1.冒泡排序 算法演示 算法步骤 算法实现 2.选择排序 算法演示 算法步骤 算法实现 3.简单插入排序 算法演示 算法步骤 算法实现 4.希尔排序 算法演示 算法步骤 算法实现 5.归并排序 算法演示 算法步骤 算法实现 6.快速排序 算法演示 算法步骤 算法实现 7.堆排序 算法演示 算法步骤 算法实现 8.计数排序 算法演示 算法步骤 算法实现 9.桶排序 算法演示 算法步骤 算法实现 10.基数排序 算法演示 算法步骤 算法实现 一文搞掂十大经典排序算法 今天整理一下十大经典排序算

  • Python 十大经典排序算法实现详解

    目录 关于时间复杂度 关于稳定性 名词解释 1.冒泡排序 (1)算法步骤 (2)动图演示 (3)Python代码 2.选择排序 (1)算法步骤 (2)动图演示 (3)Python代码 3.插入排序 (1)算法步骤 (2)动图演示 (3)Python代码 4.希尔排序 (1)算法步骤 (2)Python代码 5.归并排序 (1)算法步骤 (2)动图演示 (3)Python代码 6.快速排序 (1)算法步骤 (2)动图演示 (3)Python代码 7.堆排序 (1)算法步骤 (2)动图演示 (3)P

  • 几种经典排序算法的JS实现方法

    一.冒泡排序 function BubbleSort(array) { var length = array.length; for (var i = length - 1; i > 0; i--) { //用于缩小范围 for (var j = 0; j < i; j++) { //在范围内进行冒泡,在此范围内最大的一个将冒到最后面 if (array[j] > array[j+1]) { var temp = array[j]; array[j] = array[j+1]; arra

  • 经典排序算法之冒泡排序(Bubble sort)代码

    经典排序算法 - 冒泡排序Bubble sort 原理是临近的数字两两进行比较,按照从小到大或者从大到小的顺序进行交换, 这样一趟过去后,最大或最小的数字被交换到了最后一位, 然后再从头开始进行两两比较交换,直到倒数第二位时结束,其余类似看例子 例子为从小到大排序, 原始待排序数组| 6 | 2 | 4 | 1 | 5 | 9 | 第一趟排序(外循环) 第一次两两比较6 > 2交换(内循环) 交换前状态| 6 | 2 | 4 | 1 | 5 | 9 | 交换后状态| 2 | 6 | 4 | 1

  • C语言实现经典排序算法的示例代码

    目录 一.冒泡排序 1.原理 2.实现 3.算法分析 二.选择排序 1.原理 2.实现 3.算法分析 三.插入排序 1.原理 2.实现 3.算法分析 四.希尔排序 1.原理 2.实现 3.算法分析 总结 一.冒泡排序 1.原理 从数组的头开始不断比较相邻两个数的大小,不断将较大的数右移,一个循环后,最大数移至最后一位,无序数组规模减一.不断重复前面动作,知道数组完全有序. 2.实现 void swap(int* a, int* b) { int temp = *a; *a = *b; *b =

随机推荐