排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。
我们这里说说八大排序就是内部排序。

快速排序:是目前基于比较的内部排序中被认为是最好的方法,当待排序的关键字是随机分布时,快速排序的平均时间最短;

插入排序:直接插入排序

package algorithm.sort;

import java.util.Random;

/**
 * @author 唐宋丶
 * @create 2020/9/20
 * <p>
 * (直接)插入排序(越接近正序性能越好)
 * 时间复杂度:平均O(N^2)、最坏O(N^2)、最好O(N)
 * 空间复杂度:O(1)
 * 稳定性:稳定
 * 复杂性:简单
 */
public class InsertSort {

    public void insertSort(int[] list) {
        //第0趟直接第一个元素
        System.out.format("第 0 趟:  %d\n", list[0]);

        for (int i = 1; i < list.length; i++) {
            int j;
            int temp = list[i];
            //如果比顺序的最后一个大,则直接不走for插入到最后面。否则比temp大元素后移
            for (j = i - 1; j >= 0 && temp < list[j]; j--) {
                list[j + 1] = list[j];
            }
            //temp为最小时j=-1
            list[j + 1] = temp;

            System.out.format("第 %d 趟:  ", i);
            printPart(list,0,i);
        }
    }

    public void printPart(int[] list, int begin, int end) {
        for (int i = 0; i < begin; i++) {
            System.out.print("   ");
        }
        for (int i = begin; i <= end; i++) {
            System.out.print(list[i] + "  ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        final int MAX_SIZE = 7;
        int[] array = new int[MAX_SIZE];
        Random random = new Random();
        for (int i = 0; i < MAX_SIZE; i++) {
            array[i] = random.nextInt(10);
        }

        InsertSort insert = new InsertSort();
        System.out.print("排序前:    ");
        insert.printPart(array, 0, array.length - 1);
        insert.insertSort(array);
        System.out.print("排序后:    ");
        insert.printPart(array, 0, array.length - 1);
    }
}

插入排序:希尔排序

package algorithm.sort;

import java.util.Random;

/**
 * @author 唐宋丶
 * @create 2020/9/20
 * <p>
 * 希尔排序(缩小增量排序、加强版的直接插入排序)
 * 时间复杂度:平均O(Nlog2N)、最坏O(N^1.5)
 * 空间复杂度:O(1)
 * 稳定性:不稳定
 * 复杂性:较复杂
 */
public class ShellSort {

    public void shellSort(int[] list) {
        //按步长gap分组,每组都进行直接插入排序
        int gap = list.length / 2;

        while (gap >= 1) {
            //调用直接插入排序的算法,除了此处i++,其余1都替换为gap
            for (int i = gap; i < list.length; i++) {
                int j;
                int temp = list[i];

                for (j = i - gap; j >= 0 && temp < list[j]; j -= gap) {
                    list[j + gap] = list[j];
                }
                list[j + gap] = temp;
            }
            System.out.format("gap = %d:  ", gap);
            printAll(list);
            gap /= 2;
        }
    }

    public void printAll(int[] list) {
        for (int value : list) {
            System.out.print(value + "  ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        final int MAX_SIZE = 7;
        int[] array = new int[MAX_SIZE];
        Random random = new Random();
        for (int i = 0; i < MAX_SIZE; i++) {
            array[i] = random.nextInt(10);
        }

        ShellSort shell = new ShellSort();
        System.out.print("排序前:    ");
        shell.printAll(array);
        shell.shellSort(array);
        System.out.print("排序后:    ");
        shell.printAll(array);
    }
}

选择排序:简单选择排序

package algorithm.sort;

import java.util.Random;

/**
 * @author 唐宋丶
 * @create 2020/9/20
 * <p>
 * 希尔排序(缩小增量排序、加强版的直接插入排序)
 * 时间复杂度:平均O(Nlog2N)、最坏O(N^1.5)
 * 空间复杂度:O(1)
 * 稳定性:不稳定
 * 复杂性:较复杂
 */
public class ShellSort {

    public void shellSort(int[] list) {
        //按步长gap分组,每组都进行直接插入排序
        int gap = list.length / 2;

        while (gap >= 1) {
            //调用直接插入排序的算法,除了此处i++,其余1都替换为gap
            for (int i = gap; i < list.length; i++) {
                int j;
                int temp = list[i];

                for (j = i - gap; j >= 0 && temp < list[j]; j -= gap) {
                    list[j + gap] = list[j];
                }
                list[j + gap] = temp;
            }
            System.out.format("gap = %d:  ", gap);
            printAll(list);
            gap /= 2;
        }
    }

    public void printAll(int[] list) {
        for (int value : list) {
            System.out.print(value + "  ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        final int MAX_SIZE = 7;
        int[] array = new int[MAX_SIZE];
        Random random = new Random();
        for (int i = 0; i < MAX_SIZE; i++) {
            array[i] = random.nextInt(10);
        }

        ShellSort shell = new ShellSort();
        System.out.print("排序前:    ");
        shell.printAll(array);
        shell.shellSort(array);
        System.out.print("排序后:    ");
        shell.printAll(array);
    }
}

选择排序:堆排序

package algorithm.sort;

import java.util.Random;

/**
 * @author 唐宋丶
 * @create 2020/9/20
 * <p>
 * 堆排序
 * 时间复杂度:平均O(Nlog2N)、最坏O(Nlog2N)、最好O(Nlog2N)
 * 空间复杂度:O(1)
 * 稳定性:不稳定
 * 复杂性:较复杂
 */
public class HeapSort {

    /**
     * 建立初始堆,只需符合大根堆即可
     */
    public void heapAdjust(int[] array, int parent, int length) {
        int temp = array[parent];
        int child = 2 * parent + 1;

        while (child < length) {
            if (child + 1 < length && array[child] < array[child + 1]) {
                child++;
            }
            if (temp >= array[child]) {
                break;
            }
            array[parent] = array[child];

            //针对重新调整为大根堆时
            parent = child;
            child = 2 * parent + 1;
        }
        array[parent] = temp;
    }

    public void heapSort(int[] list) {
        //循环建立初始堆,parent为最后一个根节点(自下而上)
        for (int i = list.length / 2; i >= 0; i--) {
            heapAdjust(list, i, list.length);
        }

        //堆顶和末尾交换,n-1次排序
        for (int i = list.length - 1; i > 0; i--) {
            int temp = list[i];
            list[i] = list[0];
            list[0] = temp;

            //重构堆(自上而下)
            heapAdjust(list, 0, i);
            System.out.format("第 %d 趟:  ", list.length - i);
            printPart(list, 0, list.length - 1);
        }
    }

    public void printPart(int[] list, int begin, int end) {
        for (int i = 0; i < begin; i++) {
            System.out.print("   ");
        }
        for (int i = begin; i <= end; i++) {
            System.out.print(list[i] + "  ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        final int MAX_SIZE = 7;
        int[] array = new int[MAX_SIZE];
        Random random = new Random();
        for (int i = 0; i < MAX_SIZE; i++) {
            array[i] = random.nextInt(10);
        }

        HeapSort heap = new HeapSort();
        System.out.print("排序前:   ");
        heap.printPart(array, 0, array.length - 1);
        heap.heapSort(array);
        System.out.print("排序后:   ");
        heap.printPart(array, 0, array.length - 1);
    }
}

交换排序:冒泡排序

package algorithm.sort;

import java.util.Random;

/**
 * @author 唐宋丶
 * @create 2020/9/18
 * <p>
 * 冒泡排序(越接近正序性能越好)
 * 时间复杂度:平均O(N^2)、最坏O(N^2)、最好O(N)
 * 空间复杂度:O(1)
 * 稳定性:稳定
 * 复杂性:简单
 */
public class BubbleSort {

    public void bubbleSort(int[] list) {
        int temp;

        //从后往前冒泡,前面有大的就交换
        for (int i = 0; i < list.length - 1; i++) {
            for (int j = list.length - 1; j > i; j--) {
                if (list[j - 1] > list[j]) {
                    temp = list[j - 1];
                    list[j - 1] = list[j];
                    list[j] = temp;
                }
            }
            System.out.format("第 %d 趟:  ", i);
            printAll(list);
        }
    }

    /**
     * 优化:加入标志性变量exchange,用于标志某一趟排序过程中是否有数据交换。
     * 如果进行某一趟排序时并没有进行数据交换,则说明所有数据已经有序,可立即结束排序。
     */
    public void bubbleSort2(int[] list) {
        int temp;
        boolean bChange;

        for (int i = 0; i < list.length - 1; i++) {
            bChange = false;
            for (int j = list.length - 1; j > i; j--) {
                if (list[j - 1] > list[j]) {
                    temp = list[j - 1];
                    list[j - 1] = list[j];
                    list[j] = temp;
                    bChange = true;
                }
            }
            if (!bChange) {
                break;
            }

            System.out.format("第 %d 趟:  ", i);
            printAll(list);
        }
    }

    public void printAll(int[] list) {
        for (int value : list) {
            System.out.print(value + "  ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        final int MAX_SIZE = 7;
        int[] array = new int[MAX_SIZE];
        Random random = new Random();
        for (int i = 0; i < MAX_SIZE; i++) {
            array[i] = random.nextInt(10);
        }

        BubbleSort bubble = new BubbleSort();
        System.out.print("排序前:    ");
        bubble.printAll(array);
//        bubble.bubbleSort(array);
        bubble.bubbleSort2(array);
        System.out.print("排序后:    ");
        bubble.printAll(array);
    }
}

交换排序:快速排序

package algorithm.sort;

import java.util.Random;

/**
 * @author 唐宋丶
 * @create 2020/9/20
 * <p>
 * 快速排序(越随机性能越好)
 * 时间复杂度:平均O(Nlog2N)、最坏O(N^2)、最好O(Nlog2N)
 * 空间复杂度:平均O(logN)、就地快排O(1)、递归平分数组最优O(logN)、递归最差退为冒泡O(N)
 * 稳定性:不稳定(相等元素可能会因为分区而交换顺序)
 * 复杂性:较复杂
 */
public class QuickSort {

    public int division(int[] list, int left, int right) {
        int base = list[left];
        //不管有没有找到,只要碰头就结束,再递归成左右两部分(没找到情况下其中一部分为空)
        while (left < right) {
            //先从右边开始找
            while (left < right && list[right] >= base) {
                right--;
            }
            list[left] = list[right];
            //再从左开始找
            while (left < right && list[left] <= base) {
                left++;
            }
            list[right] = list[left];
        }
        //左边初始给右边找到的,右边找到的位置给左边找到的位置,左边找到的位置给base
        list[left] = base;
        return left;
    }

    public void quickSort(int[] list, int left, int right) {
        if (left < right) {
            int base = division(list, left, right);
            System.out.format("base = %d:  ", list[base]);
            printPart(list, left, right);

            quickSort(list, left, base - 1);
            quickSort(list, base + 1, right);
        }
    }

    public void printPart(int[] list, int begin, int end) {
        for (int i = 0; i < begin; i++) {
            System.out.print("   ");
        }
        for (int i = begin; i <= end; i++) {
            System.out.print(list[i] + "  ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        final int MAX_SIZE = 7;
        int[] array = new int[MAX_SIZE];
        Random random = new Random();
        for (int i = 0; i < MAX_SIZE; i++) {
            array[i] = random.nextInt(10);
        }

        QuickSort quick = new QuickSort();
        System.out.print("排序前:     ");
        quick.printPart(array, 0, array.length - 1);
        quick.quickSort(array, 0, array.length - 1);
        System.out.print("排序后:     ");
        quick.printPart(array, 0, array.length - 1);
    }
}

归并排序

package algorithm.sort;

import java.util.Random;

/**
 * @author 唐宋丶
 * @create 2020/9/21
 *
 * 归并排序
 * 时间复杂度:平均O(Nlog2N)、最坏O(Nlog2N)、最好O(Nlog2N)
 * 空间复杂度:O(n)
 * 稳定性:稳定
 * 复杂性:较复杂
 */
public class MergeSort {

    /**
     * 两段小数组合成一个大数组
     * [low,mid][mid+1,high] -> [low,high]
     */
    public void Meger(int[] array, int low, int mid, int high) {
        //i第一段数组下标、j第二段数组下标、array2临时大数组、k大数组下标
        int i = low;
        int j = mid + 1;
        int k = 0;
        int[] array2 = new int[high - low + 1];

        //存在两个小数组可能不等长,扫描完一个后停止
        while (i <= mid && j <= high) {
            //从小到大合并两数组
            if (array[i] <= array[j]) {
                array2[k++] = array[i++];
            } else {
                array2[k++] = array[j++];
            }
        }

        while (i <= mid) {
            array2[k++] = array[i++];
        }

        while (j <= high) {
            array2[k++] = array[j++];
        }

        for (k = 0, i = low; i <= high; i++, k++) {
            array[i] = array2[k];
        }
    }

    /**
     * gap为数组[low,mid][mid+1,high] -> [low,high]宽度
     * 2 * gap = high - low + 1;  (1 2 4 8 ...)
     */
    public void mergePass(int[] array, int gap, int length) {
        int i;
        //两个长度相等时合并(2 2 1 -> 4 1 -> 5)
        for (i = 0; i + 2 * gap - 1 < length; i += 2 * gap) {
            Meger(array, i, i + gap - 1, i + 2 * gap - 1);
        }

        //不够合并时(2 2 2 1 -> 4 3 -> 7)
        if (i + gap - 1 < length) {
            Meger(array, i, i + gap - 1, length - 1);
        }
    }

    public void megerSort(int[] list) {
        for (int gap = 1; gap < list.length; gap *= 2) {
            mergePass(list, gap, list.length);
            System.out.format("gap = %d:  ", gap);
            printAll(list);
        }
    }

    public void printAll(int[] list) {
        for (int value : list) {
            System.out.print(value + "  ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        final int MAX_SIZE = 7;
        int[] array = new int[MAX_SIZE];
        Random random = new Random();
        for (int i = 0; i < MAX_SIZE; i++) {
            array[i] = random.nextInt(10);
        }

        MergeSort merge = new MergeSort();
        System.out.print("排序前:    ");
        merge.printAll(array);
        merge.megerSort(array);
        System.out.print("排序后:    ");
        merge.printAll(array);
    }
}

基数排序

package algorithm.sort;

/**
 * @author 唐宋丶
 * @create 2020/9/21
 *
 * 基数排序
 * 时间复杂度:平均O(d(n+r))、最坏O(d(n+r))、最好O(d(n+r))  r为基数,d为位数
 * 空间复杂度:O(n+r)
 * 稳定性:稳定
 * 复杂性:较复杂
 */
public class RadixSort {

    // 获取x这个数的d位数上的数字
    // 比如获取123的1位数,结果返回3
    public int getDigit(int x, int d) {
        int a[] = {
                1, 1, 10, 100
        }; // 本实例中的最大数是百位数,所以只要到100就可以了
        return ((x / a[d]) % 10);
    }

    public void radixSort(int[] list, int begin, int end, int digit) {
        final int radix = 10; // 基数
        int i = 0, j = 0;
        int[] count = new int[radix]; // 存放各个桶的数据统计个数
        int[] bucket = new int[end - begin + 1];

        // 按照从低位到高位的顺序执行排序过程
        for (int d = 1; d <= digit; d++) {

            // 置空各个桶的数据统计
            for (i = 0; i < radix; i++) {
                count[i] = 0;
            }

            // 统计各个桶将要装入的数据个数
            for (i = begin; i <= end; i++) {
                j = getDigit(list[i], d);
                count[j]++;
            }

            // count[i]表示第i个桶的右边界索引
            for (i = 1; i < radix; i++) {
                count[i] = count[i] + count[i - 1];
            }

            // 将数据依次装入桶中
            // 这里要从右向左扫描,保证排序稳定性
            for (i = end; i >= begin; i--) {
                j = getDigit(list[i], d); // 求出关键码的第k位的数字, 例如:576的第3位是5
                bucket[count[j] - 1] = list[i]; // 放入对应的桶中,count[j]-1是第j个桶的右边界索引
                count[j]--; // 对应桶的装入数据索引减一
            }

            // 将已分配好的桶中数据再倒出来,此时已是对应当前位数有序的表
            for (i = begin, j = 0; i <= end; i++, j++) {
                list[i] = bucket[j];
            }
        }
    }

    public int[] sort(int[] list) {
        radixSort(list, 0, list.length - 1, 3);
        return list;
    }

    // 打印完整序列
    public void printAll(int[] list) {
        for (int value : list) {
            System.out.print(value + "\t");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[] array = {
                50, 123, 543, 187, 49, 30, 0, 2, 11, 100
        };
        RadixSort radix = new RadixSort();
        System.out.print("排序前:\t\t");
        radix.printAll(array);
        radix.sort(array);
        System.out.print("排序后:\t\t");
        radix.printAll(array);
    }
}
Last modification:September 22nd, 2020 at 08:41 pm
喵ฅฅ