排序3-选择

「爱情、让人受尽委屈。」 2022-11-21 01:16 43阅读 0赞

1. 动图演示

![20201029142742174.gif][]

2. 算法说明:

*  首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
 *  再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
 *  重复第二步，直到所有元素均排序完毕。

3. java源码实现

方案一:

public static int[] selectSort(int[] sourceArray)  {
            int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
            // 总共要经过 N-1 轮比较
            for (int i = 0; i < arr.length - 1; i++) {
                int min = i;
                // 每轮需要比较的次数 N-i
                for (int j = i + 1; j < arr.length; j++) {
                    if (arr[j] < arr[min]) {
                        // 记录目前能找到的最小值元素的下标
                        min = j;
                    }
                }
                // 将找到的最小值和i位置所在的值进行交换
                if (i != min) {
                    int tmp = arr[i];
                    arr[i] = arr[min];
                    arr[min] = tmp;
                }
            }
            return arr;
        }

方案二:  将以上封装成几个函数

public static int[] selectSort2( int[] sourceArray){
            int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
            for(int i=0;i<arr.length-1;i++){
                int minIndex=getIndexOfSmallest(  arr,i,arr.length-1 );
                swap( arr,i,minIndex);
            }
            return arr;
        }
    
    private static int getIndexOfSmallest(int[] arr, int first, int last) {
            int min=arr[first];
            int indexOfMin=first;
            for( int index=first+1;index<=last;index++){
                if( arr[index]<min ){
                    min=arr[index];
                    indexOfMin=index;
                }
            }
            return indexOfMin;
    }
    
    public static void swap( int [] arr, int i,int j){
            int temp=arr[i];
            arr[i]=arr[j];
            arr[j]=temp;
    }

方案三: 递归实现

public static void main(String[] args) {
            int [] x=new int[]{5,2,3,7,1,2,6,100,1};
           
            selectSort3(  x,0,1 );
            show(  x );
    }
    public static void selectSort3(int[] arr,int base,int next) {
            int i=base,j=next,temp,minIndex=base;
            if(j<=arr.length-1) {
                temp=arr[base];
                while(j<=arr.length-1) {
                    if(arr[j]<temp) {
                        temp=arr[j];
                        minIndex=j;
                    }
                    j++;
                }
                arr[minIndex]=arr[base];
                arr[base]=temp;
                i++;
                selectSort3(arr,i,++i);
            }
    }

[20201029142742174.gif]: /images/20221120/3b675b80c7d247b8884c2f42e3a77f0d.png