java 排序

一维数组排序

1. 冒泡排序

实现原理：比较相邻的元素。如果第一个比第二个大，就交换他们两个。

对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。

针对所有的元素重复以上的步骤，除了最后一个。

持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较

代码实现如下：

public class BubbleSort {

    /**
     *  <>
     * @method: bubbleSort
     * @Param: [arr]
     * @Return: void
     * @exception:    冒泡排序
     * @Author: fsy
     * @Date: 19-5-29 下午3:14
     * @description:
     *
     */
    public void bubbleSort(int[] arr) {
        boolean flag;
        for (int i=arr.length - 1; i > 0; i--) {
            //提高排序效率，减少不必要循环
            flag=false;
            for (int j=0; j < i; j++) {
                if (arr[j] > arr[j + 1]) {
                    swap(arr,j);
                    flag=true;
                }
            }
            if (!flag) {
                break;
            }
        }

    }
    static void swap(int[] arr,int j){
        arr[j]   ^=arr[j+1];
        arr[j+1] ^=arr[j];
        arr[j]   ^=arr[j+1];
    }
}

2. 选择排序

实现原理：
它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到全部待排序的数据元素排完。 选择排序是不稳定的排序方法。
实现代码如下：

public class SelectionSort {
    /**
     *  <>
     * @method: selectionSort
     * @Param: [arr]
     * @Return: void
     * @exception:
     * @Author: fsy
     * @Date: 19-5-29 下午3:21
     * @description:
     *
     */
    public void selectionSort(int[] arr) {

        for (int i=0; i <arr.length-1 ; i++) {
            int k=i;
            for (int j=k+1; j <arr.length ; j++) {
                if (arr[j]<arr[k]){
                    k=j;
                }
            }
            if (i!=k){
            swap(arr,i,k);
            }
        }

    }

    static void swap(int[] arr,int i,int j){
        arr[i]   ^=arr[j];
        arr[j]   ^=arr[i];
        arr[i]   ^=arr[j];
    }
}

3. 插入排序

实现原理：
每步将一个待排序的记录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。

代码实现如下：

public class InsertSort {

    /**
     *  <>
     * @method: insertSort
     * @Param: [arr]
     * @Return: void
     * @exception:
     * @Author: fsy
     * @Date: 19-5-29 下午3:50
     * @description:
     *
     */
        public void insertSort(int[] arr){
            //需要插入的数
            int insertNum;
            for (int i=1; i <arr.length ; i++) {
                insertNum=arr[i];
                //序列元素个数
                int j=i-1;
                //将大于insertNum的元素往后移动
                while (j>=0&&arr[j]>insertNum){
                    arr[j+1]=arr[j];
                    j--;
                }
                //找到位置，插入当前元素
                arr[j+1]=insertNum;
            }
  }

4. 快速排序

实现原理：
通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
实现代码如下：

public class QuickSort {
    /**
     * <>
     *
     * @method: quickSort
     * @Param: [arr]
     * @Return: void
     * @exception:
     * @Author: fsy
     * @Date: 19-5-29 下午4:43
     * @description: 快速排序：用递归方法对数据元素啊arr[low]-arr[high]进行快速排序
     */
    public void quickSort(int[] arr, int low, int high) {
        int i=low, j=high;
        //获取第一个元素作为标准数据元素
        int temp=arr[low];
        while (i < j) {
            //在数组的右端扫描
            while (i < j && temp < arr[j]) {
                j--;
            }
            if (i < j) {
                arr[i]=arr[j];
                i++;
            }


            //在数组的左端开始扫描
            while (i < j && arr[i] < temp) { i++;}

            if (i < j) {
                arr[j]=arr[i];
                j--;
            }
        }

        arr[i]=temp;
        //对左端子集合进行递归
        if (low < i) { quickSort(arr, low, i - 1);
        }
        //对右端子集合进行递归
        if (i < high) { quickSort(arr, j + 1, high); }

    }
}

5. 希尔排序

基本思想：
　　希尔排序的实质就是分组插入排序，又称缩小增量法。

　　将整个无序序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序时，再对全体元素进行一次直接插入排序。

　　因为直接插入排序在元素基本有序的情况下，效率是很高的，因此希尔排序在时间效率上有很大提高。
实现代码如下：

public class ShellSort {
        /**
         *  <>
         * @method: shellSort
         * @Param: [arr]
         * @Return: void
         * @exception:
         * @Author: fsy
         * @Date: 19-5-29 下午7:44
         * @description:
         *
         */

