java简单实现常用的排序算法

小鱼儿 2022-06-09 02:52 228阅读 0赞

public class Sequence {
    
        /* * 冒泡排序(从小到大)，属于交换排序 */
        public static void bubbleSequence(int[] a) {
            int h = 0, flag = 1;
            while (h < a.length && flag == 1) { // flag如果等于零，那么这一趟并没有改变任何值的顺序，说明后面的数组是有序的了
                flag = 0;
                for (int i = h + 1; i < a.length; i++) {
                    if (a[h] > a[i]) {
                        int temp;
                        temp = a[h];
                        a[h] = a[i];
                        a[i] = temp;
                        flag = 1;
                    }
                }
                h++;
            }
    
        }
    
        /* * 快速排序（取枢轴值k，将数组分为小于k的和大于k的，然后将这两个部分各取枢轴值，以此递归，最后数组排序完成），属于交换排序 */
    
        public static void quickSort(int[] a) {
            qSort(a, 0, a.length - 1);
        }
    
        public static void qSort(int[] a, int low, int high) {
            if (low < high) {
                int p = partition(a, low, high); // 按枢轴值分为大于其和小于其两部分，并返回枢轴值所在的位置
                qSort(a, low, p - 1); // 数组的前部，比枢轴值小的部分排序
                qSort(a, p + 1, high); // 数组的后部，比枢轴值大的部分排序
            }
        }
    
        public static int partition(int[] a, int low, int high) {
            int pivot = a[low]; // 以第一个值为枢轴值，第一个位置就空出来了，为后面数组尾部中小于枢轴值的值腾出空位
            /* * 每次最外层的循环都将从数组尾部（数组的右边high）开始， 将数组尾部一个小于枢轴值的数移到数组前面（low）, * 然后将数组前一个比枢轴值大的移到后面 */
            while (low < high) {
                while (low < high && a[high] > pivot) {
                    high--;
                }
                a[low] = a[high];
                while (low < high && a[low] < pivot) {
                    low++;
                }
                a[high] = a[low];
            }
            a[low] = pivot;
            return low; // 返回枢轴值在数组中的位置
        }
    
        /* * 直接插入排序 */
        public static void insertSort(int[] a) {
            for (int i = 1; i < a.length; i++) {
                if (a[i] < a[i - 1]) {
                    int temp = a[i], j;
                    a[i] = a[i - 1];
                    for (j = i - 1; a[j] > temp; j--) { // 将数组往后移，找到当前数temp（a[i]）要插入的位置
                        if (j == 0) {
                            break;
                        }
                        a[j] = a[j - 1];
    
                    }
    
                    // System.out.println("付好款："+temp+j);
                    a[j] = temp;
                }
            }
        }
    
        /* * 折半插入排序 */
        public static void binSertSort(int[] a) {
            int low, high, m, temp;
            for (int i = 1; i < a.length; i++) {
                temp = a[i];
                low = 0;
                high = i - 1;
                while (low <= high) { // 使用二分查找法找到插入元素的位置，当low>high时while循环结束，low的值就是要插入的位置
                    m = (low + high) / 2;
                    if (a[m] > temp) {
                        high = m - 1;
                    } else {
                        low = m + 1;
                    }
                }
                for (int j = i - 1; j >= low; j--) {
                    a[j + 1] = a[j];
                }
                a[low] = temp;
            }
        }
    
        /* * 简单选择排序（第一次循环将第一小的数放在数组的第一个位置，第二次将第二小的放在数组的第二个位置，以此类推） */
        public static void selectSort(int[] a){
            for(int i = 0; i < a.length - 1; i++){
                int k = i;
                for(int j = i+1; j < a.length; j++){
    
                    if (a[j] < a[i]){
                        k = j;
                    }
                }
                if (k != i){
                    int temp = a[k];
                    a[k] = a[i];
                    a[i] = temp;
                }
            }
        }
    
    
        public static void main(String[] args) {
            // int[] bubble = {9, 8, 7, 6, 5, 4, 3, 2, 1};
            // for(int b : bubble){ 
            // System.out.print(b);
            // }
            // System.out.println();
            // bubbleSequence(bubble);
            // for(int b : bubble){ 
            // System.out.print(b);
            // }
    
            // int[] quick = {9, 8, 7, 6, 5, 4, 3, 2, 1};
            // quickSort(quick);
            // for(int q : quick){ 
            // System.out.print(q);
            // }
            // int[] insert = {9, 8, 7, 6, 5, 4, 3, 2, 1};
            // insertSort(insert);
            // for(int i : insert){ 
            // System.out.print(i);
            // }
    
    // int[] binSertSort = { 9, 8, 7, 6, 5, 4, 3, 2, 1 };
    // binSertSort(binSertSort);
    // for (int bin : binSertSort) { 
    // System.out.print(bin);
    // }
    
            int[] select = { 9, 8, 7, 6, 5, 4, 3, 2, 1 };
            selectSort(select);
            for (int s : select){
                System.out.print(s);
            }
        }
    
    }