投稿
  1. 极客之音首页
  2. 技术随笔

排序算法全家桶（Java实现）

小半 • • 技术随笔 • 阅读 264

导读：本篇文章讲解 排序算法全家桶（Java实现），希望对大家有帮助，欢迎收藏，转发！站点地址：www.bmabk.com

文章目录

🤩我们每个人都要自信一点，不要因为别人的好而忘记自己的好。


在这里插入图片描述

排序算法

😛术语说明

•稳定： 如果a原本在b前面，而a = b,排序之后a仍然在b前面。
•不稳定： 如果a原本在b的前面，而a = b，排序之后a可能会出现b的后面。
•内排序： 所有排序操作都在内存中完成。
•外排序： 由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行（涉及文件操作以及归并排序思想）。
•时间复杂度： 一个算法执行所耗费的时间。
•空间复杂度： 运行完一个程序所需内存的大小。
在这里插入图片描述

1.冒泡排序

算法思想

冒泡排序从前到后遍历，依次比较相邻元素的值，如果发现当前元素的值大于其后面的元素的值，那么就进行两个数的交换，就像气泡一样往上漂浮，一个一个的浮出水面。
在这里插入图片描述

算法描述

①比较相邻的元素，如果第一个比第二个大，就交换他们两个；
②对每一对相邻元素做同样的工作，从开始第一对到结尾最后一对，这样在最后的元素就会是最大的数；
③针对所有的元素重复以上步骤，直到排序完成。

动画演示

在这里插入图片描述

代码演示


import java.util.Arrays;

public class SortTest01 {
    public static void bubbleSort(int[] arr) {
        //安全检测
        if (arr == null || arr.length == 1) {
            return;
        }

        for (int i = 0;i < arr.length - 1;i++) {//比较趟数
            for (int j = 0;j < arr.length - i - 1;j++) {// 每趟比较次数
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }
    
    public static void main(String[] args) {
        int[] arr = {7,3,22,15,8};
        System.out.println("排序前:" + Arrays.toString(arr));
        bubbleSort(arr);
        System.out.println("排序后:" + Arrays.toString(arr));
    }
}

运行结果：
在这里插入图片描述

冒泡排序的优化

如果在某一趟的比较后，整个序列已经有序，那么就没有必要再进行下一趟的比较了，因此，我们可以立一个flag，如果发生交换，改变flag。如果在一趟比较完后发现flag没有被改变就代表序列有序，跳出循环，完成冒泡排序。

代码如下


import java.util.Arrays;

public class SortTest01 {
    public static void bubbleSort(int[] arr) {
        //安全检测
        if (arr == null || arr.length == 1) {
            return;
        }

        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 = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
                flag = false;
            }
            if (flag == true) {
                break;
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {7,3,22,15,8};
        System.out.println("排序前:" + Arrays.toString(arr));
        bubbleSort(arr);
        System.out.println("排序后:" + Arrays.toString(arr));
    }
}

运行结果：
在这里插入图片描述

冒泡排序算法分析

🙈时间复杂度： 最优时间复杂度：O(n)，最差情况：O(n2)，平均时间复杂度：O(n2)
🙉空间复杂度： 平均空间复杂度：O(1)
🙊稳定性： 稳定

2.选择排序

算法思想

选择排序首先在未排序的序列中找到最小元素，存放到排序序列的起始位置，然后再从剩余未排序的元素中继续寻找最小元素，然后放到排序序列末尾。以此类推，直到所有的元素都排序完毕。
选择排序的特点:选择排序是不稳定的排序算法之一，因为无论对什么数据进行排序都是O(n2) 的时间复杂度，因为选择排序的时间复杂度比较大，所以当使用选择排序的时候，数据规模越小越好。

算法描述

首先在未排序的序列中找到最小(或最大) 的元素（根据自己所需进行排序)，存放在排序序列的起始位置，然后，再从剩余的元素中继续寻找最小(或最大)的元素，和已排序好的队列末尾进行交换，以此类推，直到所有的元素都排序完毕。

动画演示

在这里插入图片描述

代码演示


import java.util.Arrays;

public class SortTest02 {
    /*
   1.假设数组有n个元素，进行n-1趟比较
   2.每轮排序
   1）假设当前的数是最小值，下标赋值给变量min
   2）与该数后面的所有数进行比较，如果发现有比该数更小的数，得到这个数的下标赋值给min，进行完这一轮的比较后，得到这一轮的最小值的下标min。
   3）进行交换
     */
    public static void selectSort(int[] arr) {
        //安全监测
        if (arr == null || arr.length == 1) {
            return;
        }

        for (int i = 0;i < arr.length - 1;i++) {
            int min = i;
            for (int j = i + 1;j < arr.length;j++) {
                if (arr[j] < arr[min]) {
                    min = j;
                }
            }
            int temp = arr[i];
            arr[i] = arr[min];
            arr[min] = temp;
        }
    }


