数据结构之选择排序(简单选择排序)

数据结构之选择排序(简单选择排序)

首页休闲益智我们之间简单排序更新时间:2024-08-03

排序思路:在要排序的一组数中,选出最小的一个数与第一个位置的数交换;然后在剩下的数当中再找最小的与第二个位置的数交换,如此循环。

算法实现:

public static void selectSort(int arr[]){ int temp; for(int i = 0;i < arr.length-1; i ){//有N个元素只需比较N-1次 int min = i;//记住初始位置 for(int j = i 1; j < arr.length; j ){//在 [i 1,arr.length) 中选最小元素,注意这里的i 1和arr.lenth均为元素下标 if(arr[j] < arr[min]) min = j;//min记下目前找到的最元素的下标 if(min != i){ //每趟比较中元素之间只进行一次交换,即元素移动3次。 temp = arr[i]; arr[i] = arr[min]; arr[min] = temp; } } } } public static void main(String[] args) { int array[] = {2,1,1,5,2}; System.out.println("排序之前:"); for(int element : array){ System.out.print(element " "); } selectSort(array); System.out.println("\n排序之后"); for(int element : array){ System.out.print(element " "); } } }

算法分析:

1.在选择排序中,无论元素的初始序列如何,都要进行 (n-1) (n-2) (n-3) .... 1 = n*(n-1)/2 = O(n2)次比较,所以时间复杂度为O(n2) n为元素个数

2.当元素的初始序列为正序时,移动次数为0,而当元素的初始序列为反序时,总的移动次数为:3*总趟数,即Mmax = 3*(n-1)

3.在直接选择排序中只使用了i,j,min这3个辅助元素,与问题规模无关,所以空间复杂度为O(1).

4.当元素序列类似[8,5,8,1]时,在第一趟比较中第一个元素8和最后个元素1进行了交换,元素中的两个8的相对位置发生了改变,所以直接选择排序是一种不稳定排序。

查看全文
大家还看了
也许喜欢
更多游戏

Copyright © 2024 妖气游戏网 www.17u1u.com All Rights Reserved