直接插入排序

#include<stdio.h>#include<malloc.h>#include<stdlib.h>#include<time.h>#define MAXSIZE 100/***************定义和初始化顺序表************************/ typedef int DataType;typedef struct node {DataType data[MAXSIZE];int length;}SeqList,*PseqList;//定义一个顺序表。

PseqList Init_SeqList(void){PseqList PL;PL=(PseqList)malloc(sizeof(SeqList));if(PL)PL->length=0;return(PL);}//顺序表的初始化./*********************直接插入排序**********************/ void StraightInsertSort(SeqList *s){int i,j;for(i=2;i<s->length;i++){s->data[0]=s->data[i];for(j=i-1;s->data[0]<s->data[j];j--){s->data[j+1]=s->data[j];}s->data[j+1]=s->data[0];}}/*******************快速排序************************/int QuickSort1(SeqList *s,int low,int high){s->data[0]=s->data[low];while(low<high){while(low<high&&s->data[high]>=s->data[0])high--;s->data[low]=s->data[high];while(low<high&&s->data[low]<=s->data[0])low++;s->data[high]=s->data[low];}s->data[low]=s->data[0];return low;}void QuickSort(PseqList s,int low,int high){int m;if(low<high){m=QuickSort1(s,low,high);QuickSort(s,low,m-1);QuickSort(s,m+1,high);}}/******************大根堆排序************************/ void HeapAdjust(SeqList *s,int n,int m){int i,j;s->data[0]=s->data[n];i=n;for(j=2*i;j<=m;j=j*2){if(j<m&&s->data[j]<s->data[j+1])j++;if(s->data[0]>s->data[j]) break;s->data[i]=s->data[j];i=j;}s->data[i]=s->data[0];}void HeapSort(SeqList *s){int i;for(i=s->length/2;i>0;i--)HeapAdjust(s,i,s->length-1);for(i=s->length-1;i>1;i--){s->data[0]=s->data[1];s->data[1]=s->data[i];s->data[i]=s->data[0];HeapAdjust(s,1,i-1);}}/*****************归并排序************************/ void Merge(DataType r[],DataType rf[],int u,int v,int t){int i,j,k;for(i=u,j=v+1,k=u;i<=v&&j<=t;k++){if(r[i]<=r[j]){rf[k]=r[i];i++;}else{rf[k]=r[j];j++;}}while(i<=v) rf[k++]=r[i++];while(j<=t) rf[k++]=r[j++];}void MSort(DataType p[],DataType p1[],int n,int t){int m;DataType p2[MAXSIZE+1];if(n==t)p1[n]=p[n];else{m=(n+t)/2;MSort(p,p2,n,m);MSort(p,p2,m+1,t);Merge(p2,p1,n,m,t);}}void MergeSort(PseqList s){MSort(s->data,s->data,1,s->length-1);}/********************主函数*************************/ void main(){PseqList p;int i,n=0;srand((unsigned)time(NULL));p=Init_SeqList();for(i=1;i<=20;i++){p->data[i]=rand()%20+1;}p->length=i;printf("输出原序列：\n");for(i=1;i<p->length;i++) printf("%3d",p->data[i]);while(n==0||n==1||n==2||n==3||n==4){printf("\n请选择：1.直接插入排序;2.快速排序;3.大根堆排序;4.归并排序;其它退出\n");n=0;scanf("%d",&n);switch(n){case 1:StraightInsertSort(p);printf("输出直接插入排序后序列：\n");break;case 2:QuickSort(p,1,p->length-1);printf("输出快速排序序列：\n");break;case 3:HeapSort(p);printf("输出大根堆排序序列：\n");break;case 4:MergeSort(p);printf("输出归并排序序列：\n");break;default:printf("******error!*******\n");return;}for(i=1;i<p->length;i++) printf("%3d",p->data[i]);printf("\n");}}。

