欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

十大排序算法

程序员文章站 2022-06-01 20:21:22
...

1.java代码

public class SortUtil {

    //冒泡排序
    public static void bubble(int[] a) {
        int len = a.length;
        int flag = len;
        while (flag > 0) {
            flag = 0;
            for (int i = 1; i < len; i++) {
                if (a[i] < a[i - 1]) {
                    int temp = a[i];
                    a[i] = a[i - 1];
                    a[i - 1] = temp;
                    flag = i;
                }
            }
            len = flag;
        }
    }

    //简单选择排序
    public static void select(int[] a) {
        for (int i = 0; i < a.length - 1; i++) {
            int min = i;
            for (int j = i + 1; j < a.length; j++) {
                if (a[j] < a[min]) {
                    min = j;
                }
            }
            if (i != min) {
                int temp = a[min];
                a[min] = a[i];
                a[i] = temp;
            }
        }
    }

    //插入排序
    public static void insert(int[] a) {
        for (int i = 1; i < a.length; i++) {
            int j = i;
            int temp = a[i];
            while (j > 0 && a[j - 1] > temp) {
                a[j] = a[j - 1];
                j--;
            }
            a[j] = temp;
        }
    }

    //快速排序
    public static void quick(int[] a, int start, int end) {

        if (start > end) return;

        int left = start;
        int right = end;
        int partition = a[start];

        while (left < right) {

            while (left < right && a[right] >= partition) {
                right--;
            }
            while (left < right && a[left] <= partition) {
                left++;
            }

            if (left < right) {
                int temp = a[right];
                a[right] = a[left];
                a[left] = temp;
            }
        }

        a[start] = a[left];
        a[left] = partition;

        quick(a, start, left - 1);
        quick(a, right + 1, end);

    }

    //希尔排序
    public static void shell(int[] arr) {
        // i表示希尔排序中的第n/2+1个元素(或者n/4+1)
        // j表示希尔排序中从0到n/2的元素(n/4)
        // r表示希尔排序中n/2+1或者n/4+1的值
        // 划组排序
        for (int r = arr.length / 2; r >= 1; r = r / 2) {
            for (int i = r; i < arr.length; i++) {
                int tmp = arr[i];
                int j = i - r;
                // 一轮排序
                while (j >= 0 && tmp < arr[j]) {
                    arr[j + r] = arr[j];
                    j -= r;
                }
                arr[j + r] = tmp;
            }
        }
    }


    //构建大根堆
    public static void buildMaxHeap(int[] a, int lastIndex) {
        for (int i = (lastIndex - 1) / 2; i >= 0; i--) {
            int k = i;
            int bigIndex = 2 * k + 1;
            if (bigIndex + 1 <= lastIndex && a[bigIndex] < a[bigIndex + 1]) {
                bigIndex++;
            }
            if (a[k] < a[bigIndex]) {
                int temp = a[bigIndex];
                a[bigIndex] = a[k];
                a[k] = temp;
            }
        }
    }



    //堆排序
    public static void heap(int[] a) {
        for (int i = 0; i < a.length-1; i++) {
            buildMaxHeap(a, a.length - 1 - i);
            int temp = a[0];
            a[0] = a[a.length - 1 - i];
            a[a.length - 1 - i] = temp;
        }
    }


    //合并
    public static void merge(int[] a, int start, int mid, int end) {
        int[] temp = new int[a.length];
        int i = start;
        int j = mid + 1;
        int k = start;

        while (i <= mid && j <= end) {
            if (a[i] <= a[j]) {
                temp[k++] = a[i++];
            } else {
                temp[k++] = a[j++];
            }
        }

        while (i <= mid) {
            temp[k++] = a[i++];
        }

        while (j <= end) {
            temp[k++] = a[j++];
        }

        for (int n = start; n <= end; n++) {
            a[n] = temp[n];
        }

    }


    //归并排序
    public static void merge(int[] a, int start, int end) {
        if (start < end) {
            int mid = (start + end) / 2;
            merge(a, start, mid);
            merge(a, mid + 1, end);
            merge(a, start, mid, end);
        }
    }


    //基数排序
    public static void radix(int[] a) {
        int disisor = 1;
        int[][] bucket = new int[10][a.length];
        int[] count = new int[10];
        int digit;
        for (int i = 1; i <= 3; i++) {
            for (int temp : a) {
                digit = (temp / disisor) % 10;
                bucket[digit][count[digit]++] = temp;
            }
            int k = 0;
            for (int m = 0; m < 10; m++) {
                if (count[m] == 0) {
                    continue;
                }
                for (int n = 0; n < count[m]; n++) {
                    a[k++] = bucket[m][n];
                }
                count[m] = 0;
            }
            disisor *= 10;
        }
    }


    //二分插入排序
    public static void advanceInsertSortWithBinarySearch(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int temp = arr[i];
            int low = 0, high = i - 1;
            int mid = -1;
            while (low <= high) {
                mid = low + (high - low) / 2;
                if (arr[mid] > temp) {
                    high = mid - 1;
                } else { // 元素相同时,也插入在后面的位置
                    low = mid + 1;
                }
            }
            for(int j = i - 1; j >= low; j--) {
                arr[j + 1] = arr[j];
            }
            arr[low] = temp;
        }
    }


    //计数排序
    public static void count(int[] a,int maxNum){
        int[] b=new int[maxNum+1];//maxNum为数组a中最大的数,+1是因为有0这个数
        for (int i=0;i<a.length;i++){
            b[a[i]]++;
        }
        int k=0;
        for (int j=0;j<b.length;j++){
            while (b[j]>0){
                a[k++]=j;
                b[j]--;
            }
        }
    }


}