EEPW论坛

今天扣丁学堂给大家详细介绍一下关于很多人对于数据结构的应用，常见的数据结构和算法没有全面的认知和理解，首先经典的排序算法有八种，下面我们一起来看一下关于扣丁学堂Java培训数据结构与算法之基本排序详解吧。

冒泡排序

选择排序

插入排序

归并排序

希尔排序

快速排序

堆排序

基数排序

其中冒泡排序、选择排序、插入排序称为三大基本排序。虽然这三大基本排序算法时间复杂度都是O(n2)，但是其实细细讨论之下，还是有各自的特点的。

冒泡排序

基本思路：

假设我们需要进行升序排列

进行N轮的比较，每一轮将相邻的两个元素依次比较，根据大小进行交换，每轮比较结束后，将最大的元素依次‘冒’到数组的末尾，经过几轮比较后，数组就会呈现有序的状态。

图解：

假设对5个元素进行冒牌排序，先准备5个随机元素：

1）第一轮中，将第一个元素（10）与相邻的元素（20）进行比较，因为20比10大所以无需进行交换。再将第二个元素（20）与相邻的元素（5）比较，因为20比5大，所以需要往上‘冒’，因此需要与5进行交换

接着将第三个元素（20）与相邻的元素进行比较，这样经过与14和1的比较之后，因为20最大，所以被冒到了最后的位置

2）后面每轮都按照此方法进行比较，但是需要注意，此后的每一轮都需要比前一轮少比较一次，因为前面已经确定了最大元素的位置，为了提高性能，可以不用再和后面确定了位置的元素进行比较。

3）由此可以确定，当数组的长度为N时，需要比较的轮数为N-1轮。每轮中从第一个元素开始相邻元素两两进行比较，第一轮需要比较N-1次，第2轮需要比较N-2次，依次类推，实现整体排序

冒泡排序法的代码实现

首先通过一个外层的for循环确定比较的轮数，循环元素数量-1轮。

内部通过一个for循环实现每轮的两两元素比较的效果。每轮需要比较的次数都会比上一轮减少一次，通过j

元素两两比较通过array[j]>array[j+1]来实现。

冒泡排序法优化

以上的冒泡排序法还有优化的空间。因为如果一个数组已经是完全有序的情况下，冒泡排序法仍然会进行逐轮的比较，这无疑是浪费性能的行为。因此我们可以确定，当冒泡的比较中，有一轮如果没有发生交换，则可以确定当前数组已经完全有序，后面的轮数完全不必在进行。故做以下的调整：

通过定义一个标识符isSort，如果有一轮没有发生任何交换，则isSort就会为true，下次直接break，后面的轮数就不用再进行比较了。

选择排序

基本思路：

选择排序和冒泡排序不同，选择排序会通过一轮比较，选出最小的那个元素的下标，然后和第一个元素进行交换，这样第一个元素的位置就可以确定了。

第二轮如法炮制，从第二个元素开始依次比较，选出最小的元素的下标，和第二个元素交换位置，这样第二小的元素位置就确定了。

后面依次类推，直到整个数组呈现有序状态。

选择排序法的代码实现

选择排序比较的轮数和冒泡排序比较的轮数是一样的

K表示当前最小值的下标，当前是第几轮，k就先代表第几个元素的下标，然后依次和后面的元素进行比较，如果发现比k位置元素小的元素时，改变k的下标，这样一轮过后k代表的位置就是本轮最小的元素，和i进行交换即可

如果一轮过后k==i，则说明i本来就是最小的元素，则无需交换提高性能。

插入排序

插入排序的思路

基本思路

假设一个数组已经基本有序，则这个时候插入排序就是一个不错的选择。插入排序是先保证左边元素是基本有序的，然后将后面的元素依次和左边元素进行比较，如果比较到一个比自己小的元素时就可以停止比较了，因为左边已经呈现有序状态，找到比自己小的元素时，就不用再往后比较了。

插入排序的代码实现

插入排序的轮数和冒泡排序一样，但是i从1开始，因为我们假设第一个元素已经是呈现有序状态了。

内部循环依次从当前位置开始，和前面元素进行比较，如果找到了比自己小的元素，则停止比较，直接退出本轮比较，进行下一轮比较

最后总结虽然三种排序法的时间复杂度都是O(N2)，但是不同的场景还是会有不同的性能差异。冒泡排序法是性能最差的算法，正式运用中，基本不会用冒泡排序法进行排序。选择排序将交换次数降到最低，但是比较次数仍然很大。当数据量小，并且交换耗时相对于比较耗时更多的情况下，选择排序是个不错的选择。基本有序的情况下，插入排序是最好的选择，但是如果数据基本逆序的情况下，插入排序的性能和冒泡排序就基本一样了。从平均情况下来看，插入排序性能会比选择排序略好一些。

以上就是扣丁学堂Java在线学习小编给大家分享的Java使用默认浏览器打开指定URL的方法(两种方法)，希望对小伙伴们有所帮助，想要了解更多内容的小伙伴可以登录扣丁学堂官网查询。扣丁学堂是专业的Java培训机构，不仅有专业的老师和与时俱进的课程体系，还有大量的Java视频教程供学员挂看学习哦。扣丁学堂java技术交流群：487098661。微信号：codingbb