【算法】————2、选择排序

算法简介

选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

算法描述和实现

n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果。具体算法描述如下：

<1>.初始状态：无序区为R[1..n]，有序区为空；
<2>.第i趟排序(i=1,2,3...n-1)开始时，当前有序区和无序区分别为R[1..i-1]和R(i..n）。该趟排序从当前无序区中-选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R[i+1..n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区；
<3>.n-1趟结束，数组有序化了。

算法实现

C语言：

#include <stdio.h>
#define  N 10

void main(){
	
	int i,j;
	int temp;//排序过程中用于存储临时数据的临时变量
	int a[N]={72,41,2,45,5,83,3,37,38,39};

	for(i=0;i<N;i++){
		for(j=0;j<i;j++){
			if (a[i]<a[j]){
				temp=a[i];
				a[i]=a[j];
				a[j]=temp;
			}
		}
	}
	//循环输出
	for(i=0;i<N;i++){
		printf("%d   ",a[i]);
	}
	printf("\n");
	
}

【算法】————2、选择排序

JavaScript：

function selectionSort(arr) {
    var len = arr.length;
    var minIndex, temp;
    for (var i = 0; i < len - 1; i++) {
        minIndex = i;
        for (var j = i + 1; j < len; j++) {
            if (arr[j] < arr[minIndex]) {     //寻找最小的数
                minIndex = j;                 //将最小数的索引保存
            }
        }
        temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
    return arr;
}
var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(selectionSort(arr));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

JAVA：

public static void selectionSort(int[] arr) {
        int temp, min = 0;
        for (int index = 0; index < arr.length - 1; ++index) {
            min = index;
            // 循环查找最小值
            for (int j = index + 1; j < arr.length; ++j) {
                if (arr[min] > arr[j]) {
                    min = j;
                }
            }
            if (min != index) {
                temp = arr[index];
                arr[index] = arr[min];
                arr[min] = temp;
            }
        }
    }

算法稳定性

很显然，在最小值和另一个值相同的时候我们并不需要交换它们，所以，选择排序是稳定排序。

算法适用场景

选择排序实现也比较简单，并且由于在各种情况下复杂度波动小，因此一般是优于冒泡排序的。在所有的完全交换排序中，选择排序也是比较不错的一种算法。但是，由于固有的O(n^2)复杂度，选择排序在海量数据面前显得力不从心。因此，它适用于简单数据排序。

【算法】————2、选择排序

算法简介

算法描述和实现

算法实现

相关推荐