Java排序算法之选择排序

Java排序算法之选择排序

一、选择排序

选择排序就是在每一次遍历过程中将数组中值最小的排到当前的第一位。

总共需要（数组长度-1）次遍历，在每次遍历中假定第一位索引的值为最小值，然后与下一个值对比，如果最小索引所在值大于其他值就将小的那一个索引当作最小值索引，接着继续对比最小索引所在值与下一个索引的值，重复此操作，最终就会在此次遍历中得到最小值及其索引，将最小值与第一位的值进行交换，这样就将最小值放到了数组开头，完成本次遍历。

选择排序的时间复杂度为O(N^2)

二、代码实现

package com.example.algorithmdemo.sortingAlgorithm;

/**

* 选择排序

*/

public class SelectionSort {

/**

* 数组排序

* @param a

*/

public static void sort(Comparable[] a){

for(int i = 0;i

//假设本次遍历，最小值的索引为i

int minIndex = i;

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

if(greater(a[minhttp://Index],a[j])){

//更换最小值索引

minIndex = j;

}

}

//交换i索引和minIndex索引的值

exchange(a,i,minIndex);

}

}

/**

* 判断参数a是否比参数b大

* 返回true/false

* @param a

* @param b

* @return

*/

private static boolean greater(Comparable a,Comparable b){

return a.compareTo(b)>0;

}

/**

* 数组元素i和j交换位置

* @param a

* @param i

* @param j

*/

private static void exchange(Comparable[] a,int i,int j){

Comparable temp = a[i];

a[i] = a[j];

a[j] = temp;

}

}

三、测试

package com.example.algorithmdemo.test;

import com.example.algorithmdemo.sortingAlgorithm.SelectionSort;

import java.util.Arrays;

public class SelectionTest {

public static void main(String[] args) {

Integer[] a = {3,2,6,8,1,4,5,7};

SelectionSort.sort(a);

System.out.println(Arrays.toString(a));

}

}

//假设本次遍历，最小值的索引为i

int minIndex = i;

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

if(greater(a[minhttp://Index],a[j])){

//更换最小值索引

minIndex = j;

}

}

//交换i索引和minIndex索引的值

exchange(a,i,minIndex);

}

}

/**

* 判断参数a是否比参数b大

* 返回true/false

* @param a

* @param b

* @return

*/

private static boolean greater(Comparable a,Comparable b){

return a.compareTo(b)>0;

}

/**

* 数组元素i和j交换位置

* @param a

* @param i

* @param j

*/

private static void exchange(Comparable[] a,int i,int j){

Comparable temp = a[i];

a[i] = a[j];

a[j] = temp;

}

}

三、测试

package com.example.algorithmdemo.test;

import com.example.algorithmdemo.sortingAlgorithm.SelectionSort;

import java.util.Arrays;

public class SelectionTest {

public static void main(String[] args) {

Integer[] a = {3,2,6,8,1,4,5,7};

SelectionSort.sort(a);

System.out.println(Arrays.toString(a));

}

}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。