• Welcome to the world's largest Chinese hacker forum

    Welcome to the world's largest Chinese hacker forum, our forum registration is open! You can now register for technical communication with us, this is a free and open to the world of the BBS, we founded the purpose for the study of network security, please don't release business of black/grey, or on the BBS posts, to seek help hacker if violations, we will permanently frozen your IP and account, thank you for your cooperation. Hacker attack and defense cracking or network Security

    business please click here: Creation Security  From CNHACKTEAM

Recommended Posts

什么是冒泡排序?

冒泡排序的思想:成对比较相邻元素,当一个元素大于右边相邻元素时,交换位置;当一个元素小于右边的相邻元素时,位置不变。

冒泡排序是一种稳定排序,值相等的元素不打算按原来的顺序排序。因为改进排序算法的每一轮都要遍历所有元素,所以总共遍历了(元素数-1)轮,所以时间复杂度是n的平方阶。

气泡排序的优化

1)如果可以判断出顺序是有序的,并且做了标记,那么剩下的几轮排序就不用进行了,可以提前完成工作。

这只是冒泡排序优化的第一步,我们还可以进一步提高它的性能。

问题的关键在于序列有序区的定义。PHP实现代码如下:

1 ?服务器端编程语言(Professional Hypertext Preprocessor的缩写)

2

3类排序

4 {

5 /**

6 *冒泡排序的第一种写法

7 * @param array $arr

8 * @返回数组

9 */

10公共函数bubbleSort1(array $arr):数组

11 {

12 $ length=count($ arr);

13 for($ I=0;$ I $ length-1;$i ) {

14 for($ j=0;$ j $ length-$ I-1;$j ) {

15 if ($arr[$j] $arr[$j 1]) {

16 $ temp=$ arr[$ j];

17 $ arr[$ j]=$ arr[$ j 1];

18 $ arr[$ j 1]=$ temp;

19 }

20 }

21 }

22 return $ arr

23 }

24

25

26 /**

27 *冒泡排序的第二种写法

28 * @param array $arr

29 * @返回数组

30 */

31公共函数bubbleSort2(array $arr):数组

32 {

33 $ length=count($ arr);

34

35 for($ I=0;$ I $ length-1;$i ) {

36 //排序ID:如果没有交换,则列表已经排序。

37 $ isSorted=false

38 for($ j=0;$ j $ length-$ I-1;$j ) {

39 if ($arr[$j] $arr[$j 1]) {

40 $ temp=$ arr[$ j];

41 $ arr[$ j]=$ arr[$ j 1];

42 $ arr[$ j 1]=$ temp;

43 $ isSorted=true

44 }

45 }

46

47如果(!$isSorted) {

48破;

49 }

50 }

51 return $ arr

52 }

53

54 /**

5 *冒泡排序的第三种写法

56 * @param数组$arr

57 * @返回数组

58 */

59公共函数bubbleSort3(array $arr):数组

60 {

61 $ length=count($ arr);

62

3//记录每轮最后一次交换的下标

64 $ swapOffset=0;

65

66 for($ I=0;$ I $ length-1;$i ) {

67 //排序ID:如果没有交换,列表已经排序。

68 $ isSorted=false

六十九

70 //记录的交换下标后的元素已经排序,不需要再排序。

71 $swapOffset=$swapOffset?美元(长度-$ I-1);

72 for($ j=0;$ j $ swapOffset$j ) {

73 if ($arr[$j] $arr[$j 1]) {

74 $ temp=$ arr[$ j];

75 $ arr[$ j]=$ arr[$ j 1];

76 $ arr[$ j 1]=$ temp;

77

78 //记录每轮最后一次交换的下标

79 $ swapOffset=$ j;

80 $ isSorted=true

81 }

82 }

83

84如果(!$isSorted) {

85破;

86 }

87

88如果(!$swapOffset) {

89破;

90 }

91 }

92 return $ arr

93 }

94 }

95

96 /**

97 *分析:

98 * 1)n个元素,外层成对比较n-1次。

9 * 2)冒泡排序最重要的一个方面是,对于外部循环中的每次迭代,至少会有一次交换。如果没有交换,列表已经排序。

100 *时间复杂度:n-1 n-2.2 ^ 1=n *(n-1)/2=O(N2)

101 */

102

103 $arr=[1,10,2,11,12];

104 $ Sort=new Sort();

105//$ RES=$ sort-冒泡排序1($ arr);

106//$ RES=$ sort-冒泡排序2($ arr);

107 $ RES=$ sort-冒泡排序3($ arr);

108 var _ dump($ RES);

Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now