选择排序
选择排序
1、原理:选择一个值array[0]作为标杆,然后循环找到除这个值外最小的值(查找小于标杆的最小值),交换这两个值,这时最小值就被放到了array[0]上,然后再将array[1]作为标杆,从剩下未排序的值中找到最小值,并交换这两个值。
如图:(数据结构与算法中的图)
2、时间复杂度:O(N^2),与冒泡排序相比减少了数组交换的次数
3、代码
/**
* 选择排序增序
* @param array
*/
public static void selectSort(int [] array){
for(int i=0;i<array.length;i++){
int index = i;
for(int j=i+1;j<array.length;j++){
if(array[j] < array[index]){
index = j;
}
}
if(i != index) swap(i,index,array);
display(array);
System.out.println();
}
}
public static void swap(int a,int b,int array[]){
int temp = array[a];
array[a] = array[b];
array[b] = temp;
}
**************************************************************************************************
package com.jcy;
public class SelectionSort {
public static void main(String[] args) {
int[] a=new int[]{60,80,50,90,60,30};
for (int i = 0; i < a.length-1; i++) {
int minValue=a[i];
int minIndex=i;
for (int j = i; j <= a.length-1; j++) {
if(minValue>a[j]){
minValue=a[j];
minIndex=j;
}
}
int temp=a[i];
//a[i]=a[minIndex];
a[i]=minValue;
a[minIndex]=temp;
}
for (int i = 0; i < a.length; i++) {
System.out.print(a[i]+" ");
}
/*int[] arr={1,3,2,45,65,33,12};
System.out.println("交换之前:");
for(int num:arr){
System.out.print(num+" ");
}
//选择排序的优化
for(int i = 0; i < arr.length - 1; i++) {// 做第i趟排序
int k = i;
for(int j = k + 1; j < arr.length; j++){// 选最小的记录
if(arr[j] < arr[k]){
k = j; //记下目前找到的最小值所在的位置
}
}
//在内层循环结束,也就是找到本轮循环的最小的数以后,再进行交换
if(i != k){ //交换a[i]和a[k]
int temp = arr[i];
arr[i] = arr[k];
arr[k] = temp;
}
}
System.out.println();
System.out.println("交换后:");
for(int num:arr){
System.out.print(num+" ");
}*/
}
}