冒泡排序概览(java+R_优化以及双向冒泡代码)

---

排序

基本概念

定义

排序的含义:

对含有多个记录的文件进行整理，最终使得各个记录按关键字递增( 或递减)的次序排列起来。这个整理的过程称为排序。

排序分类方法

1. 具有相同关键字的记录次序是否变化:

• 稳定
• 不稳定

2. 是否需要内外存交换
   1. 内部排序:排序过程中,不涉及内外存的交换,适用于记录个数不多的小文件
   2. 外部排序:记录的个数太多,不能一次将全部记录放入内存的大文件

内部排序的分类:

• 插入排序
• 选择排序
• 交换排序
• 归并排序

我们讨论的重点是内部排序，而每一种排序方法的实现都依赖于记录在内存的存储结构。

3. 根据复杂度不同分类

4. 文件采用下列三种存储结构

5. 排序算法的衡量标准

6. 排序的目的:为了方便查找
   

冒泡排序

第一轮:

第二轮

第三轮

第四轮

第五轮

算法步骤

1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2. 对每一对相邻元素作同样的工作，从开始第一对到结尾最后一对。这步做完后，最后的格子是最大的数。
3. 针对所有的元素重复以上的步骤，出来最后一个。
4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
   

算法代码

Java版(优化)

package Bioinformatics_code.Sort;

import java.util.Arrays;

public class BubbleSort {
//    public static void swap(int a,int b){
//        int temp = a;
//        a = b;
//        b = temp;
//    }

    public static int[] bubbleSort(int[] sourceArray){
        // 对 array 进行拷贝，不改变参数内容
        int[] array = Arrays.copyOf(sourceArray, sourceArray.length);
        for (int i = 1;i<array.length;i++){
            boolean flag = true;
            for (int j = 0;j<array.length-i;j++){
                if (array[j]>array[j+1]){
                    int temp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = temp;
                    flag = false;
                }
            }
            if (flag) break;//这一行要放在第一个循环里面,第二个循环外面
        }
        return array;
    }

    public static void main(String[] args) throws Exception {
//        int a = 1;
//        int b = 2;
//        swap(a,b);
//        System.out.println(a+"+"+b);
        int[] array = bubbleSort(new int[]{1,2,3,4,7,42,13,4,67});
        System.out.println(Arrays.toString(array));
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

Java版(双向冒泡)

package Bioinformatics_code.Sort;

import java.util.Arrays;
import java.util.Scanner;

public class DoubleBubbleSort {
    public static void main(String[] args) {
        int left;
        int right;
        int n;
        int i = 0;
        Scanner scanner1 = new Scanner(System.in);
        System.out.print("请输入你要排序的数字个数:");
        n = scanner1.nextInt();
        int[] array = new int[n];
        left = 0;
        right = n-1;
        Scanner scanner2 = new Scanner(System.in);
        System.out.println("请输入你需要排序的数组");
        while (scanner2.hasNextLine()){
            if (i == n) break;
            array[i] = scanner2.nextInt();
            i++;

        }
        System.out.println("未排序前:"+Arrays.toString(array));
        while(left < right){
            boolean IsSort_1 = true;
            for (int j = 0;j < right;j++){
                if (array[j] > array[j+1]) {
                    int temp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = temp;
                    IsSort_1 = false;
                }
            }
            if (IsSort_1) {
                break;
            }
            right--;
            boolean IsSort_2 = true;
            for (int j = right;j > left;j--){
                if (array[j] < array[j-1]) {
                    int temp = array[j];
                    array[j] = array[j-1];
                    array[j-1] = temp;
                    IsSort_2 = false;
                }
            }
            if (IsSort_2) {
                break;
            }
            left++;
            System.out.println("排序中:"+ Arrays.toString(array));
        }
        System.out.println("最终结果:"+Arrays.toString(array));
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

R语言版(优化)

#bubblesort
bubbleSort <- function(array) {
  n <- length(array)
  lastchange <- 1
  sortBorder <- n - 1
  for (i in 1:(n - 1)) {
    isSort <- TRUE
    for (j in 1:sortBorder) {
      if (array[j] > array[j + 1]) {
        temp <- array[j]
        array[j] <- array[j + 1]
        array[j + 1] <- temp
        isSort <- FALSE
        lastchange <- j
      }
    }
    sortBorder <- lastchange;
    if (isSort == TRUE) {
      break;
    }
    print(sortBorder)
    print(array)
  }
  return(array)
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

算法分析

• 最好情况下：文件初始为正态，则一趟扫描就可完成排序。关键字的 比较次数为n-1，且没有记录移动，即O(n)。
• 最坏情况下：文件初始是反态，则需进行n-1次排序，每趟排序要n-i(1<=i<=n-1)次比较，每次比较都必须移动记录三次来达到交换记录的目的。

比较次数：Cmax=n(n-1)/2=O(nn)
移动次数：3Cmax=O(nn)

所以：

冒泡排序的最坏时间复杂度为O(n*n)

平均时间复杂度为O(n*n)

冒泡排序是稳定的

算法优化

疑问:

最后一轮排序时，整个序列已经是有序的了，是排序算法仍然兢兢业业的继续执行了后面的排序。
如果能判断出数列有序，并作出标记，那么剩下的几轮排序就不必执行了。

第一轮

第二轮

第三轮

第四轮

第五轮

如果某轮排序中没有发生交换操作，说明整个队伍已经有序。
算法操作：引用一个布尔量isSort判断是否发生了交换：每趟排序前先将它置为ture，排序过程中若有交换，则isSort置为true。当一趟排序结束时，我们再检查isSort，若仍为ture便终止算法。

其实右边已经是有序的了，可是每一轮还白白比较了很多次。

2. 优化方法:

在每趟扫描中，记录最后一次交换发生的位置k，因为该位置以前的相邻记录都已排了序，所以下一趟扫描终止于k，而不必进行到预定的下界i。

#bubblesort
bubbleSort3 <- function(arrayy) {
  n <- length(arrayy)
  lastchange <- 1
  sortBorder <- n - 1
  for (i in 1:(n - 1)) {
    isSort <- TRUE
    for (j in 1:sortBorder) {
      if (arrayy[j] > arrayy[j + 1]) {
        temp <- arrayy[j]
        arrayy[j] <- arrayy[j + 1]
        arrayy[j + 1] <- temp
        isSort <- FALSE
        lastchange <- j
      }
      #print(arrayy)
    }
    sortBorder <- lastchange;
    if (isSort == TRUE) {
      break;
    }
    print(sortBorder)
    print(arrayy)
  }
  return(arrayy)
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

后面会继续更新其他排序,本文中大部分代码是我自己写的,可能有需要改进的地方,
希望能帮到你