常规冒泡与快排

//排序-交换排序:冒泡和快排;冒泡:o(n^2),o(1),稳定；快排:o(nlogn),o(1),不稳定
public class K {
    public static void main(String[] args) {
        K k = new K();
        int [] arr = {4,85,98,3,42,56,88,32,44,42,12,89,74};
        k.print(k.bubbleSort(arr));
        System.out.println();
        k.print(k.betterBubbleSort(arr));
        System.out.println();
        quickSort(arr, 0, arr.length - 1);
        k.print(arr);
    }
    //冒泡方法
    private int[] bubbleSort(int[] arr) {
        int i = 0;
        int temp = 0;
        int len = arr.length;
        for(i = 0; i < len - 1; i++) { //确定排序趟数
            int j = 0;
            for(j = 0; j < len - 1 - i; j++) { //确定比较次数
                if (arr[j]>arr[j + 1])
                {
                    //交换:将最大的数换到最后,最后一个数就不用再被比较了
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            } 
        }
        return arr;
    }
    /* 优化冒泡排序
     *  a.一般冒泡排序中的问题：第一趟排序后，就算已经有序了，还是会进行第2趟排序→解决：在交换的地方添加标记，如果那一趟没有交换元素，说明这组数据已经有序，不用再继续下去
     */
    private int[] betterBubbleSort(int[] arr) {
        int i = 0;
        int temp = 0;
        int len = arr.length;
        for(i = 0; i < len -1; i++) {
            int j = 0;
            int flag = 0;
            for(j = 0; j < len - 1 - i; j++) {
                if (arr[j] > arr[j + 1])
                {
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    flag = 1;//加入标记
                }
            }
            if(flag == 0) 
                break;
        }
        return arr;
    }    
    //快排-递归地把小于基准元素的子数列和大于基准值的子数列排序(挖坑填数+分治法)
    private static void quickSort(int[] arr, int leftIndex, int rightIndex) {
        if (leftIndex >= rightIndex) {
            return;
        }

        int left = leftIndex;
        int right = rightIndex;
        //待排序的第一个元素作为基准值
        int key = arr[left];

        //从左右两边交替扫描,直到left = right一趟才结束
        while (left < right) {
            while (right > left && arr[right] >= key) {
                //从右往左扫描,找到第一个比基准值小的元素
                right--;
            }

            //找到这种元素将arr[right]放入arr[left]中
            arr[left] = arr[right];

            while (left < right && arr[left] <= key) {
                //从左往右扫描,找到第一个比基准值大的元素
                left++;
            }

            //找到这种元素将arr[left]放入arr[right]中
            arr[right] = arr[left];
        }
        //基准值归位
        arr[left] = key;
        //对基准值左边的元素进行递归排序
        quickSort(arr, leftIndex, left - 1);
        //对基准值右边的元素进行递归排序。
        quickSort(arr, right + 1, rightIndex);
    }
    //输出方法
    public void print(int[] arr) {
        for(int x : arr) {
            System.out.print(x + " ");
        }
    }
}

【注意】快排：