Java排序之冒泡排序、快速排序

冒泡排序在10大排序中是最简单的排序算法之一，它的思想非常容易理解。冒泡排序的基本思想： 通过对待排序序列从前向后，依次比较相邻元素的排序码，若发现逆序则交换，使排序码较大的元素逐渐从前部移向后部。

public static int[] sort1 (int[] arr)
{
    int[] newArr = Arrays.copyOf(arr, arr.length);

    for (int i = 0; i < newArr.length - 1; i ++) {
        for (int j = 0; j < newArr.length - i - 1; j++) {
            if (newArr[j] > newArr[j+1]) {
                int tmp = newArr[j];
                newArr[j] = newArr[j+1];
                newArr[j+1] = tmp;
            }
        }
    }

    return newArr;
}

快速排序算法是10大排序算法中速度最快的一种。

基本思想：任取待排序序列中的某个元素作为标准（ 也称为支点、界点， 一般取第一个元素），通过一次划分，将待排元素分为左右两个子序列，左子序列元素的排序码均小于基准元素的排序码，右子序列的排序码则大于或等于基准元素的排序码，然后分别对两个子序列继续进行划分，直至每一个序列只有一个元素为止。最后得到的序列便是有序序列。

快速排序算法需要使用到递归思想。

public static void quickSort (int[] arr, int left, int right)
{
    if (left >= right) {
        return;
    }

    int standard = arr[left];  // 基准值
    int tmpn = left;   // 划分两个子序列的数组索引值

    for (int i = left + 1; i <= right; i ++) {
        if (arr[i] < standard) {
            swap(arr, i, ++tmpn);
        }
    }

    swap(arr, left, tmpn);
    quickSort(arr, left, tmpn-1);
    quickSort(arr, tmpn + 1, right);
}

private static void swap (int[] arr, int i, int j)
{
    if (i == j) {
        return ;
    }

    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}