内部排序之直接插入排序

1. 基本思想

将待排序记录Key=A[i+1]插入到已排序序列A[1…i]中。Key由后向前依次与A[1…i]中的元素进行比较,若A[x]<=Key,将Key插入到A[x]的后面,即A[x+1]=Key,否则将元素A[x]后移。

S0:从无序序列A[n]的第一个元素A[1]开始,该元素可被认定已完成排序。

S1:取出下一个元素并记录为Key,在已排序序列中倒序遍历。

S2:若已排序序列中的元素A[x]<=Key,将Key插入到A[x]的后面,否则将元素A[x]后移。

S3:重复步骤S2,直到找到适合Key插入的位置。

S4:重复步骤S1,完成排序。

2. 时间复杂度

正序有序:仅需比较n次,无需元素移动,时间复杂度为O(n)。

逆序有序:需比较1+2+…+n-1+n=n*(n+1)/2≈n^2/2次,时间复杂度为O(n^2)。

3. 稳定性

排序算法的稳定性是指,两个相同元素,排序前后的位置关系是否发生变化。

若序列A[n]中的两个元素K1=K2(K1位于K2前面),在直接插入排序算法中,K2与K1进行比较时,K2直接插入到K1后面,无需做元素移动,K1与K2的位置关系不会发生变化。因此,直接插入排序算法是稳定的。

4. 算法程序

function sortArray = straightInsertionSort(array, number, sortKind)

% Straight insertion sort.
%
% input - array : disordered array.
%         number : the number of array elements.
%         sortKind : kind of sort (1 - positive and 0 - negative).
%
% output - sortArray : sorted array.

if (number <= 0)
    error(‘The disordered array empty.‘);
end

if (number > 1)
    % the number of disordered array is more than 2.
    for index = 2 : number
        % insert the element to the correct position of sorted array.
        i = index - 1;
        key = array(index);

        if (sortKind == 1)
            % positive
            while ((i > 0) && (array(i) > key))
                array(i + 1) = array(i);
                i = i - 1;
            end
        end

        if (sortKind == 0)
            % negative
            while ((i > 0) && (array(i) < key))
                array(i + 1) = array(i);
                i = i - 1;
            end
        end

        array(i + 1) = key;
    end
end

sortArray = array;

5. 视觉直观感受

时间: 02-23

内部排序之直接插入排序的相关文章

直接插入排序(内部排序)

