冒泡和快速排序

冒泡排序改良版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public static void bubbleSort(int[] num){
        if (num.length==0) {
            return;
        }
        for (int end=num.length-1;end>0;end--) {
            //记录最后一次交换的位置
            int sorted=-1;
            for (int begin = 0; begin < end; begin++) {
                if (num[begin+1]<num[begin]){
                    int tmp=num[begin+1];
                    num[begin+1]=num[begin];
                    num[begin]=tmp;
                    sorted=begin;
                }
            }
            end=sorted+1;
            if (sorted==-1){
                return;
            }
        }
    }

快速排序

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
public static void quickSort(int[] num, int begin, int end){
       if(begin<end){
           int mid=pivotIndex(num,begin,end);
           quickSort(num,begin,mid-1);
           quickSort(num,mid+1,end);
       }
   }
   public static int pivotIndex(int[] num, int begin, int end){
       //这里可以改成取数组随机一个数，避免O(n^2)的最坏情况
       int pivot=num[begin];
       while(begin<end){
           while(begin<end && pivot<=num[end]) {
               end--;
           }
           swap(num,begin,end);
           while(begin<end && pivot>=num[begin]) {
               begin++;
           }
           swap(num,begin,end);
       }
       num[begin]=pivot;
       return begin;
   }
   public static void swap(int[] num, int i, int j){
       int tmp=num[i];
       num[i]=num[j];
       num[j]=tmp;
   }

验证

获取随机数组

1
2
3
4
5
6
7
8
9
10
11
12
13
/**
     * 获得一个存在正负数的随机数组
     * @param maxSize 数组最大长度
     * @param maxValue 数组最大值
     * @return 返回生成的数组
     */
    public static int[] getRandomArray(int maxSize,int maxValue){
        int[] array = new int[(int) ((maxSize+1)*Math.random())];
        for (int i = 0; i < array.length; i++) {
            array[i]=(int) ((maxValue+1)*Math.random() - (maxValue+1)*Math.random());
        }
        return array;
    }

比较

1
2
3
4
5
6
7
8
9
10
11
12
13
public static void main(String[] args) {
        int[] num= Util.getRandomArray(50,10000);
        int[] num1=Arrays.copyOf(num,num.length);
        int[] num2=Arrays.copyOf(num,num.length);
        bubbleSort(num);
        System.out.println(Arrays.toString(num));
        quickSort(num1, 0, num1.length - 1);
        System.out.println(Arrays.toString(num1));
        Arrays.sort(num2);
        System.out.println(Arrays.toString(num2));
        System.out.println(Arrays.equals(num,num1));
        System.out.println(Arrays.equals(num1,num2));
    }

结果

image-20210709112116662