算法与数据结构大系列 - NO.1 - 插入排序

栏目: 编程工具 · 发布时间: 5年前

内容简介:这是一种就地比较排序算法。这里,维护一个始终排序的子列表。例如,维护数组的下半部分以进行排序。要在此已排序的子列表中“插入”的元素必须找到其适当的位置,然后必须将其插入其中。因此名称,插入排序。按顺序搜索数组,移动未分类的项并将其插入已排序的子列表(在同一数组中)。该算法不适用于大数据集,因为其平均和最差情况复杂度为0(n 2),其中n是项目数。我们以一个未排序的数组为例。

概述

这是一种就地比较 排序 算法。这里,维护一个始终排序的子列表。例如,维护数组的下半部分以进行排序。要在此已排序的子列表中“插入”的元素必须找到其适当的位置,然后必须将其插入其中。因此名称,插入排序。

按顺序搜索数组,移动未分类的项并将其插入已排序的子列表(在同一数组中)。该算法不适用于大数据集,因为其平均和最差情况复杂度为0(n 2),其中n是项目数。

插入排序如何工作?

我们以一个未排序的数组为例。

算法与数据结构大系列 - NO.1 - 插入排序

插入排序比较前两个元素。

算法与数据结构大系列 - NO.1 - 插入排序

它发现14和33都已按升序排列。目前,14位于已排序的子列表中。

算法与数据结构大系列 - NO.1 - 插入排序

插入排序向前移动并将33与27进行比较。

算法与数据结构大系列 - NO.1 - 插入排序

并发现33不在正确的位置。

算法与数据结构大系列 - NO.1 - 插入排序

它将33与27交换。它还检查已排序子列表的所有元素。在这里,我们看到排序的子列表只有一个元素14,而27大于14.因此,排序的子列表在交换后仍然排序。

算法与数据结构大系列 - NO.1 - 插入排序

到目前为止,我们在已排序的子列表中有14和27。接下来,它将33与10进行比较。

算法与数据结构大系列 - NO.1 - 插入排序

这些值不是按排序顺序排列的。

算法与数据结构大系列 - NO.1 - 插入排序

所以我们互换它们。

算法与数据结构大系列 - NO.1 - 插入排序

但是,交换使27和10未分类。

算法与数据结构大系列 - NO.1 - 插入排序

因此,我们也交换它们。

算法与数据结构大系列 - NO.1 - 插入排序

我们再次以未排序的顺序找到14和10。

算法与数据结构大系列 - NO.1 - 插入排序

我们再次交换它们。到第三次迭代结束时,我们有一个包含4个项目的已排序子列表。

算法与数据结构大系列 - NO.1 - 插入排序

此过程将继续,直到排序的子列表中包含所有未排序的值。现在我们将看到插入排序的一些编程方面。

算法

现在我们对这种排序技术的工作原理有了更大的了解,因此我们可以推导出简单的步骤来实现插入排序。

Step 1 − If it is the first element, it is already sorted. return 1;
Step 2 − Pick next element
Step 3 − Compare with all elements in the sorted sub-list
Step 4 − Shift all the elements in the sorted sub-list that is greater than the 
 value to be sorted
Step 5 − Insert the value
Step 6 − Repeat until list is sorted

伪代码

procedure insertionSort( A : array of items )
 int holePosition
 int valueToInsert
 for i = 1 to length(A) inclusive do:
 /* select value to be inserted */
 valueToInsert = A[i]
 holePosition = i
 /*locate hole position for the element to be inserted */
 while holePosition > 0 and A[holePosition-1] > valueToInsert do:
 A[holePosition] = A[holePosition-1]
 holePosition = holePosition -1
 end while
 /* insert the number at hole position */
 A[holePosition] = valueToInsert
 end for
end procedure

C代码

