选择排序和冒泡排序

本小节主要关于选择排序和冒泡排序的分析

选择排序

基本原理

  • 扫描整个列表或数组(长度为n),找到最小元素,将其和第一个元素进行交换,此时最小元素在有序表中的最终位置上;
  • 从第二元素开始扫描列表,找到最后n-1个元素中的最小元素,再和第二个元素交换位置;
  • 之后,在对该列表做第i遍扫描时(i值为0~n-2),在最后n-i个元素中寻找最小元素,然后将之和 A[i] 交换;
  • 在经过n-1遍后,列表已序。

示例:

1
2
3
4
5
6
7
| 89 45 68 90 29 34 17
17 | 45 68 90 29 34 89
17 29 | 68 90 45 34 89
17 29 34 | 90 45 68 89
17 29 34 45 | 90 68 89
17 29 34 45 68 | 90 89
17 29 34 45 68 89 | 90

扫描这个7个数,找到最小数17,然后将其与第一个元素89进行交换,此时17已序;之后扫描剩下的6个数,找到其中最小数29,将其与45交换;接着依次找到34,45, 68,89,最后数组已序。

代码实现

伪代码:

1
2
3
4
5
6
7
8
9
10
算法 SelectionSort(A[0..n-1])
//该算法用选择排序对给定列表排序
//输入: 一个可排序数组 A[0..n-1]
//输出: 升序排列的数组 A[0..n-1]
for i = 0 to n - 2 do
min = i
for j = i + 1 to n - 1 do
if A[j] < A[min]
min = j
swap A[i] and A[min]

python实现:

1
2
3
4
5
6
7
8
9
10
11
def SelectionSort(A):
#选择排序 对给定列表排序(升序)
#输入: 待排序列表 A[0..n-1] list
#输出: 已排序列表 A[0..n-1] list
lenA = len(A)
for i in range(lenA-1):
minValIndex = i
for j in range(i+1, lenA):
if A[minValIndex] > A[j]:
minValIndex = j
A[i], A[minValIndex] = A[minValIndex], A[i]

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
49
50
51
52
package selection_bubble_sort;
/**
* @author jwj
*
*/
public class SelectionSort {
/**
* @param arr
*/
public static void selectSort(int[] arr) {
int min = -1;
for (int i = 0; i < arr.length-1; i++) {
min = i;
for (int j = i+1; j < arr.length; j++) {
if (arr[j] < arr[min]) {
min = j;
}
}
swap(arr, i, min);
}
}
/**
* @param array
* @param i
* @param j
*/
public static void swap(int[] array, int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
/**
* @param array
*/
public static void print(int[] array) {
for (int i : array) {
System.out.print(i + " ");
}
}
/**
* @param args
*/
public static void main(String[] args) {
int[] a = {4, 2, 3, 6, 1, 7, 9, 8};
selectSort(a);
print(a);
}
}

算法分析

选择排序的输入规模是由数组中元素的个数n决定的。整个算法的基本操作是键值比较$A[j] < A[min]$。比较的执行次数:
$$
C(n) = \sum_{i=0}^{n-2} \sum_{j=i+1}^{n-1} 1 = \sum_{i=0}^{n-2} [(n-1)-(i+1)+1] = \sum_{i=0}^{n-2}(n-1-i) = \frac{(n-1)n}{2}
$$
因此,对于任何输入来说,选择排序都是一个$\Theta(n^2)$的算法,其中数组元素交换的次数仅为$\Theta(n)$,更精确点,是$n-1$次($i$循环每重复依次执行一次交换),这个特性使得选择排序优于许多其他的排序算法。

冒泡排序

基本原理

  • 从第一个元素开始,依次比较相邻元素值,即第一个元素和第二个元素比较,若逆序,则交换位置;
  • 第二个元素和第三个元素比较,若逆序,交换位置;
  • 依次下去,则将最大元素移动到了最右端(“沉到最底部”);
  • 再次从列表头开始依次比较相邻数,重复多次后,第二大的数已移到最右第二个位置上;
  • 多次比较后,列表已序。

示例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
89 <?> 45 68 90 29 34 17
45 89 <?> 68 90 29 34 17
45 68 89 <?> 90 29 34 17
45 68 89 90 <?> 29 34 17
45 68 89 29 90 <?> 34 17
45 68 89 29 34 90 <?> 17
45 68 89 29 34 17 |90
45 <?> 68 89 29 34 17 |90
45 68 <?> 89 29 34 17 |90
45 68 89 <?> 29 34 17 |90
45 68 29 89 <?> 34 17 |90
45 68 29 34 89 <?> 17 |90
45 68 29 34 17 |89 90
etc.

首先,比较数组中的第一、第二个元素值,89和45,逆序,交换位置;之后比较第二、第三个元素值,89和68,逆序,交换位置;接着比较第三、第四个元素值,89和90,已序,不变;然后继续依次比较后续的数值,直到最大数90移动到最右端为止。
再次从数组开头依次进行比较,最后将第二大的数值移动到最右第二个位置上。
之后就继续多次比较,直到所有数据已序。

代码实现

伪代码:

1
2
3
4
5
6
7
8
算法 BubbleSort(A[0..n-1])
//该算法用冒泡排序对数组A[0..n-1]进行排序
//输入:一个可排序数组A[0..n-1]
//输出:非降序排列的数组A[0..n-1]
for i = 0 to n - 2 do
for j = 0 to n - 2 - i do
if A[j+1] < A[j]
swap A[j] and A[j+1]

python实现:

1
2
3
4
5
6
7
8
9
def BubbleSort(A):
#冒泡排序 对给定列表排序(升序)
#输入: 待排序列表 A[0..n-1] list
#输出: 已排序列表 A[0..n-1] list
lenA = len(A)
for i in range(lenA-1):
for j in range(lenA-1-i):
if A[j+1] < A[j]:
A[j], A[j+1] = A[j+1], A[j]

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
49
50
package selection_bubble_sort;
/**
* @author jwj
*
*/
public class BubbleSort {
/**
* @param arr
*/
public static void bubbleSort(int[] arr) {
int len = arr.length;
for (int i = 0; i < len-1; i++) {
for (int j = 0; j < len-1-i; j++) {
if (arr[j+1] < arr[j]) {
swap(arr, j, j+1);
}
}
}
}
/**
* @param array
* @param i
* @param j
*/
public static void swap(int[] array, int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
/**
* @param arr
*/
public static void print(int[] arr) {
for (int i : arr) {
System.out.print(i + " ");
}
}
/**
* @param args
*/
public static void main(String[] args) {
int[] array = {5, 7, 4, 3, 6, 1, 2, 9, 8};
bubbleSort(array);
print(array);
}
}

算法分析

对于所有规模为n的数组来说,该冒泡排序版本的键值比较次数都是相同的,次数:
$$
C(n) = \sum_{i=0}^{n-2} \sum_{j=0}^{n-2-i} 1 = \sum_{i=0}^{n-2} [(n-2-i)-0+1] = \sum_{i=0}^{n-2}(n-1-i) = \frac{(n-1)n}{2}
$$
键交换次数取决于特定的输入。最坏的情况是遇到降序排列的数组,这时,键交换次数和键比较次数是相同的。
$$
S_{worst}(n) = C(n) = \frac{(n-1)n}{2}
$$

------------- 本 文 结 束 感 谢 您 的 阅 读 -------------
坚持原创技术分享,您的支持将鼓励我继续创作!
0%