【Java】选择排序

选择排序

思路

  1. <font face=黑体>在需要排序的数据域中，先把最小的拿出来，放在合适的位置；

  2. <font face=黑体>剩下的，再把最小的拿出来，放在合适的位置；

  3. <font face=黑体>剩下的，再把最小的拿出来，放在合适的位置；

  4. <font face=黑体>...

<font face=黑体 color = red>每次选择还没有处理的元素里最小的元素。

注意

<font face=黑体>选择排序是可以原地排序的，即不需要开辟额外的空间。

代码实现

public class SelectionSort {
private SelectionSort() {
}
/**
* 选择排序1（从头到尾遍历）
* @param arr
* @param <E>
*/
public static <E extends Comparable<E>> void sort(E[] arr) {
for (int i = 0; i < arr.length; i++) {
// 选择 arr[i...n) 中的最小值的索引
int minIndex = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[j].compareTo(arr[minIndex]) < 0) {
minIndex = j;
}
}
swap(arr, i, minIndex);
}
}
/**
* 选择排序2（从尾到头遍历）
* @param arr
* @param <E>
*/
public static <E extends Comparable<E>> void sort1(E[] arr) {
for (int i = arr.length - 1; i >= 0 ; i--) {
int maxIndex = i;
for (int j = i; j >= 0 ; j--) {
if (arr[j].compareTo(arr[maxIndex]) > 0) {
swap(arr, i, maxIndex);
}
}
}
}
// 交换
private static <E> void swap(E[] arr, int i, int j) {
E temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public static void main(String[] args) {
int[] dataSize = {10000, 100000};
for (int n : dataSize) {
Integer[] arr = ArrayGenerator.generateRandomArray(n, n);
SortingHelper.sortTest("SelectionSort", arr);
}
}
}

运行结果

【Java】选择排序
_
<font face=黑体>以下是上述代码中用到的两个类:

ArrayGenerator

<font face=黑体>作用主要是生成随机的数组，具体如下所示：

public class ArrayGenerator {
private ArrayGenerator() {
}
/**
* 生成长度为 n 的有序数组
*
* @param n
* @return
*/
public static Integer[] generateOrderedArray(int n) {
Integer[] arr = new Integer[n];
for (int i = 0; i < arr.length; i++) {
arr[i] = i;
}
return arr;
}
/**
* 生成长度为 n 的随机数组，每个数字的范围是[0, bound)
*
* @param n
* @param bound
* @return
*/
public static Integer[] generateRandomArray(int n, int bound) {
Integer[] arr = new Integer[n];
Random rnd = new Random();
for (int i = 0; i < n; i++) {
arr[i] = rnd.nextInt(bound);
}
return arr;
}
}

SortingHelper

<font face=黑体>作用主要是测试各种排序算法的性能，具体如下所示：

public class SortingHelper {
private SortingHelper() {
}
/**
* 判断一个数组是否有序
*
* @param arr
* @param <E>
* @return
*/
public static <E extends Comparable<E>> boolean isSorted(E[] arr) {
for (int i = 1; i < arr.length; i++) {
if (arr[i - 1].compareTo(arr[i]) > 0) {
return false;
}
}
return true;
}
/**
* 测试排序算法的性能
*
* @param sortName
* @param arr
* @param <E>
*/
public static <E extends Comparable<E>> void sortTest(String sortName, E[] arr) {
long startTime = System.nanoTime();
if (sortName.equals("SelectionSort")) {
SelectionSort.sort(arr);
} else if (sortName.equals("InsertionSort")) {
InsertionSort.sort(arr);
} else if (sortName.equals("InsertionSort2")) {
InsertionSort.sort2(arr);
}
long endTime = System.nanoTime();
double time = (endTime - startTime) / 1000000000.0;
if (!SortingHelper.isSorted(arr)) {
throw new RuntimeException(sortName + " failed");
}
System.out.println(String.format("%s , n = %d : %f s", sortName, arr.length, time));
}
}

以上是 【Java】选择排序 的全部内容， 来源链接： utcz.com/a/97278.html

回到顶部