    public static void main(String[] args) {
        int[] arr = {3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};
        System.out.println("排序前:" + Arrays.toString(arr));
        selectSort(arr);
        System.out.println("排序后:" + Arrays.toString(arr));
    }
}

运行结果：
在这里插入图片描述

选择排序算法分析

🙈时间复杂度： 最优时间复杂度O(n2)，平均时间复杂度O(n2)，最坏时间复杂度O(n2)
🙊空间复杂度： O(1)
🙉稳定性： 不稳定

3.插入排序

算法思想

插入排序就是通过构建有序数列，然后对于未排序的数据在已经有序的序列中从后往前扫描，找到合适的位置并插入。

算法描述

①从给定的序列中的第一个元素开始，默认该元素已经在有序序列。
②取出下一个元素并保存在一个临时变量temp中（防止数据移动时该元素丢失），在已经排序的有序序列中从后往前扫描。
③如果该元素大于temp，则继续往前扫描到下一个元素。
④重复步骤③，直到在已排序的序列中找到小于等于temp的元素。temp插入到该元素的后面；如果已排序的序列中的所有元素都大于temp，那么将temp元素插入到已排序的序列中的第一个位置。
⑤重复步骤②到④，直到所有的元素排序完毕。

动画演示

在这里插入图片描述

代码演示


import java.util.Arrays;

public class SortTest03 {
    public static void insertSort(int[] arr) {
        //安全检测
        if (arr == null || arr.length == 1) {
            return;
        }

        for (int i = 1;i < arr.length;i++) {
            int temp = arr[i];
            int j = i - 1;
            for (;j >= 0;j--) {
                if (temp < arr[j]) {
                    arr[j + 1] = arr[j];
                }else {//temp >= arr[j]
                    arr[j + 1] = temp;
                    break;
                }
            }
            //已排序的序列中没有一个元素小于temp
            //temp放在已经排序好的序列中的0号位置
            arr[j + 1] = temp;
        }
    }

