排序算法之交换排序

交换排序

交换排序有两种排序方法：快速排序和冒泡排序

快速排序

原理

快速排序就是让一个序列中第一个数归位（到它正确的位置上），然后再用归位的位置将序列分成两个序列，然后对这两个序列进行上述的归位操作，然后递归下去。那么怎么将第一个数归位呢？选择两个指针，分别指向第一个数的下一个数和该序列最后一个数，左边的指针找比第一个数小的，右边的指针找比第一个数大的，右边的指针先移动，左边的指针再移动，两个指针找到后，交换两个位置上的数，然后再移动再找，直到两个指针相遇，将相遇位置上的数和第一个数交换，那么此时第一个数就到了正确的位置上。如果看了原理和代码还是不够清晰可以看看这篇文章，总结的比较全面。

实现

public static void quickSort(int[] num, int l, int r) {
    if (l < r) {
        int mid = getMiddle(num, l, r);
        quickSort(num, l, mid - 1);
        quickSort(num, mid + 1, r);
    }
}

public static int getMiddle(int[] num, int l, int r) {
    int o = num[l];
    while (l < r) {
        while (l < r && num[r] >= o)
            r--;
        num[l] = num[r];
        while (l < r && num[l] <= o)
            l++;
        num[r] = num[l];
    }
    num[r] = o;
    return l;
}

冒泡排序

原理

冒泡排序很简单，就是每一趟找出最大的数放到数组末尾，然后下一趟再对除去末尾的数进行同样的操作，这样就能将序列排序

实现

public static void bubble(int[] num) {
    int tmp;
    for (int i = 0; i < num.length; i++) {
        for (int j = 0; j < num.length - 1 - i; j++) {
            if (num[j] > num[j + 1]) {
                tmp = num[j];
                num[j] = num[j + 1];
                num[j + 1] = tmp;
            }
        }
    }
}