Java实现冒泡排序与双向冒泡排序算法的代码示例

冒泡排序:
就是按索引逐次比较相邻的两个元素,如果大于/小于(取决于需要升序排还是降序排),则置换,否则不做改变
这样一轮下来,比较了n-1次,n等于元素的个数;n-2, n-3 ... 一直到最后一轮,比较了1次
所以比较次数为递减:从n-1 到 1
那么总的比较次数为:1+2+3+...+(n-1), 以等差公式计算:(1+n-1)/2*(n-1) ==> n/2*(n-1) ==> (n^2-n) * 0.5
用大O表示算法的时间复杂度:O(n^2) , 忽略了系数0.5和常数-n

?

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

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

public class BubbleSort {

public static void main(String[] args) {

int len = 10;

int[] ary = new int[len];

Random random = new Random();

for (int j = 0; j < len; j++) {

ary[j] = random.nextInt(1000);

}

System.out.println("-------排序前------");

for (int j = 0; j < ary.length; j++) {

System.out.print(ary[j] + " ");

}

/*

* 升序, Asc1和Asc2优化了内部循环的比较次数,比较好

* 总的比较次数:

* Asc1、Asc2:(1+n-1)/2*(n-1) ==> n/2*(n-1) ==> n*(n-1)/2 ==>(n^2-n)/2

* Asc: n^2-n

*/

// orderAsc(ary);

// orderAsc2(ary);

orderAsc1(ary);

//降序,只需要把判断大小于 置换一下

}

static void orderAsc(int[] ary) {

int count = 0;//比较次数

int len = ary.length;

for (int j = 0; j < len; j++) {//外层固定循环次数

for (int k = 0; k < len - 1; k++) {//内层固定循环次数

if (ary[k] > ary[k + 1]) {

ary[k] = ary[k + 1] + (ary[k + 1] = ary[k]) * 0;//一步交换

/* 交换两个变量值

* a=a+b

* b=a-b

* a=a-b

*/

}

count++;

}

}

System.out.println("\n-----orderAsc升序排序后------次数:" + count);

for (int j = 0; j < len; j++) {

System.out.print(ary[j] + " ");

}

}

static void orderAsc1(int[] ary) {

int count = 0;//比较次数

int len = ary.length;

for (int j = 0; j < len; j++) {//外层固定循环次数

for (int k = len - 1; k > j; k--) {//内层从多到少递减比较次数

if (ary[k] < ary[k - 1]) {

ary[k] = ary[k - 1] + (ary[k - 1] = ary[k]) * 0;//一步交换

}

count++;

}

}

System.out.println("\n-----orderAsc1升序排序后------次数:" + count);

for (int j = 0; j < len; j++) {

System.out.print(ary[j] + " ");

}

}

static void orderAsc2(int[] ary) {

int count = 0;//比较次数

int len = ary.length;

for (int j = len - 1; j > 0; j--) {//外层固定循环次数

/*

* k < j; 总的比较次数=(n^2-n)/2

*/

for (int k = 0; k < j; k++) {//内层从多到少递减比较次数

if (ary[k] > ary[k + 1]) {

ary[k] = ary[k + 1] + (ary[k + 1] = ary[k]) * 0;//一步交换

}

count++;

}

}

System.out.println("\n-----orderAsc2升序排序后------次数:" + count);

for (int j = 0; j < len; j++) {

System.out.print(ary[j] + " ");

}

}

}

打印

?

1

2

3

4

-------排序前------

898 7 862 286 879 660 433 724 316 737

-----orderAsc1升序排序后------次数:45

7 286 316 433 660 724 737 862 879 898

双向冒泡排序
冒泡排序_鸡尾酒排序、就是双向冒泡排序。
此算法与冒泡排序的不同处在于排序时是以双向在序列中进行排序,外层比较左右边界l<r,
内层一个循环从左向右比,取高值置后;一个循环从右向左,取低值置前;
效率上,O(N^2), 不比普通的冒泡快

