算法基础之选择排序

2019-11-06 07:40:02

字体：大中小

来源：转载

供稿：网友

选择排序的思想：

选出最小的一个和第一个位置交换，选出其次小的和第二个位置交换，以此类推，直到从第N个和第N-1个元素中选出最小的放在第N-1个位置。

伪代码表示

SELECTION-SORT(A)for i = 1 to A.length temp = A[i] j = i ; for j to A.length if key > A[j] temp = A[j] k = j A[k] = A[i] A[i] = temp

java代码表示

public static int[] selectSort(int[] queue) { int minIndex, temp = 0; if (queue == null || queue.length < 2) { return queue; } for (int i = 0; i < queue.length - 1; i++) { // 无序区的最小元素的下标 minIndex = i; for (int j = i + 1; j < queue.length; j++) { //寻找最小元素并保存其下标 if (queue[j] < queue[minIndex]) { minIndex = j; } } if (minIndex != i) { //将找到的最小元素与前面数据交换位置 temp = queue[i]; queue[i] = queue[minIndex]; queue[minIndex] = temp; } }

排序过程大致为：

数组编号	0	1	2	3	4	5
初始状态	5	2	4	6	1	3
第一次排序	1	2	4	6	5	3
第二次排序	1	2	4	6	5	3
第三次排序	1	2	3	6	5	4
第四次排序	1	2	3	4	5	6
第五次排序	1	2	3	4	5	6
第五次排序	1	2	3	4	5	6

插入排序的时空复杂度

1、选择排序的复杂度分析。第一次内循环比较N - 1次，然后是N-2次，N-3次，……，最后一次内循环比较1次。共比较的次数是 (N - 1) + (N - 2) + … + 1，求等差数列和，得 (N - 1 + 1)* N / 2 = N^2 / 2。舍去最高项系数，其时间复杂度为 O(N^2)。 2、虽然选择排序和冒泡排序的时间复杂度一样，但实际上，选择排序进行的交换操作很少，最多会发生 N - 1次交换。而冒泡排序最坏的情况下要发生N^2 /2交换操作。从这个意义上讲，交换排序的性能略优于冒泡排序。 3、选择排序算法的空间复杂度为一个常量，即不随被处理数据量n的大小而改变时，可表示为O(1)；