数据结构和算法 – 11.高级排序算法(上)

时间:2022-09-07 07:56:59

数据结构和算法 – 11.高级排序算法(上)

 

对现实中的排序问题,算法有七把利剑可以助你马道成功。

首先排序分为四种:

      交换排序: 包括冒泡排序,快速排序

      选择排序: 包括直接选择排序,堆排序。

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

      合并排序: 合并排序。

 

一.插入排序

1.1.直接插入排序

URL:http://www.cnblogs.com/tangge/p/5338734.html#ChaRu

总结:直接插入排序最好情况时间复杂度为O(n),最坏情况下(逆序表)时间复杂度为O(n2),因此它只适合于数据量较少的情况使用

1.2.希尔排序

本算法的关键内容是对远距离而非相邻的数据项进行比较。当算法循环遍历数
据集合的时候,每个数据项间的距离会缩短,直到算法对相邻数据项进行比较时才终止。

 

基本思想:设定一个元素增量gap,将参加排序的序列按这个间隔数gap从第1个元素开始依次分成若干子序列,对子序列进行排序,然后缩小增量gap,重新将整个序列按照新的间隔数gap进行划分,再分别对每个子序列进行排序,如此将“缩小增量gap——划分序列——将每个子序列进行排序“的操作进行下去,知道间隔数增量gap=1为止;

gap间隔数的选择:如何选择最合适的间隔数序列才能达到最优的排序效果是至今尚未解决的数学难题,我们在一般排序中gap的初始值可设定为N/2(N为排序元素的个数,这里需要注意采用四舍五入的原则),以后每一趟排序,gap值减半,直到gap=1为止;

数据结构和算法 – 11.高级排序算法(上)

 

/// <summary>
/// 希尔算法
/// </summary>
/// <param name="arr"></param>
/// <returns></returns>
public static int[] ShellSort(int[] m_SourceArray)
{
int tmp;
int length = m_SourceArray.Length;
//gap如果不能被整除需要+1
int gap = length / 2 + (length % 2 == 0 ? 0 : 1);
while (gap >= 1)
{
for (int i = 0; i + gap < length; i++)
{
if (m_SourceArray[i] > m_SourceArray[i + gap])
{
tmp = m_SourceArray[i];
m_SourceArray[i] = m_SourceArray[i + gap];
m_SourceArray[i + gap] = tmp;
}
}
if (gap == 1) break;
//gap如果不能被整除需要+1
gap = gap / 2 + (gap % 2 == 0 ? 0 : 1);
}
return m_SourceArray;
}

数据结构和算法 – 11.高级排序算法(上)

 

总结:Shell排序适用于待排序记录数量较大的情况,在此情况下,Shell排序一般要比直接插入排序要快。1971年,斯坦福大学的两位教授在大量实验的基础上推导出Shell排序的时间复杂度约为O(n1.3),使得我们终于突破了慢速排序的时代(超越了时间复杂度为O(n2))。

 

二.交换排序

2.1.冒泡排序

http://www.cnblogs.com/tangge/p/5338734.html#MaoPao

总结:冒泡排序在运行时间方面,待排序的记录越接近有序,算法的执行效率就越高,反之,执行效率则越低,它的平均时间复杂度为O(n2)

 

2.2.快速排序

快速排序是由C.A.R Hoare提出并命名的一种排序方法,在目前各种排序方法中,这种方法对元素进行比较的次数较少,因而速度也比较快,被认为是目前最好的排序方法之一在.NET中的多个集合类所提供的Sort()方法中都使用了快速排序对集合中的元素进行排序

快速排序的基本思想是:通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序的目的。

数据结构和算法 – 11.高级排序算法(上)

数据结构和算法 – 11.高级排序算法(上)

 

数据结构和算法 – 11.高级排序算法(上)

public class QuickSortClass
{ 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);
}
} ///<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;
}
}

调用

 List<int> list = new List<int>();
int[] array = new int[] { 20, 40, 50, 10, 60 };
list.AddRange(array);
new QuickSortClass().QuickSort(list, 0, list.Count - 1);
Console.WriteLine();
Console.Write(string.Join(",", list.ToList()));

总结:快速排序的平均时间复杂度为O(nlog2n),在平均时间下,快速排序时目前被认为最好的内部排序方法。但是,如果待排序记录的初始状态有序,则快速排序则会退化为冒泡排序,其时间复杂度为O(n2)。换句话说,待排序记录越无序,基准两侧记录数量越接近,排序速度越快;相反,待排序记录越有序,则排序速度越慢

