软件开发教程 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试
游戏开发 网络协议 系统运维 HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程
C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
 
   -> 数据结构与算法 -> 【算法与数据结构】之插入排序 -> 正文阅读

[数据结构与算法]【算法与数据结构】之插入排序

【算法与数据结构】之插入排序

1、定义

插入排序,一般也被称为直接插入排序。对于少量元素的排序,它是一个有效的算法 。插入排序是一种简单的排序方法,它的基本思想是将一个记录插入到已经排好序的有序表中,从而一个新的、记录数增1的有序表。在其实现过程使用双层循环,外层循环对除了第一个元素之外的所有元素,内层循环对当前元素前面有序表进行待插入位置查找,并进行移动

2、时间复杂度、空间复杂度和稳定性

时间复杂度:平均复杂度O(n2)、最好复杂度O(n)、最坏复杂度O(n2)
空间复杂度:O(1)
稳定性:稳定

3、代码

public class InsertionSort {
    public static void main(String[] args) {
        int[] a = {9,3,1,4,8,7,5,2,6};
        sort(a);
        print(a);
    }
    static void sort(int[] a){
        /*for(int i=1;i<a.length;i++){   //1.0版
            for (int j=i;j>0;j--){
                if(a[j]<a[j-1]){
                    swap(a,j,j-1);
                }
            }
        }*/
        int  j=0, temp=0;
        for (int i = 1; i < a.length; i++) {
            temp = a[i];
            j = i - 1;
            while (j >= 0 && temp < a[j]) {
                a[j + 1] = a[j];
                j--;
            }
            a[j + 1] = temp;
        }
    }
    static void swap(int[] a,int i,int j){//简单的交换函数
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
    static void print(int[] arr){
        for(int i=0;i<arr.length;i++){
            System.out.print(arr[i]+ " ");
        }
    }
}

备注:此文章用于记录自己的学习过程,无刻意指导他人之意,若文章中有错误,请多包涵并指出,希望与各位共同进步。

  数据结构与算法 最新文章
PTA (乙级)1035 插入与归并 (25 分)
动态规划学习
A. Find The Array
读《大话数据结构》记录Day 01
排序算法:希尔排序_代码
玩转算法(十二)——链表(删除链表)
西瓜书第四章拾遗
紫书第6章 数据结构基础 例题A~D
122 买卖股票的最佳时机-02
求二叉树最大深度
上一篇文章      下一篇文章      查看所有文章
加:2021-07-10 11:38:31  更:2021-07-10 11:38:51 
 
360图书馆 购物 三丰科技 阅读网 日历 万年历 2021年7日历 -2021/7/27 4:14:25-
图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  软件开发教程