选择排序分为简单选择排序和堆排序,下面看看两个算法直接的对比。
1、简单选择排序
简单选择排序法就是通过n-i此关键字间的比较,从n-i-1个记录中选出关键字最小的记录,并且和第i个记录交换。实现如下:
package com.sort.exe;public class SelectSort {public void selectSort(int[] arrs){int i,j,min=0;for( i=0;i<arrs.length;i++){//将第一个下标设为最小值;min=i;for( j=i+1;j<arrs.length;j++){//若第j个下标表示的值比 min表示的值小,就将下标j赋值给min;如此操作直到数组尾部if(arrs[min] > arrs[j])min=j;}//如果min改变了,说明找到了最小值if(min != i){int temp=arrs[i];arrs[i]=arrs[min];arrs[min]=temp;}}}public static void main(String[] args){int[] a={1,12,3,9,5,6,8}; new SelectSort().selectSort(a);for(int i=0;i<a.length;i++){ System.out.print(a[i]+" "); } }}
时间复杂度O(n^2)