正文

java集合与数据结构排序(代码片段)

头发都哪去了  头发都哪去了  2022-11-29  396

关键词：

概念

排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
平时的上下文中，如果提到排序，通常指的是排升序（非降序）。
通常意义上的排序，都是指的原地排序(in place sort)。

稳定性：两个相等的数据，如果经过排序后，排序算法能保证其相对位置不发生变化，则我们称该算法是具备稳定性的排序算法。

插入排序

直接插入排序

整个区间被分为

有序区间
无序区间

每次选择无序区间的第一个元素，在有序区间内选择合适的位置插入

代码实现

逻辑代码：

public class InsertSort 
    public static void insertSort(int[] array) 
        for (int i = 1; i < array.length; i++) 
            int temp = array[i];
            int j = i-1;
            for (; j >= 0; j--) 
                if (array[j] > temp) 
                    array[j+1] = array[j];
                else 
                    break;
                
            
            array[j+1] = temp;

调试代码：

public class TestDemo 
    public static void main(String[] args) 
        int[] array = 10,3,2,7,19,78,65,127;
        System.out.println("排序前：" + Arrays.toString(array));
        InsertSort.insertSort(array);
        System.out.println("排序后：" + Arrays.toString(array));

该代码的执行结果为：

可见，实现了对原数组的升序排序。

性能分析

时间复杂度：
最好情况：O(n)【数据有序】
平均情况：O(n²)
最坏情况：O(n²)【数据逆序】

空间复杂度：O(1)

稳定性：稳定

对于直接插入排序：越有序越快。另外，直接插入排序会用在一些排序的优化上。

希尔排序

希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有记录分成个组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工作。当到达=1时，所有记录在统一组内排好序。

希尔排序是对直接插入排序的优化。
当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。

代码实现

逻辑代码：

public class ShellSort 
    public static void shell(int[] array,int gap) 
        for (int i = gap; i < array.length; i = i + gap) 
            int temp = array[i];
            int j = i-gap;
            for (; j >= 0; j = j-gap) 
                if (array[j] > temp) 
                    array[j+gap] = array[j];
                else 
                    break;
                
            
            array[j+gap] = temp;
        
    

    public static void shellSort(int[] array) 
        int[] drr = 5,3,1;//增量数组-->没有明确的规定，但保证为素数的增量序列
        for (int i = 0; i < drr.length; i++) 
            shell(array,drr[i]);

测试代码：

public class TestDemo 
    public static void main(String[] args) 
        int[] array = 10,3,2,7,19,78,65,127;
        System.out.println("排序前：" + Arrays.toString(array));
        ShellSort.shellSort(array);
        System.out.println("排序后：" + Arrays.toString(array));

该代码的执行结果为：

可见，实现了对原数组的升序排序。

性能分析

时间复杂度：
最好情况：O(n)【数据有序】
平均情况：O(n^1.3)
最坏情况： O(n²) 【比较难构造】

空间复杂度：O(1)

稳定性：不稳定

选择排序

直接选择排序

每一次从无序区间选出最大（或最小）的一个元素，存放在无序区间的最后（或最前），直到全部待排序的数据元素排完。

代码实现

逻辑代码：

public class SelectSort 
    public static void selectSort(int[] array) 
        for (int i = 0; i < array.length-1; i++) 
            for (int j = i+1; j < array.length; j++) 
                if (array[i] > array[j]) 
                    int temp = array[j];
                    array[j] = array[i];
                    array[i] = temp;

测试代码：

public class TestDemo 
    public static void main(String[] args) 
        int[] array = 10,3,2,7,19,78,65,127;
        System.out.println("排序前：" + Arrays.toString(array));
        SelectSort.selectSort(array);
        System.out.println("排序后：" + Arrays.toString(array));

该代码的执行结果为：

可见，实现了对原数组的升序排序。

性能分析

时间复杂度 : 不管是最好情况还是最坏情况都是O(n²) 【数据不敏感】

空间复杂度: O(1)

稳定性：不稳定

堆排序

基本原理也是选择排序，只是不在使用遍历的方式查找无序区间的最大的数，而是通过堆来选择无序区间的最大的数。
注意：排升序要建大堆；排降序要建小堆。

