【数据结构与算法 11】常见的7种排序算法

叁歲伎倆 2021-08-29 15:50 324阅读 0赞

算法在手，天下我有。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d1b3J1aV9qYXZh_size_16_color_FFFFFF_t_70][]

## 一、算法分类 ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d1b3J1aV9qYXZh_size_16_color_FFFFFF_t_70 1][]

算法的时间复杂度和空间复杂度：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d1b3J1aV9qYXZh_size_16_color_FFFFFF_t_70 2][]

## 二、七大排序算法 ##

### （一）冒泡排序 ###

1、基本思想

依次比较相邻的两个数，将比较小的数放在前面，比较大的数放在后面。

2、动态效果图

![2020052123562124.gif][]

3、代码实现

//冒泡排序
    private static void bubbleSort(int[] arr){
        // 标识变量，表示是否进行过交换
        boolean flag = false;
        int temp = 0;
        for (int i = 0; i < arr.length-1; i++) {
            for (int j = 0; j < arr.length-1-i; j++) {
                // 如果前面的数比后面的数大，则交换
                if(arr[j]>arr[j+1]){
                    flag = true;
                    temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
            // 在一趟排序中，一次交换都没有发生过
            if(!flag){
                break;
            }
        }
    }

4、速度测试

冒泡排序：120000数据，23秒

![20200523091321290.png][]

### （二）选择排序 ###

1、基本思想

（1）在序列中找到最小元素，放在第一个位置；

（2）从剩余未排序元素中继续寻找最小元素，放在第二个位置；

以此类推，直到排序完毕。

2、动态效果图

![20200522000657221.gif][]

3、代码实现

//选择排序
    public static void selectSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            int minIndex = i;
            int min = arr[minIndex];
            for(int j  = 1 + i;j<arr.length;j++){
                if(min > arr[j]){
                    min = arr[j];
                    minIndex = j;
                }
            }
            arr[minIndex] = arr[i];
            arr[i] = min;
        }
    }

4、速度测试

选择排序：120000数据，4秒

![20200523091411841.png][]

### （三）插入排序 ###

1、基本思想

把n个待排序的元素第一位看成有序表，其它的看成无序表，排序过程中，每次从无序表中取出一个数，依次与有序表中的数进行比较，插入到合适的位置。

2、动态效果图

![2020052200155496.gif][]

3、代码实现

//插入排序
    public static void insertSort(int[] arr ){
        int insertVal = 0;
        int insertIndex = 0;
        for (int i = 1; i < arr.length; i++) {
            //定义待插入的数
            insertVal = arr[i];
            // 即arr[i]的前面这个数的下标
            insertIndex = i - 1;
            // 给insertVal 找到插入的位置
            // 说明
            // 1. insertIndex >= 0 保证在给insertVal 找插入位置，不越界
            // 2. insertVal < arr[insertIndex] 待插入的数，还没有找到插入位置
            // 3. 就需要将 arr[insertIndex] 后移
            while(insertIndex >= 0 && insertVal < arr[insertIndex]){
                arr[insertIndex+1] = arr[insertIndex];
                insertIndex--;
            }
            // 当退出while循环时，说明插入的位置找到, insertIndex + 1
            if(insertIndex + 1 != i){
                arr[insertIndex+1] = insertVal;
            }
        }
    }

4、速度测试

插入排序：120000数据，1秒

![20200523091529335.png][]

### （四）希尔排序 ###

1、基本思想

希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序，同时该算法也是冲破O(n²)的第一批算法之一。它与插入排序的不同之处在于，它会优先比较较远的元素。

2、效果图

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d1b3J1aV9qYXZh_size_16_color_FFFFFF_t_70 3][]

3、代码实例

希尔排序有两种方式。

①希尔排序（冒泡排序）

//希尔排序
    // 使用逐步推导的方式来编写希尔排序
    // 希尔排序时， 对有序序列在插入时采用交换法,
    // 思路(算法) ===> 代码
    public static void shellSort(int[] arr){
        // 根据前面的逐步分析，使用循环处理
        for(int step = arr.length/2;step>0;step /= 2 ){
            for (int i = step; i < arr.length; i++) {
                // 遍历各组中所有的元素(共step组，每组有个元素), 步长step
                for (int j = i - step; j >= 0; j -= step) {
                    // 如果当前元素大于加上步长后的那个元素，说明交换
                    if (arr[j] > arr[j + step]) {
                        int temp = arr[j];
                        arr[j] = arr[j + step];
                        arr[j + step] = temp;
                    }
                }
            }
        }
    }

速度测试：

冒泡法希尔排序：120000数据，11秒

![20200523091603561.png][]

②希尔排序（插入排序）