数据结构和算法 – 11.高级排序算法(上)的更多相关文章

  1. 数据结构和算法 &ndash&semi; 11&period;高级排序算法(下)

    三.选择类排序 3.1.简单选择排序 http://www.cnblogs.com/tangge/p/5338734.html#XuanZe 3.2 堆排序 要知道堆排序,首先要了解一下二叉树的模型. ...

  2. javascript数据结构与算法--高级排序算法

    javascript数据结构与算法--高级排序算法 高级排序算法是处理大型数据集的最高效排序算法,它是处理的数据集可以达到上百万个元素,而不仅仅是几百个或者几千个.现在我们来学习下2种高级排序算法-- ...

  3. javascript数据结构与算法--高级排序算法(快速排序法,希尔排序法)

    javascript数据结构与算法--高级排序算法(快速排序法,希尔排序法) 一.快速排序算法 /* * 这个函数首先检查数组的长度是否为0.如果是,那么这个数组就不需要任何排序,函数直接返回. * ...

  4. 【高级排序算法】1、归并排序法 - Merge Sort

    归并排序法 - Merge Sort 文章目录 归并排序法 - Merge Sort nlogn 比 n^2 快多少? 归并排序设计思想 时间.空间复杂度 归并排序图解 归并排序描述 归并排序小结 参 ...

  5. javascript高级排序算法之快速排序(快排)

    javascript高级排序算法之快速排序(快排)我们之前讨论了javascript基本排序算法 冒泡排序 选择排序 插入排序 简单复习: 冒泡排序: 比较相邻的两个元素,如果前一个比后一个大,则交换 ...

  6. 【高级排序算法】2、归并排序法的实现-Merge Sort

    简单记录 - bobo老师的玩转算法系列–玩转算法 -高级排序算法 Merge Sort 归并排序 Java实现归并排序 SortTestHelper 排序测试辅助类 package algo; im ...

  7. 插入排序算法--直接插入算法,折半排序算法,希尔排序算法(C&num;实现)

    插入排序算法主要分为:直接插入算法,折半排序算法(二分插入算法),希尔排序算法,后两种是直接插入算法的改良.因此直接插入算法是基础,这里先进行直接插入算法的分析与编码. 直接插入算法的排序思想:假设有 ...

  8. 数据结构与算法之--高级排序:shell排序和快速排序

    高级排序比简单排序要快的多,简单排序的时间复杂度是O(N^2),希尔(shell)排序大约是O(N*(logN)^2),而快速排序是O(N*logN). 说明:下面以int数组的从小到大排序为例. 希 ...

  9. ZH奶酪:【数据结构与算法】基础排序算法总结与Python实现

    1.冒泡排序(BubbleSort) 介绍:重复的遍历数列,一次比较两个元素,如果他们顺序错误就进行交换. 2016年1月22日总结: 冒泡排序就是比较相邻的两个元素,保证每次遍历最后的元素最大. 排 ...

随机推荐

  1. SQLServer 2000 Driver for JDBC&rsqb;&lbrack;SQLServer&rsqb;传入的表格格式数据流&lpar;TDS&rpar;远程过程调用&lpar;RPC&rpar;协议流不正确解决方法

    问题:[SQLServer 2000 Driver for JDBC][SQLServer]传入的表格格式数据流(TDS)远程过程调用(RPC)协议流不正确.参数 1 (""): ...

  2. 关于使用由CA机构&lpar;EJBCA&rpar;颁发的证书实现SLLSocket双向认证服务端报null cert chain的解决方案

    在 SSLSocket实现服务端和客户端双向认证的例子 文章中最后提到使用keytool.exe的自签证书实现双向认证可以,但是使用ejbca生成证书实现SLL Socket的双向认证是服务端老是报错 ...

  3. 演练5-5:Contoso大学校园管理系统5

    Contoso University示例网站演示如何使用Entity Framework 5创建ASP.NET MVC 4应用程序. Entity Framework有三种处理数据的方式:  Data ...

  4. Yii2&period;0 多条件搜索 带分页

                                   方法一   在控制器中 ; if($titles!=""){ $where.=" and title lik ...

  5. Python3数据库模块&lpar;sqlite3&comma;SQLite3&rpar;

    一.sqlite命令 创建数据库:在控制台sqlite3 name .databases     查看数据库 .tables            查看表格名 databaseName .dump & ...

  6. MySQL如何优化

    对于全栈而言,数据库技能不可或缺,关系型数据库或者nosql,内存型数据库或者偏磁盘存储的数据库,对象存储的数据库或者图数据库--林林总总,但是第一必备技能还应该是MySQL.从LAMP的兴起,到Ma ...

  7. 如何优雅的关闭golang的channel

    How to Gracefully Close Channels,这篇博客讲了如何优雅的关闭channel的技巧,好好研读,收获良多. 众所周知,在golang中,关闭或者向已关闭的channel发送 ...

  8. Java流程语句

    流程控制语句 if语句: if语句的执行流程 例子: public class IfDemo01 { public static void main(String[] args) { int x = ...

  9. CSS设置table下tbody滚动条与thead对齐的方法

    <style>table tbody {display:block;height:195px;overflow-y:scroll;} table thead, tbody tr {disp ...

  10. leetcode25&mdash&semi;Search Insert Position

    Given a sorted array and a target value, return the index if the target is found. If not, return the ...