Java对数组实现选择排序算法的实例详解

Java对数组实现选择排序算法的实例详解

一. 算法描述

    选择排序：比如在一个长度为N的无序数组中，在第一趟遍历N个数据，找出其中最小的数值与第一个元素交换，第二趟遍历剩下的N-1个数据，找出其中最小的数值与第二个元素交换......第N-1趟遍历剩下的2个数据，找出其中最小的数值与第N-1个元素交换，至此选择排序完成。

以下面5个无序的数据为例：

56 12 80 91 20（文中仅细化了第一趟的选择过程）

第1趟：12 56 80 91 20

第2趟：12 20 80 91 56

第3趟：12 20 56 91 80

第4趟：12 20 56 80 91

二. 算法分析

平均时间复杂度：O(n2)

空间复杂度：O(1)  (用于交换和记录索引)

稳定性：不稳定 （比如序列【5， 5， 3】第一趟就将第一个[5]与[3]交换，导致第一个5挪动到第二个5后面）

三. 算法实现

public class SelectionSort {

public static void main(String[] args) {

int len = 15;

int[] ary = new int[len];

Random random = new Random();

for (int j = 0; j < len; j++) {

ary[j] = random.nextInt(1000);

}

System.out.println("-------排序前------");

// ary=new int[]{10,9,8,7,6,5,4,3,2,1}; //测试交换次数

// ary=new int[]{1,2,3,4,5,6,7,8,10,9}; //测试交换次数

for (int j = 0; j < ary.length; j++) {

System.out.print(ary[j] + " ");

}

selectDesc(ary);

selectAsc(ary);

}

/*

* 选择排序：降序

*/

static void selectDesc(int[] ary) {

int compareCount = 0;//比较次数

int changeCount = 0;//交换次数

int len = ary.length;

int maxValueIndex = -1; //记录一轮比较下来的最小值索引

for (int i = 0; i < len - 1; i++) {

maxValueIndex = i; //从0开始

for (int j = i + 1; j < len; j++) {

if (ary[maxValueIndex] < ary[j]) {

maxValueIndex = j; //记录较大的索引

compareCount++;

}

}

// System.out.println("minValueIndex==" + maxValueIndex);

if (maxValueIndex != i) {//如果跟左边的记录索引不同，则交换

ary[i] = ary[maxValueIndex] + (ary[maxValueIndex] = ary[i]) * 0;//一步交换

changeCount++;

}

}

System.out.println("\n-------降序排序后------比较次数：" + compareCount + "，交换次数" + changeCount);

for (int j = 0; j < ary.length; j++) {

System.out.print(ary[j] + " ");

}

}

/*

* 选择排序：升序

*/

static void selectAsc(int[] ary) {

int compareCount = 0, changeCount = 0;

int len = ary.length;

int minIndex = -1;

for (int i = 0; i < len - 1; i++) {

minIndex = i;

for (int j = i + 1; j < len; j++) {

if (ary[minIndex] > ary[j]) {

minIndex = j; //记录较小的索引

compareCount++;

}

}

if (minIndex != i) {//如果跟左边的记录索引不同，则交换

ary[i] = ary[minIndex] + (ary[minIndex] = ary[i]) * 0;

changeCount++;

}

}

System.out.println("\n-------升序排序后------比较次数：" + compareCount + "，交换次数" + changeCount);

for (int j = 0; j < ary.length; j++) {

System.out.print(ary[j] + " ");

}

}

}

打印

-------排序前------

125 350 648 789 319 699 855 755 552 489 187 916 596 731 852

-------降序排序后------比较次数：26，交换次数13

916 855 852 789 755 731 699 648 596 552 489 350 319 187 125

-------升序排序后------比较次数：56，交换次数7

125 187 319 350 489 552 596 648 699 731 755 789 852 855 916

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。