算法入门教程-选择排序

上节我们学习了常见算法的冒泡排序,本篇接着来学习选择排序算法,我们通过图解和代码的方式一步一步的来学习,首先来看什么是选择排序?

选择排序介绍

选择排序也是基于内存来进行操作排序的,是从要排序的数据中,按照指定的规则来选出某一元素在按照规定来进行位置的交换进行排序.

上述介绍说的有点绕,我们直接通过实际的操作来体验下,来看一张图:

选择排序图.png

简单的来看下上图排序的过程:

• 在第一次的排序过程中,假设8为最小的,通过遍历,从第二个数开始比较(也就是从3开始比较)去寻找最小的那个数,也就是图中的1,然后进行位置的交换.
• 第二次的排序是从2个数开始(也就是3),同样假设是最小的,循环依次比较找到最小的那个数,也就是图中的2,然后交换位置.
• 第三次的排序是从第三个数开始(也就是3),同样假设是最小的,循坏依次比较找到最小的那个数也就是3本身,然后进行位置的交换....其他的重复上述过程即可

简单的了解了过程,我们来总结下选择排序算法的思想

选择排序算法的思想

• 第一次排序的时候首先从array[0]~array[n-1]中选择最小的,然后与array[0]进行交换.
• 第二次从array[1] ~array[n-1]中选择最小的与array[1]进行交换.
• 第三次从array[2] ~array[n-1]中选择最小的与array[2]进行交换.
• ......
• 第i从array[i-1] ~ array[n-1]中选择最小的与array[i-1]进行交换.
• 第n-1次是从array[n-2] ~ array[n-1] 中选择最小的与array[n-2]进行交换.

经过上述描述我们发现总共需要交换 n-1次,接着我们用图解的方法来实现一把

选择排序算法图解分析

• 假设我有一组待排序的数据如:int [] arr = {101,34,119,1};

• 第一轮的排序结果图

  
  第一轮排序结果图.png
• 代码实现

 //第一轮的排序
    //先假设最小数的下标为:
    int minIndex = 0;
    //先假设最小的数为:
    int min = arr[0];
    //从minIndex+1的数开始比较
    for (int j = minIndex +1; j < arr.length; j++) {
        if (min > arr[j]) { //说明我们假设的最小值并不是最小的
            //我们需要重置min值和以及对应的下标索引
            min = arr[j];
            minIndex = j;
        }
    }
    //2 进行交换,将最小值放在arr[0]的位置处
    if (minIndex !=0) {
        arr[minIndex] = arr[0];
        arr[0] = min;
    }
    System.out.println("第一轮的交换结果为:");
    System.out.println(Arrays.toString(arr));

• 测试结果如图

  
  第一轮测试结果图.png

• 第二轮排序

  
  第二轮排序结果图.png

• 代码实现

 //第二轮的排序
    //先假设最小数的下标为:
     minIndex = 1;
    //先假设最小的数为:
     min = arr[1];
    //从minIndex+1的数开始比较
    for (int j = minIndex +1; j < arr.length; j++) {
        if (min > arr[j]) { //说明我们假设的最小值并不是最小的
            //我们需要重置min值和以及对应的下标索引
            min = arr[j];
            minIndex = j;
        }
    }
    //2 进行交换,将最小值放在arr[1]的位置处
    if (minIndex !=1) {
        arr[minIndex] = arr[1];
        arr[1] = min;
    }
    System.out.println("第二轮的交换结果为:");
    System.out.println(Arrays.toString(arr));

• 测试结果图

  
  第二轮测试结果.png

• 第三轮排序过程

  
  第三次排序结果图.png
• 代码实现

//第三轮的排序
    //先假设最小数的下标为:
    minIndex = 2;
    //先假设最小的数为:
    min = arr[2];
    //从minIndex+1的数开始比较
    for (int j = minIndex +1; j < arr.length; j++) {
        if (min > arr[j]) { //说明我们假设的最小值并不是最小的
            //我们需要重置min值和以及对应的下标索引
            min = arr[j];
            minIndex = j;
        }
    }
    //2 进行交换,将最小值放在arr[1]的位置处
    if (minIndex !=2) {
        arr[minIndex] = arr[2];
        arr[2] = min;
    }
    System.out.println("第三轮的交换结果为:");
    System.out.println(Arrays.toString(arr));

• 测试结果图

  
  第三次测试结果图.png

通过图解分析和代码我们进行分步实现排序,从结果图来看,完成了排序,同样我们来优化下代码,将代码封装下:

代码如下:

//排序的方法
public static void selectSort(int [] arr){
    //使用一步一步推导的方式来讲解
    //原始数组 101,34,119,1
    //第一轮的排序: 1,34,119,101
    for (int i = 0; i <arr.length -1 ; i++) {
        //先假设最小数的下标为:
        int minIndex = i;
        //先假设最小的数为:
        int min = arr[i];
        //从minIndex+1的数开始比较
        for (int j = i +1; j < arr.length; j++) {
            if (min > arr[j]) { //说明我们假设的最小值并不是最小的
                //我们需要重置min值和以及对应的下标索引
                min = arr[j];
                minIndex = j;
            }
        }
        //2 进行交换,将最小值放在arr[i]的位置处
        if (minIndex !=i) {
            arr[minIndex] = arr[i];
            arr[i] = min;
        }
        System.out.println("第"+(i+1)+"轮的交换结果为:");
        System.out.println(Arrays.toString(arr));
    }

接着我们测下选择排序的执行效率,还是来测下10w数据的排序,代码如下:

public static void main(String[] args) {
    //int [] arr = {101,34,119,1};
   // selectSort(arr);
    //选择排序的时间复杂度测试
    int [] arr = new int[100000];
    for (int i = 0; i < arr.length; i++) {
        arr[i] = (int)(Math.random() * 100000); //随机生成[0,100000)的数
    }

    Date date1 = new Date();
    SimpleDateFormat dateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
    String format = dateFormat.format(date1);
    System.out.println("排序前的时间为:"+format);
    //进行排序
    selectSort(arr);
    Date date2 = new Date();
    SimpleDateFormat dateFormat2 = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
    String format2 = dateFormat.format(date2);
    System.out.println("排序后的时间为:"+format2);
   // selectSort(arr);
}

• 测试结果图

  
  选择排序执行效率.png

可以发现10w数据只需要了3s左右的时间,相比较冒泡排序算法来说快了很多,那么关于选择排序的学习就到这里了....