-
Notifications
You must be signed in to change notification settings - Fork 50
/
BubbleSort Template.java
48 lines (43 loc) · 1.49 KB
/
BubbleSort Template.java
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
/*
Given an integer array, sort it in ascending order. Use bubble sort.
Example
Given [3, 2, 1, 4, 5], return [1, 2, 3, 4, 5].
Tags
Sort
*/
/**
* Approach: Bubble Sort
* 两两比较,如果后面的数比前面的数要大,则交换这两个数,否则继续。
* 这样一轮下去,便可以确定 最后一个数(最大的数) 是多少。
* 然后除去最后一个数,再次从头到尾进行 两两比较,第二轮结束,我们便可以确定 第二大的元素。
* 依次循环下去,直到 待比较的只有一个数时,说明排序完成。
* 时间复杂度为:O(n^2) 与数据状况无关
*
* http://bubkoo.com/2014/01/12/sort-algorithm/bubble-sort/
*/
public class Solution {
/*
* @param A: an integer array
* @return:
*/
public void sortIntegers(int[] nums) {
if (nums == null || nums.length < 2) {
return;
}
// 每确定一个最大值 end--
for (int end = nums.length - 1; end > 0; end--) {
// 两两比较 nums[i] 和 nums[i+1] 直到 end 位置
for (int i = 0; i < end; i++) {
// 如果前的数比后面的数大,交换二者位置
if (nums[i] > nums[i + 1]) {
swap(nums, i, i + 1);
}
}
}
}
private void swap(int[] nums, int i, int j) {
nums[i] ^= nums[j];
nums[j] ^= nums[i];
nums[i] ^= nums[j];
}
}