排序-简述

叁歲伎倆 2023-10-03 11:18 26阅读 0赞

#### 文章目录 ####

*  冒泡排序
 *  快速排序
 *  插入排序
 *  其他

## 冒泡排序 ##

每次冒泡过程都是从数列的第一个元素开始，然后依次和剩余的元素进行比较, 跟列队一样, **从左到右两两相邻的元素比大小**, 高的就和低的换一下位置. 最后最高(值最大)的肯定就排到后面了。

实现：

public static void maoSort(int[] arr){
        
        if(arr != null && arr.length > 1){
        
            for(int i = 0; i < arr.length - 1; i++){
        
                // 通过布尔值判断是否可以提前结束
                //如果内循环没有交换值,说明已经排序完成,提前终止
                boolean flag = true;
                for(int j = 0; j < arr.length - i - 1 ; j++){
        
                    if(arr[j] > arr[j+1]){
        
                        // 调换
                        int temp;
                        temp = arr[j];
                        arr[j] = arr[j+1];
                        arr[j+1] = temp;
                        // 改变flag
                        flag = false;
                    }
                }
                if(flag){
        
                    break;
                }
            }
        }
    }

## 快速排序 ##

也是分治排序法。  
快速排序,说白了就是**给基准数据找其正确索引位置的过程**.  
简单的说, 就是设置一个标准值, 将大于这个值的放到右边(不管排序), 将小于这个值的放到左边(不管排序), 那么这样只是区分了左小右大, 没有排序, 没关系, 左右两边再重复这个步骤.直到不能分了为止.  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NzAzOTc0NQ_size_16_color_FFFFFF_t_70]

public static void main(String[] args) {
        
    
            int arr[] = {
        7, 5, 3, 2, 4, 1, 8, 9, 6};
    
            //快速排序
            int low = 0;
            int high = arr.length - 1;
            quickSort(arr, low, high);  
        }
    
        public static void quickSort(int[] arr, int low, int high) {
        
            //如果指针在同一位置(只有一个数据时)，退出
            if (high - low < 1) {
        
                return;
            }
            //标记，从高指针开始，还是低指针（默认高指针）
            boolean flag = true;
            //记录指针的其实位置
            int start = low;
            int end = high;
            //默认中间值为低指针的第一个值
            int midValue = arr[low];
            while (true) {
        
                //高指针移动
                if (flag) {
        
                    //如果列表右方的数据大于中间值，则向左移动
                    if (arr[high] > midValue) {
        
                        high--;
                    } else if (arr[high] < midValue) {
        
                        //如果小于，则覆盖最开始的低指针值，并且移动低指针，标志位改成从低指针开始移动
                        arr[low] = arr[high];
                        low++;
                        flag = false;
                    }
                } else {
        
                    //如果低指针数据小于中间值，则低指针向右移动
                    if (arr[low] < midValue) {
        
                        low++;
                    } else if (arr[low] > midValue) {
        
                        //如果低指针的值大于中间值，则覆盖高指针停留时的数据，并向左移动高指针。切换为高指针移动
                        arr[high] = arr[low];
                        high--;
                        flag = true;
                    }
                }
                //当两个指针的位置相同时，则找到了中间值的位置，并退出循环
                if (low == high) {
        
                    arr[low] = midValue;
                    break;
                }
            }
            //然后出现有，中间值左边的小于中间值。右边的大于中间值。
            //然后在对左右两边的列表在进行快速排序
            quickSort(arr, start, low -1);
            quickSort(arr, low + 1, end);
        }

[参考链接-原理和结论部分][-]

## 插入排序 ##

类似于扑克牌的插入。  
将待插元素，依次与已排序好的子数列元素从后到前进行比较，如果当前元素值比待插元素值大，则将移位到与其相邻的后一个位置，否则直接将待插元素插入当前元素相邻的后一位置，因为说明已经找到插入点的最终位置

public class InsertSort {
        
    
        public static void sort(int[] arr) {
        
            if (arr.length >= 2) {
        
                for (int i = 1; i < arr.length; i++) {
        
                    //挖出一个要用来插入的值,同时位置上留下一个可以存新的值的坑
                    int x = arr[i];
                    int j = i - 1;
                    //在前面有一个或连续多个值比x大的时候,一直循环往前面找,将x插入到这串值前面
                    while (j >= 0 && arr[j] > x) {
        
                        //当arr[j]比x大的时候,将j向后移一位,正好填到坑中
                        arr[j + 1] = arr[j];
                        j--;
                    }
                    //将x插入到最前面
                    arr[j + 1] = x;
                }
            }
        }
    }

[参考链接][Link 1]

## 其他 ##

Arrays工具类提供的排序方法，内部使用的是快速排序。

private static void arraysSort(int[] a){
        
        Arrays.sort(a);
      }

利用java8排序

List<String> inventory = Arrays.asList("311","6","11","211111");
            inventory.sort(Comparator.comparing(String::length).reversed());
            System.out.println(inventory);
            inventory.sort(String::compareTo);
            System.out.println(inventory);

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NzAzOTc0NQ_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20210717102235973.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NzAzOTc0NQ==,size_16,color_FFFFFF,t_70
[-]: https://blog.csdn.net/nrsc272420199/article/details/82587933
[Link 1]: https://blog.csdn.net/zzzgd_666/article/details/87634775