IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> 排序算法之三种基本排序:直接插入排序、冒泡排序、简单选择排序 -> 正文阅读

[数据结构与算法]排序算法之三种基本排序:直接插入排序、冒泡排序、简单选择排序

1、冒泡排序

? ? ? ? 时间复杂度:O(n^2)

????????基本思想:相邻的元素两两进行比较,反序则交换,这样每一趟会将最小或最大的元素“浮”到顶端,最终达到完全有序。

????????代码实现如下:

public class BubbleSort {

    /**
     * 冒泡排序:时间复杂度O(n^2)
     * 思想:基本就是相邻的元素两两进行比较,反序则交换,这样每一趟会将最小或最大的元素“浮”到顶端,最终达到完全有序。
    * @author lst
    */
    public static void main(String[] args){

        int [] array = {10,2,4,87,4,6,19,100,123,1312,13,44,324,32,42,42,4,24,5,2,52,525};
        bubbleSort(array);

        System.out.println(Arrays.toString(array));
    }

    private static void bubbleSort(int[] arr){
        for (int i = 0; i <arr.length ; i++) {
            for(int j=0;j<arr.length-1-i;j++ ){//这个地方length-1-i,是因为之前的循环中已经找到了最大的放在了后面,所以不用再比较交换
                if(arr[j]>arr[j+1]){//如果前面的角标处的元素大于后面的角标则交换
                    swap(arr,j+1,j);
                }
            }
        }
    }

    private static void swap(int[] arr, int i, int j) {
        int temp;
        temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

}

?2、简单选择排序

? ??????时间复杂度:O(n^2),不稳定排序

????????基本思想:(两层循环)从前往后一直不断寻找最小的值,用一个变量min记录一次循环中最小的值的索引,一次循环结束的时候让min角标处的元素与这次循环的起始位置的元素交换。?大体上就是不断寻找后面待排序数组的最小值的索引,最后进行交换。

????????代码实现如下:

public class EasySelectSort {
    public static void main(String[] args){

        int [] array = {10,2,4,87,4,6,19};
        easySelectSort(array);

        System.out.println(Arrays.toString(array));
    }

    /**
     * 简单选择排序:时间复杂度O(n^2),不稳定排序
     * 思想:(两层循环)从前往后一直不断寻找最小的值,用一个变量min记录一次循环中最小的值的索引,
     * 一次循环结束的时候让min角标处的元素与这次循环的起始位置的元素交换
     * 大体上就是不断寻找后面待排序数组的最小值的索引,最后进行交换
     *
     * @author lst
     */
    private static void easySelectSort(int[] arr){

        for(int i = 0;i<arr.length;i++){
            int currentIndex = i;//记录当前遍历角标
            for(int j=currentIndex;j<arr.length;j++ ){
                if(arr[j]<arr[currentIndex]){//如果小于当前角标处的值
                    currentIndex = j;//记录当前最小的值
                }
            }
            swap(arr,i,currentIndex);//找到最小的节点,然后交换
        }
    }
    private static void swap(int[] arr, int i, int j) {
        int temp;
        temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

}

3、直接插入排序

????????时间复杂度:直接插入排序:最好的情况下的时间复杂度是O(n),最坏的情况下为O(n^2), * 总体上与前两种简单排序算法一样是O(n^2)

?????????基本思想:? 将数组分为两个部分,比如前的n个元素为有序的,后面的是无序的。?那么我们每次将arr[n]这个元素在数组角标为n到0的遍历中,找到第一个小于arr[n]的位置,并且在这个过程中将大于arr[n]的元素依次往后挪(覆盖即可),然后将arr[n]这个元素插入到这个位置后,仍然满足前面的数组元素是有序的,后面的n+1个是无序的,然后 n++进行下一次循环。

概括就是每一步将就后面一个待排序的记录插入到前面已排好序的有序序列中,知道插完所有元素为止。

????????代码实现如下:

public static void main(String[] args){
        int [] array = {10,2,4,87,4,6,19,100,123,1312,13,44,324,32,42,42,4,24,5,2,52,525};
        insertSort(array);

        System.out.println(Arrays.toString(array));
    }

    private static void insertSort(int[] arr) {

        for (int i = 1; i <arr.length ; i++) {//从第二个数,都查一遍待插入的位置
            int value = arr[i];//记录下待插入的值
            int j = i-1;//默认从前一个遍历
            while(j>=0&&value<arr[j]){//如果没有到最前面第一个元素,并且前面的前元素大于value
                //将前一个元素前移,可以想象成小卖部买东西插队的时候,后面的人都依次往后挪的过程
                //并且不用担心覆盖,因为value记录着我们待插入的值。
                arr[j+1] = arr[j];
                j--;
            }//循环结束说明找到了value插入的位置
            //插入value
            arr[j+1] = value;
        }
    }

}

  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2021-07-14 00:23:40  更:2021-07-14 00:24:01 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年12日历 -2024/12/27 10:23:58-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码
数据统计