希尔排序（优化的插入排序）

使用思想：缩小增量排序。对数组进行预排序，再进行插入排序。

小数字在数组最后的的话，在插入时需要遍历全部已经排好的数组。

交换法（个人理解就是升级的冒泡）

  public static void ShellSort(int[] array){
        int temp = 0;
        for (int gap = array.length/2; gap >0 ; gap/=2) {
            for (int i = gap; i < array.length; i++) {
                for (int j = i-gap; j >= 0; j-=gap) {
                    if (array[j] > array[j+gap]){
                        temp = array[j];
                        array[j] = array[j+gap];
                        array[j+gap] = temp;
                    }
                }
            }
        }
    }

移动法 （个人理解就是升级的插入排序）

    public static void ShellSort2(int[] array){
        for (int gap = array.length/2; gap >0 ; gap/=2) {
            for (int i = gap; i < array.length; i++) {
               int j = i;
               int temp = array[j];
               if (array[j] < array[j-gap]){
                   while (j-gap >= 0 && temp<array[j-gap]){
                       array[j] = array[j-gap];
                       j -= gap;
                   }
                   array[j] = temp;
               }
            }
        }
    }

测试：

public class ShellSort {
    public static void main(String[] args) {
        int arr[] = new int[80000];
        for (int i = 0; i < 80000; i++) {
            arr[i] = (int)(Math.random()*80000);
        }
        Date before = new Date();
        System.out.println(before.getTime());
        ShellSort(arr);
        Date after = new Date();
        System.out.println(after.getTime());
        System.out.println(after.getTime()-before.getTime());
    }

快速排序

快速排序是对冒泡排序的改进

import java.util.Date;

public class QuickSort {

    public static void main(String[] args) {
        int arr[] = new int[8000000];
        for (int i = 0; i < 8000000; i++) {
            arr[i] = (int)(Math.random()*8000000);
        }
        Date before = new Date();
        System.out.println(before.getTime());
        quickSort(arr,0,arr.length-1);
        Date after = new Date();
        System.out.println(after.getTime());
        System.out.println(after.getTime()-before.getTime());
    }

    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+=1;
            }

            while (array[r] > pivot){
                r-=1;
            }

            if (l >= r){
                break;
            }

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

            if (array[l]==pivot){
                r--;
            }
            if (array[r] == pivot){
                l++;
            }
        }
        if (l==r){
            l++;
            r--;
        }
        if (left<l){
            quickSort(array,left,r);
        }
        if (right>r){
            quickSort(array,l,right);
        }
    }
}

归并排序（分治策略）

public class MergeSort {
    public static void main(String[] args) {
        int[] arr = {8,4,5,7,1,3,6,2};
        int temp[] = new int[arr.length];
        mergeSort(arr,0,arr.length-1,temp);
        System.out.println(Arrays.toString(arr));
    }

    public static void mergeSort(int[] array,int left,int right,int[] temp) {
        if (left<right){
            int mind = (left+right)/2;
            mergeSort(array, left, mind, temp);
            mergeSort(array, mind+1, right, temp);
            merge(array,left,mind,right,temp);
        }
    }

    //实现合并的过程
    public static void merge(int[] array,int left,int mind,int right,int[] temp){
        int l = left;
        int r = mind+1;
        int t = 0;
        //第一步
        while (l <= mind && r <= right){
            if (array[l]<array[r]){
                temp[t] = array[l];
                l++;
            }else {
                temp[t] = array[r];
                r++;
            }
            t++;
        }
        //第二步
        while (l<=mind){
            temp[t] = array[l];
            l++;
            t++;
        }
        while (r<=right){
            temp[t] = array[r];
            r++;
            t++;
        }
        //第三步
        t = 0;
        int tempLeft = left;
        while (tempLeft<=right){
            array[tempLeft] = temp[t];
            t++;
            tempLeft++;
        }
    }
}