美文网首页
排序——插入排序

排序——插入排序

作者: vavid | 来源:发表于2020-12-01 14:55 被阅读0次

业精于勤荒于嬉

插入排序包括:直接插入排序、折半插入排序、希尔排序(缩小增量排序)

一、直接插入排序

1. 算法思想

直接插入排序

2. 算法实现

void insertSort(int R[], int n){
    int j; 
    int temp;
    for(int i = 1; i < n; ++i){ 
        // i 标示带排序关键字下标,从第二个开始排,因为第一个默认有序
        temp = R[i]; // 将当前待插入关键字暂存下来
        j = i - 1; // j 默认是当前待插入关键字前面的关键字
        while(j >= 0 && temp < R[j]){
            R[j+1] = R[j];
            --j;
        } // 寻找待插入关键字的插入位置,如果j和j之前的关键字比待插入关键字,则依次向后移动
        // 将当前待插入关键字放入找到的位置,最后依次while循环使得j多减了1,
        // 所以待插入位置下标应该是 j+1
        R[j+1] = temp; 
    }   
}

二、折半插入排序

折半插入排序是对直接插入排序的一个优化,在排序过程的不断进行中,已排好序的元素会依次增多,后续的待元素在已排好序的序列中寻找其插入位置时,可通过折半查找减少比较次数(移动次数没有发生变化)。

1. 算法思想

算法思想同直接插入排序,折半插入排序比较次数与初始状态无关:O(nlog2n);直接插入排序比较次数与初态有关:O(n)~O(n2)

2. 算法实现

void binaryInsertSort(int R[], int n){
    int i, j, k; 
    int temp;
    int low, high;
    for(i = 1; i < n; i++){ 
        // i 标识待排序关键字下标,从第二个开始排,因为第一个默认有序
        temp = R[i];
        low = 0;
        high = i - 1;
        // 折半查找待插入的位置
        while(low <= high){
            k = (low+high)/2;
            if(R[k] > R[i]){
                high = k - 1;
            }else {
                low = k + 1;
            }
        }
        //将k到i位置的元素依次后移
        for(j = i; j > k + 1; j--){
            R[j] = R[j-1];
        }
        R[k+1] = temp;
    }   
}

三、希尔排序

又叫缩小增量排序,希尔提出的(还有其他人提出的,思想相同)增量默认选取为序列长度n的一半⌊n/2⌋,再依次缩小增量为⌊n/4⌋...⌊n/2k⌋...,2,1,算法时间复杂度为O(n2)。当增量选取为1时,就是直接插入排序。

1. 算法思想

希尔排序

2. 算法实现


void shellSort(int R[], int n)
{
    int i, j, temp;
    int k = n / 2;
    while (k >= 1) {
        for (i = k; i < n; i++) {
            temp = R[i];
            j = i - k;
            while (R[j] < temp && j >= 0) {
                R[j+k] = R[j];
                j = j - k;
            }
            R[j+k] = temp;
        }
        k = k / 2;
    }


相关文章

  • 算法-插入排序

    算 法:插入排序算法时间复杂度: 插入排序算法描述 插入排序伪代码 插入排序实现 插入排序算法概述 插入排...

  • c算法O(n)^2(一)

    选择排序 插入排序 优化插入排序算法

  • java快速学习排序---插入排序

    1.java实现插入排序 (1)、图解插入排序 (2)、插入排序的思想 (3)、插入排序的代码实现

  • 算法(排序)

    一、内部排序 1、插入排序—直接插入排序(Straight Insertion Sort) 2、插入排序—希尔排序...

  • Java排序算法

    插入排序 直接插入排序 折半插入排序 交换排序 冒泡排序 快速排序 选择排序 简单选择排序 堆排序 其他排序 二路...

  • 一遍文章搞定插入排序-java版

    插入排序 1.1 插入排序的基本介绍 插入排序属于内排,就是以插入的方式来达到排序的目的 1.2 插入排序思想 将...

  • 排序(新排版)

    冒泡排序 插入排序 二分插入排序 希尔排序 选择排序 快速排序

  • iOS算法

    排序方法 选择排序:直接选择排序、堆排序。 交换排序:冒泡排序、快速排序。 插入排序:直接插入排序、二分法插入排序...

  • Java学习记录(常用 算法 排序 )

    排序算法的分类如下: 1.插入排序(直接插入排序、折半插入排序、希尔排序);2.交换排序(冒泡泡排序、快速排序);...

  • 排序——插入排序

    业精于勤荒于嬉 插入排序包括:直接插入排序、折半插入排序、希尔排序(缩小增量排序) 一、直接插入排序 1. 算法思...

网友评论

      本文标题:排序——插入排序

      本文链接:https://www.haomeiwen.com/subject/mufusktx.html