代码实现

逻辑代码：

public class HeapSort 
    public static void heapSort(int[] array) 
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new Comparator<Integer>() 
            @Override
            public int compare(Integer o1, Integer o2) 
                return o1-o2;
            
        );
        for (int i = 0; i < array.length; i++) 
            priorityQueue.add(array[i]);
        
        for (int i = 0; i < array.length; i++) 
            array[i] = priorityQueue.poll();

测试代码：

public class TestDemo 
    public static void main(String[] args) 
        int[] array = 10,3,2,7,19,78,65,127;
        System.out.println("排序前：" + Arrays.toString(array));
        HeapSort.heapSort(array);
        System.out.println("排序后：" + Arrays.toString(array));

该代码的执行结果为：

可见，实现了对原数组的升序排序。

性能分析

时间复杂度：不管是最好的情况还是最坏的情况都是O(n * log(n)) 。

空间复杂度：O(1)。

稳定性：不稳定

交换排序

冒泡排序

在无序区间，通过相邻数的比较，将最大的数冒泡到无序区间的最后，持续这个过程，直到数组整体有序。

代码实现

逻辑代码：

public class BubbleBort 
    public static void bubbleBort(int[] array) 
        for (int i = 0; i < array.length-1; i++) 
            for (int j = 0; j < array.length-i-1; j++) 
                if (array[j] > array[j+1]) 
                    int temp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = temp;

测试代码：

public class TestDemo 
    public static void main(String[] args) 
        int[] array = 10,3,2,7,19,78,65,127;
        System.out.println("排序前：" + Arrays.toString(array));
        BubbleBort.bubbleBort(array);
        System.out.println("排序后：" + Arrays.toString(array));

该代码的执行结果为：

可见，实现了对原数组的升序排序。

性能分析

时间复杂度：
最好情况：O(n)【数据有序】
平均情况：O(n²)
最坏情况： O(n²) 【数据逆序】

空间复杂度：O(1)。

稳定性：稳定

快速排序

从待排序区间选择一个数，作为基准值(pivot)；
Partition: 遍历整个待排序区间，将比基准值小的（可以包含相等的）放到基准值的左边，将比基准值大的（可以包含相等的）放到基准值的右边；
采用分治思想，对左右两个小区间按照同样的方式处理，直到小区间的长度 = 1，代表已经有序，或者小区间的长度 = 0，代表没有数据。

代码实现

逻辑代码：

public class QuickSort 
    public static void quick(int[] array,int low,int high) 
        if (low < high) 
            int piv = piovt(array,low,high);//找基准
            quick(array,low,piv-1);
            quick(array,piv+1,high);
        
    

    private static int piovt(int[] array,int start,int end) 
        int temp = array[start];
        while (start < end) 
            while (start < end && array[end] >= temp) 
                end--;
            
            array[start] = array[end];


            while (start < end && array[start] < temp) 
                start++;
            
            array[end] = array[start];
        
        array[start] = temp;
        return start;
    

    public static void quickSort(int[] array) 
        quick(array,0,array.length-1);

测试代码：

public class TestDemo 
    public static void main(String[] args) 
        int[] array = 10,3,2,7,19,78,65,127;
        System.out.println("排序前：" + Arrays.toString(array));
        QuickSort.quickSort(array);
        System.out.println("排序后：" + Arrays.toString(array));

该代码的执行结果为：

可见，实现了对原数组的升序排序。

性能分析

时间复杂度：
最好情况：O(n * log(n))
平均情况：O(n * log(n))
最坏情况： O(n²)

空间复杂度：
最好情况：O(log(n))
平均情况：O(log(n))
最坏情况：O(n)

稳定性：不稳定

非递归实现快速排序

代码实现

逻辑代码：

/**
 * 非递归实现快速排序
 */
