这几天无聊，就去研究排序算法，话不多说，用事实说话。
|
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading;
using System.Diagnostics;
namespace 排序算法大PK
{
class Program
{
static void Main(string[] args)
{
Console.WriteLine("规则：取20000随机数，比较各自耗时");
for (int i = 0; i < 5; i++)
{
List<int> list = new List<int>();
//取20000个随机数到集合中
for (int j = 0; j < 20000; j++)
{
Thread.Sleep(1);
list.Add(new Random((int)DateTime.Now.Ticks).Next(0, 1000000));
}
Console.WriteLine("\n第" + i + "轮PK:");
Stopwatch watch = new Stopwatch(); //Stopwatch类可用于准确地测量运行时间
watch.Start(); //开始或继续测量某个时间间隔的运行时间
var result = list.OrderBy(single => single).ToList();
watch.Stop();
Console.WriteLine("快速排序耗费时间：" + watch.ElapsedMilliseconds + "毫秒");
Console.WriteLine("输出前十个数：" + string.Join("，", result.Take(10).ToList()));
watch.Reset();
watch.Start();
result = DirectSequence(list);
watch.Stop();
Console.WriteLine("选择排序耗费时间：" + watch.ElapsedMilliseconds + "毫秒");
Console.WriteLine("输出前十个数：" + string.Join("，", result.Take(10).ToList()));
watch.Reset();
watch.Start();
result = BubbleSort(list);
watch.Stop();
Console.WriteLine("冒泡排序耗费时间：" + watch.ElapsedMilliseconds + "毫秒");
Console.WriteLine("输出前十个数：" + string.Join("，", result.Take(10).ToList()));
watch.Reset();
watch.Start();
result = HeapSort(list);
watch.Stop();
Console.WriteLine("堆排序耗费时间：" + watch.ElapsedMilliseconds + "毫秒");
Console.WriteLine("输出前十个数：" + string.Join("，", result.Take(10).ToList()));
watch.Reset();
watch.Start();
result = InsertionSort(list);
watch.Stop();
Console.WriteLine("插入排序耗费时间：" + watch.ElapsedMilliseconds + "毫秒");
Console.WriteLine("输出前十个数：" + string.Join("，", result.Take(10).ToList()));
watch.Reset();
watch.Start();
result = HillSort(list);
watch.Stop();
Console.WriteLine("希尔排序耗费时间：" + watch.ElapsedMilliseconds + "毫秒");
Console.WriteLine("输出前十个数：" + string.Join("，", result.Take(10).ToList()));
watch.Reset();
watch.Start(); //开始或继续测量某个时间间隔的运行时间
result = list.OrderByDescending(single => single).Take(10).ToList();
watch.Stop();
Console.WriteLine("快速排序取最大的前十个耗费时间：" + watch.ElapsedMilliseconds + "毫秒");
Console.WriteLine("输出前十个数：" + string.Join("，", result.Take(10).ToList()));
watch.Reset();
watch.Start();
result = NewHeapSort(list, 10);
watch.Stop();
Console.WriteLine("堆排序取最大的前十个耗费时间：" + watch.ElapsedMilliseconds + "毫秒");
Console.WriteLine("输出前十个数：" + string.Join("，", result.Take(10).ToList()));
}
Console.Read();
}
#region 冒泡排序
private static List<int> BubbleSort(List<int> list)
{
int temp = 0;
for (int i = 0; i < list.Count - 1; i++)
{
for (int j = list.Count - 1; j > i; j--)
{
if (list[j] < list[j - 1])
{
temp = list[j - 1];
list[j - 1] = list[j];
list[j] = temp;
}
}
}
return list;
}
#endregion
#region 选择排序
static List<int> DirectSequence(List<int> list)
{
for (int i = 0; i < list.Count - 1; i++)
{
int min = i; //假设min的下标的值最小
for (int j = i + 1; j < list.Count; j++)
{
//如果min下标的值大于j下标的值,则记录较小值下标j
if (list[min] > list[j])
{
min = j;
}
}
//最后将假想最小值跟真的最小值进行交换
var temp = list[min];
list[min] = list[i];
list[i] = temp;
}
return list;
}
#endregion
#region 堆排序
//构建堆
static void HeapAdjust(List<int> list, int parent, int length)
{
//temp保存当前父节点
int temp = list[parent];
//得到左孩子(这可是二叉树的定义，大家看图也可知道)
int child = 2 * parent + 1;
while (child < length)
{
//如果parent有右孩子，则要判断左孩子是否小于右孩子
if (child + 1 < length && list[child] < list[child + 1])
child++;
//父亲节点大于子节点，就不用做交换
if (temp >= list[child])
break;
//将较大子节点的值赋给父亲节点
list[parent] = list[child];
//然后将子节点做为父亲节点，已防止是否破坏根堆时重新构造
parent = child;
//找到该父亲节点较小的左孩子节点
child = 2 * parent + 1;
}
//最后将temp值赋给较大的子节点，以形成两值交换
list[parent] = temp;
}
///<summary>
/// 堆排序
///</summary>
///<param name="list"></param>
static List<int> HeapSort(List<int> list)
{
//list.Count/2-1:就是堆中父节点的个数
for (int i = list.Count / 2 - 1; i >= 0; i--)
{
HeapAdjust(list, i, list.Count);
}
//最后输出堆元素
for (int i = list.Count - 1; i > 0; i--)
{
//堆顶与当前堆的第i个元素进行值对调
int temp = list[0];
list[0] = list[i];
list[i] = temp;
//因为两值交换，可能破坏根堆，所以必须重新构造
HeapAdjust(list, 0, i);
}
return list;
}
#endregion
#region 堆排序（取前N大的数）
///<summary>
/// 构建堆
///</summary>
///<param name="list">待排序的集合</param>
///<param name="parent">父节点</param>
///<param name="length">输出根堆时剔除最大值使用</param>
static void NewHeapAdjust(List<int> list, int parent, int length)
{
//temp保存当前父节点
int temp = list[parent];
//得到左孩子(这可是二叉树的定义哇)
int child = 2 * parent + 1;
while (child < length)
{
//如果parent有右孩子，则要判断左孩子是否小于右孩子
if (child + 1 < length && list[child] < list[child + 1])
child++;
//父节点大于子节点，不用做交换
if (temp >= list[child])
break;
//将较大子节点的值赋给父亲节点
list[parent] = list[child];
//然后将子节点做为父亲节点，已防止是否破坏根堆时重新构造
parent = child;
//找到该父节点左孩子节点
child = 2 * parent + 1;
}
//最后将temp值赋给较大的子节点，以形成两值交换
list[parent] = temp;
}
///<summary>
/// 堆排序
///</summary>
///<param name="list">待排序的集合</param>
///<param name="top">前K大</param>
///<returns></returns>
public static List<int> NewHeapSort(List<int> list, int top)
{
List<int> topNode = new List<int>();
//list.Count/2-1:就是堆中非叶子节点的个数
for (int i = list.Count / 2 - 1; i >= 0; i--)
{
NewHeapAdjust(list, i, list.Count);
}
//最后输出堆元素（求前K大）
for (int i = list.Count - 1; i >= list.Count - top; i--)
{
//堆顶与当前堆的第i个元素进行值对调
int temp = list[0];
list[0] = list[i];
list[i] = temp;
//最大值加入集合
topNode.Add(temp);
//因为顺序被打乱，必须重新构造堆
NewHeapAdjust(list, 0, i);
}
return topNode;
}
#endregion
#region 插入排序
static List<int> InsertionSort(List<int> list)
{
for (int i = 1; i < list.Count; i++)
{
var temp = list[i];
int j;
for (j = i - 1; j >= 0 && temp < list[j]; j--)
{
list[j + 1] = list[j];
}
list[j + 1] = temp;
}
return list;
}
#endregion
#region 希尔排序(“插入排序”的改进版)
static List<int> HillSort(List<int> list)
{
int num = list.Count / 2; //取增量
while (num >= 1)
{
for (int i = num; i < list.Count; i++) //无须序列
{
var temp = list[i];
int j;
for (j = i - num; j >= 0 && temp < list[j]; j = j - num) //有序序列
{
list[j + num] = list[j];
}
list[j + num] = temp;
}
num = num / 2;
}
return list;
}
#endregion
}
}
分享到：
相关推荐
可能是最快的算法alpha-blend汇编源代码，排序算法数据结构.doc
各种数据结构、算法及实用的C#源代码. C#，弗洛伊德-瑞文斯特（Floyd-Rivest）算法与源代码. Floyd-Rivest 算法是一种选择算法，用于在不同元素的数组中找到第k个最小元素。它类似于快速选择算法，但在实际运行中有...
复杂度分析是数据结构和算法的精髓，能帮助我们解决如何更省，更快地存储和处理数据地问题。 2.20 个重要的知识点： a.10 个数据结构：数组，链表，栈，队列，散列表，三叉树，堆，跳表图，Trie 树。 b.10 个算法...
基于EJB的真实世界模型，附源代码，部分功能需JSP配合完成。 J2ME优化压缩PNG文件 4个目标文件 内容索引:JAVA源码,综合应用,J2me游戏,PNG,图形处理 这是个J2ME控制台程序，它能剔除PNG文件中的非关键数据段，减少...
LightGBM（Light Gradient Boosting Machine） 是微软开源的一个实现 GBDT 算法的框架，支持高...其具有以下优点：更快的训练速度更低的内存消耗更好的准确率分布式支持，可以快速处理海量数据 标签：LightGBM
matlab的egde源代码Wave_clus 3 Wave_clus是一种快速且不受监督的峰值检测和排序算法，可在Windows，Mac或Linux操作系统下运行。 要安装，请将此存储库下载到文件夹中。 在MATLAB（R2009b或更高版本）中，转到“设置...
5.3.1 排序算法223 5.3.2 字符串查找225 5.4 一个实际的应用程序226 5.4.1 识别测量数据的趋势226 5.4.2 LISLP算法的复杂度226 5.4.3 用T-SQL解决最长上升子序列的长度问题227 5.5 总结229 第6章 子查询、表...
该资料是《TCP/IP详解 卷1:协议》的源代码 对应的书籍资料见: TCP/IP详解 卷1:协议(09年度畅销榜TOP50)(08年度畅销榜TOP50) http://download.csdn.net/detail/fksec/4657587 基本信息 原书名： TCP/IP ...
java二叉树算法源码 @[TOC](《恋上数据结构》第1季 + 第2季) 想深入学习 Java 基础建议看这个，同款小码哥系列： CSDN 博客地址： 前言 正在从头开始逐渐翻新笔记（就当复习） 第1季笔记已经快翻新结束！！！ 我好歹...
重写新新百篇+百篇精华算法，速度提高new[rexsp独立开发] 32．重写明星算法new[rexsp独立开发] 33．发贴颜色选择更智能方便new 34．魅力贴new[rexsp独立开发] 35．威望贴new[rexsp独立开发] 36．经验...
5.3.1 排序算法223 5.3.2 字符串查找225 5.4 一个实际的应用程序226 5.4.1 识别测量数据的趋势226 5.4.2 LISLP算法的复杂度226 5.4.3 用T-SQL解决最长上升子序列的长度问题227 5.5 总结229 第6章 子查询、表表达式...
1 介绍 1.1 动机 在七十年代末，Alexander Stepanov 第一个发现一些算法不依赖于数据结构的特定实现， 而仅仅和结构的一些基本...方法，有了STL，程序员可以写更少且更快的代码，把精力集中在问题解决上，而不必关心
该存储库包含我的出版物的C / C ++实现的源代码： A. Rauh，GR Arce：快速加权中值搜索中的最佳枢轴选择。 IEEE信号处理事务（第60卷，第8期） 抽象的 加权中值滤波器越来越多地用于信号处理应用中，因此快速实现...
基于EJB的真实世界模型，附源代码，部分功能需JSP配合完成。 J2ME优化压缩PNG文件 4个目标文件 内容索引:JAVA源码,综合应用,J2me游戏,PNG,图形处理 这是个J2ME控制台程序，它能剔除PNG文件中的非关键数据段，...
PatNet分页控件，以最快响应速度，极易使用，多种分页算法，支持多种数据库，承载上百万记录的快速分页作为你的观注点。 无论你是小型的站点，还是大型的WEB项目，它的方便性都可以为你免去分页的烦琐，大大提高你...
技术点34 定位reduce 端数据倾斜问题技术点35 确定reduce 任务是否存在整体吞吐量过低技术点36 缓慢的洗牌（shuffle）和排序 ．6．2．4 任务的一般性能问题技术点37 作业竞争和调度器限制技术点38 使用堆转储...
在他的论文中给出了伪代码，但原始源代码并不可用。 您可以在 Anonymization Toolbox[2] 中找到第三部分 Java 实现。 该存储库是Mondrian 的开源 Python 实现。 动机 数据隐私的研究已经持续了十多年，发表了大量...
写⼊速度快，适⽤于读少写多的场景 5. 稀疏性，为空的列并不占⽤存储空间，表可以设计的⾮常稀疏。不需要null填充 缺点： 1. 不能⽀持条件查询，只⽀持按照row key来查询 2. 只能在主键上索引和排序 3. 对join以及...