算法基础遍之选择排序算法详解

之前为大家讲解了一个简单的二分法数组查找算法,一笔触而无法停止,看看时间也不算怎么晚,就再给大家讲解一个排序的算法把,在这里我讲解的是选择排序,也是最简单与最基础的排序方法,我想这些简单与基础的你把它耳熟能详了,后面对稍微复杂的算法相对来说也不会有太多的问题,OK,废话少说,跟到思路一步一步的走吧:

这里需要注意的是,不管你做什么,首先你需要去思考做你所需要做的前提是什么,以至于它所可能产生的问题是什么,这是必要的,算法嘛,不就是一个思考问题的过程吗,即一个逻辑的实现过程,所以我要写这样一个算法,首先就得考虑,这个算法能达到的效果是什么,好了,我在这里就单针对一个对无序数组进行排序来讲解吧:

首先,我需要定义一个数据:int[] arr = new int[]{2,4,7,4,8,3,2,4,1,4,0,6,4,3,2,6,77,43,232,43};它是无序的

其次,我们需要对其数据做排序,以便成为有序的数组,在这里,我们需要思考,我们该怎么去对这个数组进行排序呢,如果我们以小到大的顺序排序或者是大到小的排序都需要对其位置进行两次以上的交换来轮询操作,如在数组中a[0]=2,a[1]=4,相对来说在数组中a[10]=0是最小的,这里就需要有两个循环进行操作,首先是在第一层循环数组长度为:for(int i=0;i<arr.length-1;i++){},这样来一次可以对所有数组都进行一次取值来做比较,当然在这里要假设第一个取值就是最小值,所以需要对其最小值进行保存起来:int min = i;在第一层循环中我们只需要循环都倒数第一个对其比较即可,因为在最后一个比较时是自己跟自己进行比较,所以没必要,不然的话会增加计算过程,从而降低其效率,其次就是我们在固定第一层循环选值后会对当前值与其下一个值进行对比,如:a[0]需要与a[1]进行对比,如a[0]大于a[1]的话,就需要对其值位置进行交换,然而这是轮询的,也就是说这种对比交换方式是依次都会对比一次,因为可能最小的值在这个数组的最后,所以就需要依次轮询对比并进行交换后才能判断得出它的最小值老保存:for(int j=i;j<arr.length;j++){},再次就是需要在第二层对比后进行判断,if(arr[min] > arr[j])时就需要对其位置进行交换:min = j;这是交换下标的位置,所以就需要对其保存后对其值的位置进行交换:if(min != i){int tmp=arr[i];arr[i]=arr[min];arr[min]=tmp;}这里我们对其算法进行优化,也就是说当min不等于i时才进行位置交换,否则就没必要进行交换了,因为在这里最小的小表与这min的下标本身就是同一个下标,所以就不需要进行罗列了,然后不等时就设定一个临时变量对其初始对比值进行保存,这是在当我们对比的结果a[n-1]>a[n]时需要对其位置进行交换,并把大的那个数使用临时位置进行保存,把小的数进行前移,然后再把放在临时文件里的那个数放在已经前移后的那个数据的位置,依次来进行轮询对比就可以得到外层第一次循环后内层多次循环比较出来的结果并置于最小值为最前位,当外层循环第二次循环的时候就从a[1]开始了,一次对内层循环进行比较,个得到第二个最小值,知道外层循环依次到最后一个循环位置,这样就可以得到我们想要的数组排序结果了,OK,上面说的是以小到大的排序方式来做的,如果想要实现大到小的方式来排序的话我想这我拘没必要再说了吧,下面我把完整的代码写在下面,并顺以面向对象方式优化后进行展示:

public class SelectionSort{

public static void main(String args[]){

int[] arr = new int[]{3,4,7,2,23,3,4,5,66,7,89,43,23,2,2,43,67,8,9};

selectionSort(arr);

}

private static int selectionSort(int[] arr){

for(int i=0;i<arr.length-1;i++){

int min = i;

for(int j=i;j<arr.length;j++){

if(arr[min] > arr[j]){

min = j;

}

}

if(min != i){

int tmp = arr[i];

int arr[i] = arr[min];

int arr[min] = tmp;

}

System.out.println("第"+i+"次");

for(int ele:arr){

System.out.println(ele+"/t");

}

System.out.println(" ");

}

System.out.println("最终: ");

for(int ele:arr){

System.out.println(ele);

}

return 0;

}

}

以上就是完整的源代码,只是这个实现都是在一个方法中执行的,如果这个方法你需要处理很多的数据的话,那样这个方法相对来说是比较膨胀的,所以我们要对其重构:

public class ReconstructionSelectionSort{

public static void main(String args[]){

int[] arr = new int[]{3,4,7,2,23,3,4,5,66,7,89,43,23,2,2,43,67,8,9};

selectionSort(arr);

}

public static int selectionSort(int[] arr){

for(int i=0;i<arr.length;i++){

int min = i;

for(int j=i;j<arr.length;j++){

min = innerSort(arr,min,j);

}

swap(arr,i,min);

showArray("第"+i+"次",arr);

}

showArray("最终:",arr);

}

public staticvoid showArray(int i,int[] arr){

System.out.print(i);

for(int ele:arr){

System.out.println(ele+"/t");

}

System.out.println(" ");

}

public static void swap(int[] arr,int i,int min){

if(i!=min){

int tmp = arr[i];

arr[i] = arr[min];

arr[min] = tmp;

}

}

public static int innerSort(int[] arr,int min,int j){

if(arr[min]>arr[j]){

min = j;

}

return min;

}

}

以上就是重构过后的代码,希望能给初学者提供最详细与完整的讲解,如果有问题,自己来邮,本人会第一次回复:[e-mail]