选择排序法

分析

  • 假设已经给定了一个无序数组，现在需要将其按照一定顺序排好。现在我们使用选择排序法，每次从数组中选出一个最大的元素并将其与数组最后一个元素交换位置，使数组最后一个元素变为最大的。

  • 随着排序的进行，每次需要检查的元素数在逐渐减少，最后一次需要检查的元素都只有一个。既然如此，运行时间怎么还是O(n2)呢？这个问题问得好，这与大 O 表示法中的常数相关。第 4 章将详细解释，这里只简单地说一说。

    你说得没错，并非每次都需要检查n个元素。第一次需要检查n个元素，但随后检查的元素数依次为n - 1, n – 2, …, 2 和 1。平均每次检查的元素数为 1/2 × n，因此运行时间为O(n × 1/2 × n)。但大 O 表示法省略诸如 1/2 这样的常数（有关这方面的完整讨论，请参阅第 4 章），因此简单地写作O(n × n)或O(n2)。

    ​ —- 《算法图解》

代码实现

C 语言实现

因为 C 中对数组的删除比较麻烦，所以我没有按照《算法图解》中的思路每次选择最小的元素，而是选择了最大的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void SelectionSort(int arr[], int length){
  	//C在函数中传数组长度较为麻烦，所以在数组定义出就将长度定义好传了过来

	int i, temp,biggest_index = 0;
	while (length){
         biggest_index = 0;
		for (i = 0; i < length; i++){
			if (arr[biggest_index] < arr[i]){
				biggest_index = i;
			}
		}
		printf("%d\n", arr[biggest_index]);
		temp = arr[biggest_index];
		arr[biggest_index] = arr[length - 1];
		arr[length -1] = temp;
		length --;
	}

}

JAVA 语言实现

JAVA 实现思路同 C。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public int[] SelectionSort(int[] arr) {
		int length = arr.length;
		int biggestIndex;
		int i, temp;

		while(length > 0) {
			biggestIndex = 0;
			for(i = 0; i < length; i ++) {
				if(arr[biggestIndex] < arr[i]) {
					biggestIndex = i;
				}
			}
			temp = arr[biggestIndex];
			arr[biggestIndex] = arr[length - 1];
			arr[length - 1] = temp;
			System.out.println(arr[length - 1]);
			length --;
		}
		return arr;
	}