Java教程

【数据结构与算法】之交换排序java代码实现

本文主要是介绍【数据结构与算法】之交换排序java代码实现,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

前言

        今天开始给大家分享数据结构与算法当中十分重要的排序算法,所谓排序,就是将数据元素按指定关键字大小进行升序降序等重新排序,排序是线性表,二叉树等数据结构的一种基本运算,排序它可以提高我们查找的效率,那么接下来就让我们一起进入排序的世界吧


目录

一、交换排序的思想

二、冒泡排序

        2.1冒泡排序算法描述

        2.2冒泡排序java代码实现

        2.3冒泡排序算法分析

三、快速排序

        3.1快速排序算法描述

        3.2快速排序代码实现

        3.3快速排序算法总结


一、交换排序的思想

GIF小表情包 [为小表情控收集的可爱迷你动态表情包]

        交换排序的思想:比较两个元素的大小,如果反序,即未按照一定规则进行排序,例如升序,则交换。交换排序有两种算法,一是冒泡排序,二是快速排序。

二、冒泡排序

        2.1冒泡排序算法描述

        冒泡排序即比较相邻两元素大小,如果反序,则交换,若按照升序排序,则每次应将数据元素序列中最大元素交换到最后位置,即两两相比较,大的元素向后移动,直至将最大的交换到最后的位置,就像水中气泡一样冒出去,得名冒泡排序。

        例如,我要将6,5,4,3,2,1这样一组数据按照升序排序,那么第一趟应该是5,4,3,2,1,6,即6和每一个元素比较最终到了最后位置,即符合我们的要求,第二趟就是4,3,2,1,5,6,直到排成了1,2,3,4,5,6则排序结束。

GIF小表情包 [为小表情控收集的可爱迷你动态表情包]

        2.2冒泡排序java代码实现

        以上述例子为例,我们建一个BubbleSort类,类中定义两个方法,一个swap方法,用于交换数据,一个bubblesort方法用于实现冒泡排序算法。

        代码实例

        对于代码中的解释我放在注释当中,大家可以自行查看,有不明白的欢迎评论区讨论

        Bubble类

package com.Sorting.bubblesort;

/**
 * @author wang
 * @packageName com.Sorting.bubblesort
 * @className Bubble
 * @date 2021/11/11 23:24
 */
public class Bubble {
    //冒泡排序,升序
    public static void bubbleSort(int[] arr) {
        //定义一个变量,判断是否有交换
        boolean exchange = true;

        //双层for循环,外层循环控制是否进行下一次冒泡
        for(int i = 1;i<arr.length && exchange;i++) {
            //入果下层循环没有进入if语句,说明没有交换存在,外层循环结束
            exchange = false;
            for(int j = 0;j<arr.length-i;j++) {
                //内层循环比较相邻两个元素大小,如果前一个元素大于后一个元素,则调用swap方法两数交换
                if(arr[j]>arr[j+1]) {
                    swap(arr,j,j+1);
                    //发生交换
                    exchange = true;
                }
            }
        }
    }
    public static void swap(int[] arr,int i,int j) {
        //交换两个数据
        int temp = arr[j];
        arr[j] = arr[i];
        arr[i] = temp;
    }
}

测试类: 

package com.Sorting.bubblesort;

import java.util.Arrays;

/**
 * @author wang
 * @packageName com.Sorting.bubblesort
 * @className BubbleTest
 * @date 2021/11/11 23:39
 */
public class BubbleTest {
    public static void main(String[] args) {
        int [] arr = {6,2,4,3,5,1};
        Bubble.bubbleSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}
/*
输出结果
[1, 2, 3, 4, 5, 6]
 */

        2.3冒泡排序算法分析

GIF小表情包 [为小表情控收集的可爱迷你动态表情包]

 GIF小表情包 [为小表情控收集的可爱迷你动态表情包]

        冒泡排序我们分析他的两种情况:

1.最好情况:数据序列排序,那么只进行一次冒泡,比较n此,时间复杂度为O(n).

2.最坏情况:数据反序排列或者随机排列,那么数据就会进行n-1此冒泡, 因为我们最后一趟冒泡n已经排好,所以我们要进行n-1此冒泡,大家可以自行画图理解。比较次数和移动次数都是(n-1)+(n-2) +.....+2+1;最后可以得到其时间复杂度为O(n2)。那么我们的冒泡排序即在越接近有序的情况下,他的算法的时间效率就越高,反之,如果我的数据有成千上万个,且刚好反序,那么我的效率就十分的低了。因此,冒泡排序虽然稳定,但是也难免会造成效率低下。那么接下来我们就可以学习另一种高级一点的排序方式,快速排序。

三、快速排序

