算法-简单选择排序

发表于 更新于 分类于
学习简单选择排序

简单选择排序属于内部排序中的选择排序的一种。

算法思想

在要排序的一组数中，选出最小（或者最大）的一个数与第1个位置的数交换；然后在剩下的数当中再找最小（或者最大）的与第2个位置的数交换，依次类推，直到第n-1个元素（倒数第二个数）和第n个元素（最后一个数）比较为止。

空间复杂度

最优的情况下（已正序）复杂度为O(0)，最差情况下（全部元素都需要排序），空间复杂度为O(n)

时间复杂度

最优，最差和平均都是O(n^2)

算法实现思想

从牌堆里找出最大的的一张牌，插在左手边。

java实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int[] selectSort(int[] array){
	if (array.length <= 1){
		return array;
	}
	for(int i = 0; i < array.length - 1; i++){
		int temp = 0;
		int index = i;
		for (int j = i + 1; j < array.length; j++){
			if (array[index] > array[j]){
				index = j;
			}
		}
		temp = array[index];
		array[index] = array[i];
		array[i] = temp;
	}
	return array;
}

c实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void selectSort(int array[], int length){
	int i, j, temp;
	if(1 >= length)
		return;
	for(i = 0; i < length; i ++){
		temp = i;
		for(j = i; j < length; j++){
			if(array[temp] < array[j])
				temp = j;
		}
		if(i != temp){
			j = array[temp];
			array[temp] = array[i];
			array[i] = j;
		}
	}
}

python实现

1
2
3
4
5
6
7
8
def selectSort(self, A):
        for i in range(len(A) - 1):
            min_ind = i
            for j in range(i + 1,len(A)):
                if A[min_ind] > A[j]:
                    min_ind = j
            if min_ind != i:
                self.swap(A, min_ind, i)