十大排序算法

1.冒泡排序

冒泡排序的思路就是每次找到数组中最大的值放到数组的末尾，

时间复杂度：O（n2）

public void sort(int[] array){
        for(int end = array.length - 1 ; end > 0 ; end--){
            for(int begin = 1 ; begin <= end ;begin++){
                if(array[begin] < array[begin-1]){
                    int temp = array[begin];
                    array[begin] = array[begin - 1];
                    array[begin - 1] = temp;
                }
            }
        }
    }

冒泡排序的优化1：如果一次循环中没有元素的交换，就说明此时的数组已经是有序的了，就不用在排序了。

public void sort(int[] array){
        for(int end = array.length - 1 ; end > 0 ; end--){
            boolean sorted = true;
            for(int begin = 1 ; begin <= end ;begin++){
                if(array[begin] < array[begin-1]){
                    int temp = array[begin];
                    array[begin] = array[begin - 1];
                    array[begin - 1] = temp;
                    sorted = false;
                }
            }
            if(sorted) return;
        }
    }

冒泡排序的优化2：用一个int来记录最后一次交换的索引，当局部有序的时候，可以减少排序的次数.

public static void sort(int[] array){
        for(int end = array.length - 1 ; end > 0 ; end--){
            int sortedIndex = 1;
            for(int begin = 1 ; begin <= end ;begin++){
                if(array[begin] < array[begin-1]){
                    int temp = array[begin];
                    array[begin] = array[begin - 1];
                    array[begin - 1] = temp;
                    sortedIndex = begin;
                }
            }
            end = sortedIndex;
        }
    }

2.选择排序

时间复杂度：O（n2）

记录数组中最大的值，一次循环之后，在把最大值和数组最后一个元素进行交换.

与冒泡排序的区别：冒泡排序每进行一次比较，就会有一次交换，但是选择排序会在一轮循环之后在交换，交换次数小于冒泡排序.

public static void sort(int[] array){
        for(int end = array.length - 1 ; end > 0 ; end--){
            int max = 0;
            for(int begin = 1 ; begin <= end ;begin++){
                if(array[begin] > array[max]){
                    max = begin;
                }
            }
            int temp = array[max];
            array[max] = array[end];
            array[end] = temp;
        }
    }

3.堆排序

4.插入排序

插入排序的主要思想就是像扑克牌一样，把一张插入已经排好序的数组中，重新变得有序

package suanfa2;

public class InsertSort {

    public static void sort(int[] arr){
        for(int i = 1 ; i < arr.length ; i++){
            int cur = i;
            while(cur > 0 && arr[cur] < arr[cur-1]){
                int temp = arr[cur];
                arr[cur] = arr[cur-1];
                arr[cur-1] = temp;
                cur--;
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {2,3,5,7,4,6,1};
        InsertSort.sort(arr);
        for(int i = 0 ; i < arr.length ; i++){
            System.out.print(arr[i] + " ");
        }
    }
}

优化:比较之后可以先不交换，先移动，最后空出的那个位置就是你要插入的位置

package suanfa2;

public class InsertSort2 {

    public static void sort(int[] arr){
        for(int i = 1 ; i < arr.length ; i++){
            int cur = i;
            int value = arr[cur];
            while(cur > 0 && value < arr[cur-1]){
                arr[cur] = arr[cur-1];
                cur--;
            }
            arr[cur] = value;
        }
    }

    public static void main(String[] args) {
        int[] arr = {2,3,5,7,4,6,1};
        InsertSort2.sort(arr);
        for(int i = 0 ; i < arr.length ; i++){
            System.out.print(arr[i] + " ");
        }
    }
}

使用二分查找优化

package suanfa2;

public class InsertSort3 {

    public static void sort(int[] arr){
        for(int begin = 1 ; begin < arr.length ; begin++){
            insert(arr,begin,search(arr,begin));
        }
    }
    public static int search(int[] arr,int index){
        int  begin = 0;
        int end = index;
        while(begin < end){
            int middle = (begin + end)/2;
            if(arr[index] < arr[middle]){
                end = middle;
            }else if(arr[index] > arr[middle]){
                begin = middle+1;
            }
        }
        return end;
    }

    public static void insert(int[] arr,int source , int dest ){
        int value = arr[source];
        for(int i = source  ; i > dest ; i--){
            arr[i] =  arr[i - 1];
        }
        arr[dest] = value;
    }


    public static void main(String[] args) {
        int[] arr = {2,3,5,7,4,6,1};
        InsertSort3.sort(arr);
        for(int i = 0 ; i < arr.length ; i++){
            System.out.print(arr[i] + " ");
        }
    }
}