20
交换类
（2）快速排序 快速排序采用分而治之(Divide and Conquer)
的策略将问题分解成若干个较小的子问题，采用 相同的方法一一解决后，再将子问题的结果整合 成最终答案。快速排序的每一轮处理其实就是将 这一的基准数定位，直到所有的数都排序完成 为止。
21
快速排序的基本步骤：
1. 选定一个基准值（通常可选第一个元素）； 2. 将比基准值小的数值移到基准值左边，形
14
• 交换类
交换类排序的基本思想是：通过交换无序序列 中的记录得到其中关键字最小或最大的记录，并将 其加入到有序子序列中，最终形成有序序列。交换 类排序可分为冒泡排序和快速排序等。
15
交换类
（1）冒泡排序 两两比较待排序记录的关键字，发现两
个记录的次序相反时即进行交换，直到没有 反序的记录为止。因为元素会经由交换慢慢 浮到序列顶端，故称之为冒泡排序。
3. 最后对这个组进行插入排序。步长的选法 一般为 d1 约为 n/2，d2 为 d1 /2， d3 为 d2/2 ，…， di = 1。
11
【例】给定序列（11，9，84，32，92，26，58，91，35， 27，46，28，75，29，37，12 ），步长设为d1 =5、d2 =3、 d3 =1，希尔排序过程如下：
for i in range(1,len(alist)):
#外循环n-1
for j in range(i,0,-1):
#内循环
if alist[j]<alist[j-1]:
alist[j],alist[j-1]=alist[j-1],alist[j] #交换
li=[59,12,77,64,72,69,46,89,31,9] print('before: ',li) insert_sort(li) print('after: ',li)

c#实现的⼏种排序⽅法1.经典排序算法 – 插⼊排序Insertion sort插⼊排序就是每⼀步都将⼀个待排数据按其⼤⼩插⼊到已经排序的数据中的适当位置，直到全部插⼊完毕。

插⼊排序⽅法分直接插⼊排序和折半插⼊排序两种，这⾥只介绍直接插⼊排序，折半插⼊排序留到“查找”内容中进⾏。

图1演⽰了对4个元素进⾏直接插⼊排序的过程，共需要(a),(b),(c)三次插⼊。

