|
马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
x
本帖最后由 影-死神 于 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[j] > list[j+1]) {
- temp = list[j];
- list[j] = list[j+1];
- list[j+1] = 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[i] + " ");
- }
- }
- }
复制代码
二. 优化冒泡算法
发现问题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[j] > list[j+1]) {
- temp = list[j];
- list[j] = list[j+1];
- list[j+1] = 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[j] > list[j+1]) {
- temp = list[j];
- list[j] = list[j+1];
- list[j+1] = 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[j] > list[j+1]) {
- temp = list[j];
- list[j] = list[j+1];
- list[j+1] = 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[j] > list[j+1]) {
- temp = list[j];
- list[j] = list[j+1];
- list[j+1] = 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[j] > list[j+1]) {
- temp = list[j];
- list[j] = list[j+1];
- list[j+1] = 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);
|
|