选择排序:选择排序 (Selection sort) 是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小 (或最大) 的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完
源代码:
- package SelectionSortArithmetic;
- /**
- * 选择排序,求数组的升序排序
- * @author heqingjiang
- *
- */
- public class SelectionSortArithmeticClass {
- private static int[] NeedToSort = new int[1000];
- private static int flag = 0;
- public SelectionSortArithmeticClass(){
- }
- public void insortInto(int number){
- NeedToSort[flag ++] = number;
- }
- public void printNeedToSort(){
- for(int i = 0;i < flag;i ++){
- System.out.print(NeedToSort[i] + " ");
- }
- System.out.println();
- }
- public void selectionSort(){
- for(int i = 0;i < flag;i ++){
- int state = 0;
- int min = 1000000;
- for(int j = i;j < flag;j ++){
- if(min > NeedToSort[j]){
- min = NeedToSort[j];
- state = j;
- }
- }
- if(min < NeedToSort[i]){
- NeedToSort[i] = NeedToSort[i] + NeedToSort[state];
- NeedToSort[state] = NeedToSort[i] - NeedToSort[state];
- NeedToSort[i] = NeedToSort[i] - NeedToSort[state];
- // NeedToSort[state] = NeedToSort[i];
- // NeedToSort[i] = min;
- }
- }
- }
- }
- package ArithmeticBySuperHakceMain;
- import java.util.Scanner;
- import SelectionSortArithmetic.SelectionSortArithmeticClass;
- public class ArithmeticBySuperHakceMain {
- static public void main(String[] args){
- Scanner scanner = new Scanner(System.in);
- SelectionSortArithmeticClass selectionSort = new SelectionSortArithmeticClass();
- System.err.println("Please enter your N");
- int n = scanner.nextInt();
- for(int i = 1;i <= n;i ++){
- int m = scanner.nextInt();
- selectionSort.insortInto(m);
- }
- selectionSort.selectionSort();
- selectionSort.printNeedToSort();
- }
- }
复杂度分析:O(n^2), 主要耗时在双重循环;选择排序比较次数 O(n^2), 交换次数在 O(n),因为交换操作比比较操作 CPU 耗时多的多,所以当 n 较小时,选择排序效率比冒泡排序要好
稳定性分析:因为在一躺比较的过程中,从头到尾部,前面的数字会被后面相同的数字覆盖掉,所以选择排序是不稳定的。
来源: http://www.bubuko.com/infodetail-1965896.html