Java数据结构之选择排序算法的实现与优化

 

初识选择排序

算法思想[以升序为例]:

第一趟选择排序时,从第一个记录开始,通过n-1次关键字的比较,从第n个记录中选出关键字最小的记录,并和第一个记录进行交换

第二趟选择排序时,从第二个记录开始,通过n-2次关键字的比较,从第n-1个记录中选出关键字最小的记录,并和第二个记录进行交换

第i趟选择排序时,从第i个记录开始,通过n-i次关键字的比较,从n-i+1个记录中选择出关键字最小的记录,并和第i个记录进行交换

反复进行上述步骤,经过n-1趟选择排序,将把n-1个记录排到位,最后剩下的那个元素同样已经就位,所以共需进行n-1趟选择排序

文字描述[以升序为例]

将数组分为两个子集,排序的和未排序的,每一轮从未排序的子集中选出最小的元素,放入排序子集,重复上述步骤,直至整个数组有序

 

算法实现

代码如下:

package bin_find;
import java.util.Arrays;

public class selectionSort {
  public static void main(String[] args) {
      int[] a={5,3,7,2,1,9,8,4};
      selection(a);
  }

  private static void selection(int[] a){
      for(int i=0;i<a.length-1;i++) {//n个元素参与排序,需要进行n-1次
          for (int j = i + 1; j < a.length; j++) {//每轮i+1---a.length个元素之间相比较
              if (a[i] > a[j]) {//前者大于后者,则进行交换
                  swap(a, i, j);
              }
          }
          System.out.println("第"+(i+1)+"轮选择排序的结果"+Arrays.toString(a));
      }
  }
  public static void swap(int arr[],int i,int j){
      int t=arr[i];
      arr[i]=arr[j];
      arr[j]=t;
  }
}

输出如下:

第1轮选择排序的结果[1, 5, 7, 3, 2, 9, 8, 4]
第2轮选择排序的结果[1, 2, 7, 5, 3, 9, 8, 4]
第3轮选择排序的结果[1, 2, 3, 7, 5, 9, 8, 4]
第4轮选择排序的结果[1, 2, 3, 4, 7, 9, 8, 5]
第5轮选择排序的结果[1, 2, 3, 4, 5, 9, 8, 7]
第6轮选择排序的结果[1, 2, 3, 4, 5, 7, 9, 8]
第7轮选择排序的结果[1, 2, 3, 4, 5, 7, 8, 9]

 

优化后的算法实现

优化思路

减少交换次数,每一轮可以先找到最小的索引,再每轮最后再交换元素

代码如下:

package bin_find;
import java.util.Arrays;

public class selectionSort {
  public static void main(String[] args) {
      int[] a={5,3,7,2,1,9,8,4};
      selection(a);
  }

  private static void selection(int[] a){
      //代表每轮选择最小元素要交换到的目标索引
      for(int i=0;i<a.length-1;i++) {

          int s = i;//代表最小元素的索引[这里是升序]---第一次最小元素的索引为1,第二次最小元素的索引为2.....

          //从当前最小元素的下一位元素开始直到最后一个元素---完成一次选择排序
          for (int j = s + 1; j < a.length; j++) {
              //[这里是升序],前者大于后者,则将更小数的索引值赋值给s,因为变量s本身代表的含义为最小元素的索引
              if (a[s] > a[j]) {
                  s = j;
              }
          }
          if (s != i) {//若不是同一个数,则进行交换
              swap(a, s, i);
          }
          System.out.println("第"+(i+1)+"轮选择排序的结果"+Arrays.toString(a));
      }
  }
  public static void swap(int arr[],int i,int j){
      int t=arr[i];
      arr[i]=arr[j];
      arr[j]=t;
  }
}

输出:

第1轮选择排序的结果[1, 3, 7, 2, 5, 9, 8, 4]
第2轮选择排序的结果[1, 2, 7, 3, 5, 9, 8, 4]
第3轮选择排序的结果[1, 2, 3, 7, 5, 9, 8, 4]
第4轮选择排序的结果[1, 2, 3, 4, 5, 9, 8, 7]
第5轮选择排序的结果[1, 2, 3, 4, 5, 9, 8, 7]
第6轮选择排序的结果[1, 2, 3, 4, 5, 7, 8, 9]
第7轮选择排序的结果[1, 2, 3, 4, 5, 7, 8, 9]

未进行优化的算法输出:

进行优化的算法输出:

通过比较二者的输出结果,我们能够很明显的感觉到,经过优化后的算法在实现的过程中,数据之间的交换次数明显减少

 

选择排序 VS 冒泡排序

1:二者的平均复杂度都是O(n^2),但是当有序数组使用冒泡排序时,其时间复杂度为O(n)

2:选择排序一般要快于冒泡排序,因为其交换的次数少

3:但如果集合有序度高,那么冒泡排序优先于选择排序

例:在上篇文章的冒泡排序优化算法中,我们通过设置变量,去判断当前的数组元素是否发生交换,如果未发生交换,则证明当前数组已经有序,不再进行排序

4:冒泡排序属于稳定排序算法,而选择属于不稳定排序

稳定 VS 不稳定:即为两个大小相等的数,在参与排序之前具有先后关系,若排序完成,这两个数的先后顺序并未发生改变,那么即为稳定排序,否则为不稳定排序

举例:

(3,3,2)

对于上述数组:

参与冒泡排序:

第一轮:3和3相等,无需交换位置,3和2交换位置

第二轮:3和2交换位置

排序结束,排序后的结果为(2,3,3)

参与选择排序:

第一轮:将3取出,与3比较,3不满足大于3,再与2进行比较,满足大于2,交换位置

第二轮:将3取出,与3进行比较,不满足大于3

排序结束,排序成功,排序后的结果为(2,3,3)

通过两种方法的排序结果,我们不难看出通过冒泡排序算法,两个大小相等的数的先后关系并没有发生改变,即为稳定的排序,而通过选择排序算法,两个大小相等的数的先后关系发生了改变,即为不稳定的排序

关于Java数据结构之选择排序算法的实现与优化的文章就介绍至此,更多相关Java选择排序算法内容请搜索编程宝库以前的文章,希望以后支持编程宝库

在项目开发中往往需要使用到数据的导入和导出,导入就是从Excel中导入到DB中,而导出就是从DB中查询数据然后使用POI写到Excel上。大数据的导入和导出,相信大家在日常的开发、面试中都会 ...