希尔排序 快速排序 归并排序 Java实现

希尔排序 快速排序 归并排序 Java实现

1.希尔排序

将数组分成n组，n/2组，n/4组...1组，在每次分组后在组内进行排序。最后得到有序的数组

//通过交换的方式实现
public void sort(int[] arr) {
        int temp = 0;
        for (int gap = arr.length / 2; gap > 0; gap /= 2) {

            for (int i = gap; i < arr.length; i++) {
                for (int j = i - gap; j >= 0; j -= gap) {
                    if (arr[j] > arr[j + gap]) {
                        temp = arr[j];
                        arr[j] = arr[j + gap];
                        arr[j + gap] = temp;
                    }
                }
            }
        }
    }
//通过插入的方式实现
public void sort(int[] arr) {
        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < arr.length; i++) {
                int index = i;
                int insertValue = arr[index];
                while (index - gap >= 0 && insertValue > arr[index - gap]) {
                        arr[index] = arr[index - gap];
                        index -= gap;
                    }
                    arr[index] = insertValue;
                }


        }
    }

2.快速排序

首先确定一个基准，将比该基准大的变量均放在右边，比基准小的变量放在左边。再循环这个过程。

    public static void sort(int[] arr,int left,int right) {
        int pivot = arr[left];
        int l = left;
        int r = right;
        while (r > l)
        {
            while (arr[r] >= pivot && l < r)
            {
                r--;
            }
            arr[l] = arr[r];
            while (arr[l] <= pivot && l < r)
            {
                l++;
            }
            arr[r] = arr[l];
        }
        arr[l] = pivot;
        if (l > left)
        {
            sort(arr,left,l-1);
        }
        if (right > l)
        {
            sort(arr,l+1,right);
        }

    }

3.归并排序

基本思想是分治，先分：将数组每次分为原来的一半，直到无法再分为止。再按照原来的路径进行合并，合并时进行排序，最后得到一个有序的数组。

 public static void sort(int[] arr,int left,int right,int[] temp)
    {
    if (left < right)
    {
        int mid = (left+right)/2;
        sort(arr,left,mid,temp);
        sort(arr,mid+1,right,temp);
        merge(arr,left,mid,right,temp);
        System.out.println(Arrays.toString(arr));
    }

    }

    public static void merge(int[] arr, int left, int mid, int right, int[] temp) {
        int l = left;
        int r = mid+1;
        int t = 0;
        while (l <= mid&&r <= right)
        {
            if (arr[l] < arr[r])
            {
                temp[t] = arr[l];
                t++;
                l++;
            }else
            {
                temp[t] = arr[r];
                t++;
                r++;
            }
        }
        while (l <= mid)
        {
            temp[t] = arr[l];
            t++;
            l++;
        }
        while (r <= right)
        {
            temp[t] = arr[r];
            t++;
            r++;
        }
        t = 0;
        int tLeft = left;
        while (tLeft <= right)
        {
            arr[tLeft] = temp[t];
            t++;
            tLeft++;
        }
    }