?

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

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

public class Bubble_CocktailSort {

public static void main(String[] args) {

int len = 10;

int[] ary = new int[len];

Random random = new Random();

for (int j = 0; j < len; j++) {

ary[j] = random.nextInt(1000);

}

/*

* 交换次数最小也是1次,最大也是(n^2-n)/2次

*/

// ary=new int[]{10,9,8,7,6,5,4,3,2,1}; //测试交换次数

// ary=new int[]{1,2,3,4,5,6,7,8,10,9}; //测试交换次数

System.out.println("-------排序前------");

for (int j = 0; j < ary.length; j++) {

System.out.print(ary[j] + " ");

}

orderAsc1(ary);

// orderAsc2(ary);

//降序,只需要把判断大小于 置换一下

}

static void orderAsc1(int[] ary) {

int compareCount = 0;//比较次数

int changeCount = 0;//交换次数

int len = ary.length;

int left = 0, right = len -1, tl, tr;

while (left < right) {//外层固定循环次数

tl = left + 1;

tr = right - 1;

for (int k = left; k < right; k++) {//内层从多到少递减比较次数, 从左向右

if (ary[k] > ary[k + 1]) {//前大于后, 置换

ary[k] = ary[k + 1] + (ary[k + 1] = ary[k]) * 0;//一步交换

changeCount++;

tr = k; //一轮中最后一比较的时候,将k所在索引赋给tr, tr表示以后比较的结束索引值, 从左向右比后,k表示左边的索引

}

compareCount++;

}

right = tr;

for (int k = right; k > left; k--) {//内层从多到少递减比较次数, 从右向左

if (ary[k] < ary[k - 1]) {//后小于前 置换

ary[k] = ary[k - 1] + (ary[k - 1] = ary[k]) * 0;//一步交换

changeCount++;

tl = k; //一轮中最后一比较的时候,将k所在索引赋给tl, tl表示以后比较的开始索引值, 从向右向左比后,k表示右边的索引

}

compareCount++;

}

left = tl;

}

System.out.println("\n-----orderAsc1升序排序后------比较次数:" + compareCount + ", 交换次数:" + changeCount);

for (int j = 0; j < len; j++) {

System.out.print(ary[j] + " ");

}

}

//跟orderAsc1的思路没有区别

static void orderAsc2(int[] ary) {

int compareCount = 0;//比较次数

int changeCount = 0;//交换次数

int len = ary.length;

int l = 0, r = len -1, tl, tr;

for (; l < r; ) {//外层固定循环次数

tl = l + 1;

tr = r - 1;

/*

* 从左向右比,将大的移到后面

*/

for (int k = l; k < r; k++) {

if (ary[k] > ary[k + 1]) {

int temp = ary[k] + ary[k + 1];

ary[k + 1] = temp - ary[k + 1];

ary[k] = temp - ary[k + 1];

changeCount++;

tr = k;

}

compareCount++;

}

r = tr;

/*

* 从右向左比,将小的移到前面

*/

for (int k = r; k > l; k--) {

if (ary[k] < ary[k - 1]) {

int temp = ary[k] + ary[k - 1];

ary[k - 1] = temp - ary[k - 1];

ary[k] = temp - ary[k - 1];

changeCount++;

tl = k;

}

compareCount++;

}

l = tl;

}

System.out.println("\n-----orderAsc2升序排序后------比较次数:" + compareCount + ", 交换次数:" + changeCount);

for (int j = 0; j < len; j++) {

System.out.print(ary[j] + " ");

}

}

}

打印

?

1

2

3

4

-------排序前------

783 173 53 955 697 839 201 899 680 677

-----orderAsc1升序排序后------比较次数:34, 交换次数:22

53 173 201 677 680 697 783 839 899 955

本文链接:https://my.lmcjl.com/post/12956.html

展开阅读全文

4 评论

留下您的评论.