算法|排序 冒泡、选择、插入、快排、归并

冒泡、选择、插入、快速

import java.util.Arrays;

public class Sort {

    public static void main(String[] args) {
        int[] nums = {3, 4,3232,22,3423,223,323};
        Sort sort = new Sort();
        sort.quickSort2(nums, 0, nums.length - 1);

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


    /**
     * 交换两个数
     * @param nums
     * @param i
     * @param j
     */
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];;
        nums[i] = nums[j];
        nums[j] = temp;
    }
    /**
     * 冒泡排序1
     * @param nums
     */
    private void bublleSort1(int[] nums) {
        int length = nums.length;
        for (int i = 0; i < length - 1; i++){
            for (int j = 0; j < length - 1 - i; j++){
                if (nums[j] > nums[j + 1]) {
                    swap(nums, j, j + 1);
                }
            }
        }
    }

    /**
     * 冒泡排序2 优化提前结束条件
     * @param nums
     */
    private void bublleSort2(int[] nums) {
        int length = nums.length;
        for (int i = 0; i < length - 1; i++){
            boolean swapFlag = false;
            for (int j = 0; j < length - 1- i; j++){
                if (nums[j] > nums[j + 1]) {
                    swap(nums, j, j + 1);
                    swapFlag = true;
                }
            }
            if (!swapFlag) return;
        }
    }

    /**
     * 冒泡排序3
     * @param nums
     */
    private void bublleSort3(int[] nums) {
        int length = nums.length;
        int n = length - 1;
       while (true) {
           int last = 0;
           for (int i = 0; i < n; i++){
               if (nums[i] > nums[i + 1]) {
                   swap(nums, i, i + 1);
                   last = i;
               }
           }
           n = last;
           if (n == 0) break;
       }
    }

    /**
     * 选择排序
     * @param nums
     */
    private void selectSort(int[] nums) {
        int length = nums.length;
        for (int i = 0; i < length - 1; i++) {
            int s = i;
            for (int j = i + 1; j < length; j++){
                if (nums[s] > nums[j]) {
                    s = j;
                }
            }
            if (s != i) {
                swap(nums, s, i);
            }
        }
    }

    /**
     * 插入排序
     * @param nums
     */
    private void insertSort(int[] nums) {
        int length = nums.length;
        for (int i = 1; i < length; i++){
            int temp = nums[i];
            int j = i;
            for (; j > 0 && nums[j - 1] > temp; j--){
                nums[j] = nums[j - 1];
            }
            nums[j] = temp;
        }
    }

    /**
     * 快速排序 单路排序
     * @param nums
     * @param left
     * @param right
     */
    private void quickSort1(int[] nums, int left, int right){
        if (left >= right) return;
        int pi = partion1(nums, left, right);
        quickSort1(nums, left, pi - 1);
        quickSort1(nums, pi + 1, right);
    }

    /**
     * 快速排序1 单路排序partion
     * @param nums
     * @param left
     * @param right
     * @return
     */
    private int partion1(int[] nums, int left, int right) {
        int pv = nums[right];
        int j = left;
        for (int i = left; i < right; i++){
            if (nums[i] < pv) {
                //比基准点小
                swap(nums, i, j);
                j++;
            }
        }
        //基准点和中间的交换
        swap(nums, j, right);
        return j;
    }

    /**
     * 快速排序 双路排序
     * @param nums
     * @param left
     * @param right
     */
    private void quickSort2(int[] nums, int left, int right) {
        if (left >= right) return;
        int pi = partion2(nums, left, right);
//        System.out.println(pi);
        quickSort2(nums, left, pi - 1);
        quickSort2(nums, pi + 1, right);
    }

    /**
     * 双路快排
     * @param nums
     * @param left
     * @param right
     * @return
     */
    private int partion2(int[] nums, int left, int right) {
        int i = left;
        int j = right;
        int pv = nums[left];
        while (i < j) {
            while (i < j && nums[j] > pv) {
                j--;
            }
            while (i < j && nums[i] <= pv){
                i++;
            }

            swap(nums, i, j);
        }
        swap(nums, left, i);
        return i;
    }

}

/**
     * 归并排序
     * @param nums
     * @param left
     * @param right
     */
    private void mergeSort(int[] nums, int left, int right) {
        if (left >= right) return;
        int mid = left + (right - left) / 2;
        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);
        merger(nums, left, mid, right);
    }

    /**
     * 归并排序归并过程
     * @param nums
     * @param left
     * @param mid
     * @param right
     */
    private void merger(int[] nums, int left, int mid, int right) {
        //备份一份
        int[] temp = new int[right - left + 1];
        for (int i = 0; i < temp.length; i++) {
            temp[i] = nums[left + i];
        }
        int k = left;
        int j = mid + 1;
        //排序
        for (int i = left; i <= right; i++){
            if (k <= mid && j <= right) {
                if (temp[k - left] < temp[j - left]) {
                    nums[i] = temp[k - left];
                    k++;
                } else {
                    nums[i] = temp[j - left];
                    j++;
                }
            } else if (k > mid) {
                nums[i] = temp[j - left];
                j++;
            } else {
                nums[i] = temp[k - left];
                k++;
            }
        }
    }