数据结构与算法|数据结构与算法——选择排序数据结构|算法

【数据结构与算法|数据结构与算法——选择排序】选择排序（select sorting）也是一种简单的排序方法。它的基本思想是：第一次从arr[0]~arr[n-1]中选取最小值，与arr[0]交换，第二次从arr[1]~arr[n-1]中选取最小值，与arr[1]交换，第三次从arr[2]~arr[n-1]中选取最小值，与arr[2]交换，…，第i次从arr[i-1]~arr[n-1]中选取最小值，与arr[i-1]交换，…, 第n-1次从arr[n-2]~arr[n-1]中选取最小值，与arr[n-2]交换，总共通过n-1次，得到一个按排序码从小到大排列的有序序列。

文章图片

import java.text.SimpleDateFormat; import java.util.Arrays; import java.util.Date; public class SelectSort { public static void main(String[] args) {//int arr[]={101,34,119,1}; //System.out.println("排序前："+Arrays.toString(arr)); //int[] sort = selectSort(arr); //System.out.println("排序后："+Arrays.toString(sort)); int arr2[] = new int[80000]; for (int i=0; i<80000; i++){ arr2[i]=(int)(Math.random()*800000); }Date date1 = new Date(); SimpleDateFormat format = new SimpleDateFormat("yyy-MM-dd HH:mm:ss"); String d1 = format.format(date1); System.out.println("排序前："+d1); selectSort(arr2); Date date2 = new Date(); String d2 = format.format(date2); System.out.println("排序后："+d2); }public static int[] selectSort(int[] arr){ int minIndex = 0; int min = arr[0]; //假定第一个数最小for(int i =0; i arr[j]){//假定最小值不是最小的 min = arr[j]; minIndex = j; } }//优化，如果该值是本轮最小值则不交换 if(minIndex!=i){ //把最小值放到前面，从下标0开始 arr[minIndex]=arr[i]; arr[i] = min; }//重新设置下一个值为最小值,开始下一轮排序 min = arr[i+1]; minIndex = i+1; } return arr; } }

测试排序80000条数据时间：2秒