十大经典排序算法(Java)_java 十大排序

排序算法是《数据结构与算法》中最基本的算法之一。

十大经典排序算法(Java)

1. 冒泡排序 BubbleSort

public class BubbleSort {
    //冒泡排序
    public static void bubbleSort(int[] arr, boolean ascending) { //exchange标志表示为升序排序还是降序排序

        boolean flag = true; //加一个标志位，记录上一次是否发生了交换，如果是，我们则进行下一轮，如果没有，说明已经冒泡好了

        for (int i = 1; i < arr.length && flag; i++) { //控制次数，第几趟排序，只需要n-1趟，有交换时进行，只有flag=false就说明上一次一个元素都没有进行交换
            flag = false; //假定未交换
            for (int j = 0; j < arr.length - i; j++) {
                if (ascending ? arr[j] > arr[j + 1] : arr[j] < arr[j + 1]) { //控制升序还是降序
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    flag = true;
                }
            }
        }
    }

    //冒泡排序 -- 默认不传参升序
    public static void bubbleSort(int[] arr) {
        bubbleSort(arr, true);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

2. 选择排序 SelectSort

public class SelectSort {
    //直接选择排序
    public static void selectSort(int[] arr, boolean ascending) {
        for (int i = 0; i < arr.length; i++) {
            int m = i; //最小值或最小值的下标
            for (int j = i + 1; j < arr.length; j++) {
                if (ascending ? arr[j] < arr[m] : arr[j] > arr[m]) {
                    m = j; //找到待排序的数中最小或最大的那个数，记录下标
                }
            }
            //交换位置
            int temp = arr[i];
            arr[i] = arr[m];
            arr[m] = temp;

        }
    }

    public static void selectSort(int[] arr) {
        selectSort(arr, true);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

3. 插入排序 StraghtInsertSort

public class StraghtInsertSort {
    //插入排序  
    public static void straghtInsertSort(int[] arr, boolean ascending) {
        for (int i = 1; i < arr.length; i++) {
            int temp = arr[i];
            int j=0; //这就是那个合适的位置
            for (j = i - 1; j >= 0 && (ascending ? temp < arr[j] : temp > arr[j]); j--) {
                arr[j + 1] = arr[j];
            }
            arr[j + 1] = temp;
        }
    }
    
	public static void straghtInsertSort(int[] arr) {
        straghtInsertSort(arr, true);//默认进行升序
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

4. 希尔排序 ShellSort

public class ShellSort { 
    public static void shellSort(int[] arr,boolean ascending) {
        for(int d = arr.length/2;d>0;d/=2){
            for(int i=d;i< arr.length;i++){
                int temp = arr[i];
                int j=0;
                for(j=i-d;j>=0&&(ascending?temp<arr[j]:temp>arr[j]);j-=d){
                    arr[j+d]=arr[j];
                }
                arr[j+d] = temp;
            }
        }
    }
    
	public static void shellSort(int[] arr) {
        shellSort(arr,true);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

5. 归并排序

public class MergeSort {

    //归并排序
    public static void mergeSort(int []arr ,boolean ascending){
        int[] temp = new int[arr.length]; //在排序前，先建好一个长度等于原数组长度的临时数组，避免递归中频繁开辟空间
        mergeSort(arr,0,arr.length-1,temp,ascending);
    }
    public static void mergeSort(int []arr){
        mergeSort(arr,true);
    }

    public static void mergeSort(int []arr,int left,int right,int[] temp,boolean ascending){
        if(left<right){ //这里是递归结束的条件，我们是对半分，那当left==right的时候肯定大家都是只有一个元素了。

            //对半分，比如总长度是10，left=0，right=9，mid=4确实是中间分了，0~4，5~9
            //当长度9，left=0，right=8，mid=4，0~4，5~8
            int mid = left + (right-left)/2; // 防止越界的写法
            //int mid = (left+right)/2;

            mergeSort(arr,left,mid,temp,ascending); //左边归并排序，使得左子序列有序
            mergeSort(arr,mid+1,right,temp,ascending); //右边归并排序，使得右子序列有序

            merge(arr,left,mid,right,temp,ascending); //将两个有序子数组合并操作
        }
    }

    private static void merge(int[] arr,int left,int mid,int right,int[] temp,boolean ascending){
        int i = left; //左序列起始下标
        int j = mid+1; //右序列起始下标
        int t = 0; //临时数组指针
        while(i<=mid&&j<=right){
            if(ascending?arr[i]<arr[j]:arr[i]>arr[j]){ //比较两个序列第一个元素谁小，谁小先拷贝谁到temp，然后对应子序列下标加1
                temp[t++] = arr[i++];
            }else {
                temp[t++] = arr[j++];
            }
        }

        while(i<=mid){ //将左边剩余元素填充进temp中——左序列有一些数总是比右边的大的数
            temp[t++] = arr[i++];
        }

        while(j<=right){ //将右序列剩余元素填充进temp中——右序列有一些数总是比左边的大的数
            temp[t++] = arr[j++];
        }

        t = 0;

        //将temp中的元素全部拷贝到原数组中
        while(left<=right){
            arr[left++] = temp[t++];
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

6. 快速排序 QuickSort
7. 堆排序 HeapSort
8. 计数排序 CountSort
9. 桶排序 BucketSort
10. 基数排序 RadixSort

相关参考

https://www.runoob.com/w3cnote/ten-sorting-algorithm.html