算法系列15天速成 第二天 七大经典排序【中】
算法系列15天速成 第二天 七大经典排序【中】
发布时间:2016-12-29 来源:查字典编辑
摘要:首先感谢朋友们对第一篇文章的鼎力支持,感动中.......今天说的是选择排序,包括“直接选择排序”和“堆排序”。话说上次“冒泡排序”被快排虐...

首先感谢朋友们对第一篇文章的鼎力支持,感动中.......算法系列15天速成 第二天 七大经典排序【中】1

今天说的是选择排序,包括“直接选择排序”和“堆排序”。

话说上次“冒泡排序”被快排虐了,而且“快排”赢得了内库的重用,众兄弟自然眼红,非要找快排一比高下。

这不今天就来了两兄弟找快排算账。

1.直接选择排序:

先上图:

算法系列15天速成 第二天 七大经典排序【中】2

说实话,直接选择排序最类似于人的本能思想,比如把大小不一的玩具让三岁小毛孩对大小排个序,

那小孩首先会在这么多玩具中找到最小的放在第一位,然后找到次小的放在第二位,以此类推。。。。。。

算法系列15天速成 第二天 七大经典排序【中】3,小孩子多聪明啊,这么小就知道了直接选择排序。羡慕中........算法系列15天速成 第二天 七大经典排序【中】4

对的,小孩子给我们上了一课,

第一步: 我们拿80作为参照物(base),在80后面找到一个最小数20,然后将80跟20交换。

第二步: 第一位数已经是最小数字了,然后我们推进一步在30后面找一位最小数,发现自己最小,不用交换。

第三步:........

最后我们排序完毕。大功告成。

既然是来挑战的,那就5局3胜制。

复制代码 代码如下:

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Threading;

using System.Diagnostics;

namespace SelectionSort

{

public class Program

{

static void Main(string[] args)

{

//5次比较

for (int i = 1; i <= 5; i++)

{

List<int> list = new List<int>();

//插入2w个随机数到数组中

for (int j = 0; j < 20000; j++)

{

Thread.Sleep(1);

list.Add(new Random((int)DateTime.Now.Ticks).Next(1000, 1000000));

}

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 = SelectionSort(list);

watch.Stop();

Console.WriteLine("n直接选择排序耗费时间:" + watch.ElapsedMilliseconds);

Console.WriteLine("输出前十个数:" + string.Join(",", list.Take(10).ToList()));

}

}

//选择排序

static List<int> SelectionSort(List<int> list)

{

//要遍历的次数

for (int i = 0; i < list.Count - 1; i++)

{

//假设tempIndex的下标的值最小

int tempIndex = i;

for (int j = i + 1; j < list.Count; j++)

{

//如果tempIndex下标的值大于j下标的值,则记录较小值下标j

if (list[tempIndex] > list[j])

tempIndex = j;

}

//最后将假想最小值跟真的最小值进行交换

var tempData = list[tempIndex];

list[tempIndex] = list[i];

list[i] = tempData;

}

return list;

}

}

}

比赛结果公布:

算法系列15天速成 第二天 七大经典排序【中】5

堆排序:

要知道堆排序,首先要了解一下二叉树的模型。

下图就是一颗二叉树,具体的情况我后续会分享的。

算法系列15天速成 第二天 七大经典排序【中】6

那么堆排序中有两种情况(看上图理解):

大根堆: 就是说父节点要比左右孩子都要大。

小根堆: 就是说父节点要比左右孩子都要小。

那么要实现堆排序,必须要做两件事情:

第一:构建大根堆。

首先上图:

算法系列15天速成 第二天 七大经典排序【中】7

首先这是一个无序的堆,那么我们怎样才能构建大根堆呢?

第一步: 首先我们发现,这个堆中有2个父节点(2,,3);

第二步: 比较2这个父节点的两个孩子(4,5),发现5大。

第三步: 然后将较大的右孩子(5)跟父节点(2)进行交换,至此3的左孩子堆构建完毕,

如图:

算法系列15天速成 第二天 七大经典排序【中】8

第四步: 比较第二个父节点(3)下面的左右孩子(5,1),发现左孩子5大。

第五步: 然后父节点(3)与左孩子(5)进行交换,注意,交换后,堆可能会遭到破坏,

