1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

private int[] bubbleSort(int[] arr) {
    // 外n-1 内n-i-1
    // 在第n-1轮的时候，只剩下一个元素没有位于有序区，但此时所有元素已经有序，所以总共遍历n-1轮
    for (int i = 0; i < arr.length - 1; i++) {
        // 内层用于遍历无序区
        // 每轮排序中:需要比较的元素个数比上一轮少一个
        // 即外层遍历i轮，无序区元素减少i个，所以内层应遍历n-i轮；
        // 又因为j+1可以遍历到最后一个元素，所以只需要遍历n-i-1轮（否则会数组越界），或者看成(n-1)-i来理解
        for (int j = 0; j < arr.length - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr, j, j + 1);
            }
        }
    }
    return arr;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

private int[] bubbleSort(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        boolean isSorted = true;
        for (int j = 0; j < arr.length - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr, j, j + 1);
                isSorted = false; // 若没有进判断条件则说明没有进行元素互换，也即数组已经有序，后面不需要继续遍历，isSorted值为true。
            }
        }
        if (isSorted) {
            break;
        }
    }
    return arr;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

private int[] selectSort(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        int min = i;
        // 由于无序区的第一个元素一定会被比较，所以直接i+1开始即可
        for (int j = i + 1; j < arr.length; j++) {
            min = minIndex(arr, min, j);
        }
        swap(arr, i, min);
    }
    return arr;
}

public int minIndex(int[] arr, int min, int j) {
    return arr[min] < arr[j] ? min : j;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

private int[] insertSort(int[] arr) {
    // 遍历无序区，默认第一个元素有序，从 1 开始
    for (int i = 1; i < arr.length; i++) {
        int sortingVal = arr[i];
        // 遍历有序区（0~i-1），找到插入位置；移动有序区，为插入元素挪出一个单元
        int j = 0;
        for (j = i - 1; j >= 0; j--) {
            // 待排序元素与有序区的每一个元素进行比较，如果遇到小于有序区的元素，则有序区的那个元素之后的所有元素后移一位，往前插入元素
            if (sortingVal < arr[j]) arr[j+1] = arr[j];
            else break;
        }
        // 插入元素，因为循环最后 j-- 了，所以插入位置是 j+1
        arr[j+1] = sortingVal;
    }
    return arr;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

private int[] quickSort(int[] arr, int left, int right) {
    // 递归结束条件 left >= right
    if (left < right) {
        // 得到基准元素位置
        int pivotIndex = randomPartition(arr, left, right);
        // 根据基准元素，分成两部分进行递归排序
        quickSort(arr, left, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, right);
    }
    return arr;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

public int partition(int[] arr, int left, int right) {
    // 设定基准值，由于前面已经随机并且交换到序列头部，因此此处只需要选取头部位置即可
    int pivotIndex = left;
    int mark = left;    // 设置一个mark指针指向数列起始位置，表示 小于基准元素的区域边界
    // 从基准元素的下一个位置开始遍历数组
    for (int i = pivotIndex + 1; i <= right; i++) {
        if (arr[i] < arr[pivotIndex]) {  // 遍历到的元素小于基准元素，需做两件事
            mark++; // 1.mark指针右移一位，因为小于基准元素的区域边界增大了1
            swap(arr, mark, i); // 2.让最新遍历到的元素和mark指针所在位置的元素交换位置，因为最新遍历的元素要归属于小于pivot的区域
        }
    }
    // 最后把pivot交换到mark指针所在位置
    swap(arr, pivotIndex, mark);
    return mark;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

private int partitionV2(int[] arr, int left, int right) {
    // 设定基准值，由于前面已经随机并且交换到序列头部，因此此处只需要选取头部位置即可
    int pivotIndex = left;
    int start = pivotIndex + 1;  // 因为基准值元素是有序的，所以不需要比较
    int end = right;
    while (true) {
        // 从左往右扫描，找到第一个大于等于 基准值(pivot) 的元素位置
        while (start <= end && arr[start] <= arr[pivotIndex]) start++;
        // 从右往左扫描，找到第一个小于等于 基准值(pivot) 的元素位置
        while (start <= end && arr[end] >= arr[pivotIndex]) end--;
        // 左右指针相遇
        if (start >= end) break;
        // 交换左右数据，使得左边的元素不大于pivot，右边的不小于pivot
        swap(arr, start, end);
    }
    // 将基准值元素插入序列
    swap(arr, pivotIndex, end);
    return end;
}

1
2
3
4
5
6
7

int randomPartition(int[] arr, int left, int right) {
    // 随机设定基准值
    int pivotIndex = (new Random()).nextInt(right) % (right - left + 1) + left;
    // 把基准值元素交换到序列头部，完成分治后再换回去
    swap(arr, left, pivotIndex);
    return partitionV2(arr, left, right);
}