一、排序介绍

排序,是将一组数据按照指定顺序排列的过程。

1.1 分类

image.png

内部排序

将需要处理的所有数据都加载到内存中进行排序。

外部排序

数据量过大,无法全部加载进内存,需要借助外部存储进行排序。

二、冒泡排序

package a06.sort;

import java.util.Arrays;

public class BubbleSort {
    public static void main(String[] args) {
        int[] arr = {2, 6, 9, 3, 8, 1, -4};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void sort(int[] arr) {
        //冒泡排序,相邻两个元素依次进行对比,将大的元素交换到后面


        //标志是否已经有序
        boolean flag;

        //一共进行数组大小-1次大循环
        for (int i = 0; i < arr.length - 1; i++) {
            flag = true;
            for (int j = 0; j < arr.length - i - 1; j++) {
                //相邻两个元素进行比较
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    flag = false;
                }
            }
            if(flag){
                break;
            }
        }
    }
}

三、选择排序

package a06.sort;

import java.util.Arrays;

public class SelectSort {
    public static void main(String[] args) {
        int[] arr = {2, 6, 9, 3, 8, 1, -4};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }

    private static void sort(int[] arr) {
        //选择排序,每次从未排序列中选择一个最小的放入已排序列。
        for (int i = 0; i < arr.length - 1; i++) {
            int minIndex = i;
            for (int j = i; j < arr.length; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }
}

四、插入排序

4.1 普通插入排序

4.2 希尔排序

package example.test;

import java.util.Arrays;

/**
 * @author Tao
 * @Date 2020/10/16
 * @Time 14:51
 */
public class InsertSort {
    public static void main(String[] args) {
        //            j  i
        int[] arr = {-1, 0, 8, 1, 4, 9, 2, 3, 7};
        System.out.println(Arrays.toString(arr) + "\n");
        sort(arr);
        System.out.println("\n" + Arrays.toString(arr));

        System.out.println("\n----------\n希尔排序\n----------");
        int[] arr2 = {-1, 0, 8, 1, 4, 9, 2, 3, 7};
        System.out.println(Arrays.toString(arr2));
        shell(arr2);
        System.out.println("\n" + Arrays.toString(arr2));

    }

    private static void shell(int[] arr) {
//                 j           i
//         {-1, 0, 8, 1, 4, 9, 2, 3, 7}
//        希尔排序,插入排序的改进版本,将待排序的列按间隙分组,每组调用插入排序,则小元素被取到前边。
        for (int group = arr.length / 2; group > 0; group /= 2) {
            System.out.println("group="+group);
//            i:未排序
            for (int i = group; i < arr.length; i++) {
                int j=i;
                if(arr[j]<arr[j-group]){
                    int temp = arr[i];
                    while(j-group>=0 && temp<arr[j-group]){
                        arr[j] = arr[j-group];
                        j-=group;
                        System.out.println(Arrays.toString(arr));
                    }
                    arr[j]=temp;
                    System.out.println(Arrays.toString(arr));
                }
            }
        }
    }


    private static void sort(int[] arr) {
//                        i
//         {-4, -1, 3, 4, 1, 8, 9, 2, 7}
//        插入排序,每次从未选择的取出一个,插入到已排序列
//        i:未排序开始索引
        for (int i = 1; i < arr.length; i++) {
            int j=i;
            if(arr[j]<arr[j-1]){
                int temp = arr[i];
                while(j-1>=0 && temp<arr[j-1]){
                    arr[j] = arr[j-1];
                    j--;
                    System.out.println(Arrays.toString(arr));
                }
                arr[j]=temp;
                System.out.println(Arrays.toString(arr));
            }
        }
    }


}

五、快速排序

package a06.sort;

import java.util.Arrays;

public class QuickSort {
    public static void main(String[] args) {
        int[] arr = {2, 6, 9, 3, 8, 1, -4};
        sort(arr, 0, arr.length-1);
        System.out.println(Arrays.toString(arr));
    }

    private static void sort(int[] arr, int start, int end) {
        //快速排序,挖坑填数+分治法
        if (start >= end) {
            return;
        }

        int i = start;
        int j = end;
        int flag = arr[start];
        // 从右向左找第一个小于x的数
        while (i < j && arr[j] >= flag) {
            j--;
        }
        if (i < j) {
            arr[i] = arr[j];
            i++;
        }
        // 从左向右找第一个大于等于x的数
        while (i < j && arr[i] <= flag) {
            i++;
        }
        if (i < j) {
            arr[j] = arr[i];
            j--;
        }
        arr[i] = flag;
        sort(arr,start,i-1);
        sort(arr,i+1,end);
    }

}

六、归并排序

package a06.sort;

import java.util.Arrays;

public class MergeSort {
    //归并排序,分治法——先分后治
    public static void main(String[] args) {
        int[] arr = {2, 6, 9, 3, 8, 1, -4};
        sort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }

    private static void sort(int[] arr, int start, int end) {
        if (start >= end) {
            return;
        }
        int middle = (start + end) / 2;
        sort(arr, start, middle);
        sort(arr, middle + 1, end);
        merge(arr, start, middle, middle + 1, end);
    }

    private static void merge(int[] arr, int lStart, int lEnd, int rStart, int rEnd) {
        int[] result = new int[rEnd - lStart + 1];
        int index = 0;
        int left = lStart;
        while (lStart <= lEnd && rStart <= rEnd) {
            if (arr[lStart] <= arr[rStart]) {
                result[index++] = arr[lStart++];
            } else {
                result[index++] = arr[rStart++];
            }
        }
        while (lStart <= lEnd) {
            result[index++] = arr[lStart++];
        }
        while (rStart <= rEnd) {
            result[index++] = arr[rStart++];
        }
        index = 0;
        for (int i = left; i <= rEnd; i++) {
            arr[i] = result[index++];
        }
    }
}

七、归并排序

package a06.sort;

import java.util.Arrays;

public class RadixSort {
    public static void main(String[] args) {
        int[] arr = {2, 6, 9, 3, 8, 1, 4};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }

    private static void sort(int[] arr) {
        //基数排序,将整数按位数切割成不同的数字

        //得到最大值位数
        int max = arr[0];
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
        }
        int maxSize = (max + "").length();

        //由整数0-9组成的桶,每个桶都是一个数组
        int[][] bucket = new int[10][arr.length];

        //统计桶中元素的个数
        int[] count = new int[10];

        //位数表示的值,从个位数开始


        //入桶
        for (int i = 0, temp = 1; i < maxSize; i++, temp *= 10) {
            for (int j = 0; j < arr.length; j++) {
                int element = arr[j] / temp % 10;
                bucket[element][count[element]] = arr[j];
                count[element]++;
            }

            //出桶
            int index = 0;
            for (int k = 0; k < count.length; k++) {
                if (count[k] != 0) {
                    for (int l = 0; l < count[k]; l++) {
                        arr[index++] = bucket[k][l];
                    }
                }
                count[k] = 0;
            }

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

七、对比

image.png
k:桶的个数

Q.E.D.

知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议