//对交换式的希尔排序进行优化->插入法
    public static void shellSort2(int[] arr) {
    // 增量step, 并逐步的缩小增量
    for (int step = arr.length / 2; step > 0; step /= 2) {
        // 从第step个元素，逐个对其所在的组进行直接插入排序
        for (int i = step; i < arr.length; i++) {
            int j = i;
            int temp = arr[j];
            if(arr[j]<arr[j-step]){
                while (j - step >= 0&&temp<arr[j-step]){
                    arr[j] = arr[j-step];
                    j -= step;
                }
                arr[j] = temp;
            }
        }
    }

速度测试：

插入法希尔排序：12000000数据，4秒，叹为观止

![2020052309171161.png][]

### （五）快速排序 ###

1、基本思想

通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录进行排序，以达到整个排序的过程。

2、效果图

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d1b3J1aV9qYXZh_size_16_color_FFFFFF_t_70 4][]

3、算法描述

*  快速排序使用分治法把一个串分为两个子串；
 *  找一个基准点，暂时选中间点为基准点；
 *  重新排序数列，比基准值小的放在基准点前面，大的放在后面；
 *  递归的把小于基准值的子数列和大于基准值的子数列排序；

4、代码实例

//快速排序
    public static void quickSort(int[] arr,int left, int right) {
        int l = left; //左下标
        int r = right; //右下标
        //pivot 中轴值
        int pivot = arr[(left + right) / 2];
        int temp = 0; //临时变量，作为交换时使用
        //while循环的目的是让比pivot 值小放到左边
        //比pivot 值大放到右边
        while( l < r) {
            //在pivot的左边一直找,找到大于等于pivot值,才退出
            while( arr[l] < pivot) {
                l += 1;
            }
            //在pivot的右边一直找,找到小于等于pivot值,才退出
            while(arr[r] > pivot) {
                r -= 1;
            }
            //如果l >= r说明pivot 的左右两的值，已经按照左边全部是
            //小于等于pivot值，右边全部是大于等于pivot值
            if( l >= r) {
                break;
            }
    
            //交换
            temp = arr[l];
            arr[l] = arr[r];
            arr[r] = temp;
    
            //如果交换完后，发现这个arr[l] == pivot值 相等 r--， 前移
            if(arr[l] == pivot) {
                r -= 1;
            }
            //如果交换完后，发现这个arr[r] == pivot值 相等 l++， 后移
            if(arr[r] == pivot) {
                l += 1;
            }
        }
    
        // 如果 l == r, 必须l++, r--, 否则为出现栈溢出
        if (l == r) {
            l += 1;
            r -= 1;
        }
        //向左递归
        if(left < r) {
            quickSort(arr, left, r);
        }
        //向右递归
        if(right > l) {
            quickSort(arr, l, right);
        }
    }

5、速度测试

快速排序：12000000数据，1秒，逆天而行

![20200523135509144.png][]

### （六）归并排序 ###

1、基本思想

归并排序采用经典的分治策略，分治法将问题分成一些小的问题然后递归解决，则治的阶段就是将分的阶段得到的答案修补在一起，即分而治之。

2、效果图

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d1b3J1aV9qYXZh_size_16_color_FFFFFF_t_70 5][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d1b3J1aV9qYXZh_size_16_color_FFFFFF_t_70 6][]

3、代码实现

//归并排序
    public static void mergerSort(int[] arr,int left,int right,int[] temp){
        if(left<right){
            //中间索引
            int middle = (left + right)/2;
            //向左递归进行分解
            mergerSort(arr,left,middle,temp);
            //向右递归进行分解
            mergerSort(arr,middle + 1,right,temp);
            //合并
            merger(arr, left, middle, right, temp);
        }
    }
    
    //合并
    public static void merger(int[] arr,int left,int middle,int right,int[] temp){
        int i = left; // 初始化i, 左边有序序列的初始索引
        int j = middle + 1; //初始化j, 右边有序序列的初始索引
        int t = 0; // 指向temp数组的当前索引
    
        //先把左右两边(有序)的数据按照规则填充到temp数组
        //直到左右两边的有序序列，有一边处理完毕为止
        while (i <= middle && j <= right) {//继续
            //如果左边的有序序列的当前元素，小于等于右边有序序列的当前元素
            //即将左边的当前元素，填充到 temp数组
            //然后 t++, i++
            if(arr[i] <= arr[j]){
                temp[t] = arr[i];
                t++;
                i++;
            }else { //反之,将右边有序序列的当前元素，填充到temp数组
                temp[t] = arr[j];
                t++;
                j++;
            }
        }
    
        //把有剩余数据的一边的数据依次全部填充到temp
        //左边的有序序列还有剩余的元素，就全部填充到temp
        while (i <= middle){
            temp[t] = arr[i];
            t++;
            i++;
        }
    
        //右边的有序序列还有剩余的元素，就全部填充到temp
        while (j <= right){
            temp[t] = arr[j];
            t++;
            j++;
        }
    
        //将temp数组的元素拷贝到arr
        //注意，并不是每次都拷贝所有
        t = 0;
        int tempLeft = left; //
        while (tempLeft <= right){
            arr[tempLeft] = temp[t];
            t++;
            tempLeft++;
        }
    }

