《算法》学习笔记2.1 初级排序算法

﹏ヽ暗。殇╰゛Y 2022-11-19 09:42 152阅读 0赞

### 2.1 初级排序算法 ###

*   *  2.1.1 选择排序
     *  2.1.2 插入排序
     *  2.1.3 选择、插入排序比较
     *  2.1.4 希尔排序
     *  2.1.5 其他
     *   *  数据类型
         *  几种典型的部分有序数组
         *  插入排序中的哨兵

## 2.1.1 选择排序 ##

1.思想  
不断地选择剩余元素之中的最小者

## 2.1.2 插入排序 ##

1.思想  
插入已经有序的数组中的适当位置，其余元素在插入之前都向右移一位

2.最优适用情况

*  部分有序的数组；
 *  小规模数组

## 2.1.3 选择、插入排序比较 ##

<table> 
 <thead> 
  <tr> 
   <th></th> 
   <th>测试数组</th> 
   <th>比较/次数</th> 
   <th>交换/次数</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>选择排序</td> 
   <td>长度为N</td> 
   <td>N2/2</td> 
   <td>N</td> 
  </tr> 
  <tr> 
   <td>插入排序</td> 
   <td>长度为N且主键不重复</td> 
   <td>最坏：N2/2 最好：N2/2</td> 
   <td>最坏：N-1 最好：0</td> 
  </tr> 
 </tbody> 
</table>

比较两种排序算法：sortCompare()

## 2.1.4 希尔排序 ##

1.思想  
使数组中任意间隔为h的元素有序的

2.最优适用情况

*  中等大小的数组；
 *  需要解决一个排序问题而又没有系统排序函数可用，可先用希尔，再考虑是否值得用其他替代

## 2.1.5 其他 ##

### 数据类型 ###

实现Comparable()接口

### 几种典型的部分有序数组 ###

*  数组中的每个元素距离他的最终位置都不远
 *  一个有序的大数组接一个小数组
 *  数组中只有几个元素的位置不正确

### 插入排序中的哨兵 ###

插入排序的实现中先找出最小的元素将其置于数组的最左边，这样就能去掉内循环的判断条件j>o，这是一种常见的规避边界测试的方法，能够省略判断条件的元素通常被称为哨兵

发表评论取消回复

表情：

评论列表（有 0 条评论，152人围观）

还没有评论，来说两句吧...

相关阅读

相关排序算法学习笔记（三）

目录一：基数排序二：常用排序算法总结和对比 -------------------- 一：基数排序 1.1 概念： > 基数排序属于“分配式排序”，又

秒速五厘米/ 2023年09月29日 14:03/ 0 赞/ 51 阅读

相关排序算法学习笔记（二）

目录一：快速排序二：归并排序 -------------------- 一：快速排序 1.1 基本思想： > [快速排序][Link 1]是我们之前学习的冒

àì夳堔傛蜴生んèń/ 2023年09月29日 13:21/ 0 赞/ 32 阅读

相关《算法》学习笔记2.1 初级排序算法

2.1 初级排序算法 2.1.1 选择排序 2.1.2 插入排序 2.1.3 选择、插入排序比较 2.1.4 希尔排

﹏ヽ暗。殇╰゛Y/ 2022年11月19日 09:42/ 0 赞/ 153 阅读

相关算法学习笔记之插入排序算法

接下我们介绍下一种排序算法：插入排序插入排序算法通过比较和插入来实现排序，其排序流程如下： 1）首先对数组前两个数据进行从小到大排序 2）接下来将第3个数据

谁践踏了优雅/ 2022年08月21日 07:56/ 0 赞/ 361 阅读

相关算法学习笔记之选择排序算法

接下来我们学习第二种排序算法：选择排序 -------------------- 选择排序算法通过选择和交换来排序，其排序流程如下： 1）首先从原始数组中选择最

素颜马尾好姑娘i/ 2022年08月21日 07:56/ 0 赞/ 238 阅读

相关算法学习笔记之冒泡排序算法

我们这里先介绍几种适用的比较少的数据时候，算法复杂度都是O(n2),介绍三种算法： ①冒泡排序算法 ②选择排序算法 ③插入排序算法这篇介绍第一种：冒泡排序算法

迷南。/ 2022年08月21日 07:49/ 0 赞/ 318 阅读

相关【算法学习笔记】-排序算法

排序算法常见的有：直接插入排序，归并排序，堆排序，快速排序和冒泡排序等。它们的性能如下表所示： ![Center][] 注：排序算法的稳定性：假定在待排序的记录序列中

﹏ヽ暗。殇╰゛Y/ 2022年08月04日 11:51/ 0 赞/ 211 阅读

相关排序算法之初级排序

该系列是我看人民邮电出版社的《算法》这本书的一些理解，不写下来感觉很快就忘掉，代码来自原书。初级排序主要包括简单的选择排序和插入排序，以及插入排序的一个优化：

曾经终败给现在/ 2022年07月14日 10:21/ 0 赞/ 305 阅读

相关代码笔记：排序算法初级比较

Think: 1感觉自己的代码可能会超时，但是提交AC，自己需要思考更优化的算法 2贪心算法思想：由当前的最优解最终得到最终最优解（局部最优解得到最终最优解）商人小

àì夳堔傛蜴生んèń/ 2022年06月17日 03:38/ 0 赞/ 208 阅读

相关排序——初级排序算法

I. Compare接口 Java中提供了 `Compare` 接口来给我们自定义的数据类型定义排序规则，`Compare` 接口的定义如下，实现该接口需要重写 `com

た入场券/ 2022年05月14日 00:35/ 0 赞/ 240 阅读