        public void shellSort(int[] arr) {
            int num=arr.length;
            int gap;
            for (gap=num >> 1; gap > 0; gap >>= 1) {
                for (int i=0; i <gap; i++) {
                    for (int j=i+gap; j <num ; j+=gap) {
                        int temp=arr[j];
                        int k;
                        for ( k=j-gap; k >=0&&arr[k]>temp ; k-=gap) {
                            arr[k+gap] =arr[k];
                        }
                        arr[k+gap]=temp;
                    }
                }

            }
        }
    }

6. 堆排序

实现思想：在堆的数据结构中，堆中的最大值总是位于根节点（在优先队列中使用堆的话堆中的最小值位于根节点）。堆中定义以下几种操作：

• 最大堆调整（Max Heapify）：将堆的末端子节点作调整，使得子节点永远小于父节点
• 创建最大堆（Build Max Heap）：将堆中的所有数据重新排序
• 堆排序（HeapSort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算

实现代码如下:

public class HeapSort {


  private void creatHeap(int[] arr,int n,int h){
        int i,j,flag;
        int temp;

        //i为要建堆的二叉树根节点下标
        i=h;
        //j为i的左孩子节点的下标
        j=2*i+1;

        temp=arr[i];
        flag=0;
        //沿左右孩子中值较大者重复向下筛选
        while(j<n&&flag!=1){
            //寻找左右孩子节点中的较大者，j为其下标
            if (j<n-1&&arr[j]<arr[j+1]){
                j++;
            }

            /**
             * arr[i>arr[j]
             * 标记结束筛选条件
             * 否则把arr[j]上移
             */
            if (temp>arr[j]){
                flag=1;
            }else {
                arr[i]=arr[j];
                i=j;
                j=2*i+1;
            }

        }

        arr[i]=temp;
    }

   private void initCreatHeap(int[] arr,int n){
        for (int i=(n - 1) >> 1; i >=0; i--) {
            creatHeap(arr, n, i);
        }
    }
    /**
     *  <>
     * @method: heapSort
     * @Param: [arr, n]
     * @Return: void
     * @exception:
     * @Author: fsy
     * @Date: 19-5-29 下午8:14
     * @description: 堆排序
     *
     */

    public void heapSort(int[] arr){

        //初始化创建最大堆
      initCreatHeap(arr,arr.length);
        for (int i=arr.length-1; i >0; i--) {

            //把堆顶arr[0]元素与当前最大堆的最后一个元素交换
           swap(arr, i);

            //调整根节点满足最大堆
           creatHeap(arr, i, 0);
        }

    }

      //元素交换

    static void swap(int[] a,int i){
       a[0] ^=a[i];
       a[i] ^=a[0];
       a[0] ^=a[i];
    }
}

二分排序

实现思想：

二分法插入排序是在插入第 i 个元素时，对前面的 0～i- 1 元素进行折半，先跟他们中间的那个元素比，如果小，则对前半再进行折半，否则对后半进行折半，直到 left>right，然后再把第 i 个元素前 1 位与目标位置之间的所有元素后移，再把第 i 个元素放在目标位置上。
实现代码如下：

public class BinarySort {
    /**
     *  <>
     * @method: binarySort
     * @Param: [arr]
     * @Return: void
     * @exception:
     * @Author: fsy
     * @Date: 19-5-29 下午8:31
     * @description:二分排序算法
     *
     */
    public  void binarySort(int[] arr) {
        int i, j;
        int high, low, mid;
        int temp;
        for (i = 1; i < arr.length; i++) {
            // 查找区上界
            low = 0;
            // 查找区下界
            high = i - 1;
            //将当前待插入记录保存在临时变量中
            temp = arr[i];
            while (low <= high) {
                // 找出中间值
                // mid = (low + high) / 2;
                mid = (low + high) >> 1;
                //如果待插入记录比中间记录小
                if (temp<arr[mid] ) {
                    // 插入点在低半区
                    high = mid - 1;
                } else {
                    // 插入点在高半区
                    low = mid + 1;
                }
            }
            //将前面所有大于当前待插入记录的记录后移
            for (j = i - 1; j >=low; j--) {
                arr[j + 1] = arr[j];
            }
            //将待插入记录回填到正确位置.
            arr[low] = temp;


        }
    }

}

测试类

//测试各个排序算法
public class Test {
    public static void main(String[] args) {


        int[] arr={12, 15, 19, 2, 0, 78, 115, 73, -16, 99};
        /*
        new BubbleSort().bubbleSort(arr);
        new SelectionSort().selectionSort(arr);
        new InsertSort().insertSort(arr);
        new QuickSort().quickSort(arr, 0, arr.length-1);
        new ShellSort().shellSort(arr);
        new HeapSort().heapSort(arr);

         */
        new BinarySort().binarySort(arr);

        for (int ele:arr
             ) {
            System.out.println(ele);
        }

    }
}

各种排序方法性能比较