十大排序算法Java实现

向右看齐 2022-12-29 02:25 152阅读 0赞

> 之前写了JavaScript实现的排序算法，因为社会的压迫233333，Java可能也得写写，所以就将这个放在这里来了，算法介绍看之前JavaScript那一篇播客吧，这里就只有代码。

> 我知道，给类起中文名是一个很不好的习惯，但我现在只是为了让自己找的时候比较方便。

> 我没写完，还有基数排序，但是我饿了，，，，干饭人！！！要干饭了！

> **一、冒泡排序（Bubble Sort）**

public class 冒泡排序 { 
        public static void main(String[] args) { 
            int[] arr = { 2,4,5,1,2,3,9,5,4,11,10};
    
            for (int i = 0; i < arr.length - 1; i++) { 
                for (int j = 1 ; j < arr.length - i; j++) { 
                    if (arr[j] < arr[j-1]){ 
                        int temp = arr[j];
                        arr[j] = arr[j-1];
                        arr[j-1] = temp;
                    }
                }
            }
    
            for (int i: arr) { 
                System.out.print(i + " ");
            }
        }
    }

> **二、快速排序（Quick Sort）**

import java.util.stream.StreamSupport;
    
    public class 快速排序 { 
        public static void main(String[] args) { 
            int[] num = { 5,2,8,6,-1,15,20,4,-2};
    
            int left = 0, right = num.length - 1;
    
            num = quickSort(num, left, right);
    
            for (int i = 0; i < num.length; i++) { 
                System.out.print(num[i] + " ");
            }
        }
    
        public static int[] quickSort(int[] num, int left, int right){ 
            if (left >= right)
                return num;
    
            int start = left, end = right, flag = left;
    
            while (left < right){ 
                //当队尾元素 >= 基准元素，向前挪动right
                while (left < right && num[right] >= num[flag])
                    right--;
    
                //当队尾元素 < 基准元素，进行位置交换，队尾元素成为新的基准元素
                //调整扫描顺序
                if (num[right] < num[flag]){ 
                    int temp = num[right];
                    num[right] = num[flag];
                    num[flag] = temp;
    
                    flag = right;
                }
    
                //当队首元素 <= 基准元素，向后挪动left
                while (left < right && num[left] <= num[flag])
                    left++;
    
                //当队首元素 > 基准元素，进行位置交换，队首元素成为新的基准元素
                //调整扫描顺序
                if (num[left] > num[flag]){ 
                    int temp = num[left];
                    num[left] = num[flag];
                    num[flag] = temp;
    
                    flag = left;
                }
    
            }
            quickSort(num,start,left - 1);
            quickSort(num,left + 1, end);
    
            return num;
        }
    }

> **三、选择排序（Select Sort）**

public class 选择排序 { 
        public static void main(String[] args) { 
            int[] num = { 5,-1,2,6,8,4,5,10,7};
    
            int minIndex;
            /* 选择最小数 */
            for (int i = 0; i < num.length; i++){ 
                minIndex = i;
                for (int j = i + 1; j < num.length; j++) { 
                    if (num[j] < num[minIndex])
                        minIndex = j;
                }
                int temp = num[i];
                num[i] = num[minIndex];
                num[minIndex] = temp;
            }
    
            for (int i = 0; i < num.length; i++) { 
                System.out.print(num[i] + " ");
            }
        }
    }

> **四、希尔排序（Shell Sort）**

public class 希尔排序 { 
        public static void main(String[] args) { 
            int[] num = { 5,1,2,-1,-2,3,10,7,6};
    
            int len = num.length;
            int i;
    
            for (int gap = len / 2; gap > 0; gap /= 2) { 
                // gap为间隔，初始为len/2；
                for (int p = gap; p < len; p++) { 
                    //组内进行插入排序
                    int temp = num[p];
                    for (i = p; i >= gap && num[i - gap] > temp; i -= gap) { 
                        num[i] = num[i - gap];
                    }
                    num[i] = temp;
                }
            }
    
            for (int j = 0; j < num.length; j++) { 
                System.out.print(num[j] + " ");
            }
        }
    }

> **五、插入排序（Insert Sort）**

public class 插入排序 { 
        public static void main(String[] args) { 
            int[] num = { 5,-1,2,6,2,8,10,4,-2};
            /* 默认第一位已排序，故从第二位开始遍历 */
            for (int i = 1; i < num.length; i++) { 
                int preIndex = i - 1, cur = num[i];
                /* 这里我之前将cur直接用num[i]来替代，但是后来才发现， 循环会改变目前num[i]的值，所以需要一个元素去保存当前所参与插入的值 */
                while (preIndex >= 0 && num[preIndex] > cur){ 
    
                    int temp = num[preIndex + 1];
                    num[preIndex + 1] = num[preIndex];
                    num[preIndex] = temp;
    
                    preIndex--;
                }
            }
    
            for (int i = 0; i < num.length; i++) { 
                System.out.print(num[i] + " ");
            }
        }
    }

> **六、归并排序（Merge Sort）**