4、速度测试

归并排序：12000000数据，1秒，惊为天人

![20200524104937495.png][]

### （七）基数排序 ###

1、基本思想

将所有带比较数值统一为同样的数位长度，数据较短的数前面补0，然后从最低位开始依次进行依次排序，这样从最低位排序一直到最高位排序完成之后，数列就变成了一个有序序列。

2、动态效果图

![20200525000047423.jpg][]

3、代码实例

//基数排序
    public static void radixSort(int arr[]){
        System.out.println("基数排序，arr长度:"+arr.length);
        //1. 得到数组中最大的数的位数
        int max = arr[0]; //假设第一数就是最大数
        for(int i = 1; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
        }
        //得到最大数是几位数
        int maxLength = (max + "").length();
    
        //定义一个二维数组，表示10个桶, 每个桶就是一个一维数组
        //说明
        //1. 二维数组包含10个一维数组
        //2. 为了防止在放入数的时候，数据溢出，则每个一维数组(桶)，大小定为arr.length
        //3. 名明确，基数排序是使用空间换时间的经典算法
        int[][] bucket = new int[10][arr.length];
    
        //为了记录每个桶中，实际存放了多少个数据,我们定义一个一维数组来记录各个桶的每次放入的数据个数
        //可以这里理解
        //比如：bucketElementCounts[0] , 记录的就是  bucket[0] 桶的放入数据个数
        int[] bucketElementCounts = new int[10];
    
        //这里我们使用循环将代码处理
        for(int i = 0 , n = 1; i < maxLength; i++, n *= 10) {
            //(针对每个元素的对应位进行排序处理)， 第一次是个位，第二次是十位，第三次是百位..
            for(int j = 0; j < arr.length; j++) {
                //取出每个元素的对应位的值
                int digitOfElement = arr[j] / n % 10;
                //放入到对应的桶中
                bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
                bucketElementCounts[digitOfElement]++;
            }
            //按照这个桶的顺序(一维数组的下标依次取出数据，放入原来数组)
            int index = 0;
            //遍历每一桶，并将桶中是数据，放入到原数组
            for(int k = 0; k < bucketElementCounts.length; k++) {
                //如果桶中，有数据，我们才放入到原数组
                if(bucketElementCounts[k] != 0) {
                    //循环该桶即第k个桶(即第k个一维数组), 放入
                    for(int l = 0; l < bucketElementCounts[k]; l++) {
                        //取出元素放入到arr
                        arr[index++] = bucket[k][l];
                    }
                }
                //第i+1轮处理后，需要将每个 bucketElementCounts[k] = 0 ！！！！
                bucketElementCounts[k] = 0;
    
            }
        }
    }

4、速度测试

基数排序：12000000数据，1秒，速度感人

![20200525000205375.png][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d1b3J1aV9qYXZh_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200521234628290.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d1b3J1aV9qYXZh,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d1b3J1aV9qYXZh_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200521234918890.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d1b3J1aV9qYXZh,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d1b3J1aV9qYXZh_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200521234945101.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d1b3J1aV9qYXZh,size_16,color_FFFFFF,t_70
[2020052123562124.gif]: https://img-blog.csdnimg.cn/2020052123562124.gif
[20200523091321290.png]: https://img-blog.csdnimg.cn/20200523091321290.png
[20200522000657221.gif]: https://img-blog.csdnimg.cn/20200522000657221.gif
[20200523091411841.png]: https://img-blog.csdnimg.cn/20200523091411841.png
[2020052200155496.gif]: https://img-blog.csdnimg.cn/2020052200155496.gif
[20200523091529335.png]: https://img-blog.csdnimg.cn/20200523091529335.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d1b3J1aV9qYXZh_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200523135326850.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d1b3J1aV9qYXZh,size_16,color_FFFFFF,t_70
[20200523091603561.png]: https://img-blog.csdnimg.cn/20200523091603561.png
[2020052309171161.png]: https://img-blog.csdnimg.cn/2020052309171161.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d1b3J1aV9qYXZh_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200523135234234.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d1b3J1aV9qYXZh,size_16,color_FFFFFF,t_70
[20200523135509144.png]: https://img-blog.csdnimg.cn/20200523135509144.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d1b3J1aV9qYXZh_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20200524095803847.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d1b3J1aV9qYXZh,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d1b3J1aV9qYXZh_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20200524095819888.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d1b3J1aV9qYXZh,size_16,color_FFFFFF,t_70
[20200524104937495.png]: https://img-blog.csdnimg.cn/20200524104937495.png
[20200525000047423.jpg]: https://img-blog.csdnimg.cn/20200525000047423.jpg
[20200525000205375.png]: https://img-blog.csdnimg.cn/20200525000205375.png