    public static void main(String[] args) {
        int[] arr = {3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};
        System.out.println("排序前:" + Arrays.toString(arr));
        insertSort(arr);
        System.out.println("排序后:" + Arrays.toString(arr));
    }
}

运行结果：
在这里插入图片描述

插入排序算法分析

🙈时间复杂度： 最优时间复杂度：O(n)，平均时间复杂度：O(n2)，最差时间复杂度：O(n2)
🙊空间复杂度： 平均空间复杂度：O(1)
🙉稳定性： 稳定

4.希尔排序

算法思想

希尔排序也是一种插入排序，它是简单插入排序的一种算法改进方式。也称为见效增量排序，希尔排序的时间复杂度相比直接插入排序的时间复杂度要小。他与直接插入排序的不同在于它会优先比较距离较远的元素。希尔排序是按照一定的增量进行分组排序，对每一组进行直接插入排序，随着分组个数的减少，每组中的元素就会越来越多，当增量减为1时，排序结束。

算法描述

①选择增量gap = length / 2;缩小增量继续以gap = gap / 2的方式进行分组。{n/2,(n/2)/2,(n/2)/4,…,1}的增量序列。
②选择一个增量序列，按照增量序列个数m，进行m趟排序。
③每趟排序根据对应的增量次数，分别进行元素的分组操作，对组内进行直接插入排序操作。
④继续下一个增量，分别进行分组直接插入操作。
⑤重复第③个步骤，直到增量变成1，所有元素在一个分组内，希尔排序结束。

动画演示

在这里插入图片描述

算法详解

现在我们用希尔排序对以下序列进行排序。
在这里插入图片描述
第一次排序： 用序列长度的一半 10 / 2 = 5 作为第一次排序时的 gap 值，此时相隔距离为5的元素分为了一组，一共分为了 5 组，每组有 2 个元素，再分别对每一组进行直接插入排序。
在这里插入图片描述

第二次排序： 对 gap 值进行折半 gap = 5 / 2 = 2；所以在序列中距离为 2 的元素分为一组，一共分为了 2 组，每组有 5 个元素，再分别对每一组进行直接插入排序。

在这里插入图片描述
第三次排序： 对 gap 值进行折半 gap = 2 / 2 = 1；所以在序列中距离为 1 的元素分为一组，一共分为了 1 组，每组有 10 个元素，再分别对每一组进行直接插入排序。
在这里插入图片描述
所以排序后的结果为：
在这里插入图片描述

代码演示


import java.util.Arrays;

public class SortTest04 {
    public static void shell(int[] arr, int gap) {
        //安全监测
        if (arr == null || arr.length == 1) {
            return;
        }

        for (int i = gap; i < arr.length; i++) {
            int temp = arr[i];
            int j = i - gap;
            for (; j >= 0; j -= gap) {
                if (arr[j] > temp) {
                    arr[j + gap] = arr[j];
                } else {
//                    arr[j + 1] = temp;
                    break;
                }
            }
            arr[j + gap] = temp;
        }
    }

    public static void shellSort(int[] arr) {
        int[] gaps = {5, 3, 1};
        for (int i = 0; i < gaps.length; i++) {
            shell(arr, gaps[i]);
        }

    }

    public static void main(String[] args) {
        int[] arr = {8,9,1,7,2,3,5,4,6,0};
        System.out.println("排序前:" + Arrays.toString(arr));
        shellSort(arr);
        System.out.println("排序后:" + Arrays.toString(arr));
    }
}

运行结果：
在这里插入图片描述

希尔排序算法分析

🙈时间复杂度： 平均时间复杂度：O(n1.3~n1.5)
🙊空间复杂度： O(1)
🙉稳定性： 不稳定

5.归并排序

算法思想

归并排序建立在归并的有效操作上进行排序，主要采用分治法将已有序的子序列合并，得到完全有序的序列。即先让每一小段有序，再让小段之间变得有序。若将两个有序合成一个有序段，这又称为二路归并。
补充：分治法，字面意思是“分而治之”，就是把一个复杂的问题分成两个或多个相同或相似的子问题，再把子问题分成更小的子问题直到最后子问题可以简单地直接求解，原问题的解即子问题的解的合并。
将两个有序序列合并成一个有序序列演示：
在这里插入图片描述

算法描述

①开始以间隔为1的进行归并，也就是说，第一个元素跟第二个进行归并。第三个与第四个进行归并；
②然后，再以间隔为2的进行归并，1-4进行归并，5-8进行归并；
③再以2 * 2的间隔进行归并，同理直到2 * k超过序列的长度为止。
④当不够两组进行归并时，如果超过k个元素元素，仍然进行归并；如果剩余元素不超过k个元素，那么直接复制给中间元素。

动画演示

在这里插入图片描述

算法详解

将序列 26 53 67 48 57 13 49 32 60 50 进行归并排序。
在这里插入图片描述
在进行归并排序过程中我们需要考虑三种特殊情况：
第一种： 最后一个小组没有与之对应的小组存在，则不需要排序。
在这里插入图片描述
第二种： 最后一个小组没有与之对应的小组存在，且最后一个小组中的元素个数不够gap个，则不需要排序。
在这里插入图片描述
第三种： 最后一个小组有与之对应的小组存在，但是与之对应的小组中的元素个数不够gap个，则需要控制与之对应小组的边界。
在这里插入图片描述

代码演示

import java.util.Arrays;

public class SortTest05 {
    private static void marge(int[] arr,int gap,int[] brr){
        int left1 = 0;//第一个序列左边界
        int right1 = left1 + gap - 1; //第一个序列右边界
        int left2 = right1 + 1;//第二个序列左边界
        //第二个序列的右边界 考虑两种情况 1）其序列左边界 + gap - 1如果超过序列长度，则右边界直接等于数组的最大下标
        //                          2)其序列左边界 + gap - 1如果没有超过序列长度，则右边界等于 left2 + gap - 1
        int right2 = left2 + gap - 1 > arr.length - 1  ? arr.length - 1 : left2 + gap - 1;

        //开辟一个与数组arr相同长度的brr数组，用来在归并排序过程中存放已经完成排序的序列

        int j = 0;//控制新数组下标
        while (left2 < arr.length) {
            //合并两个有序序列
            while (left1 <= right1 && left2 <= right2) {
                if (arr[left1] < arr[left2]) {
                    brr[j++] = arr[left1++];
                }else {
                    brr[j++] = arr[left2++];
                }
            }

         //当其中一个序列中元素全部排序完，另一个序列剩余元素直接归入brr数组中
            if (left1 > right1) {
                while(left2 <= right2) {
                    brr[j++] = arr[left2++];
                }
            }
            if (left2 > right2) {
                while (left1 <= right1) {
                    brr[j++] = arr[left1++];
                }
            }

          //更新两个待排序序列的左下标和右下标
            left1 = right2 + 1;
            right1 = left1 + gap - 1;
            left2 = right1 + 1;
            right2 = left2 + gap - 1 > arr.length - 1 ? arr.length - 1 : left2 + gap - 1;
        }

        //只剩一个归并字段
        while(left1 <= arr.length - 1) {
            brr[j++] = arr[left1++];
        }

        System.arraycopy(brr,0,arr,0,arr.length);
    }