必须按照以上的步骤一,步骤二,步骤三进行重新构造堆。

最后构造的堆如下:

算法系列15天速成 第二天 七大经典排序【中】9

第二:输出大根堆。

至此,我们把大根堆构造出来了,那怎么输出呢?我们做大根堆的目的就是要找出最大值,

那么我们将堆顶(5)与堆尾(2)进行交换,然后将(5)剔除根堆,由于堆顶现在是(2),

所以破坏了根堆,必须重新构造,构造完之后又会出现最大值,再次交换和剔除,最后也就是俺们

要的效果了,算法系列15天速成 第二天 七大经典排序【中】10

发现自己兄弟被别人狂殴,算法系列15天速成 第二天 七大经典排序【中】11,堆排序再也坐不住了,决定要和快排干一场。

同样,快排也不甘示弱,谁怕谁?

复制代码 代码如下:

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Threading;

using System.Diagnostics;

namespace HeapSort

{

public class Program

{

static void Main(string[] args)

{

//5次比较

for (int j = 1; j <= 5; j++)

{

List<int> list = new List<int>();

//插入2w个数字

for (int i = 0; i < 20000; i++)

{

Thread.Sleep(1);

list.Add(new Random((int)DateTime.Now.Ticks).Next(1000, 100000));

}

Console.WriteLine("n第" + j + "次比较:");

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 = new Stopwatch();

watch.Start();

HeapSort(list);

watch.Stop();

Console.WriteLine("n堆排序耗费时间:" + watch.ElapsedMilliseconds);

Console.WriteLine("输出前十个数" + string.Join(",", list.Take(10).ToList()));

}

}

///<summary>

/// 构建堆

///</summary>

///<param name="list">待排序的集合</param>

///<param name="parent">父节点</param>

///<param name="length">输出根堆时剔除最大值使用</param>

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>

public static void 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);

}

}

}

}

结果公布:

算法系列15天速成 第二天 七大经典排序【中】12

堆排序此时心里很尴尬,双双被KO,心里想,一定要捞回面子,一定要赢,

于是堆排序提出了求“前K大问题”。(就是在海量数据中找出前几大的数据),

快排一口答应,小意思,没问题。

双方商定,在2w随机数中找出前10大的数:

复制代码 代码如下:

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 j = 1; j <= 5; j++)

{

List<int> list = new List<int>();

for (int i = 0; i < 20000; i++)

{

Thread.Sleep(1);

list.Add(new Random((int)DateTime.Now.Ticks).Next(1000, 100000));

}

Console.WriteLine("n第" + j + "次比较:");

Stopwatch watch = new Stopwatch();

watch.Start();

var result = list.OrderByDescending(single => single).Take(10).ToList();

watch.Stop();

Console.WriteLine("n快速排序求前K大耗费时间:" + watch.ElapsedMilliseconds);

Console.WriteLine("输出前十个数:" + string.Join(",", result.Take(10).ToList()));

watch = new Stopwatch();

watch.Start();

result = HeapSort(list, 10);

watch.Stop();

Console.WriteLine("n堆排序求前K大耗费时间:" + watch.ElapsedMilliseconds);

Console.WriteLine("输出前十个数:" + string.Join(",", list.Take(10).ToList()));

}

}

///<summary>

/// 构建堆

///</summary>

///<param name="list">待排序的集合</param>

///<param name="parent">父节点</param>

///<param name="length">输出根堆时剔除最大值使用</param>

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>

///<param name="top">前K大</param>

///<returns></returns>

public static List<int> HeapSort(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--)

{

HeapAdjust(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);

//因为顺序被打乱,必须重新构造堆

HeapAdjust(list, 0, i);

}

return topNode;

}

}

}

求前K大的输出结果:

算法系列15天速成 第二天 七大经典排序【中】13

最后堆排序赶紧拉着直接选择排序一路小跑了,因为求前K大问题已经不是他原本来的目的。

ps: 直接选择排序的时间复杂度为:O(n^2)

堆排序的时间复杂度:O(NlogN)

推荐文章
猜你喜欢
附近的人在看
推荐阅读
拓展阅读
相关阅读
网友关注
最新相关技巧学习
热门相关技巧学习
编程开发子分类