import java.util.*;
    
    public class 归并排序 { 
        public static void main(String[] args) { 
            int[] num = { 5,2,-1,2,3,9,7,15,4};
    
            num = mergeSort(num);
            for (int i = 0; i < num.length; i++) { 
                System.out.print(num[i] + " ");
            }
        }
    
        public static int[] mergeSort(int[] num){ 
            int len = num.length;
    
            if (len < 2)
                return num;
    
            int mid = len / 2;
            //将数组以mid为界，进行切割
            int[] left = Arrays.copyOfRange(num, 0, mid);
            int[] right = Arrays.copyOfRange(num, mid, len);
    
            return merge(mergeSort(left), mergeSort(right));
        }
    
        public static int[] merge(int[] l, int[] r){ 
            List<Integer> res = new ArrayList<>();
            List<Integer> left = new ArrayList<>(l.length);
            List<Integer> right = new ArrayList<>(r.length);
    
            for (int i: l) { 
                left.add(i);
            }
            for (int i: r) { 
                right.add(i);
            }
    
            while (left.size() > 0 && right.size() > 0){ 
                if (left.get(0) <= right.get(0)){ 
                    res.add(left.get(0));
                    left.remove(0);
                }else{ 
                    res.add(right.get(0));
                    right.remove(0);
                }
            }
    
            //如果两边剩下了，那说明后面的值都比较大
            while (left.size() != 0){ 
                res.add(left.get(0));
                left.remove(0);
            }
            while (right.size() != 0){ 
                res.add(right.get(0));
                right.remove(0);
            }
    
            //这个方法我真的不是很熟悉，找了很久才找到比较好的list转int数组
            int[] ress = res.stream().mapToInt(i->i).toArray();
    
            return ress;
        }
    }

> **七、堆排序（Heap Sort）**

public class 堆排序 { 
        public static void main(String[] args) { 
            int[] num = { 20,-3,6,4,2,8,10,-5,7,8,3};
    
            num = heapSort(num);
    
            for (int i = 0; i < num.length; i++) { 
                System.out.print(num[i] +" ");
            }
        }
    
        public static int[] heapSort(int[] num){ 
            int len = num.length;
            for (int i = len / 2; i >= 0; i--){ 
                num = heapify(num, i);
            }
            return num;
        }
    
        public static int[] heapify(int[] num, int i){ 
            int len = num.length;
    
            int left = 2 * i + 1, right = 2 * i + 2;
            int largest = i;
    
            if (right < len && num[right] > num[largest])
                largest = right;
    
            if (left < len && num[left] > num[largest])
                largest = left;
    
            if (largest != i){ 
                int temp = num[i];
                num[i] = num[largest];
                num[largest] = temp;
    
                heapify(num, largest);
            }
            return num;
        }
    }

> **八、计数排序（Count Sort）**

public class 计数排序 { 
        public static void main(String[] args) { 
            int[] num = { 10,2,8,6,3,4,9,-1,2};
    
            num = countSort(num);
    
            for (int i = 0; i < num.length; i++) { 
                System.out.print(num[i] + " ");
            }
        }
    
        public static int[] countSort(int[] num){ 
            int min = num[0], max = num[0];
    
            //先找出最大最小值确定计数范围，所以这个方法对于数值区间跨度大的元素排序不太合适
            for (int i = 1; i < num.length; i++){ 
                if (num[i] < min)
                    min = num[i];
    
                if (num[i] > max)
                    max = num[i];
            }
    
            int len = max - min + 1;
            int temp[] = new int[len];
    
            //数字一出现，就将其对应的数组值+1，比如20，最大值为25，最小值为5，temp[20-5]++
            for (int i = 0; i < num.length; i++) { 
                temp[num[i] - min]++;
            }
    
            int k = 0;
            //对temp进行遍历，temp[i]的值就是数值i+min出现的次数
            for (int i = 0; i < len; i++) { 
                for (int j = temp[i]; j > 0; j--) { 
                    num[k] = i + min;
                    k++;
                }
            }
    
            return num;
        }
    }

> **九、桶排序（Bucket Sort）**

import java.util.ArrayList;
    import java.util.Collections;
    
    public class 桶排序 { 
        public static void main(String[] args) { 
            int[] num = { 5,-1,13,38,24,6,100,57};
    
            num = bucketSort(num);
    
            for (int i = 0; i < num.length; i++) { 
                System.out.print(num[i] + " ");
            }
        }
    
        public static int[] bucketSort(int[] num){ 
            if (num.length == 0)
                return num;
    
            int min = num[0], max = num[0];
    
            for (int i = 1; i < num.length; i++) { 
                if (num[i] < min)
                    min = num[i];
                else if(num[i] > max)
                    max = num[i];
            }
    
            //初始化桶
            //通的数量
            int buckNum = (max - min) / num.length + 1;
            ArrayList<ArrayList<Integer>> buckArr = new ArrayList<>(buckNum);
    
            for (int i = 0; i < buckNum; i++) { 
                buckArr.add(new ArrayList<Integer>());
            }
    
            //将每个元素放入相应的桶
            //比如20，最小值是15，长度为10，index=(20-5)/10=1
            //将15添加在buckARR的0中
            for (int i = 0; i < num.length; i++) { 
                int index = (num[i] - min) / num.length;
                buckArr.get(index).add(num[i]);
            }
    
            //对每个桶进行排序
            for (int i = 0; i < buckArr.size(); i++) { 
                Collections.sort(buckArr.get(i));
            }
    
            int[] res = new int[num.length];
            int count = 0;
            for (int i = 0; i < buckArr.size(); i++) { 
                for (int j = 0; j < buckArr.get(i).size(); j++) { 
                    res[count++] = buckArr.get(i).get(j);
                }
            }
            return res;
        }
    }