1 冒泡排序

冒泡排序的基本思想就是两两进行比较, 也就是相邻的两个元素进行比较, 每次一个外循环都可以确定一个最大值, 并将这个最大值放在无序序列的最后面, 持续这个过程, 直到整个序列有序.
详细执行过程如下:

代码如下:

public static void bubbleSort(int[] arr) {
        for (int i = 0; i < arr.length-1; i++) {
            boolean flag = false;
            for (int j = 0; j < arr.length-1-i; j++) {
                if (arr[j] > arr[j+1]) {
                    int tmp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = tmp;
                    flag = true;
                }
            }
            if (flag == false) {
                break;
            }
        }
    }
    public static void main(String[] args) {
        int[] arr = {3,2,5,7,1,6,8,9,4};
        System.out.println(Arrays.toString(arr));
        bubbleSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

运行结果:

性能分析: 这里需要注意一下: 如果序列是优化过的, 也就是有序的, 其时间复杂度可能是 O(n).

2 快速排序

快速排序的基本思想如下:

• 从待排序列中选择一个数, 作为基准值(pivot);

关于基准值的选择主要有三种方式:
1) 选择边上的数字, 例如我们经常会选择序列的首位数字作为基准值;
2) 随机选择;
3) 三位数中, 也就是arr[start], arr[mid], arr[end] 这三个数中选择中间大的数字, 下面的代码我们就是用的这种方式.

• 遍历整个待排序列, 将比基准值小的放在基准值的左边, 将比基准值大的或者相等的放在基准值的右边, 如下图所示;
• 采用分治的思想, 对基准值左右两个区间按照以上顺序处理, 直到小区间的长度等于 1 的时候, 代表已经有序.
  

关于快速排序这里主要介绍两种方法, 一种是递归遍历的方式, 另一种是非递归遍历的方式.

2.1 递归实现

详细过程如下:

代码如下:

public class SwapSort {
    public static int partition(int[] arr, int low, int high) {
        int tmp = arr[low];
        while (low < high) {
            while (low < high && arr[high] >= tmp) {
                high--;
            }
            arr[low] = arr[high];
            while (low < high && arr[low] <= tmp) {
                low++;
            }
            arr[high] = arr[low];
        }
        arr[high] = tmp;
        return low;
    }
    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
    public static void selectPivotMedianOfThree(int[] arr, int start, int end, int mid) {
        while (true) {
            if (arr[mid] > arr[start]) {
                swap(arr, start, mid);
                continue;
            }
            if (arr[start] > arr[end]) {
                swap(arr, start, end);
                continue;
            }
            if (arr[mid] > arr[end]) {
                swap(arr, start, end);
                continue;
            }
            break;
        }
    }
    
    public static void quick(int[] arr, int start, int end) {
        if (start >= end) {
            return;
        }
        int mid = (start+end)/2;
        selectPivotMedianOfThree(arr, start, end, mid);
        int pivot = partition(arr, start, end);
        quick(arr, start, pivot-1);
        quick(arr, pivot+1, end);
    }
    public static void quickSort(int[] arr) {
        quick(arr, 0, arr.length-1);
    }
    
    public static void main(String[] args) {
        int[] arr = {3,2,5,7,1,6,8,9,4};
        System.out.println(Arrays.toString(arr));
        quickSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

运行结果:

性能分析:

2.2 非递归实现

非递归的实现需要用到栈, 详细过程如下:

代码如下:

public class SwapSort {
    public static int partition(int[] arr, int low, int high) {
        int tmp = arr[low];
        while (low < high) {
            while (low < high && arr[high] >= tmp) {
                high--;
            }
            arr[low] = arr[high];
            while (low < high && arr[low] <= tmp) {
                low++;
            }
            arr[high] = arr[low];
        }
        arr[high] = tmp;
        return low;
    }

    public static void quickSort2(int[] arr) {
        Stack<Integer> stack = new Stack<>();
        int start = 0;
        int end = arr.length - 1;
        int pivot = partition(arr, start, end);
        // 左边有两个元素及以上
        if (pivot > start + 1) {
            stack.push(0);
            stack.push(pivot - 1);
        }
        if (pivot < end - 1) {
            stack.push(pivot + 1);
            stack.push(end);
        }
        while (!stack.empty()) {
            end = stack.pop();
            start = stack.pop();
            pivot = partition(arr, start, end);
            // 左边有两个元素及以上
            if(pivot > start+1) {
                stack.push(0);
                stack.push(pivot-1);
            }
            if(pivot < end-1) {
                stack.push(pivot+1);
                stack.push(end);
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {3,2,5,7,1,6,8,9,4};
        System.out.println(Arrays.toString(arr));
        quickSort2(arr);
        System.out.println(Arrays.toString(arr));
    }
}

运行结果: