选择排序

选择排序

选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是：第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法。

参考链接

算法描述

1、首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
2、再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
3、重复第二步，直到所有元素均排序完毕。

动图演示

代码实现

Java

package com.test;

import java.util.Arrays;

public class MySorts {


    public static void main(String[] args) {
        int[] arr = new int[]{23,20,32,5,45,6,8,9,15,1};
        selectionSort(arr);
        System.out.println("排序結果："+ Arrays.toString(arr));
    }

    private static void selectionSort(int[] arr) {
        for(int i=0;i<arr.length-1;i++){
            int minIndex = i;//最小数位置
            for(int j=i;j<arr.length-1;j++){
                if(arr[j+1]<arr[minIndex]){
                    minIndex = j+1;
                }
            }
            //内循环结束说明找到了最小数位置
            if(minIndex != i){
                swapReferences(arr,minIndex,i);
            }
        }
    }

    private static void swapReferences(int[] arr, int minIndex, int i) {
        int tmp = arr[minIndex];
        arr[minIndex] = arr[i];
        arr[i] = tmp;
    }
}

排序結果：[1, 5, 6, 8, 9, 15, 20, 23, 32, 45]

JavaScript

function selectionSort(arr) {
	 for(var i=0;i<arr.length-1;i++){
		var minIndex = i;//最小数位置
		for(var j=i;j<arr.length-1;j++){
			if(arr[j+1]<arr[minIndex]){
				minIndex = j+1;
			}
		}
		//内循环结束说明找到了最小数位置
		if(minIndex != i){
			swapReferences(arr,minIndex,i);
		}
	}
	return arr;
}

function swapReferences(arr,minIndex,i){
	var tmp = arr[minIndex];
	arr[minIndex] = arr[i];
	arr[i] = tmp;
}

var arr = [23,20,32,5,45,6,8,9,15,1];
var arrSorted = selectionSort(arr);
console.log(arrSorted);

(10) [1, 5, 6, 8, 9, 15, 20, 23, 32, 45]