冒泡排序算法及其优化
本帖最后由 影-死神 于 2018-10-12 22:39 编辑一. 冒泡排序算法基本思路
1. 从第一位开始，每次比较相邻元素，根据大小来交换元素的位置，序号增加一后循环执行此步骤
2. 一轮循环完后，无序区中最大的元素被交换到末尾，作为有序区，最大元素之前作为无序区
3. 将无序区按照上述步骤循环执行，直到无序区的元素个数为1
算法的时间复杂度：
由于需要执行两个for循环，所以时间复杂度为 n**2
Java代码实现:
public class BubbleSort {
private static void sort1(int[] list) {
int temp;
for (int i=0;i<list.length;i++) {
for (int j=0;j<list.length-i-1;j++) {
if (list > list) {
temp = list;
list = list;
list = temp;
}
}
}
}
public static void main(String[] args) {
int[] list = {5, 8, 6, 3, 9, 2, 1, 7};
sort1(list);
for (int i=0;i<list.length;i++) {
System.out.print(list + " ");
}
}
}
二. 优化冒泡算法
发现问题1：如果数列经过几轮排序后，已经是有序的了，此时，循环仍然继续执行
优化思路1：每轮循环执行后，判断数列是否有序，如果有序，直接结束循环
实现方法1：
1. 设置一个标记，每轮执行前标记为有序
2. 如果执行过程中有元素交换，说明数列不是有序的，标记为无序
3. 执行完成后，如果标记为仍为有序，则跳出循环
Java代码实现：
public class BubbleSort {
private static void sort2(int[] list) {
int temp;
for (int i=0;i<list.length;i++) {
boolean isSorted = true;
for (int j=0;j<list.length-i-1;j++) {
if (list > list) {
temp = list;
list = list;
list = temp;
isSorted = false;
}
}
if (isSorted) {
break;
}
}
}
public static void main(String[] args) {
int[] list = {5, 8, 6, 3, 9, 2, 1, 7};
sort2(list);
for (int i=0;i<list.length;i++) {
System.out.print(list + " ");
}
}
}
发现问题2：在执行某轮排序前，无序区中，最后几位已经是无序区中最大值的有序排列
优化思路2：若某轮执行后，发现上述情况，直接将最大值的有序排列并入有序区
优化方法2：
1. 在每轮排序的最后记录最后一次元素交换的位置，将此位置作为边界，之后的为有序区
2. 将每轮排序的判断条件改为：从0到边界
Java代码实现：
public class BubbleSort {
private static void sort3(int[] list) {
int temp;
//最后交换元素的位置
int index = 0;
//无序和有序的边界
int sortBorder = list.length -1;
for (int i=0;i<list.length;i++) {
boolean isSorted = true;
for (int j=0;j<sortBorder;j++) {
if (list > list) {
temp = list;
list = list;
list = temp;
isSorted = false;
//不要在for循环内改变for循环判断的条件，即不能直接使用sortBorder = j
index = j;
}
}
sortBorder = index;
if (isSorted) {
break;
}
}
}
public static void main(String[] args) {
int[] list = {5, 8, 6, 3, 9, 2, 1, 7};
sort3(list);
for (int i=0;i<list.length;i++) {
System.out.print(list + " ");
}
}
}
三. 所有代码
public class BubbleSort {
private static void sort1(int[] list) {
int temp;
for (int i=0;i<list.length;i++) {
for (int j=0;j<list.length-i-1;j++) {
if (list > list) {
temp = list;
list = list;
list = temp;
}
}
}
}
private static void sort2(int[] list) {
int temp;
for (int i=0;i<list.length;i++) {
boolean isSorted = true;
for (int j=0;j<list.length-i-1;j++) {
if (list > list) {
temp = list;
list = list;
list = temp;
isSorted = false;
}
}
if (isSorted) {
break;
}
}
}
private static void sort3(int[] list) {
int temp;
//最后交换元素的位置
int index = 0;
//无序和有序的边界
int sortBorder = list.length -1;
for (int i=0;i<list.length;i++) {
boolean isSorted = true;
for (int j=0;j<sortBorder;j++) {
if (list > list) {
temp = list;
list = list;
list = temp;
isSorted = false;
//不要在for循环内改变for循环判断的条件，即不能直接使用sortBorder = j
index = j;
}
}
sortBorder = index;
if (isSorted) {
break;
}
}
}
public static void main(String[] args) {
int[] list = {5, 8, 6, 3, 9, 2, 1, 7};
//sort1(list);
//sort2(list);
sort3(list);
for (int i=0;i<list.length;i++) {
System.out.print(list + " ");
}
}
}
另外，排序算法在java中可直接使用java.util.Arrays.sort(list);
页:
[1]