1 package com.trfizeng.insertionsort; 2 3 /** 4 * 5 * @author trfizeng 内部排序 插入排序 --- 直接插入排序(Straight Insertion Sort) 6 * 7 */ 8 public class StraightInsertionSort { 9 public static int[] straightInsertionSort(int[] array) { 10 // 对传来的待排序数组进行合法验证 11 i

数据结构6种内部排序算法的比较

1.需求分析 (1)输入数据的形式为:伪随机数产生程序产生,且每次输入数不少于100个,至少要用5组不同的输入数据 (2)输出的形式为:输出关键字参加的比较次数和关键字的移动次数(关键字交换计为3次移动)的数据 (3)程序能达到的功能:对起泡排序,直接插入排序,简单选择排序,快速排序,希尔排序,堆排序这6种常用的内部排序算法进行比较,比较的指标为有关键字参加的比较次数和关键字的移动次数(关键字交换计为3次移动) (4)测试数据:正确输入为由伪随机数产生程序产生100个随机数,然后输出比较结果,错

几种内部排序-分类-复杂性-稳定性

1. 简述 本文主要说明一些常用的内部排序算法的分类.复杂性和稳定性.主要基于现在的理解和学习,详细准确的复杂度可以参见维基百科等比较权威的网站,对于一些算法的不同实现,复杂度也不同,这里给出的复杂度都是相对较好的算法的复杂度. 2. 分类    3. 复杂性和稳定性 冒泡排序:在已经有序的情况,取得O(N)的复杂度.    快速排序:每次递归都是N的复杂度,递归次数根据序列有关系,当已经有序的情况下,递归N次,时间复杂度为O(N*LogN)    插入排序:在已经有序的情况,取得O(N)的复杂

简单的选择排序(内部排序)

1 /** 2 * 3 */ 4 package com.trfizeng.selectionsort; 5 6 /** 7 * @author trfizeng 内部排序 选择排序—简单选择排序(Simple Selection Sort) 8 */ 9 public class SimpleSelectionSort { 10 11 /** 12 * 每次选择一个最小记录放在前面去 13 */ 14 public static int[] simpleSelectionSort(int[]

内部排序-第10章-《数据结构题集》习题解析-严蔚敏吴伟民版

//**留坑待填**// 一.基础知识题 10.1?以关键码序列(503,087,512,061,908,170,897,275,653,426)为例,手工执行以下排序算法,写出每一趟排序结束时的关键码状态: (1)直接插入排序:                            (2)希尔排序(增量d[1]=5): (3)快速排序:                                  (4)堆排序: (5)归并排序:                              

10-12-顺序表地址排序-内部排序-第10章-《数据结构》课本源码-严蔚敏吴伟民版

课本源码部分 第10章  内部排序 - 顺序表地址排序 ——<数据结构>-严蔚敏.吴伟民版        源码使用说明  链接??? <数据结构-C语言版>(严蔚敏,吴伟民版)课本源码+习题集解析使用说明        课本源码合辑  链接??? <数据结构>课本源码合辑        习题集全解析  链接??? <数据结构题集>习题解析合辑        本源码引入的文件  链接? SequenceListType.c        相关测试数据下载  链

基于比较的内部排序总结

★ 基于“比较”操作的内部排序性能大PK 我们首先总结一下<排序结构专题1-4>中的十种方法的性能((N个关键字的待排序列)): 排序方法        平均时间   最坏时间    辅助存储空间   稳定性   直接插入排序 O(N^2)   O(N^2)    O(1)                √      折半插入排序 O(N^2) O(N^2)  O(1)      √ 希尔排序  O(N*logN) O(N*logN) O(1)        × 起泡排序        O(N

内部排序算法(一):交换排序(冒泡排序,快速排序)

这是我的博文系列<内部排序算法>的第一篇.所谓排序,就是要整理文件中的记录,使之按关键字递增(或递减)次序排列起来.所谓内部排序,是指在排序过程中,若整个文件都是放在内存中处理,排序时不涉及数据的内.外存交换(外排序的定义则相反). 内部排序法按照策略可以划分为五类:插入排序.选择排序.交换排序.归并排序和分配排序.待排文件的存储方式采用顺序表(或直接用向量)作为存储结构(其他的存储结构还有以链表作为存储结构等). 在这个系列的博文中,我按照排序算法的给出,排序算法的分析(包括算法的时空复杂度

算法 - 内部排序方法总结

各种排序方法的性能比较 排序方法 最好时间复杂度 平均时间复杂度 最坏时间复杂度 空间复杂度 稳定性 直接插入排序 O(n) O(n2) O(n2) O(1) 稳定 简单选择排序 O(n2) O(n2) O(n2) O(1) 不稳定 冒泡排序 O(n) O(n2) O(n2) O(1) 稳定 希尔排序 - O(n1.25) - O(1) 不稳定 快速排序 O(nlog2n) O(nlog2n) O(n2) O(log2n)~O(n) 不稳定 堆排序 O(nlog2n) O(nlog2n) O(n

内部排序实现(数据结构)

以下源码全部经过测试,有些地方可能不是最优,仅是练习.如果错误或更好的方法欢迎大家指出.以下仅供参考: 说明:为了测试的方便,在每个排序算法前都进行了一次初始化-重新分配内存,以防止影响后面的测试.cygwin下G++测试通过 #include <cstdio> #include <cmath> #include <queue> #include <climits> #include <cstring> #include <cstdlib&