排序算法小总结

排序算法	时间复杂度
冒泡排序	O(n2)
选择排序	O(n2)
插入排序	O(n2)
希尔排序	O(n1.5)
快速排序	O(N*logN)
归并排序	O(N*logN)
堆排序	O(N*logN)
基数排序	O(d(n+r))

1.冒泡排序（BubbleSort）

基本思想：两个数相比较大小，较大的数下沉，较小的数冒起来。
过程：

• 比较相邻的两个数据，如果第二个数小，就交换位置。
• 从后向前两两比较，一直到比较最前两个数据。最终最小数被交换到起初的位置，这样第一个最小数的位置就排好了。
• 继续重复上述过程，依次将第2.3....n-1个最小数排好位置。
  Java代码实现

public static void bubbleSort(int[] arr) {
        int temp;

        for (int i = 0; i < arr.length; i++) {
            for (int j = arr.length - 1; j > i; j--) {
                if (arr[j] < arr[j-1]) {
                    temp= arr[j];
                    arr[j] = arr[j-1];
                    arr[j-1] = temp;
                }
            }
        }

       System.out.println(Arrays.toString(arr));
    }

优化

• 针对问题：
  数据的顺序排好后，冒泡算法仍是会继续进行下一轮的比较，直到arr.length - 1次，后面的比较没有意义的。
• 方案：
  设置标志位flag，如果发生了交换flag设置为true；如果没有交换就是默认false。
  这样当一轮比较结束后如果false仍然是false,即：这一轮没有发生交换，说明数据的顺序已经排好，没有必要继续进行下去。

public static void bubbleSort(int[] arr) {
        int temp;
        boolean flag;
        for (int i = 0; i < arr.length; i++) {

            flag = false;
            for (int j = arr.length - 1; j > i; j--) {
                if (arr[j] < arr[j-1]) {
                    temp= arr[j];
                    arr[j] = arr[j-1];
                    arr[j-1] = temp;
                    flag = true;
                }
            }
            
            if(!flag) {
                break;
            }
        }

       System.out.println(Arrays.toString(arr));
    }

2.选择排序(selectionSort)

基本思想：在长度为N的无序数组中，第一次遍历n-1个数，找到最小的数值与第一个元素交换；
第二次遍历n-2个数，找到最小的数值与第二个
Java代码实现：

//一种
public static void selectionSort(int[] arr) {
        
        int temp;

        for (int i = 0; i < arr.length-1; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                if(arr[i] > arr[j]) {
                    temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }
        }

       System.out.println(Arrays.toString(arr));
    }

//二种
public static void select_sort(int array[],int lenth){

    for(int i=0;i<lenth-1;i++){

        int minIndex = i;
        for(int j=i+1;j<lenth;j++){
           if(array[j]<array[minIndex]){
               minIndex = j;
           }
        }
        if(minIndex != i){
            int temp = array[i];
            array[i] = array[minIndex];
            array[minIndex] = temp;
        }
    }
}

3.插入排序(insertionSort)

基本思想：再要排序的一组数中，假定前n-1个数已经排序好了，现在将第n个数插到前面的有序数列中，使得这n个数也是排好顺序的。如此反复循环，直到全部排好顺序。
Java代码实现：

public static void  insert_sort(int array[],int lenth){

    int temp;

    for(int i=0;i<lenth-1;i++){
        for(int j=i+1;j>0;j--){
            if(array[j] < array[j-1]){
                temp = array[j-1];
                array[j-1] = array[j];
                array[j] = temp;
            }else{         //不需要交换
                break;
            }
        }
    }
}

4.希尔排序(shell Sort)

前言：
数据序列1:13-17-20-42-28 利用插入排序， 13-17-20-28-42.
Number of swap：1
数据序列1:13-17-20-42-14 利用插入排序， 13-14-17-28-42.
Number of swap：3
如果数据序列基本有序，使用插入排序会更加高效。
基本思想：
在要排序的一组数中，根据某一增量分为若干子序列，并对子序列分别进行插入排序。
然后逐渐将增量减小，并重复上述过程。直至增量为1，此时数据序列基本有序，最后进行插入排序。
Java代码实现

public static void shell_sort(int array[],int lenth){

    int temp = 0;
    int incre = lenth;

    while(true){
        incre = incre/2;

        for(int k = 0;k<incre;k++){    //根据增量分为若干子序列

            for(int i=k+incre;i<lenth;i+=incre){

                for(int j=i;j>k;j-=incre){
                    if(array[j]<array[j-incre]){
                        temp = array[j-incre];
                        array[j-incre] = array[j];
                        array[j] = temp;
                    }else{
                        break;
                    }
                }
            }
        }

        if(incre == 1){
            break;
        }
    }
}

待续