排序Java
文章发布较早,内容可能过时,阅读注意甄别。
# 快速排序
# 思想
快速排序将一个数组分成两个数组,再对两个数组独立排序,是个递归算法。 首先随机选出一个切分元素temp(一般为这个数组的第一个元素),将小于temp的数放在temp的左边,将大于temp的数放在temp的右边。 快排和堆排序很像,他们都是将一个数组分成两个子数组,都属于递归算法。但是不同之处在于:快排空间复杂度为o(1),而堆排为o(n), 快排是原地排序,只需要一个很小的辅助栈,时间复杂度为NlogN。
# 代码实现
public class Quick { public static void sort(int[] a,int lo,int hi) { if(hi<=lo) return; //切分 int j = partition(a,lo,hi); sort(a,lo,j-1); sort(a,j+1,hi); } //a[j]就是那个切分元素,从数组的左端开始向右扫描直到找到一个大于等于它的元素 //再从数组的右端开始向左扫描直到找到一个小于等于它的元素,将这两个元素交换位置。 public static int partition(int[] a,int lo,int hi) { //左右扫描数组 int j = lo; int i = hi+1;; int v = a[lo]; while(true) { while(v>=a[++j]){ if(j==hi) break; //j++; } while(v<=a[--i]) { if(i==lo) break; //i--; } if(j>=i) { break; } int t = a[i]; a[i] = a[j]; a[j] = t; } a[lo] = a[j]; a[j] = v; return j; } public static void main(String[] args) { int[] a = {49,78,23,34,67,45,73,90,120,12,20,9,5}; int lo = 0; int hi = a.length-1; sort(a,lo,hi); for(int i=0;i<a.length;i++) { System.out.print(a[i]+" "); } } }
已复制!
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
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
public class PuickSort { //arr 需要排序的数组 //low 开始时最左边的索引 = 0 //high 开始时最右边的索引 = arr.length - 1 public static void quickSort(int[] arr, int low, int high) { int i, j, temp, z,y; if (low > high) { return; } i = low;//左边哨兵的索引 j = high;//右边哨兵的索引 //temp就是基准位 temp = arr[low];//以最左边为 基准位 while (i < j) { //先看右边,依次往左递减 //先从右往左找一个小于 基准位的数 //当右边的哨兵位置所在的数 > 基准位的数 时 //继续从右往左找(同时 j 索引 - 1) //找到后会跳出 while循环 while (temp <= arr[j] && i < j) { j--; } //再看左边,依次往右递增 //步骤和上面类似 while (temp >= arr[i] && i < j) { i++; } //如果满足条件则交换 if (i < j) { //z、y 都是临时参数,用于存放 左右哨兵 所在位置的数据 z = arr[i]; y = arr[j]; //左右哨兵 交换数据(互相持有对方的数据) arr[i] = y; arr[j] = z; } } //这时 跳出了 “while (i < j) {}”循环 //说明 i = j 左右在同一位置 //最后将基准为与i和j相等位置的数字交换 arr[low] = arr[i];//或 arr[ low] =arr[j]; arr[i] = temp;//或 arr[ j] =temp; //i = j //这时 左半数组<(i或j所在索引的数) < 右半数组 //也就是说(i或j所在索引的数) 已经确定排序位置,所以就不用再排序了, //只要用相同的方法 分别处理 左右数组就可以了 //递归调用左半数组 quickSort(arr, low, j - 1); //递归调用右半数组 quickSort(arr, j + 1, high); } public static void main(String[] args) { int[] arr = {10, 7, 2, 4, 7, 62, 3, 4, 2, 1, 8, 9, 19}; quickSort(arr, 0, arr.length - 1); for (int i = 0; i < arr.length; i++) { System.out.println(arr[i]); } } }
已复制!
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
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
# 冒泡排序
# 思想
从序列的第一个元素开始,对相邻的两个元素进行比较,如果它们的顺序错误就交换它们的位置,即将较大的元素往后移动,直到遍历到序列的最后一个元素。 对剩下的元素重复上述步骤,直到整个序列都已经有序。
# 代码实现
public class BubbleSort { public static void bubbleSort(int[] arr) { int n = arr.length; for (int i = 0; i < n; i++) { // 每轮遍历将最大的数移到末尾 for (int j = 0; j < n - i - 1; j++) { if (arr[j] > arr[j+1]) { int temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; } } } } public static void main(String[] args) { int[] arr = {64, 34, 25, 12, 22, 11, 90}; bubbleSort(arr); System.out.println(Arrays.toString(arr)); // [11, 12, 22, 25, 34, 64, 90] } }
已复制!
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 堆排序
# 思想
堆排序(Heap Sort)是一种基于堆数据结构的排序算法,其核心思想是将待排序的序列构建成一个最大堆(或最小堆),然后将堆顶元素与最后一个元素交换,再将剩余元素重新调整为最大堆(或最小堆),重复以上步骤直到所有元素都有序。
# 代码实现
public static void heapSort(int[] arr) { int n = arr.length; // 构建最大堆 for (int i = n / 2 - 1; i >= 0; i--) { heapify(arr, n, i); } // 排序 for (int i = n - 1; i > 0; i--) { // 将堆顶元素与最后一个元素交换 int tmp = arr[0]; arr[0] = arr[i]; arr[i] = tmp; // 调整剩余元素为最大堆 heapify(arr, i, 0); } } public static void heapify(int[] arr, int n, int i) { // 将以 i 为根节点的子树调整为最大堆 int largest = i; // 初始化最大元素为根节点 int left = 2 * i + 1; // 左子节点的索引 int right = 2 * i + 2; // 右子节点的索引 // 找出左右子节点中的最大值 if (left < n && arr[left] > arr[largest]) { largest = left; } if (right < n && arr[right] > arr[largest]) { largest = right; } // 如果最大值不是根节点,则交换根节点和最大值,并递归调整子树 if (largest != i) { int tmp = arr[i]; arr[i] = arr[largest]; arr[largest] = tmp; heapify(arr, n, largest); } }
已复制!
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
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