    public static void margeSort(int[] arr) {
        //安全检测
        if (arr == null || arr.length == 1) {
            return;
        }

        int[] brr = new int[arr.length];
        for (int i = 1; i < arr.length ; i*=2) {
            marge(arr,i,brr);
        }
    }

    public static void main(String[] args) {
        int[] arr = {26,53,67,48,57,13,49,32,60,50};
        System.out.println("排序前:" + Arrays.toString(arr));
        margeSort(arr);
        System.out.println("排序后:" + Arrays.toString(arr));
    }
}

运行结果：
在这里插入图片描述

归并排序算法分析

🙈时间复杂度： 平均时间复杂度：O(nlog2n) ，最坏时间复杂度：O(nlog2n)
🙊空间复杂度： O(n)
🙉稳定性： 不稳定

6.快速排序

算法思想

快速排序主要是通过选择一个关键值作为基准值。比基准值小的都在左边序列（一般是无序的），比基准值大的都在右边（一般是无序的）。依次类推，达到总体待排序序列都有序。

算法描述

① 选择基准： 在待排序列中，按照某种方式挑出一个元素，作为“基准”（pivot）。
② 分割操作： 以该基准在序列中的实际位置，把序列分成两个子序列。此时，在基准左边的元素都比基准小，在基准右边的元素都比基准大。
③ 递归地对两个序列进行快速排序，直到两个序列为空或者只有一个元素。

动画描述

在这里插入图片描述

算法详解

将序列 26 53 67 48 57 13 49 32 60 50 进行快速排序。
在这里插入图片描述
①选左边界为基准，把基准位置值保存在临时变量temp中。
②先从后往前找比基准位置值（temp）小的值停止，将high位置元素放在low位置处。
③再从前往后找，找到比基准位置值大的值停止，将low 位置元素放在high位置处。
④继续重复步骤②③，直到 high = low，此时low（high）位置就是基准值temp所放的位置。
在这里插入图片描述
进行完第一轮排序后，从基准点为切割位置，统计切割位置左右的元素个数，如果切割位置左边的元素个数大于等于2个，那么继续重复步骤①②③④，切割位置右边同理。完成排序后，继续以基准点为切割位置统计切割位置左右的元素个数…直到切割位置左右两边的元素个数都小于等于1个。 如下：

在这里插入图片描述
所以结果为：
在这里插入图片描述

代码演示

import java.util.Arrays;

public class SortTest06 {
    public static int partition(int[] arr,int low,int high) {
        //安全检测
        if (arr == null || arr.length == 1) {
            return -1;
        }
        int temp = arr[low];//基准值
        while(low < high) {
            //从后向前找比基准位置元素小的元素
            while (low < high && arr[high] > temp) {
                high--;
            }
            if (low == high) {//如果low == high，那么这个位置就是基准元素所放的位置
//                arr[low] = temp;
//                return low;
                break;
            }
            arr[low] = arr[high];

            //从前往后找比基准位置元素大的元素就停止
            while(low < high && arr[low] < temp) {
                low++;
            }
            if (low == high) {//如果low == high，那么这个位置就是基准元素所放的位置
//                arr[low] = temp;
//                return low;
                break;
            }
            arr[high] = arr[low];
        }
        arr[high] = temp;
        return low;
    }
    public static void quick(int[] arr,int low,int high) {
        int index = partition(arr,low,high);//返回基准位置的下标
        if (index == -1) {
            return;
        }
        //如果基准位置下标的左边元素个数 >= 2，则左边继续划分
        if (index - low > 1) {
            quick(arr,low,index - 1);
        }
        //如果基准位置下标的右边元素个数 <= 2，则右边继续划分
        if (high - index > 1) {
            quick(arr,index + 1,high);
        }

    }

