算法之排序

排序算法可分为8种，如图所示。外部排序只有在数据非常大时(超过10亿)。

一. 冒泡排序(每次一次，比较两两次，后面放大或小的数字(交换位置)

package com.bzw.sort;  import java.util.Arrays;  public class BubbleSort {     public static void main(String[] args) {          int[] array = {5,4,3,2,1};          boolean flag = false;         int count = 0;         for (int i=0;i<array.length-1;i  ){             for (int j=0;j<array.length-1-i;j  ){   ///每次历相当于选择当前数组的最大值                 if (array[j] > array[j 1]){                     flag = true;                     int temp = array[j];                     array[j] = array[j 1];                     array[j 1] = temp;                 }                 count  ;             }             if (!flag){     ///在一次遍历中没有交换一次，说明排名已经完成，不必回收                 break;             } else {                 flag = false;             }         }          System.out.println(Arrays.toString(array));         System.out.println("遍历次数"   count);      }  } 

二. 简单选择排序(假设第一个数字是最大值或最小值，然后在遍历中找到真正的最小值，交换位置)

package com.bzw.sort;  import java.util.Arrays;  public class ChooseSort {     public static void main(String[] args) {         int[] array = {4,3,-2,6,5};          for (int i=0;i<array.length-1;i  ){             for (int j=i;j<array.length;j  ){                 if (array[j] < array[i]){                     int temp = array[j];                     array[j] = array[i];                     array[i] = temp;                 }             }         }         System.out.println(Arrays.toString(array));     } } 

三. 直接插入排序(从头开始，每次将一个数字与前面的数字进行比较，当一个数字与这个数字进行比较时，插入这个数字后面。

package com.bzw.sort;  import java.util.Arrays;  public class InsertSort {     public static void main(String[] args) {         int[] array = {2, 1, 5, -3, 4, 2, -5, 9};  //        自己写的代码，没有老师写的通俗易懂 //        for (int i=0;i<array.length;i  ){ //            for (int j=0;j<i 1;j  ){ //                if (array[i] < array[j]){ //                   int temp = array[i]; //                    int k = i; //                    while ( j != k ){ //                        array[k] = array[k-1]; //                        k--; //                    } //                    array[j] = temp; //                } //            } //        } //        System.out.println(Arrays.toString(array)); //    }  //        老师代码         for (int i = 0; i < array.length; i  ) {             int insertVal = array[i];             int insertIndex = i - 1;              while (insertIndex >= 0 && insertVal < array[insertIndex]) {                 array[insertIndex   1] = array[insertIndex];                 insertIndex--;             }             //insertIndex   1 即要插入的位置             array[insertIndex   1] = insertVal;           }         System.out.println(Arrays.toString(array));     } } 

四. 希尔排名(可以看作是直接插入排名的优化，直接插入排名的一个缺点是，当一个较小的数字在后面时，它应该经历更多次。希尔排名可以解决这个问题。它的想法是将数组分成几部分(array.length/2)然后用直接插入法对每份进行排序，直到最后只剩下一组。

package com.bzw.sort;  import java.util.Arrays;  public class ShellSort {      public static void main(String[] args) {          int[] array = {-3,4,2,1,3};         shellSort(array);         System.out.println(Arrays.toString(array));       } //      试着自己写，没写出来 //    public static void shellSort(int[] array,int n){ //        int[] temp1 = new int[array.length]; //        int[] temp2 = new int[array.length]; //        while (n != 1){ //            for (int j=0;j<n;j  ){ //                for (int i=j;i<array.length;i=n   i){ //                    temp1[i] = array[i]; //                    insertSort(temp1,n); //                    array[i] = temp1[i]; //                } //            } //            n = n/2; //            shellSort(array,n); //        } // // // //    } // //    public static void insertSort(int[] array,int n){ //        for (int i=0;i<array.length;i=i n){ //            int insertVal = array[i]; //            int insertIndex = i - n;    ////插入数的前一个下标 // //            while (insertIndex >= 0 && insertVal < array[insertIndex]){ //                array[insertIndex   n] = array[insertIndex]; //                insertIndex = i - n; //            } // //            array[insertIndex   n] = insertVal; //        } //    }      public static void shellSort(int[] array){         for (int grap = array.length/2;grap > 0;grap /= 2){     //grap 步长，即分组的长度
            for (int i = grap;i < array.length;i++){
//                因为后面代码要对i值进行修改，所以把当前的i值和数组值存到一个变量中
                int temp = array[i];
                int j = i;

                if (temp < array[j - grap] ){
                    while (j - grap >= 0 && temp < array[j - grap]){
                        array[j] = array[j - grap];
                        j = j - grap;       //每次减少一个步长，确保在同一个组内移动
                    }
                    array[j] = temp;
                }
            }
        }
    }
}

五. 快速排序(可以看成是冒泡排序的优化。它的思想是先选择一个数，然后将比这个数大的放在一边，比这个数小的放在一边，然后用递归实现排序。因为用的是递归，快排还是比较快的。)

package com.bzw.sort;

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

public class QuickSort {

    public static void main(String[] args) {

  //      int[] array = {4,3,-1,78,45,0,3,10};

        int[] array = new int[80000000];
        for (int i=0;i<array.length;i++){
            array[i] = (int)Math.random()*80000000;
        }
        Date datal = new Date();
        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
        String datelStr = simpleDateFormat.format(datal);
        System.out.println("排序前的时间"+datelStr);

        quickSort(array,0,array.length-1);

        Date data2 = new Date();
        String datelStr2 = simpleDateFormat.format(data2);
        System.out.println("排序后的时间"+datelStr2);

//        System.out.println(Arrays.toString(array));

    }

    public static void quickSort(int[] array,int left,int right){
        int l = left;
        int r = right;
        int pivot = array[(left + right) / 2];
        int temp = 0;

        while (l < r ){
            while (array[l] < pivot){
                l ++;
            }
            while (array[r] > pivot){
                r --;
            }

            if (l >= r){
                break;
            }

            temp = array[l];
            array[l] = array[r];
            array[r] = temp;

            if (array[r] == pivot){     //交换完如果发现 array[r] == pivot，要将左下标手动向后移一位，
                l ++;                   // 不然 l 就不会动了，造成死循环(可以举个相等的例子，画图理解)
            }
            if (array[l] == pivot){     //右下标同理
                r --;
            }

        }

//        当 l == r 必须l++,r-- 否则出现栈溢出
//        当l == r时，如果不手动l++,r--的话，l和r的值将不在发生变化(因为没有其他代码使其变化),那么递归的条件将不会发生改变，
//        递归函数不停的压栈，最终导致栈溢出
        if (l == r){
            l ++;
            r --;
        }

        if (left < r){
            quickSort(array,left,r);
        }
        if (l < right){
            quickSort(array,l,right);
        }
    }
}

六. 归并排序(采用分治策略，将一个数组分解成一个个的数，再进行合并，最终完成排序。合并的思路：将左面的一组和右面的一组进行比较，将较小的或较大的数放到一个临时数组中，最后将这个临时数组再复制原数组。)

package com.bzw.sort;

import java.util.Arrays;

public class MergerSort {
    public static void main(String[] args) {

        int[] array = {6,29,17,9,3,11,-3,0,4};
        int[] temp = new int[array.length];

        mergerSort(array,0,array.length-1,temp);

        System.out.println(Arrays.toString(array));

    }

    //分解 + 合并
    public static void mergerSort(int[] array,int left,int right,int[] temp){
       if (left < right){
           int mid = (left + right) / 2;

           //向左递归分解
           mergerSort(array,left,mid,temp);
           //向右递归分解
           mergerSort(array,mid+1,right,temp);
           //合并
           merger(array,left,right,mid,temp);
       }

    }

    //合并
    public static void merger(int[] array ,int left,int right,int mid,int[] temp ){
        int l = left;
        int j = mid + 1;
        int t = 0;

        while (l <= mid && j <= right){
            if (array[l] <= array[j]){
                temp[t] = array[l];
                t++;
                l++;
            }else {
                temp[t] = array[j];
                t++;
                j++;
            }
        }

        while (l <= mid){
            temp[t] = array[l];
            t++;
            l++;
        }

        while (j <= right){
            temp[t] = array[j];
            t++;
            j++;
        }

        //把temp中的值复制到array中，这里的tempLeft表明复制到array哪个位置。
        t = 0;
        int tempLeft = left;
        while (tempLeft <= right){
            array[tempLeft] = temp[t];
            tempLeft++;
            t++;
        }
    }
}

七. 基数排序(桶排序的扩展，它的思想很简单，把一组数先按个位数字的大小排序，再按十位数字的大小排序，然后百位，千位.........。所以需要10个桶(一位数组)分别表示0-9 十个数，而且也不能确定每个桶中有多少的数，只能按最坏的情况算，即每个桶的大小都是和原数组大小一样。这样有时候就会造成空间的浪费，基数排序就是空间换时间的经典算法。)

package com.bzw.sort;

import java.util.Arrays;

public class RadixSort {
    public static void main(String[] args) {

        int[] array = {3,35,3,0,9,7};

        radixSort(array);

        System.out.println(Arrays.toString(array));

    }

    public static void radixSort(int[] array){
        //用一个二维数组表示桶和桶中的数据，比如bucket[1][2] = 31 表示编号为1的桶在第二个位置有个数是31
        int[][] bucket = new int[10][array.length];
        //表示桶中有多少个数，比如bucketElement[4] = 3 表示编号为4这个桶中有3个数据(有一个数组来存储，便于后面将值取出赋给array)
        int[] bucketElement = new int[10];
        int max = array[0];
        for (int i = 0;i < array.length;i++){
            if (array[i] > max){
                max = array[i];
            }
        }
        int length = (max + "").length();//最大值的位数
//        System.out.println(length);
        for (int j = 0,n = 1;j < length;j++,n = n * 10){
            for (int i = 0;i < array.length;i++){
                int data = array[i] / n % 10;
                bucket[data][bucketElement[data]] = array[i];
                bucketElement[data]++;
            }
            int index = 0;
            for (int k = 0;k <bucketElement.length;k++){
                if (bucketElement[k] != 0){
                    for (int l = 0;l <bucketElement[k];l++){
                        array[index++] = bucket[k][l];
                    }
                }
                bucketElement[k] = 0;
            }
            System.out.println("第" + (j + 1) +"轮后" + Arrays.toString(array));

        }


    }
}

八. 总结

 稳定表示，如果两个相同的数，在排序过后，原来在前面的那个数仍然在前面。不稳定就不确定了。

In-place表示没有额外占用空间，Out-place表示有额外占用空间。

当数的规模较大的时候(超过2^10)，用基数排序较快。