(三) 数据结构 - 冒泡排序
冒泡排序
冒泡排序是一种简单的排序算法。该排序算法是基于比较的算法，其中比较每对相邻元素，如果元素不按顺序交换。该算法不适用于大型数据集，因为其平均和最坏情况下的复杂度为Ο(n^2)，其中n是项数。
核心思想
我们以未排序的数组为例。冒泡排序需要Ο(n^2)的时间，因此我们将其简短而精确。
冒泡排序从头两个元素开始，然后比较它们以检查哪个更大。
在这种情况下，值33大于14，因此它已经在排序的位置。接下来，我们将33与27进行比较。
我们发现27小于33，并且必须交换这两个值。
新数组应如下所示：
我们知道10比35小。因此，需要进行交换
我们交换这些值。我们发现已经到达数组的末尾。一次迭代后，数组应如下所示：
确切地说，我们现在显示每次迭代后数组的外观。在第二次迭代后，它应该看起来像这样
请注意，每次迭代后，至少有一个值在末尾移动。
而且，当不需要交换时，冒泡排序会得知数组已完全排序。
代码开发
实现思路
Step 1-每次冒泡排序操作都会将相邻的两个元素进行比较
Step 2-看是否满足大小关系要求，如果不满足，就交换这两个相邻元素的次序
Step 3-一次冒泡至少让一个元素移动到它应该排列的位置
Step 4-重复N次，就完成了冒泡排序
伪代码
import com.paal.demo.Sort;
import com.paal.demo.utils.SortTestHelper;
/**
* <p/>
* <li>title: 基础排序-冒泡排序</li>
* <li>@author: li.pan</li>
* <li>Date: 2019/11/5 12:58 下午</li>
* <li>Version: V1.0</li>
* <li>Description: </li>
*/
public class BubbleSort implements Sort {
public void sort(Integer[] arr) {
int n = arr.length;
for (int i = 0; i < n; i++) {
//此处你可能会疑问的j<n-i-1，因为冒泡是把每轮循环中较大的数飘到后面，
for (int j = 0; j < n - i - 1; j++) {
// 数组下标又是从0开始的，i下标后面已经排序的个数就得多减1，总结就是i增多少，j的循环位置减多少
if (arr[j] > (arr[j + 1])) { //即这两个相邻的数是逆序的，交换
SortTestHelper.swap(arr, j + 1, j);
}
}
}
}
}
/**
* 冒泡排序
*/
@Test
public void bubbleSortTest() {
Integer[] integers0 = SortTestHelper.generateRandomArray(100, 0, 1000000);
Integer[] integers1 = SortTestHelper.generateRandomArray(10000, 0, 1000000);
Integer[] integers2 = SortTestHelper.generateRandomArray(100000, 0, 1000000);
System.out.println("------------------------------随机数组--------------------------------");
System.out.println("选择排序测试1数据量为100耗" + SortTestHelper.testSort(integers0, new SelectionSort()));
System.out.println("选择排序测试2数据量为10000" + SortTestHelper.testSort(integers1, new SelectionSort()));
System.out.println("选择排序测试3数据量为100000" + SortTestHelper.testSort(integers2, new SelectionSort()));
System.out.println("插入排序测试1数据量为100" + SortTestHelper.testSort(integers0, new InsertionSort()));
System.out.println("插入排序测试2数据量为10000" + SortTestHelper.testSort(integers1, new InsertionSort()));
System.out.println("插入排序测试3数据量为100000" + SortTestHelper.testSort(integers2, new InsertionSort()));
System.out.println("冒泡排序测试1数据量为100" + SortTestHelper.testSort(integers0, new BubbleSort()));
System.out.println("冒泡排序测试2数据量为10000" + SortTestHelper.testSort(integers1, new BubbleSort()));
System.out.println("冒泡排序测试3数据量为100000" + SortTestHelper.testSort(integers2, new BubbleSort()));
}
执行结果
------------------------------随机数组--------------------------------
选择排序测试1数据量为100耗排序时长为: 0.0s
选择排序测试2数据量为10000排序时长为: 0.168s
选择排序测试3数据量为100000排序时长为: 9.875s
插入排序测试1数据量为100排序时长为: 0.0s
插入排序测试2数据量为10000排序时长为: 0.0s
插入排序测试3数据量为100000排序时长为: 0.005s
冒泡排序测试1数据量为100排序时长为: 0.0s
冒泡排序测试2数据量为10000排序时长为: 0.055s
冒泡排序测试3数据量为100000排序时长为: 11.052s
正文到此结束
