java排序算法（二）：直接选择排序

java排序算法（二） 直接选择排序

直接选择排序排序的基本操作就是每一趟从待排序的数据元素中选出最小的（或最大的）一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完，它需要经过n-1趟比较，算法不稳定，o(1)的额外的空间，比较的时间复杂度是o(n^2),交换的时间复杂度是o(n),并不是自适应的.。在大多数情况下不推荐使用。只有在希望减少交换次数的情况下可以用。

基本思想

n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果

1、初始状态：无序区为R[1,n] ,有序区为空

2、第一趟排序

在无序区R[1,n]中选中关键字最小的记录R[k],它将与无序区的第一个记录R[1]交换，使R[1,1和R[]2..n]分别变为记录个数增加1个新有序区和记录个数减少1个新无序区。

。。。。。

3、第i趟排序

第i趟排序开始时，当前有序区和无序区分别为R[1.i-1]和R[1<=i<=n-1].该趟排序从当前无序区选出关键字最小的记录R[K] ,将他与无序区的第一个记录R交换，使R[1..i]和R分别变为记录个数增加1个新有序区和记录个数减少1个的新无序区

这样n个记录的文件可以直接选择排序经过n-1趟直接选择排序得到有序结果

示例代码1

package com.spring.test;

import java.security.Principal;

/**
 * 直接选择排序测试类
 */
public class SelectSortTest {
    public static void main(String[] args) {
        int[] data = new int[]{5, 3, 6, 2, 1, 9, 4, 8, 7};
        print(data);
        SelectSort(data);
        print(data);
    }
    /**
     * 交换两个数据
     */
    private static void swap(int[] data,int i,int j){
        if(i == j){
            return ;
        }
        data[i] = data[i]+data[j];
        data[j] = data[i]-data[j];
        data[i] = data[i]-data[j];
    }
    /**
     * 对数组进行排序
     */
    private static void SelectSort(int[] data){
        for(int i =0;i<data.length-1;i++){
            int minIndex = i;
            for(int j=i+1;j<data.length;j++){
                if(data[j] < data[minIndex] ){
                    minIndex = j;
                }
            }
            if(minIndex!=i){
                swap(data,i,minIndex);
                print(data);
            }
        }
    }

    /**
     * 打印数组
     */
    private static void print(int[] data){
        for(int i=0; i < data.length;i++){
            System.out.print(data[i]+"\t");
        }
        System.out.println();
    }


}

运算结果