        3.1快速排序算法描述

        在数据序列中选择一个元素作为基准值,每趟从数据序列的两端开始交替进行,将小于基准值的元素交换到序列前端,将大于基准值的元素交换到序列后端,介于两者之间的位置则成为基准位置的最终位置,同时,序列将会被划分成为两个子序列,分别对两个子序列进行快速排序,直到子序列长度为1,则完成排序。

        那么我们通过图来理解

首先我们有一组数组int[] arr = {6,1,2,3,8,9,4,5,7};

         目前数组这样排序,我们可以给定一个low指针,来指向数组中第一个元素,high指针来指向最后一个元素,首先我们先比较high的值7与基准元素的值6,发现7大于6,就将high的位置向左移动,直到high的值小于或等于基准元素的值,比如5时,我们交换5与6,使得high位置的值为6,low位置的值为5;接下来从low位置向右开始找,找到元素比基准元素值小,例如5,1,2,3,均比基准元素6小,那么我们就将low的值移动到直到8,这时,8>6,那么应该将8与6的位置交换,因为,大的元素始终在右边,小的元素始终在右边(升序排序),接下来我们就会得到这样一个结果

         这时我们的low与high还是不相等,说明排序还没有完成,继续将high的值与左边的值相比较,一样的道理,high值与基准元素比较,如果大于6,high的值向左进,low的值与其比较,如果小于,则向右进,排序完结果如下,

 

                 当我们在继续进行下一次排序循环时,结果如下:

        这时我们的 low值与high值已经相等,我们就退出循环,这时第一趟排序就已经完成,我们发现其实此时的数组并未按照升序进行排序,此时就需要调用递归对基准元素左边数组,右边数组分别进行以上排序,递归进行排序就可以了。那么java版代码实现如下

        3.2快速排序代码实现

package com.Sorting.quickSort;



/**
 * @author wang
 * @packageName com.Sorting.quickSort
 * @className QSort
 * @date 2021/11/16 22:57
 */
public class QSort {
    public static void main(String[] args) {
        int[] arr = {6,1,2,3,8,9,4,5,7};
        QuickSort(arr,0,arr.length-1);
        for(int i : arr) {
            System.out.print(i + " ");
        }
        
        //输出结果:1 2 3 4 5 6 7 8 9 

    }

    public static void QuickSort(int[] arr,int low,int high) {
        int pivot;
        if(low<high) {
            pivot = partition(arr,low,high);

            //对基准值左边数组进行排序,基准值减一即从索引0处的值到基准值前一个元素参与下一次排序
            QuickSort(arr,low,pivot-1);
            //同理,对基准值右边数组进行递归排序,从基准值后一个元素到最后一个元素的值进行排序
            QuickSort(arr,pivot+1,high);
        }
    }

    public static int partition(int[] arr,int low,int high) {

        //记录一个关键值,例如数组中第一个元素
        int pivotKey = arr[low];

        //当low的位置小于high的位置时,循环结束
        while(low<high) {
            //当high处的值大于基准位置的值时,进入循环,当其值小于基准值时,退出循环
            while(low<high && arr[high] >= pivotKey) {
                high--;
            }
            //退出循环后,应该将此时的high的值和low处的值交换,也就是将high处的值与基准值进行交换
            swap(arr,low,high);

            //与上面同理
            while(low<high && arr[low] <= pivotKey) {
                low++;
            }
            swap(arr,low,high);
        }
        //返回关键字所在位置,这里返回low,high皆可,因为当low==high循环结束
        return low;
    }

    public static void swap(int[] arr,int i,int j) {
        //交换两个数据
        int temp = arr[j];
        arr[j] = arr[i];
        arr[i] = temp;
    }
}

        3.3快速排序算法总结

        快速排序算法因为关键字的比较和交换是跳跃进行的,因此,快速排序算法是不稳定的。当待排序序列元素较多且数据元素随机排列时,快速排序是相当快速的;当待排序序列元素较多且基准值选择不合适时,快速排序则较慢。

        最后,欢迎大家在评论区提出一些建议,文中可能有不少表述较为不清晰的地方,欢迎大家结合图以及代码来阅读,最后,恳求大家路过时给个小小的点赞,下期还会继续为大家带来一些java小知识哦,再见!

GIF小表情包 [为小表情控收集的可爱迷你动态表情包]

 GIF小表情包 [为小表情控收集的可爱迷你动态表情包]

 

这篇关于【数据结构与算法】之交换排序java代码实现的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!