public void Sort(int[] arr){for (int i = 1; i < arr.Length; i++){int t = arr[i];int j = i;while ((j > 0) && (arr[j - 1] > t)){arr[j] = arr[j - 1];//交换顺序--j;}arr[j] = t;}}折半排序算法是对直接插⼊算法的⼀种优化，优化的核⼼是：通过折半查看有序数组中间位置的数值（a）与待插⼊的数值（temp）的⼤⼩，如果a>=temp，则转向折半的左区间继续折半查找；如果a<temp，则转向折半后的右区间继续折半查找。

直到左右下标相同时，此时折半的下标也指向相同的位置，再做最后⼀次循环，最终的结果是：左右下标相差1，并且原来左侧的下标指向⼤于temp的位置，原来右侧的下标指向了⼩于temp的位置，即：array[biggerIndex] < temp < array[smallerIndex]。

//折半排序算法（传递待排数组名，即：数组的地址。

故形参数组的各种操作反应到实参数组上）private static void BinaryInsertionSortFunction(int[] array){try{int smallerIndex = 0; //记录有序数组的起始位置int biggerIndex = 0; //记录有序数组的终⽌位置int midIndex = 0; //记录获取有序数组的中间位置（折半法的关键：折半的位置）int temp; //记录带排的数值for (int i = 1; i < array.Length; i++) //循环向有序数组中插⼊数值（i从1开始，因为操作的是同⼀个数组）{temp = array[i]; //记录待插⼊有序数组的数值biggerIndex = i - 1;//当smallerIndex==biggerIndex时，进⼊最后⼀次循环：smallerIndex指向⼤于temp的数组位置，biggerIndex指向⼩于temp的数组位置while (smallerIndex <= biggerIndex){midIndex = (smallerIndex + biggerIndex) / 2; //确定折半的位置if(array[midIndex] >= temp) //折半位置的数值 >= temp{biggerIndex = midIndex - 1; //biggerIndex以midIndex为基础向前移动⼀位}else{smallerIndex = midIndex + 1; //smallerIndex以midIndex为基础向后移动⼀位}}for (int j = i - 1; j >biggerIndex; j--) //将有序数组中⼤于temp的数值分别向后移动⼀位{array[j + 1] = array[j]; //}array[biggerIndex + 1] = temp; //将temp插⼊biggerIndex + 1，因为此时array[biggerIndex]<temp<array[smallerIndex]}}catch (Exception ex){ }}2. //选择排序public static void SelectionSort(int[] num){int min, temp;for (int i = 0; i < num.Length-1; i++){min = i;for (int j =i+1; j < num.Length; j++){if (num[j] < num[min]){min = j;}}temp = num[i];num[i] = num[min];num[min] = temp;}}3. //冒泡排序(Bubble Sort)的基本思想是：将相邻的记录的关键码进⾏⽐较，若前⾯记录的关键码⼤于后⾯记录的关键码，则将它们交换，否则不交换。

当n较大，则应采用时间复杂度为O(nlog2n)的排序方法：快速排序、堆排序或归并排序序。

快速排序：是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短；1. 插入排序—直接插入排序(Straight Insertion Sort)基本思想:将一个记录插入到已排序好的有序表中，从而得到一个新，记录数增1的有序表。

即：先将序列的第1个记录看成是一个有序的子序列，然后从第2个记录逐个进行插入，直至整个序列有序为止。

要点：设立哨兵，作为临时存储和判断数组边界之用。

直接插入排序示例：如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。

所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳定的。

算法的实现：效率：时间复杂度：O（n^2）.其他的插入排序有二分插入排序，2-路插入排序。

2. 插入排序—希尔排序（Shell`s Sort）希尔排序是1959 年由D.L.Shell 提出来的，相对直接排序有较大的改进。

希尔排序又叫缩小增量排序基本思想：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。

操作方法：1.选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；2.按增量序列个数k，对序列进行k 趟排序；3.每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。

仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

希尔排序的示例：算法实现：我们简单处理增量序列：增量序列d = {n/2 ,n/4, n/8 .....1} n为要排序数的个数即：先将要排序的一组记录按某个增量d（n/2,n为要排序数的个数）分成若干组子序列，每组中记录的下标相差d.对每组中全部元素进行直接插入排序，然后再用一个较小的增量（d/2）对它进行分组，在每组中再进行直接插入排序。

哨兵的作用
哨兵的作用
算法中引进的附加记录R称监视哨或哨兵(Sentinel)。 哨兵有两个作用： ①进入查找(插入位置)循环之前，它保存了R[i]的副本，使不致于因记录后移而丢失R[i]的内容； ②它的主要作用是：在查找循环中"监视"下标变量j是否越界。一旦越界(即j=0)，因为R.可以和自己比较， 循环判定条件不成立使得查找循环结束，从而避免了在该循环内的每一次均要检测j是否越界(即省略了循环判定 条件"j>=1")。 注意： ①实际上，一切为简化边界条件而引入的附加结点(元素)均可称为哨兵。 【例】单链表中的头结点实际上是一个哨兵 ②引入哨兵后使得测试查找循环条件的时间大约减少了一半，所以对于记录数较大的文件节约的时间就相当 可观。对于类似于排序这样使用频率非常高的算法，要尽可能地减少其运行时间。所以不能把上述算法中的哨兵 视为雕虫小技，而应该深刻理解并掌握这种技巧。
算法描述
算法描述
Python代码实现 C/C+ve-C实现 JAVA实现 C#实现
谢谢观看
直接插入排序
一种最简单的排序方法
01 简介
03 过程实例
目录
02 哨兵的作用 04 算法描述
基本信息
直接插入排序（Straight Insertion Sort）是一种最简单的排序方法，其基本操作是将一条记录插入到已 排好的有序表中，从而得到一个新的、记录数量增1的有序表。
简介
引言 基本思想
基本思想
每一趟将一个待排序的记录，按其关键字的大小插入到已经排好序的一组记录的适当位置上，直到所有待排 序记录全部插入为止。
待排序记录 R1，R2，…，Rn–1, Rn 第一步：R1 第二步：(R1 ), R2 第三步：(R1, R2), R3 …… 第 j步：(R1，R2，…，Rj–1), Rj …… 第 n步: (R1，R2，…，Rn–1), Rn． 例：j=5

插入排序的基本概念插入排序是一种简单直观的排序算法，它通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

插入排序的时间复杂度为O(n^2)，但在小规模数据时表现优异，且稳定性较好。

一、基本思想插入排序将待排序数组分为已排好序和未排好序两部分。

每次将未排好序的第一个元素插入到已排好序部分的相应位置，直至全部元素有序。

二、具体实现1. 直接插入排序直接插入排序是最基本的插入排序算法。

它从第二个元素开始遍历待排数组，将当前元素与前面已经排好序的元素依次比较，找到合适位置并插入。

2. 希尔排序希尔排序是直接插入排序的改进版。

它通过设置增量gap来分组进行直接插入排序，每轮对每个组进行一次直接插入排序。

随着增量gap逐渐减小，组数也逐渐减少，当gap=1时即为最后一轮直接插入排序。

三、优化方案1. 二分查找优化在寻找待插入位置时使用二分查找可以提高效率。

二分查找的时间复杂度为O(logn)，相比于直接比较可以减少一部分比较次数。

2. 跳跃式插入跳跃式插入是对直接插入排序的优化，它将待插入元素与一定间隔的元素进行比较，从而减少了比较次数。

四、应用场景由于插入排序在小规模数据时表现优异，因此常被用于对小规模数据进行排序。

同时，由于其稳定性较好，也常被用于稳定性要求较高的场景。

五、总结插入排序是一种简单直观的排序算法，通过构建有序序列实现对待排数组的排序。

虽然时间复杂度为O(n^2)，但在小规模数据时表现优异，并且稳定性良好。

同时，通过二分查找和跳跃式插入等优化方案可以进一步提高效率。

⽤Java实现常见的8种内部排序算法⼀、插⼊类排序插⼊类排序就是在⼀个有序的序列中，插⼊⼀个新的关键字。

从⽽达到新的有序序列。

插⼊排序⼀般有直接插⼊排序、折半插⼊排序和希尔排序。

1. 插⼊排序1.1 直接插⼊排序/*** 直接⽐较，将⼤元素向后移来移动数组*/public static void InsertSort(int[] A) {for(int i = 1; i < A.length; i++) {int temp = A[i]; //temp ⽤于存储元素，防⽌后⾯移动数组被前⼀个元素覆盖int j;for(j = i; j > 0 && temp < A[j-1]; j--) { //如果 temp ⽐前⼀个元素⼩，则移动数组A[j] = A[j-1];}A[j] = temp; //如果 temp ⽐前⼀个元素⼤，遍历下⼀个元素}}/*** 这⾥是通过类似于冒泡交换的⽅式来找到插⼊元素的最佳位置。

⽽传统的是直接⽐较，移动数组元素并最后找到合适的位置*/public static void InsertSort2(int[] A) { //A[] 是给定的待排数组for(int i = 0; i < A.length - 1; i++) { //遍历数组for(int j = i + 1; j > 0; j--) { //在有序的序列中插⼊新的关键字if(A[j] < A[j-1]) { //这⾥直接使⽤交换来移动元素int temp = A[j];A[j] = A[j-1];A[j-1] = temp;}}}}/*** 时间复杂度：两个 for 循环 O(n^2)* 空间复杂度：占⽤⼀个数组⼤⼩，属于常量，所以是 O(1)*/1.2 折半插⼊排序/** 从直接插⼊排序的主要流程是：1.遍历数组确定新关键字 2.在有序序列中寻找插⼊关键字的位置* 考虑到数组线性表的特性，采⽤⼆分法可以快速寻找到插⼊关键字的位置，提⾼整体排序时间*/public static void BInsertSort(int[] A) {for(int i = 1; i < A.length; i++) {int temp = A[i];//⼆分法查找int low = 0;int high = i - 1;int mid;while(low <= high) {mid = (high + low)/2;if (A[mid] > temp) {high = mid - 1;} else {low = mid + 1;}}//向后移动插⼊关键字位置后的元素for(int j = i - 1; j >= high + 1; j--) {A[j + 1] = A[j];}//将元素插⼊到寻找到的位置A[high + 1] = temp;}}2. 希尔排序希尔排序⼜称缩⼩增量排序，其本质还是插⼊排序，只不过是将待排序列按某种规则分成⼏个⼦序列，然后如同前⾯的插⼊排序⼀般对这些⼦序列进⾏排序。

24种插入法24种插入法是一种优化排序算法，它的基本思想是将一个列表分为已排序区间和未排序区间，每次从未排序区间取出一个元素，插入到已排序区间的正确位置，使已排序区间保持有序。

在这个过程中，相邻元素的比较和交换次数都很少，所以可以提高排序的效率。

此外，24种插入法还有一些变体，可以根据不同情况选用相应的插入法，达到更好的排序效果。

以下是24种插入法的详细介绍：1. 直接插入排序直接插入排序是最简单的插入法，它将未排序元素插入到已排序区间合适的位置。

时间复杂度为O(n²)，空间复杂度为O(1)。

2. 折半插入排序折半插入排序是对直接插入排序的优化，它采用二分查找的方式找到插入位置。

时间复杂度为O(n²)，空间复杂度为O(1)。

3. 希尔排序希尔排序是一种针对直接插入排序的改进，它将列表按照一定步长分组，每个子列表采用直接插入排序，随着步长逐渐缩小，最终变为一组，完成排序。

时间复杂度为O(nlogn)，空间复杂度为O(1)。

4. 二路插入排序二路插入排序是对直接插入排序的改进，它采用两个指针，在有序区间之前和之后分别插入未排序元素。

时间复杂度为O(n²)，空间复杂度为O(1)。

5. 多关键词插入排序多关键词插入排序是针对多关键词排序的优化，它将排序条件拆分为多个关键词，分别进行插入排序。

时间复杂度为O(nlogn)，空间复杂度为O(1)。

6. 基数插入排序基数插入排序是对基数排序的优化，它使用插入法对每个桶内的元素进行排序，并合并桶内已排序的元素。

时间复杂度为O(dn)，空间复杂度为O(max)。

7. 大小插入排序大小插入排序是对多关键词排序的优化，它根据元素的大小关系建立排序树，对树进行遍历并插入已排序区间。

时间复杂度为O(nlogn)，空间复杂度为O(nlogn)。

8. 块插入排序块插入排序是对桶排序的优化，它将待排序元素分为若干块，分别进行插入排序，再将已排序块合并。

插入排序、冒泡排序和选择排序之间的比较。 除了直接插入排序，我们还可以学习其他很多排序算法。
感谢观看！
1 信息
更多信息和算法请访问 我们的网站。
2 学习
访问我们的课程和图书 来提升你的技能。
3 代码
查看我们的代码库，学 习更多关于算法和数据 件
欢迎来到这个课件！在这个课件里，我们将会学习关于直接插入排序的一些 基础知识。
什么是直接插入排序？
简介
直接插入排序是一种简单 的排序算法。
适用场景
通常用于对少量元素进行 排序。
核心思想
通过不断比较和移动元素， 将一个无序的数列变为有 序。
工作原理
1
已排序的元素
从第一个元素开始，该元素可以认为已经被排序。
2
寻找插入位置
取出下一个元素，在已经排序的元素序列中从后向前扫描。
3
后移元素
如果被扫描的元素（已排序）大于新元素，将该元素后移一位。
4
插入新元素
重复步骤 3 直到找到已排序的元素小于或者等于新元素的位置。将新元素插入到该位 置后。
示例代码
Java 代码
在 Java 中实现直接插入算法。 我们可以通过使用上述代码实现直接插入排序。
时间复杂度
1 最好情况
2 最坏情况
时间复杂度为 O(n)。
时间复杂度为 O(n²)。
直接插入排序的时间复杂度取决于排序数据的初始顺序。
总结
优点
简单而有效，适用于排序少量元素。
缺点
时间复杂度为平方级别，不适合排序大量元素。
思考
你认为还有哪些实际应用可以使用直接插入排序？
常见的排序算法
几种排序算法的比较

直接插入排序的主要代码直接插入排序是一种简单但有效的排序算法。

它的基本思想是将待排序的元素插入到已经排好序的序列中，从而得到一个新的有序序列。

下面将详细介绍直接插入排序的主要代码。

一、算法流程直接插入排序的算法流程如下：1. 将待排序的元素分为已排序区间和未排序区间，初始时已排序区间只包含一个元素，即第一个元素。

2. 从未排序区间取出第一个元素，依次与已排序区间中的元素进行比较，找到合适的位置插入该元素，并将已排序区间相应地调整。

3. 重复步骤2，直到未排序区间中所有元素都被插入到已排序区间中。

二、主要代码下面是直接插入排序的主要代码：```pythondef insertion_sort(arr):n = len(arr)for i in range(1, n):# 将arr[i]插入到已排好序的子数组中temp = arr[i]j = i - 1while j >= 0 and arr[j] > temp:arr[j + 1] = arr[j]j -= 1arr[j + 1] = tempreturn arr```三、代码解析该代码使用Python编写。

其中，insertion_sort函数接受一个列表作为参数，返回一个排好序的列表。

在函数内部，首先获取列表的长度，并使用for循环遍历未排序区间中的元素。

循环变量i表示当前需要插入的元素在未排序区间中的位置。

接着，将arr[i]保存到temp变量中。

j变量表示已排序区间中待插入位置的索引，初始值为i-1。

然后，使用while循环将arr[i]插入到已排好序的子数组中。

如果arr[j]大于temp，则将arr[j]向右移动一位，并将j减1。

循环结束后，将temp插入到arr[j+1]中。

最后，返回排好序的列表。

四、时间复杂度和空间复杂度直接插入排序算法的时间复杂度为O(n^2)，空间复杂度为O(1)。

其中，n为待排序元素个数。

五、优化直接插入排序算法可以进行一些优化，例如使用二分查找来寻找待插入元素在已排好序子数组中的位置，可以减少比较次数。

直接插入排序法的算法1.引言1.1 概述直接插入排序法是一种简单而常见的排序算法，它的基本思想是将未排序的元素逐个插入到已排序的序列中，直至整个序列有序。

该算法的时间复杂度为O(n^2)，适用于数据规模较小的情况。

在直接插入排序法中，我们从第二个元素开始，将它与已排序序列中的元素进行比较，将其插入到合适的位置。

具体来说，我们将第二个元素与第一个元素进行比较，如果第二个元素小于第一个元素，则交换它们的位置；然后再将第三个元素与前两个元素进行比较并交换位置，以此类推，直到将全部元素都插入到合适的位置为止。

这种排序方法相对于其他排序算法的优点在于，它的实现较为简单，算法的代码逻辑易于理解。

此外，直接插入排序法是一种稳定的排序算法，即相等元素在排序后的位置不会发生变化。

这个特点对于某些特定场景非常重要。

直接插入排序法在实际应用中也有一定的局限性。

由于其时间复杂度较高，当数据规模较大时，其性能明显不如其他高效的排序算法。

因此，在实际应用中，我们需要根据具体情况选择合适的排序算法。

通过本文，我们将详细介绍直接插入排序法的原理和步骤，并探讨其优点和应用。

通过学习直接插入排序法，读者将能够更好地理解排序算法的工作原理，并能够灵活运用它们解决实际问题。

1.2 文章结构本文主要介绍了直接插入排序法的算法。

文章分为引言、正文和结论三个部分。

引言部分首先概述了直接插入排序法的基本概念和原理。

随后介绍了文章的结构和目的，即对直接插入排序法进行详细的解析和讨论。

正文部分主要包括两个小节，分别是直接插入排序法的原理和步骤。

在原理部分，将详细解释直接插入排序法的工作原理和算法思想，包括如何将无序的序列按照升序排列。

在步骤部分，将逐步介绍直接插入排序法的具体步骤和实现过程，包括比较和交换元素的操作。

结论部分总结了直接插入排序法的优点和应用场景。

在优点部分，将强调直接插入排序法的稳定性、简单性和适用性。

在应用部分，将介绍直接插入排序法在实际问题中的应用场景，例如对小规模或基本有序的序列进行排序等。

一插入排序1.1 直接插入排序基本思想：每次将一个待排序额记录按其关键码的大小插入到一个已经排好序的有序序列中，直到全部记录排好序。

图解：代码实现：[cpp]view plaincopy1.//直接顺序排序2.void InsertSort(int r[],int n)3.{4.for(int i=2;i<n;i++)5.{6.r[0]=r[i];//设置哨兵7.for(int j=i-1;r[0]<r[j];j--)//寻找插入位置8.r[j+1]=r[j];//记录后移9.r[j+1]=r[0];10.}11.for(int k=1;k<n;k++)12.cout<<r[k]<<"";13.cout<<"\n";14.}1.2 希尔排序基本思想是：先将整个待排序记录序列分割成若干个子序列，在在序列内分别进行直接插入排序，待整个序列基本有序时，再对全体记录进行一次直接插入排序。

图解：代码实现：[cpp]view plaincopy1.<spanstyle="font-size:14px;">//希尔排序2.void ShellSort(int r[],int n)3.{4.int i;5.int d;6.int j;7.for(d=n/2;d>=1;d=d/2)//以增量为d进行直接插入排序8.{9.for(i=d+1;i<n;i++)10.{11.r[0]=r[i];//暂存被插入记录12.for(j=i-d;j>0&&r[0]<r[j];j=j-d)13.r[j+d]=r[j];//记录后移d个位置14.r[j+d]=r[0];15.}16.}17.for(i=1;i<n;i++)18.cout<<r[i]<<"";19.cout<<"\n";20.}</span>二交换排序2.1 起泡排序起泡排序是交换排序中最简单的排序方法，其基本思想是：两两比较相邻记录的关键码，如果反序则交换，直到没有反序的记录为止。

希尔排序中增量di的取法
▪ Shell最初的方案是d1 = n/2, di+1 = di /2，直到dt =1.
▪ Knuth的方案是di+1 = di /3+1 ▪ 其它方案有：都取奇数为好；或
di互质为好等等。
希尔排序的算法分析
▪ 对希尔排序的复杂度的分析很困难，在特定情 况下可以准确地估算关键字的比较和对象移动 次数，但是考虑到与增量之间的依赖关系，并 要给出完整的数学分析，目前还做不到。
原理：关键字相同的两个对象，在整个排序过 程中，不会通过比较而相互交换。
希尔排序
▪ 1959年由D.L. Shell提出，又称缩小 增量排序(Diminishing-increment sort) 。
▪ 基本思想：在直接插入排序中，只比 较相邻的结点，一次比较最多把结点 移动一个位置。如果对位置间隔较大 距离的结点进行比较，使得结点在比 较以后能够一次跨过较大的距离，这 样就可以提高排序的速度。
希尔排序的基本过程
设待排序的对象序列有n个对象，首先 取一个整数d1 <n作为间隔，将全部对 象分为d1个子序列，所有距离为d1的对 象放在同一个序列中，在每一个子序列
中分别施行直接插入排序，然后缩小间 隔d2 ，如取d2 = d1 /2，重复上述的子 序列划分和排序工作，直到最后取dt= 1为止。
void ShellSort(SeqList R) { int increment=n； do { increment=increment/3+1； ShellPass(R，increment)； }while(increment>1)； }
为什么shell排序的时间性能优于直接插入排序呢？ 因为直接插入排序在初态为正序时所需时间最少， 实际上，初态为基本有序时直接插入排序所需的比 较和移动次数均较少。另一方面，当n值较小时，n 和n2的差别也较小，即直接插入排序的最好时间复 杂度O(n)和最坏时间复杂度O(n2)差别不大。在 shell排序开始时增量较大，分组较多，每组的记录 数目少，故各组内直接插入较快，后来增量逐渐缩 小，分组数逐渐减少，而各组的记录数目逐渐增多， 但组内元素已经过多次排序，数组已经比较接近有 序状态，所以新的一趟排序过程也较块。

08
16
1
2
3
4
5
6
r[0]
i=5 j=3
21 1
25 2
25* 3
25* 4
49 08 5 6
16
r[0]
i=5 j=2
21 1
25 2
25 3
25* 4
49 08 5 6
16 r[0]
i=5 j =1
16 21 1
21
25
25*
49 08
16
2
3
4
5
6
r[0]
算法分析

设待排序对象个数为currentSize = n, 则该算 法的主程序执行n-1趟。 排序码比较次数和对象移动次数与对象排序 码的初始排列有关。


直接插入排序是一种稳定的排序方法。
折半插入排序 (Binary Insertsort)



基本思想: 设在顺序表中有一 个对象序列 r[1], r[2], …, r[n]。其中, r[1], r[2], …, r[i-1] 是已经 排好序的对象。在插入r[i] 时, 利用折半查找法 寻找r[i] 的插入位置。 仅减少比较次数，移动次数未减少 P267 算法10.2 算法分析
49 4
16 5
08 6
16 r[0]
i=6
16
21
25
25*
49 08 08
1
2
3
4
5
6
r[0]
完成
08 1
16
2
21 3
25 4
25* 5
49 6
i = 5 时的排序过程 i=5

详解排序算法（⼀）之3种插⼊排序（直接插⼊、折半插⼊、希尔）直接插⼊排序打过牌的⼈都知道，当我们拿到⼀张新牌时，因为之前的牌已经经过排序，因此，我们只需将当前这张牌插⼊到合适的位置即可。

⽽直接插⼊排序，正是秉承这⼀思想，将待插⼊元素与之前元素⼀⼀⽐较，从⽽找到合适的插⼊位置。

那么使⽤直接插⼊排序，具体是怎样操作的呢？我们取 3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48 来进⾏⽰范。

（1）第1轮排序，3之前⽆可⽐较值，因此我们从44开始操作，取44和3⽐较，⼤于3，顺序保持不变。

得数据3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48（2）第2轮排序，取38和44⽐较，38 < 44，再将38与3⽐较，38 > 3，故将38放于第2位，得数据3, 38, 44, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48（3）第3轮排序，取5与44⽐较，5 < 44，再将5与38⽐较，5 < 38，再将5与3⽐较，5 > 3, 置于第2位，得数据3, 5, 38, 44, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48（4）如此经过14轮排序后，得到最终结果2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50动态图javascript实现function directInsertSort (arr) {let compare, // 对⽐元素下标current // 待插⼊元素值for (let i = 1; i < arr.length; i++) {current = arr[i]compare = i - 1while (current < arr[compare] && compare >= 0) {arr[compare + 1] = arr[compare]compare--}arr[compare + 1] = current}return arr}折半插⼊排序细⼼的同学可能已经注意到，当我们要将⼀个元素插⼊合适的位置时，其之前的元素是有序的，因此，我们可以⽤折半查找的⽅式来⽐对并插⼊元素，也就是所谓的折半插⼊排序。

判断某序列是否符合堆定义
只要将序列依次排成一棵完全二叉树，所有结点的 值都不大于（或不小于）其左右子树结点的值，那么该 序列就符合堆的定义。 例：序列：102、87、100、79、82、62、84
10 2 87 10 0 82
故： 此序列符 合堆定义。
84
79
62
若n个元素的排序码k1，k2，k3，…，kn满足堆，且让结点 按1、2、3、…、n顺序编号，根据完全二叉树的性质（若i为 根结点，则左孩子为2i，右孩子为2i+1）可知，堆排序实际与 一棵完全二叉树有关。若将排序码初始序列组成一棵完全二 叉树，则堆排序可以包含建立初始堆（使排序码变成能符合 堆的定义的完全二叉树）和利用堆进行排序两个阶段。
14
17
25 )
20
9
(3
14
17
20
25 )
9
第五次插入
(3
9
14
17
20
25)
图 9-1 直接插入排序示例
注意:
排正序时，要插入的元素先和有序表中最后 一个元素进行比较，即从后往前；排逆序时， 则刚相反，得从前往后进行比较。 当n很小时，直接插入排序的效率较高，时间 复杂度为o(n^2)。 正序时比较次数最少为n-1； 逆序时最大为(n+2)*(n-1)/2； 两者的平均值约为(n^2)/4。
例如，n=6，数组R的六个排序码分别为：17，3，25，14，20， 9。下面用图9-3给出冒泡排序算法的执行过程。
0 1 2 3 4 5
初始状态
（17
3
25
14
20
9)
第一趟排序
3
(17
9
25

…
姓名 学习成绩 思想政治
XXX 262
29
XXX 250
29
XXX 249
28
XXX 248
28
XXX 243
28
XXX 242
27
XXX 231
27
XXX 211
27
…
…
…
总分 291 279 277 276 271 269 258 238
…
奖学金等次 1 2 2 2 3 3 3 3 …
8.2.1 排序概念
R[j+1]=tRe[0m]p;
} }
使用R[0]的意义
第一 进入循环之前，保存R[i]的值
监视哨
第二 在while循环中“监视”下标 是否越界。
8.2.3 改进后算法
insertsort(R){ int i,j;
for (i=2 ;i<n;i++){
R[0]=R[i]; j=i-1;
while(R[0]<R[j]) {
无序 数据
排序
有序 数据
排序算法主要有：
直接插入排序、希尔排序、冒泡排序、快速排 序、直接选择排序、堆排序、归并排序等。
8.2.2 直接插入排序基本思想
数组R
13 21 … 25 49
0…
i-1
有序区
无序区第 1个元素
36 08 … 16 i … n-1 数组下标
无序区
关键问题
如何确定 插入位置 ？
《数据结构》
8.2 直接插入排序
徐洪章
计算机科学系
教学内容： 1、排序的基本概念 2、直接插入排序算法的基本思想 3、直接插入排序算法实现 4、直接插入排序算法性能分析