【算法】排序（一）选择排序

日期：2021-05-17 栏目：程序人生浏览：次

在排序算法中，最简单的莫过于选择排序了。

排序思路：

在选择排序算法中分别有一个外循环和一个内循环，假设需要排序的序列共有n个元素，所以外循环的次数为n次，在n次交换（外循环）中，每次设置序列中的第一个元素为最小值（min)，然后进行内循环，每次内循环都将序列中与min比较，若有元素小于min，则进行交换（若没有，min自己与自己交换）。所以内循环的次数暂时不确定。

简而言之，就是在未排序的序列中，每次选取序列首位元素，依次与序列中其他元素比较，进而交换元素，达到排序的效果。

开始排序 1.外循环 public static void selectionSort(int[] a){ int n = a.length; for (int i = 0; i < n; i++) { //外循环共n次 int min = i; int temp = a[i]; // a[i] = a[min]; // 交换元素 a[min] = temp; // } }

共有n次交换

2.内循环（比较大小并交换元素索引） for (int j = i + 1; j < n; j++) { if(a[j] < a[min]){ min = j; //如果由元素小于min,则交换元素索引 } }

j = i + 1, i +2 , i + 3 ... n.
共有n - i - 1次比较，比较的次数将会在下文提及。

3.交换元素 int temp = a[i]; a[i] = a[min]; a[min] = temp; 所以，选择排序的代码块就是如此了： public static void selectionSort(int[] a){ int n = a.length; for (int i = 0; i < n; i++) { int min = i; for (int j = i + 1; j < n; j++) { if(a[j] < a[min]){ min = j; } } int temp = a[i]; a[i] = a[min]; a[min] = temp; } } 接下来是测试阶段

我们来写一个测试数据：

public static void main(String[] args){ int[] a = new int[10]; for (int i = 0; i < a.length; i++) { a[i] = (int)(Math.random()*100); //随机输入测试数据 System.out.print(a[i] + " "); } System.out.println(); selectionSort(a); for (int i = 0; i < a.length; i++) { System.out.print(a[i] + " "); } }

随机选取几组排序结果：

test 1