#include <stdio.h>
#include <stdbool.h>
#define MAX 7
int intArray[MAX] = {4,6,3,2,1,9,7};
void printline(int count) {
 int i;
 for(i = 0;i < count-1;i++) {
 printf("=");
 }
 printf("=
");
}
void display() {
 int i;
 printf("[");
 // navigate through all items 
 for(i = 0;i < MAX;i++) {
 printf("%d ",intArray[i]);
 }
 printf("]
");
}
void insertionSort() {
 int valueToInsert;
 int holePosition;
 int i;
 // loop through all numbers 
 for(i = 1; i < MAX; i++) { 
 // select a value to be inserted. 
 valueToInsert = intArray[i];
 // select the hole position where number is to be inserted 
 holePosition = i;
 // check if previous no. is larger than value to be inserted 
 while (holePosition > 0 && intArray[holePosition-1] > valueToInsert) {
 intArray[holePosition] = intArray[holePosition-1];
 holePosition--;
 printf(" item moved : %d
" , intArray[holePosition]);
 }
 if(holePosition != i) {
 printf(" item inserted : %d, at position : %d
" , valueToInsert,holePosition);
 // insert the number at hole position 
 intArray[holePosition] = valueToInsert;
 }
 printf("Iteration %d#:",i);
 display();
 } 
}
void main() {
 printf("Input Array: ");
 display();
 printline(50);
 insertionSort();
 printf("Output Array: ");
 display();
 printline(50);
}

输出

Input Array: [4 6 3 2 1 9 7 ]
==================================================
Iteration 1#:[4 6 3 2 1 9 7 ]
 item moved : 6
 item moved : 4
 item inserted : 3, at position : 0
Iteration 2#:[3 4 6 2 1 9 7 ]
 item moved : 6
 item moved : 4
 item moved : 3
 item inserted : 2, at position : 0
Iteration 3#:[2 3 4 6 1 9 7 ]
 item moved : 6
 item moved : 4
 item moved : 3
 item moved : 2
 item inserted : 1, at position : 0
Iteration 4#:[1 2 3 4 6 9 7 ]
Iteration 5#:[1 2 3 4 6 9 7 ]
 item moved : 9
 item inserted : 7, at position : 5
Iteration 6#:[1 2 3 4 6 7 9 ]
Output Array: [1 2 3 4 6 7 9 ]
==================================================

总结

一个for和一个while循环,for用于遍历已经排序好的数组,while用于遍历未排序的数组。进行交换。

代码如下

// 插入排序
public class insertSort {
 public static void sort(int[] numbers){
 // 其中insert为要插入的数据
 int i, j , insert;
 // 从数组的第二个元素开始循环数组中的元素插入
 for(i = 1; i < numbers.length; i++){
 // 用于保存被替换的值
 insert = a[i];
 // 用于保存已经排序好的列表
 j = i - 1;
 // 寻找剩余列表的数组,用于进行插入
 while(j >= 0 && insert < a[j]){
 // 把待插入的位置挪开
 a[j + 1] = a[j];
 j--;
 }
 // 进行插入
 a[j + 1] = insert;
 }
 }
}

核心在于维护两个,一个用于已经排序好的,一个用于没有排序好的。

算法与数据结构大系列 - NO.1 - 插入排序


以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

生物信息学算法导论

生物信息学算法导论

N.C.琼斯 / 第1版 (2007年7月1日) / 2007-7 / 45.0

这是一本关于生物信息学算法和计算思想的导论性教科书,原著由国际上的权威学者撰写,经国内知名专家精心翻译为中文,系统介绍推动生物信息学不断进步的算法原理。全书强调的是算法中思想的运用,而不是对表面上并不相关的各类问题进行简单的堆砌。 体现了以下特色: 阐述生物学中的相关问题,涉及对问题的模型化处理并提供一种或多种解决方案: 简要介绍生物信息学领域领军人物; 饶有趣味的小插图使得概念更加具体和形象,方......一起来看看 《生物信息学算法导论》 这本书的介绍吧!

MD5 加密
MD5 加密

MD5 加密工具

Markdown 在线编辑器
Markdown 在线编辑器

Markdown 在线编辑器