public class QuickSortNor 
    public static void quickSortNor(int[] array) 
        int low = 0;
        int high = array.length - 1;
        int piv = piovt(array, low, high);
        Stack<Integer> stack = new Stack<>();
        if (piv > low + 1) 
            stack.push(low);
            stack.push(piv - 1);
        
        if (piv < high - 1) 
            stack.push(piv + 1);
            stack.push(high);
        
        while (!stack.isEmpty()) 
            high = stack.pop();
            low = stack.pop();
            piv = piovt(array, low, high);
            if (piv > low + 1) 
                stack.push(low);
                stack.push(piv - 1);
            
            if (piv < high - 1) 
                stack.push(piv + 1);
                stack.push(high);
            
        
    

    private static int piovt(int[] array, int start, int end) 
        int temp = array[start];
        while (start < end) 
            while (start < end && array[end] >= temp) 
                end--;
            
            array[start] = array[end];
            while (start < end && array[start] < temp) 
                start++;
            
            array[end] = array[start];
        
        array[start] = temp;
        return start;

测试代码：

public class TestDemo 
    public static void main(Stringjava集合与数据结构——七大排序算法的实现(代码片段)
文章目录排序介绍稳定性一、直接插入排序1.原理2.基本思想3.代码展示4.性能分析二、希尔排序1.基本思想*注意点2.代码展示3.增量gap的选取4.性能分析三、选择排序1.基本思想2.代码展示3.性能分析四、堆排序1.基本思想2.建堆操作...  查看详情  
                
20172308《java软件结构与数据结构》第四周学习总结(代码片段)
教材学习内容总结第6章列表一.列表集合列表集合：一种概念性表示法，思想是使事物以线性列表的方式进行组织特点：列表集合没有内在的容量大小，它可以随着需要而增大列表集合更具一般化，可以在列表的中间和末端添加...  查看详情  
                
java集合与数据结构优先级队列堆(代码片段)
Java集合与数据结构优先级队列【堆】二叉树的顺序存储存储方式堆(heap)操作-向下调整堆的应用-优先级队列操作-入队列操作-出队列java中的优先级队列堆的其他应用TopK问题堆的其他应用堆排序二叉树的顺序存储存储方式使用数...  查看详情  
                
java集合与数据结构优先级队列堆(代码片段)
Java集合与数据结构优先级队列【堆】二叉树的顺序存储存储方式堆(heap)操作-向下调整堆的应用-优先级队列操作-入队列操作-出队列java中的优先级队列堆的其他应用TopK问题堆的其他应用堆排序二叉树的顺序存储存储方式使用数...  查看详情  
                
java自用集合练习题：treeset的自然排序与定制排序(代码片段)
定义一个Employee类。该类包含：private成员变量name,age,birthday，其中birthday为MyDate类的对象；并为每一个属性定义getter,setter方法；并重写toString方法输出name,age,birthday。MyDate类包含:private成员变量year,month,day；并  查看详情  
                
集合collectionlistset迭代器iterator元素排序(代码片段)
...*集合是用来保存一组元素的，不同的实现类实现了不同数据结构。*Collection是所有集合的顶级接口，规定了所有集合都必须具备的功能。**集合与数组一样，保存一组元素，但是操作元素的方法集合已经提供了。**Collection下面有...  查看详情  
                
201723062018-2019《程序设计与数据结构》第四周总结(代码片段)
201723062018-2019-2《Java程序设计》第四周学习总结教材学习内容总结列表集合列表集合是一种概念性表示法，其思想是使事物以线性列表的方式进行组织，没有内在的容量大小，它可以随着需要而增大。列表集合的三种类型：有序...  查看详情  
                
java集合04_map接口概述常用方法排序hashtable面试题(代码片段)
....TreeMap排序⑥.Hashtable面试题①.Map接口的概述①.Map是双列集合与Collection的单列集合并列存在②.Map<K,V>这里的K、V都应该是引用数据类型③.HashSet底层依赖HashMap,单列底层依赖双列集合④.Map中的key可以为null,value  查看详情  
                
java使用集合排序(代码片段)
  查看详情  
                
初识java语言-数组(代码片段)
...、数组的概念数组是存储相同类型值的序列。数组是一种数据结构，用来存储同一类型值的集合。通过一个整形下标（索引）可以访问  查看详情  
                
list集合排序总结(代码片段)
...：1、Collections.sort(java对象) 2、Collections.sort(java对象集合,newComparator<>());拓展：3、list.stream().sorted()拓展：总结：4、List排序4.1、List的单条件升序（默认）排序4.2、List的单条件降序排序 4.3、List的多条...  查看详情  
                
java基础知识点笔记总结(代码片段)
文章目录1.数组与集合概述2.Collection接口和Map接口集合3.Collection接口集合3.1Collection接口方法3.2集合转数组和数组转集合的一些方法4.Iterator遍历4.1使用Iterator遍历Collection4.2使用foreach循环遍历集合元素5.Collection子接口之一list接口5.1...  查看详情  
                
java集合与数据结构map和set(代码片段)
Java集合与数据结构Map和Set搜索树操作：查找、插入、删除性能分析搜索模型Map的使用关于Map的说明关于Map.Entry<K,V>的说明Map的常用方法说明Set的使用常见方法说明Map和Set试题练习只出现一次的数字复制带随机指针的链表...  查看详情  
                
java集合与数据结构栈和队列(代码片段)
Java集合与数据结构栈和队列栈(Stack)基本方法栈的习题出栈顺序不可能中缀表达式转后缀表达式（逆波兰式）手动实现栈队列(Queue)基本方法链表实现队列循环队列用队列实现栈用栈实现队列括号匹配问题实现一个最小栈...  查看详情  
                
java集合与数据结构栈和队列(代码片段)
Java集合与数据结构栈和队列栈(Stack)基本方法栈的习题出栈顺序不可能中缀表达式转后缀表达式（逆波兰式）手动实现栈队列(Queue)基本方法链表实现队列循环队列用队列实现栈用栈实现队列括号匹配问题实现一个最小栈...  查看详情  
                
java数据结构与算法——冒泡排序(代码片段)
1.关于排序排序也称排序算法(SortAlgorithm)，排序是将一组数据，依指定的顺序进行排列的过程。排序的分类：内部排序: 指将需要处理的所有数据都加载到内部存储器中进行排序。外部排序法：数据量过大，无...  查看详情  
                
201723052018-2019-1《java软件结构与数据结构》第二周学习总结(代码片段)
201723052018-2019-1《Java软件结构与数据结构》第二周学习总结教材学习内容总结本周内容主要为书第三章和第四章的内容：第三章(以数组来替代栈的作用)集合(聚集，组织了其他对象的对象)：线性集合(直线方式组织的集合)非线性...  查看详情  
                
数组与排序及工具类（arrays类）(代码片段)
数组概述数组是相同类型数据的有序集合数组描述的是相同类型的若干个数据，按照一定的先后顺序排列组合而成。其中，每一个数据称作一个数组元素，每个数组元素可以通过一个下标来访问它们。数组声明创建首先必须声明...  查看详情



      
        
          免责声明：如内容涉及版权或违规等问题，请在尽快内联系我们pp114#vip.qq.com，我们将在第一时间删除内容。

正文

java集合与数据结构排序(代码片段)

Java集合与数据结构 排序

概念

插入排序

直接插入排序

代码实现

性能分析

希尔排序

代码实现

性能分析

选择排序

直接选择排序

代码实现

性能分析

堆排序

代码实现

性能分析

交换排序

冒泡排序

代码实现

性能分析

快速排序

代码实现

性能分析

非递归实现快速排序

代码实现

java集合与数据结构——七大排序算法的实现(代码片段)

20172308《java软件结构与数据结构》第四周学习总结(代码片段)

java集合与数据结构优先级队列堆(代码片段)

java集合与数据结构优先级队列堆(代码片段)

java自用集合练习题：treeset的自然排序与定制排序(代码片段)

集合collectionlistset迭代器iterator元素排序(代码片段)

201723062018-2019《程序设计与数据结构》第四周总结(代码片段)

java集合04_map接口概述常用方法排序hashtable面试题(代码片段)

java使用集合排序(代码片段)

初识java语言-数组(代码片段)

list集合排序总结(代码片段)

java基础知识点笔记总结(代码片段)

java集合与数据结构map和set(代码片段)

java集合与数据结构栈和队列(代码片段)

java集合与数据结构栈和队列(代码片段)

java数据结构与算法——冒泡排序(代码片段)

201723052018-2019-1《java软件结构与数据结构》第二周学习总结(代码片段)

数组与排序及工具类（arrays类）(代码片段)

Java集合与数据结构排序