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

        选择排序(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次,得到一个按排序码从小到大排列的有序序列。

数据结构与算法——选择排序_第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秒

数据结构与算法——选择排序_第2张图片 

你可能感兴趣的