java八种常用排序算法

不念不忘少年蓝@ 2022-12-20 02:20 137阅读 0赞

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xicWx6Y2g_size_16_color_FFFFFF_t_70][]

[在线动画演示插入/选择/冒泡/归并/希尔/快速排序算法过程工具][Link 1](点击查看)

> **冒泡排序**

冒泡排序将一个列表中的两个元素进行比较，并将最小的元素交换到顶部。两个元素中较小的会冒到顶部，而较大的会沉到底部，该过程将被重复执行，直到所有元素都被排序。

//冒泡排序
    public class BubbleSort {
        public static void main(String[] args) {
            int arr[] = new int[]{5, 3, 0, 9, 1, 7, 4, 6, 1};
            System.out.println(Arrays.toString(arr));
            sort(arr);
            System.out.println(Arrays.toString(arr));
        }
    
        public static void sort(int arr[]) {
            /*比较过程
             * 5,3,0,9,1,7,4,6,1
             * 3,5,0,9,1,7,4,6,1
             * 3,0,5,9,1,7,4,6,1
             * 依次进行
             * */
            //控制比较的次数
            for (int i = 0; i < arr.length - 1; i++) {//length-1  9个数 比较8次
                for (int j = 0; j < arr.length - 1 - i; j++) {//length-1-i   排除掉上次比较过的数
                    if (arr[j] > arr[j + 1]) {
                        int temp = arr[j];
                        arr[j] = arr[j + 1];
                        arr[j + 1] = temp;
                    }
                }
            }
        }
    }

> **快速排序**

快速排序（Quicksort）是对冒泡排序的一种改进。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。（递归进行排序，直到排序就是自己时 ，停止递归排序）

//快速排序
    public class QuitSort {
        public static void main(String[] args) {
            int arr[] ={4,1,2,3,0,0,6,8,10,11};
            quitSort(arr,0,arr.length-1);
            System.out.println(Arrays.toString(arr));
        }
        public static void quitSort(int arr[],int start,int end){
            if(start<end){
            //把数组中的第0个数作为标准数（其他数也可以  一般是第0个数）
            int stard = arr[start];
            //记录需要排序的下标
            int low = start;
            int hight = end;
            //循环找比标准数大的数和小的数
            while (low<hight){
                //右边的数数字比标准数小
                while(low<hight&&stard<=arr[hight]){
                    hight--;
                }
                //使右边的数字替换左边的数字
                arr[low] = arr[hight];
                //左边的数字比标准数小
                while (low<hight&&arr[low]<=stard){
                  low++;
                }
                //使左边的数字替换右边的数字
                arr[hight]=arr[low];
            }
            //把标准数赋值给低所在的位置的元素
            arr[low]=stard;
            //处理所有的小的数字
            quitSort(arr,start,low);
            //处理所有的大的数字
            quitSort(arr,low+1,end);
        }
        }
    }

> **插入排序**

插入排序：插入排序基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为O(n^2)。是稳定的排序方法。插入排序的基本思想是：每步将一个待排序的纪录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止

public class InsertSort {
        public static void main(String[] args) {
            int arr[] ={2,8,0,3,9,1,6,7};
            insertSort(arr);
            System.out.println(Arrays.toString(arr));
        }
        public static void insertSort(int arr[]){
            //遍历所有的数字
            for (int i = 1; i <arr.length; i++) {
                //如果当前数字比前一个数字小   就倒回来循环 
                if(arr[i]<arr[i-1]){
                    //把当前遍历的数字存起来
                    int temp = arr[i];
                    //遍历当前数字前面的所有的数字
                    int j;
                    for (j = i-1; j >=0&&temp<arr[j];j--) {
                        //把前一个数字赋值给后一个数字
                        arr[j+1]=arr[j];
                    }
                    //把临时变量（外层for循环的当前元素）赋值给不满足条件的后一个元素
                    arr[j+1]=temp;
                }
            }
        }
    }

> **希尔排序**

希尔排序：希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

public class ShellSort {
        public static void main(String[] args) {
            int arr[] ={4,2,9,0,5,1,2,6,1};
            shellSort(arr);
            System.out.println(Arrays.toString(arr));
        }
        public static void shellSort(int arr[]){
            //遍历所有的步长
            for (int d = arr.length/2; d>0; d/=2) {
                //遍历所有的元素
                for (int i = d; i <arr.length; i++) {
                    for (int j =i-d; j >=0 ; j-=d) {
                        //如果当前元素大于加上步长后的那个元素
                        if(arr[j]>arr[j+d]){
                            int temp = arr[j];
                            arr[j]=arr[j+d];
                            arr[j+d]=temp;
                        }
                    }
                }
            }
        }
    }

> **选择排序**

选择排序：选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。 选择排序是不稳定的排序方法。

public class SelectSort {
        public static void main(String[] args) {
            int arr[] = new int[]{9,0,4,5,3,1,2,8,7,2};
            selectSort(arr);
            System.out.println(Arrays.toString(arr));
        }
        public static void selectSort(int arr[]){
            //10个数  arr.length-1,只需要下标为0~8的数跟其他数进行比较  最后一个数就不进行比较了
            for (int i = 0; i <arr.length-1; i++) {
                for (int j = i+1; j <arr.length ; j++) {
                    if(arr[i]>arr[j]){
                        int temp=arr[i];
                        arr[i]=arr[j];
                        arr[j]=temp;
                    }
                }
            }
        }
    }

其他三种排序待续

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xicWx6Y2g_size_16_color_FFFFFF_t_70]: /images/20221120/8c18d4454b094a0f8be0d80e122d8e96.png
[Link 1]: http://tools.jb51.net/aideddesign/paixu_ys/