-
数据结构Python实现-直接插入排序算法
2019-10-05 11:30:58直接插入排序算法思想: 每步将一个待排序的纪录,按其关键码值的大小插入前面已经排序的文件中适当位置上,直到全部插入完为止。 range: range是左闭右开 for i in range(5): print(i) 输出1 2 3 4 直接...直接插入排序算法思想:
每步将一个待排序的纪录,按其关键码值的大小插入前面已经排序的文件中适当位置上,直到全部插入完为止。
range:
range是左闭右开
for i in range(5): print(i)
输出1 2 3 4
直接插入排序代码实现:
def insert_sort(alist): n=len(alist) for j in range(1,n): for i in range(j): if alist[i] > alist[j]: alist[j],alist[i]=alist[i],alist[j] #return alist if __name__ =="__main__": alist=[0,1,8,7,9,2,10] print(alist) insert_sort(alist) print(alist)
此方法是每次都和前面的第一个进行比较,如果前面的大,那么交换,如果一直不大,那么其在原位置不动。其中每次交换后
def insert_sort(alist): n=len(alist) for j in range(1,n): for i in range(j,0,-1): if alist[i] < alist[i-1]: alist[i],alist[i-1]=alist[i-1],alist[i] #return alist if __name__ =="__main__": alist=[0,1,8,7,9,2,10] print(alist) insert_sort(alist) print(alist)
最常见的是此种方法,每次都是把要比较的那个和前面那个进行比较,如果比前面那个小,则进行交换,一直到和第一个比较完毕。这里不懂的地方是怎么从后往前来用Python书写,其(j,0,-1)从 j 开始到 1 步长 -1
def insert_sort(alist): n=len(alist) for j in range(1,n): i=j while i > 0: if alist[i] < alist[i-1]: alist[i],alist[i-1]=alist[i-1],alist[i] i-=1 else: break; #return alist if __name__ =="__main__": alist=[0,1,8,7,9,2,10] print(alist) insert_sort(alist) print(alist)
while方法写直接插入排序
range用法巩固
- range(9) 为0~8的有序集合
- range(start,stop,[step]) start表示数字的开始值,stop代表数字的结束值,step代表循环时数字递增的步长(默认值为1)
-
数据结构 | 排序算法总结——(一)直接插入排序(附Java实现代码)
2020-09-03 16:12:29算法的稳定性:如果待排序表中有两个元素Ri、Rj,其对应的关键字keyi=keyj,且在排序前Ri在Rj前面,如果使用某一排序算法排序后,Ri仍在Rj的前面,则称这个排序算法是稳定的。 分类:在排序过程中,根据数据元素...1.1排序基本概念
排序:重新排列表中的元素,使表中的元素满足按关键字递增或递减的过程。
算法的稳定性:如果待排序表中有两个元素Ri、Rj,其对应的关键字keyi=keyj,且在排序前Ri在Rj前面,如果使用某一排序算法排序后,Ri仍在Rj的前面,则称这个排序算法是稳定的。
分类:在排序过程中,根据数据元素是否完全在内存中,可将排序算法分为两类。
内部排序:在排序期间元素全部存放在内存中的排序。
外部排序:在排序期间元素无法全部同时存放在内存中,必须在排序过程中根据要求不断地在内外存之间移动的排序。
1.2插入排序
基本思想:每次将一个待排序的记录,按其关键字大小插入到前面已经排好序的子序列中,直到全部记录完成。
1.2.1直接插入排序
原理:把n个待排序的元素看成一个有序表和一个无需表,开始的时候有序表只有1个元素,无序表中有n-1个元素每次从无序表中取出第一个元素,将它插入到有序表中,使之成为新的有序表,重复n-1次完成整个排序过程。
具体流程如下:
- 首先比较数组的前两个数据,并排序;
- 比较第三个元素与前两个排好序的数据,并将第三个元素放入适当的位置;
- 比较第四个元素与前三个排好序的数据,并将第四个元素放入适当的位置;
… - 直至把最后一个元素放入适当的位置
实例:
0.初始状态 3,1,5,7,2,4,9,6(共8个数)
有序表:3;无序表:1,5,7,2,4,9,6
1.第一次循环,从无序表中取出第一个数 1,把它插入到有序表中,使新的数列依旧有序
有序表:1,3;无序表:5,7,2,4,9,6
2.第二次循环,从无序表中取出第一个数 5,把它插入到有序表中,使新的数列依旧有序
有序表:1,3,5;无序表:7,2,4,9,6
3.第三次循环,从无序表中取出第一个数 7,把它插入到有序表中,使新的数列依旧有序
有序表:1,3,5,7;无序表:2,4,9,6
4.第四次循环,从无序表中取出第一个数 2,把它插入到有序表中,使新的数列依旧有序
有序表:1,2,3,5,7;无序表:4,9,6
5.第五次循环,从无序表中取出第一个数 4,把它插入到有序表中,使新的数列依旧有序
有序表:1,2,3,4,5,7;无序表:9,6
6.第六次循环,从无序表中取出第一个数 9,把它插入到有序表中,使新的数列依旧有序
有序表:1,2,3,4,5,7,9;无序表:6
7.第七次循环,从无序表中取出第一个数 6,把它插入到有序表中,使新的数列依旧有序
有序表:1,2,3,4,5,6,7,9;无序表:(空)性能分析:
空间效率:仅使用常数个辅助单元,空间复杂度O(1)
时间效率:时间复杂度O(n2)最差情况:反序,需要移动n*(n-1)/2个元素,时间复杂度O(n2)
最好情况:正序,不需要移动元素,时间复杂度O(n)稳定性:稳定的
适用性:适用于顺序存储和链式存储的线性表
import java.util.Scanner; import java.util.Arrays; public class InsertSort { public static void insertSort(int[] arr){ int i=0,j=0,temp=0;//定义变量i,j,temp并初始化 for (i=1;i<arr.length;i++){//从第二个开始比较 temp = arr[i]; for (j=i-1;j>=0;j--){ if (arr[j]>temp){//如果前面的数大于当前数,将它后移 arr[j+1] = arr[j]; }else { break; } } arr[j+1] = temp;//一轮比较结束,将此轮确定元素放到正确位置 } System.out.println("直接插入排序:"+Arrays.toString(arr)); } public static void main(String[] args) { Scanner scanner = new Scanner(System.in);//Scanner工具类键盘输入数据 while (scanner.hasNext()) { int n = scanner.nextInt(); if (n > 0) { int arr[] = new int[n]; for (int i = 0; i < n; i++) { arr[i] = scanner.nextInt(); } insertSort(arr);//调用直接插入排序insertSort方法 } } } }
-
数据结构排序算法(一)直接插入排序
2018-09-02 09:59:02直接插入排序算法的思想:每次将一个待排序的记录,按其关键字大小插入到前面已经排好序的子序列中,直到全部记录插入完成。 代码如下: def insert_sort(a,n): #a是待排序的数组,n是数组的长度 for i in ...直接插入排序算法的思想:每次将一个待排序的记录,按其关键字大小插入到前面已经排好序的子序列中,直到全部记录插入完成。
代码如下:这里写代码片def insert_sort(a,n): #a是待排序的数组,n是数组的长度 for i in range(1,n):#将循环从1开始而不是从0开始 if a[i-1]>a[i]:#如果带插入的值小于前面的值,就将带插入的值赋值给t #j是为了给带插入的元素寻找位置而添加的变量 t=a[i] j=i-1 while a[j]>t and j>=0: a[j+1]=a[j] j-=1 a[j+1]=t#因为在while循环的时候j值已经减了一,所以最后要把这个1加上 a=[3,1,2,6,8,5] insert_sort(a,len(a)) print(a)
-
数据结构经典算法之直接插入排序
2019-03-24 16:32:38目录 插入排序 直接排序 一、排序原理 二、时间复杂度 三、 动画演示 ...四、实现代码 ...五、算法分析: ...概念:所谓排序,就是整理文件中的记录。使之按关键字递增(或递减)的次序...插入排序方法主要有直接插...目录
概念:所谓排序,就是整理文件中的记录。使之按关键字递增(或递减)的次序排列起来,当待排序关键字均不相同时,排序结果是唯一的,否则排序结果不唯一。
插入排序
基本思想:每步将一个待排序码值的大小,插到前面已经排好的文件中的适当位置,直到全部插入完为止。插入排序方法主要有直接插入排序和希尔排序。
直接排序
一、排序原理
核心思想:插入排序通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入 ,如此重复,直至完成序列排序。(类似于扑克牌,打牌的时候,你拿一张牌,你要排一下顺序,看拿到的牌的大小,大的往后,小的直接插前面,但不同的是你拿到牌直接能看出来放哪,而在计算机里的排序,必须先比较,前面已经排好的数字,你才知道放哪),直接插入排序就是按这个思想来走的。
二、时间复杂度
1. 直接插入排序最好的时间复杂度为O(n)
2. 直接插入排序的最坏时间复杂度为O(n^2)
3. 因此直接插入排序总的平均时间复杂度为O(n^2)
注:具有稳定性
三、 动画演示
四、实现代码// 直接插入排序(C++) void InsertSort(vector<int> &vi) { for(int i=1;i<vi.size();i++) { int temp=vi[i]; int j; for(j=i-1;j>=0&&temp<vi[j];j--) { vi[j+1]=vi[j]; //将较大元素后移 } vi[j+1]=temp; //temp插入正确的位置 } }
五、算法分析:
1. 从序列第一个元素开始,该元素可以认为已经被排序
2. 取出下一个元素,设为待插入元素,在已经排序的元素序列中从后向前扫描,如果该元素(已排序)大于待插入元素,将该元素移到下一位置。
3. 重复步骤2,直到找到已排序的元素小于或者等于待排序元素的位置,插入元素
4. 重复2,3步骤,完成排序。 -
数据结构与算法笔记 —— 排序算法及代码实现
2016-03-08 09:31:00数据结构与算法笔记 —— 排序算法及代码实现一. 直接插入排序直接插入排序是向一个已经排序好的序列中插入一个数,但是,插入此数后,序列的仍然有序。改算法的时间复杂度为 O(n2)O(n^{2}) ,时间复杂度较高。适合... -
数据结构与算法:冒泡/简单选择/直接插入/堆/归并/快速排序介绍以及代码实现
2020-06-10 16:19:00介绍了冒泡排序、简单选择排序、直接插入排序、希尔排序、堆排序、归并排序、快速排序等主要排序算法。并在文章的最后对这几类算法做了一个简单的对比。 首先了解几个概念: 排序的稳定性: 对于值相等的两个元素... -
数据结构与算法(一):插入排序
2020-10-29 17:44:09插入排序主要包括直接插入排序和希尔排序两种。 Q: 直接插入排序 每次从无序区取出第一个元素把它插入到有序区的适当位置,使之成为新的有序区,经过n-1次插入后完成。 时间复杂度:最好是O(n),最坏是O(n^2) 空间... -
数据结构 | 排序算法总结——(三)希尔排序排序(附Java实现代码)
2020-09-03 17:27:23先在各组内进行直接插入排序;然后,取第二个增量d2<d1重复上述的分组和排序,直至所取的增量dt=1(dt<dt-l<…<d2<d1),即所有记录放在同一组中进行直接插入排序为止。 具体算法步骤: 选择一个增量... -
数据结构与算法(c++)--排序算法
2020-09-11 13:12:43这篇文章主要简单记录下数据结构与算法中的排序算法技术 只记录下了七种排序算法: 插入排序 直接插入排序 希尔排序 交换排序 起泡排序 快速排序 选择排序 简单选择排序 堆排序 归并排序 二路归并排序 插入... -
《数据结构》复习之排序算法
2016-07-06 16:07:501排序算法的稳定性 2复杂度总结 3稳定性总结 4其他1.排序算法1.1直接插入排序 算法思想: 每次将一个待排序的数据元素,插入到前面已经排好序的数列中的适当位置,使数列 依然有序;直到待排序数据元素全部插入... -
【数据结构】排序算法
2018-07-26 13:28:00直接插入排序、折半插入排序、2-路插入排序、表插入排序、希尔排序、快速排序、冒泡排序 2)选择排序 简单选择排序、堆排序 2, 直接插入排序(Insertion Sort) 1)原理 每次将一个待排序的记录,按其... -
数据结构排序算法总结
2019-08-05 09:19:24(1)直接插入排序 基本思想:每次将一个待排序的记录按其关键字大小插入到前面已排好的子序列中。 代码: step1——查找出插入位置 step2——前面的元素全部后移 step3——复制到插入位上 void ... -
数据结构-排序算法原理和Python实现
2017-04-09 22:30:47排序算法概览插入排序基本思想是每次讲一个待排序的记录,按其关键字大小插入到前面已拍好的子序列中,直到全部完成。直接插入排序讲元素L(i)插入到有序序列L[1,…,i-1]中,执行以下操作: 1. 查找出L -
数据结构常见排序算法解析和时间复杂度
2020-06-01 20:10:32因此,从上面的描述中我们可以发现,直接插入排序可以用两个循环完成: 第一层循环:遍历待比较的所有数组元素 第二层循环:将本轮选择的元素(selected)与已经排好序的元素(ordered)相比较。 如果:selected > ... -
数据结构算法动图识记_10大经典排序算法动图演示,看这篇就够了!(配相应代码)...
2020-12-20 14:12:56排序算法是《数据结构与算法》中最基本的算法之一。排序算法可以分为内部排序和外部排序。内部排序是数据记录在内存中进行排序。而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外... -
数据结构之之一: 直接插入排序 && 冒泡排序
2010-11-02 13:07:051,冒泡排序 在要排序的一组数中,对当前还未排好序的范围内的全部数,自上 而下对相邻的两个数依次进行比较和调整,让较大的数往下沉,较 小的往上冒。即:每当两相邻的数比较后发现它们的排序与排序要 求相反... -
数据结构----直接选择排序C++代码
2018-12-20 21:10:43直接插入排序是一种最简单的排序方法,其基本操作是将一条记录插入到已经排好序的有序表中,从而得到一个新的、记录数增1的有序表。 算法步骤: 首先在当前有序区R[1..i-1]中查找R[i]的正确插入位置k(1≤... -
利用Python实现十大经典排序算法(附代码流程)
2020-02-09 15:50:09排序算法是《数据结构与算法》中最基本的算法之一。 排序算法可以分为内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问... -
关于数据结构中的几种排序以及相关代码实现
2018-09-14 09:10:06目录结构以及排序算法比较: ... 直接插入排序 直接插入排序是一种简单的插入排序法,其基本思想是:把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中,直到所有的记录插入完为止,得到... -
数据结构之希尔排序图文详解及代码(C++实现)
2018-07-11 20:17:05n)把全部记录分为d1个组,所有间隔为d1的记录分在同一组,在各个组中进行直接插入排序。 2、第二趟取增量d2(d2<d1),重复上述的分组和排序。 3、以此类推,直到所取的增量dt=1(dt<dt_1<d_t-2... -
knn算法代码java_Java十大经典排序算法动画解析和 代码实现
2021-01-21 06:55:07排序算法是《数据结构与算法》中最基本的算法之一。排序算法可以分为内部排序和外部排序。内部排序是数据记录在内存中进行排序。而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外... -
【常用排序算法】以最简单的方式理解插入排序
2017-10-19 16:03:06插入排序的工作原理非常像抓扑克牌,最开始是一张,大的放后面,小的放前面。 主要要实现的就是插入,时间复杂度是O(1);但是主要费时的就是插入要实现插入位置之后的元素全部往后移动一位,但是如果插入的元素是... -
数据结构学习笔记(14)---插入排序
2017-10-22 14:42:13数据结构学习笔记(14)—内部排序基本思想:在一个已经排好序的记录子集的基础上,每一步将下一个人等待排序的记录有序插入到已经排序的记录子集上,知道所有待排序记录全部插入为止。(1)直接插入排序:直接插入... -
数据结构经典算法之希尔排序
2019-03-27 16:48:22目录 希尔排序 一、操作方法 ...所有距离为d1的倍数的记录放在同个一个组中,现在各组内进行直接插入排序;然后,取第二个增量d2<d1重复上述的分组中的分组和排序,直到所取的增量dt=(d... -
c++代码实现 模糊综合算法_十大经典排序算法动画解析和 Java 代码实现
2021-01-10 04:51:18排序算法是《数据结构与算法》中最基本的算法之一。排序算法可以分为内部排序和外部排序。内部排序是数据记录在内存中进行排序。而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外... -
【数据结构与算法】-【排序:希尔排序】
2020-06-11 19:04:08希尔排序 1.基本思路 ... * 先在各组内进行直接插入排序;然后,取第二个增量d2<d1重复上述的分组和排序, * 直至所取的增量dt=1(dt<dt-l<…<d2<d1),即所有记录放在同一组中进行直接插入排 -
java代码_十大经典排序算法动画解析和 Java 代码实现
2020-10-21 21:42:45排序算法是《数据结构与算法》中最基本的算法之一。排序算法可以分为内部排序和外部排序。内部排序是数据记录在内存中进行排序。而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外... -
java分治法求数列的最大子段和_Java十大经典排序算法动画解析和 代码实现
2020-11-24 00:39:37排序算法是《数据结构与算法》中最基本的算法之一。排序算法可以分为内部排序和外部排序。内部排序是数据记录在内存中进行排序。而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外... -
java 快速排序_十大经典排序算法动画解析和 Java 代码实现
2020-11-29 05:36:18排序算法是《数据结构与算法》中最基本的算法之一。排序算法可以分为内部排序和外部排序。内部排序是数据记录在内存中进行排序。而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外... -
数据结构与算法理论篇--希尔排序
2020-04-13 21:47:34先取一个小于n的整数d1作为第一个增量,把表的全部元素分成d1个组,将所有距离为d1的倍数的元素放在同一个组中,在各个组内进行直接插入排序,依次重复。 举个栗子:{9,8,7,6,5,4,3,2,1,0}。例子中有10个数,d=5时,...