排序算法

• Main

package sort;

import java.util.Random;

public class Main {

    static final int NUMS_SIZE = 10;
    static final int RANDOM_MAX = 100;

    static ISort sorter;

    public static void main(String[] args) {
        int[] nums = initNums();
        show(nums);

        // 交换排序
        // sorter = new MaoPaoImpl();
        // sorter = new KuaiPaiImpl();

        // 插入排序
        // sorter = new ZhiJieInsertImpl();
        // sorter = new XiErImpl();

        // 选择排序
        // sorter = new SimpleChooseImpl();
        // sorter = new HeapSortImpl();
        
        // 归并排序
        sorter = new GuibingImpl();

        sorter.sort(nums);
        show(nums);
    }

    private static int[] initNums() {
        Random random = new Random();
        int[] nums = new int[NUMS_SIZE];
        for (int i = 0; i < NUMS_SIZE; i++) {
            nums[i] = random.nextInt(RANDOM_MAX);
        }
        return nums;
    }

    public static void show(int[] nums) {
        System.out.print("[");
        for (int i = 0; i < nums.length; i++) {
            System.out.print(nums[i]);
            if (i == nums.length - 1) {
                System.out.print("]");
            } else {
                System.out.print(",");
            }
        }
        System.out.println();
    }

    public static void changePosition(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }

    public static void insert(int[] nums, int from, int to, int step) {
        int num = nums[from];

        for (int i = from; i > to; i -= step) {
            nums[i] = nums[i - step];
        }
        nums[to] = num;
    }

}

• 冒泡排序

package sort;

public class MaoPaoImpl implements ISort {

    @Override
    public void sort(int[] nums) {

        for (int i = 0; i < nums.length - 1; i++) {
            for (int j = 0; j < nums.length - i - 1; j++) {
                if (nums[j] > nums[j + 1]) {
                    Main.changePosition(nums, j, j + 1);
                }
            }
        }

    }
}

• 快速排序

package sort;

public class KuaiPaiImpl implements ISort {

    @Override
    public void sort(int[] nums) {
        split(nums, 0, nums.length - 1);
    }

    void split(int[] nums, int left, int right) {
        if (right - left <=0) {
            return;
        }
        
        int index = left;
        int i = left;
        int j = right;

        while (left < right) {
            while (left < right && nums[index] <= nums[right]) {
                right--;
            }
            Main.changePosition(nums, index, right);
            index = right;

            while (left < right && nums[index] >= nums[left]) {
                left++;
            }
            Main.changePosition(nums, left, index);
            index = left;
        }

        Main.show(nums);
        
        split(nums, i, index-1);

        split(nums, index+1, j);

    }

}

• 直接插入排序

package sort;

public class ZhiJieInsertImpl implements ISort {

    @Override
    public void sort(int[] nums) {
        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] < nums[j]) {
                    Main.insert(nums, i, j, 1);
                    break;
                }
            }
            Main.show(nums);
        }
    }

}

• 希尔排序

package sort;

public class XiErImpl implements ISort {

    @Override
    public void sort(int[] nums) {
        int step = nums.length / 2;
        while (step != 0) {
            System.out.println(step);
            sort(nums, step);
            step /= 2;
        }
    }

    void sort(int[] nums, int step) {
        for (int i = 0; i < step; i++) {
            sort(nums, step, i);
            Main.show(nums);
        }
    }

    void sort(int[] nums, int step, int begin) {
        for (int i = begin + step; i < nums.length; i += step) {
            for (int j = begin; j < i; j += step) {
                if (nums[i] < nums[j]) {
                    Main.insert(nums, i, j, step);
                }
            }
        }
    }

}

• 简单选择排序

package sort;

public class SimpleChooseImpl implements ISort {

    @Override
    public void sort(int[] nums) {

        for (int i = 0; i < nums.length; i++) {
            int minIndex = findMin(nums, i);
            Main.changePosition(nums, i, minIndex);
        }

    }

    private int findMin(int[] nums, int begin) {
        int min = begin;
        for (int i = begin + 1; i < nums.length; i++) {
            if (nums[i] < nums[min]) {
                min = i;
            }
        }
        return min;
    }

}

• 堆排序

package sort;

public class HeapSortImpl implements ISort {

    @Override
    public void sort(int[] nums) {
        int index = nums.length - 1;
        while (index != 0) {
            buildHeap(nums, index);
            Main.changePosition(nums, 0, index);
            index--;
        }
    }

    void buildHeap(int[] nums, int last) {
        for (int i = last; i > 0; i--) {
            if (i % 2 == 0) {
                if (nums[i] > nums[(i - 1) / 2]) {
                    Main.changePosition(nums, i, (i - 1) / 2);
                }
            } else {
                if (nums[i] > nums[i / 2]) {
                    Main.changePosition(nums, i, i / 2);
                }
            }
        }
    }

}

• 归并排序

package sort;

public class GuibingImpl implements ISort {

    @Override
    public void sort(int[] nums) {
        sort(nums, 0, nums.length - 1);
    }

    void sort(int[] nums, int left, int right) {
        if (left >= right) {
            return;
        }

        int middle = (left + right) / 2;
        sort(nums, left, middle);
        sort(nums, middle + 1, right);

        merge(nums, left, middle, right);
    }

    private void merge(int[] nums, int left, int middle, int right) {
        int[] tmp = new int[right - left + 1];
        int tmp_index = 0;
        int array1_left = left;
        int array1_right = middle;
        int array2_left = middle + 1;
        int array2_right = right;

        while (array1_left <= array1_right && array2_left <= array2_right) {

            while (array1_left <= array1_right && nums[array1_left] < nums[array2_left]) {
                tmp[tmp_index] = nums[array1_left];
                tmp_index++;
                array1_left++;
            }

            while (array2_left <= array2_right && nums[array2_left] < nums[array1_left]) {
                tmp[tmp_index] = nums[array2_left];
                tmp_index++;
                array2_left++;
            }
        }

        while (array2_left <= array2_right) {
            tmp[tmp_index] = nums[array2_left];
            tmp_index++;
            array2_left++;
        }

        while (array1_left <= array1_right) {
            tmp[tmp_index] = nums[array1_left];
            tmp_index++;
            array1_left++;
        }

        for (int i = left, j = 0; i <= right; i++, j++) {
            nums[i] = tmp[j];
        }

    }

}