    public static void quickSort(int[] arr) {
        //安全检测
        if (arr == null) {
            return;
        }
        quick(arr,0,arr.length - 1);
    }

    public static void main(String[] args) {
        int[] arr = {26,53,67,48,57,13,49,32,60,50};
        System.out.println("排序前:" + Arrays.toString(arr));
        quickSort(arr);
        System.out.println("排序后:" + Arrays.toString(arr));
    }
}

运行结果：
在这里插入图片描述

快速排序算法分析

🙈时间复杂度： 最优时间复杂度：O(nlog2n) ，平均时间复杂度：O(nlog2n)，最坏时间复杂度：O(n2)
🙊空间复杂度： O(1)
🙉稳定性： 不稳定

7.堆排序

二叉树

二叉树： 当前结点最多有两个子树的树结构。如下：
在这里插入图片描述
😀根结点： 没有父结点的结点，如图中的7；
😁左孩子： 二叉树中一个结点的左分支，如图中的4；
😂右孩子： 二叉树中一个结点的右分支，如图中的3；
🤣叶子结点： 也叫终端结点，是度为 0 的结点，如图中的6 8 0 1；
😊分枝结点： 度不为0的结点，如图中的4 3 2；
😎完全二叉树： 二叉树上的每一层都是满的，或者最后一层没填满并且最后一层的叶子结点都是靠最左边存放，图中的二叉树就是一个完全二叉树。

大顶堆和小顶堆

堆是一颗顺序存储的完全二叉树，分为大顶堆和小顶堆。
😜大顶堆： 每个结点的值大于等于其左、右孩子的值，这样的堆称为大顶堆。
如图示例：
在这里插入图片描述
大顶堆特点： arr[i] >= arr[2 * i + 1] && arr[i] >= arr[2 * i + 2] 其中i对应第几个节点，i从0开始编号。

😝小顶堆： 每个结点的值小于等于其左、右孩子的值，这样的堆称为小顶堆。
在这里插入图片描述
小顶堆特点： arr[i] <= arr[2 * i + 1] && arr[i] <= arr[2 * i + 2] 其中i对应第几个节点，i从0开始编号。

算法思想

堆排序是指利用堆这种数据结构进行设计的一种排序算法。堆排序利用了大顶堆（或小顶堆）堆顶记录的关键字最大（最小）这一特征，使得在当前无序区中选取最大（或最小）关键字的记录变得简单。 一般升序排序采用大顶堆，降序排序采用小顶堆。

算法描述

堆排序首先是根据元素构建堆。然后将堆的根节点取出（一般是与最后一个节点进行交换），将前面 len – 1个节点继续进行堆调整的过程，然后再将根节点取出，这样一直到所有节点都取出。
用大顶堆排序的基本思想
① 先将待排序序列建成一个大顶堆，此堆为初始的无序。
② 此时，整个序列的最大值就是堆顶的根节点。
③ 将其与末尾元素进行交换，此时末尾就是最大值。
④ 然后将剩余n-1个元素重新建成一个堆，这样会得到n个元素的次小值。如此反复执行，便得到一个有序的序列了。

算法图示

要求:给你一个数组 {4,6,8,5,9}，要求使用堆排序法，将数组升序排序。
步骤一： 构造初始堆。将给定的无序序列构造成一个大顶堆。原始数组： {4,6,8,5,9}
① 假定给定的无序序列结构如下
在这里插入图片描述
② 此时我们从最后一个非叶子结点开始（叶结点自然不用调整，第一个非叶子结点 arr.length / 2 – 1 = 1，也就是下面的6结点），从左到右，从下到上进行调整。
在这里插入图片描述
③找到第二个非叶子结点4，由于【4 9 8】中9最大，4和9交换。
在这里插入图片描述
④这时，交换了导致【4 5 6】结构混乱，继续调整，【4 5 6】中6最大，4和6交换。
在这里插入图片描述
此时我们就将一个无序序列构造成了一个大顶堆。

步骤二：将堆顶元素与末尾元素进行交换，使末尾元素最大。然后继续调整堆，再将堆顶元素与末尾元素交换，得到第二大元素。如此反复进行交换、重建、交换。
①将堆顶元素9和末尾元素4进行交换。
在这里插入图片描述
②重新调整结构，使其继续满足堆定义。
在这里插入图片描述
③再将堆顶元素8与末尾元素5进行交换，得到第二大元素8。
在这里插入图片描述
④后续过程，继续进行调整，交换，如此反复进行，最终使得整个序列有序。
在这里插入图片描述

代码演示


import java.util.Arrays;

public class SortTest07 {
    public static void adjust(int[] arr,int begin,int end) {
        //1.保存begin位置的值
        int temp = arr[begin];
        //2.挑选左右孩子中的较大值
        for (int i = 2 * begin + 1;i <= end;i = 2 * i + 1) {
            if (i + 1 <= end && arr[i] < arr[i + 1]) {
                i = i + 1;
            }
            //3.较大值与begin位置的值比较
            if (arr[i] > temp ) {
                arr[begin] = arr[i];
                begin = i;//交换以后 更新begin
            }else {
//                arr[begin] = temp;
                break;
            }
        }
        //越界了，最后把temp值赋给begin位置的值
        arr[begin] = temp;

    }
    public static void heapSort(int[] arr) {
        //将堆调整成大根堆的形式(从倒数第一个非叶子结点开始)
        for (int i = (arr.length - 1 - 1) / 2; i >= 0; i--) {
            adjust(arr,i,arr.length - 1);
        }
        //交换0号下标元素和“相对最后”的元素
        for (int i = 0;i < arr.length;i++) {
            int temp = arr[0];
            arr[0] = arr[arr.length - 1 - i];
            arr[arr.length - 1 - i] = temp;
            adjust(arr,0,arr.length - 1 - 1 - i);
        }

    }

    public static void main(String[] args) {
        int[] arr = {4,6,8,5,9};
        System.out.println("排序前:" + Arrays.toString(arr));
        heapSort(arr);
        System.out.println("排序后:" + Arrays.toString(arr));
    }
}

运行结果：
在这里插入图片描述

堆排序算法分析

🙈时间复杂度： 最优时间复杂度：O(nlog2n)，平均时间复杂度：O(nlog2n)，最坏时间复杂度：O(nlog2n)
🙊空间复杂度： O(1)
🙉稳定性分析： 不稳定

版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。

文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/95540.html

赞 (0)
小半的头像小半
0 0

相关推荐

极客之音——专业性很强的中文编程技术网站，欢迎收藏到浏览器，订阅我们！