常用排序（Java）

谁借莪１个温暖的怀抱￠ 2023-07-17 06:25 58阅读 0赞

public class Sort { 
    
    
        //数组申请过大，会出java.lang.OutOfMemoryError
        int[] a = { 10,1,35,61,89,36,55};
    
        //输出数组
        void showArr(int[] a){ 
            for(int i = 0; i < a.length; i++){ 
                System.out.printf("%d ", a[i]);
            }
            System.out.println();
        }
        //交换函数
        void swap(int[] a, int i, int j){ 
            int t;
            t = a[i];
            a[i] = a[j];
            a[j] = t;
        }
        //快速排序
        //容易出现ArrayIndexOutOfBoundsException
        void Quicksort(int[] a, int low, int high){ 
            int i = low;
            int j = high;
            int key = a[low];
    
            //一定要带，否则可能会出现无法跳出递归
            //java.lang.StackOverflowError
            if (low>=high)
                return;
            while (i<j){ 
                while (i<j&&a[j]>=key)j--;
                a[i] = a[j];
                while (i<j&&a[i]<=key)i++;
                a[j] = a[i];
            }
            a[i] = key;
            Quicksort(a, low, i-1);
            Quicksort(a, i+1, high);
        }
        //冒泡排序
        void BubbleSort(int[] a){ 
            int t;
            for(int i = 0; i < a.length - 1; i++){ 
                for(int j = 0; j < a.length - i -1; j++){ 
                    if (a[j]>a[j+1]){ 
                        swap(a, j, j+1);
                    }
                }
            }
        }
        //选择排序
        /* 1. O(n²) 的时间复杂度。所以用到它的时候，数据规模越小越好 */
        void SelectionSort(int[] a){ 
            int minIndex;
            for(int i = 0; i < a.length - 1; i++){ 
                minIndex = i;
                for(int j = i+1; j < a.length; j++){ 
                    if (a[j]<a[minIndex])
                        minIndex = j;
                }
                swap(a, i, minIndex);
            }
        }
    
        public static void main(String[] args) { 
            Sort sort = new Sort();
            //sort.BubbleSort(sort.a);
            //sort.Quicksort(a, 0, a.length-1);
            sort.SelectionSort(sort.a);
            sort.showArr(sort.a);
        }
    }