数据结构-八种排序算法
2021-01-23 14:12
标签：结构 bool 方法 合并 i++ nbsp 最大的 存在 左右 一、常见的排序算法分类 二、各种算法的时间复杂度 三、冒泡排序 冒泡排序（BubbleSorting）的基本思想是：通过对待排序序列从前向后（从下标较小的元素开始）,依次比较相邻元素的值，若发现逆序则交换，使值较大的元素逐渐从前移向后部，就象水底下的气泡一样逐渐向上冒。 小结上面的图解过程: (1)一共进行数组的大小-1次大的循环 (2)每一趟排序的次数在逐渐的减少 (3)如果我们发现在某趟排序中，没有发生一次交换，可以提前结束冒泡排序。这个就是优化 四、选择排序 选择排序（selectsorting）也是一种简单的排序方法。它的基本思想是：第一次从arr[0]~arr[n-1]中选取最小值，与arr[0]交换，第二次从arr[1]~arr[n-1]中选取最小值，与arr[1]交换，第三次从arr[2]~arr[n-1]中选取最小值，与arr[2]交换，...，第i次从arr[i-1]~arr[n-1]中选取最小值，与arr[i-1]交换，...,第n-1次从arr[n-2]~arr[n-1]中选取最小值，与arr[n-2]交换，总共通过n-1次，得到一个按
public class BubbleSort {
public static void main(String[] args) {
int arr[] = {3, 9, -1, 10, 20};
System.out.println("排序前");
System.out.println(Arrays.toString(arr));
bubbleSort(arr);
System.out.println("排序后");
System.out.println(Arrays.toString(arr));
}
public static void bubbleSort(int[] arr) {
// 冒泡排序 的时间复杂度 O(n^2), 自己写出
int temp = 0; // 临时变量
boolean flag = false; // 标识变量，表示是否进行过交换
for (int i = 0; i 1; i++) {
for (int j = 0; j 1 - i; j++) {
// 如果前面的数比后面的数大，则交换
if (arr[j] > arr[j + 1]) {
flag = true;
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
//System.out.println("第" + (i + 1) + "趟排序后的数组");
//System.out.println(Arrays.toString(arr));
if (!flag) { // 在一趟排序中，一次交换都没有发生过
break;
} else {
flag = false; // 重置flag!!!, 进行下次判断
}
}
}
}