2.2 选择排序

2.2.1基本思想：

2.2.2 直接选择排序:

思路1:

1. 设i=0, 将i存放在minIndex里, 假设i是最小值的下标
2. 遍历i后面的元素, 如果有比minIndex下标的值小的数据, 则更改minIndex的值, 即minIndex = j
3. 遍历完成后, minIndex里面存放的是最小数据的值, 接着交换i和minIndex下标的值

注意: 此时不能写arr[i] = arr[minIndex], 如果这样写, 假设i下标存放的不是最小值, 那么用minIndex下标的值将i下标的值覆盖, 则会丢失i下标的值

     4. 接着i++, 循环上述步骤, 直到遍历完整个数组

代码:

public static void selectSort(int[] arr){
        for (int i = 0; i < arr.length; i++) {
            int minIndex = i;
            for (int j = i+1; j < arr.length; j++) {
                if(arr[j] < arr[minIndex]){
                    minIndex = j;
                }
            }
            swap(arr,i,minIndex);
        }
    }
    private static void swap(int[] arr,int i,int j){
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

思路2:

1. 相当于思路1的优化, 遍历一遍数组可以同时找出最小值和最大值
2. left 和 right相当于思路1中i的作用
3. i 相当于思路1中j的作用, 用来遍历数组(注意:此时要从left开始遍历, 而不是left+1, 因为有可能left值就是最大值, 如果从left+1开始, 则最大值找不到)
4. minIndex 和 maxIndex作用同样是存放最小值下标和最大值下标

代码:

public static void selectSort2(int[] arr){
        int left = 0;
        int right = arr.length -1;
       while(left< right){
           for (int i = left; i <= right ; i++) {
               int minIndex = left;
               int maxIndex = right;
               if(arr[i] < arr[minIndex]){
                 minIndex = i;
               }
               if(arr[i] > arr[maxIndex]){
                  maxIndex = i;
               }
               swap(arr,left,minIndex);
               swap(arr,right,maxIndex);
               left++;
               right--;
           }
       }
    }
    private static void swap(int[] arr,int i,int j){
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

2.2.3 堆排序

思路:

1. 建立大根堆
2. 交换堆顶元素和最后一个元素end, 这样就找到的最大的数放在最后
3. 向下调整成大根堆, 但不算最后一个结点, 因为最后一个结点已经在应该的位置, 这样堆顶元素又变成了除最后一个元素外最大的元素
4. 重复前两个步骤, 交换倒数第二个元素end--和堆顶元素, 这样就找到了倒数第二大的元素, 以此类推, 直到end==0时, 说明已经全部有序, 输出即可

代码:

public static void heapSort(int[] arr){
        createHeap(arr);
        int end = arr.length-1;
        while(end > 0){
            swap(arr,0,end);
            siftDown(arr,0,end);
            end--;
        }
    }
    private static void createHeap(int[] arr){
        for(int parent = (arr.length-1-1)/2;parent >0;parent--){
            siftDown(arr,parent,arr.length);
        }
    }
    private static void siftDown(int[] arr, int parent, int len){
        int child = (parent*2)+1;
        while(child < len){
            if(child +1 < len && arr[child+1]>arr[child]){
                child = child+1;
            }
            if(arr[child] > arr[parent]){
                swap(arr,child,parent);
                parent = child;
                child = (parent*2)+1;
            }else{
                break;
            }
        }
    }