java实现几种常用排序:选择排序
一.选择排序介绍
选择排序,顾名思义就是用逐个选择的方式来进行排序,逐个选择出数组中的最大(或最小)的元素,直到选择至最后一个元素。此时数组完成了排序。
二.选择排序原理分析
三.选择排序代码实现
/**
* @Author {LearnAndGet}
* @Time 2019年1月8日
* @Discription:选择排序
*/
package com.sort;
import java.util.Arrays;
public class ChooseSort {
static int[] array = {3,2,4,1,5,0};
public static void chooseSort(int[] a)
{
int max = 0;
int index = 0;
//外层循环,控制选择的次数,数组长度为6,一共需要选择5次
for(int i=0;i<a.length-1;i++)
{
for(int j=0;j<a.length-i;j++)
{
if(max < a[j])
{
max = a[j];
index = j;
}
}
//每次选择完成后,max中存放的是该轮选出的最大值
//将max指向位置的元素和数组最后一个元素位置互换
int temp = a[a.length-i-1];
a[a.length-i-1] = max;
a[index] = temp;
//清空max和index,便于下次
max=0;
index =0;
System.out.println("经过第"+(i+1)+"轮选择后,数组为"+Arrays.toString(a));
}
}
public static void main(String[] args) {
chooseSort(array);
}
}
四选择排序代码优化
因为选择排序过程中,每一轮选择出最大的元素并将它和数组最后一位互换位置,那么即使在某一轮的选择过程中,未发生位置互换,此时也不能说明数组已经排序完成,假设数组: 2 1 3 4 5 进行升序排列
-
第一轮选择后,数组序列为:2 1 3 4 5
-
第二轮选择后,数组序列为:2 1 3 4 5
-
第三轮选择后,数组序列为:2 1 3 4 5
-
第四轮选择后,数组序列为:1 2 3 4 5
可以看到,即使前三轮的选择过程中,都没有发生数组元素互换,但是此时数组仍未排序完成,直到第4轮选择完成后,数组才完成了排序。因此选择排序并不能优化。
五.选择排序时间复杂度
计算时间复杂度时,默认计算最复杂的情况下需要进行的次数:比如将数组:5 4 2 1 3进行升序排列:
- 第一轮选择排序:一共需要进行4次比较。可以将5和3互换,得到:3 4 2 1 5
- 第二轮选择排序:一共需要进行3次比较。可以将4和1互换,得到:3 1 2 4 5
- 第三轮选择排序:一共需要进行2次比较。可以将3和2互换,得到:2 1 3 4 5
- 第四轮选择排序:一共需要进行1次比较。可以将2和1互换,得到:1 2 3 4 5
可以看到,对数组长度为5进行排序,需要进行比较的次数为4+3+2+1=10次。若数组长度为n,那么进行比较的次数为(n-1)+(n-2)+(n-3)+…1 = n * (n – 1) / 2,当n足够大时,n * (n – 1) / 2约等于n*n。
综上所述,选择排序的时间复杂度为:O(n²)