當(dāng)數(shù)組中有n個(gè)元素時(shí)，只需要進(jìn)行n-1輪比較，則整個(gè)數(shù)組就是有序的
public static void bubbleSort(int[] arr) {
 // 進(jìn)行i輪比較
    for (int i = 0; i < arr.length - 1; i++)
     {
        for (int j = 0; j < arr.length - 1 - i; j++) {
        //后一位的值大于前一位的值進(jìn)行值交換
            if (arr[j] > arr[j + 1]) {
                swap(arr, j, j + 1);
            }
        }
    }
}

public static void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

public static void selectionSort(int[] a) {
//每當(dāng)完成一輪，將會(huì)找到最小值，一個(gè)i代表一輪
    for (int i = 0; i < a.length; i++) {
        int index = i;
        //每一輪從i+1開(kāi)始找，查找是否有比當(dāng)前值更小的值
        for (int j = i + 1; j < a.length; j++) {
            if (a[index] > a[j]) {
                index = j;
            }
        }//如果index和i不相等說(shuō)明，下標(biāo)交換過(guò)，也就是說(shuō)找到更小的數(shù)值了
        if (index != i) {
            swap(a, index, i);
        }
    }
}

public static void swap(int[] a, int i, int j) {
    int temp = a[i];
    a[i] = a[j];
    a[j] = temp;
}

public static void insertionSort(int[] a) {
    for (int i = 1; i < a.length; i++) {
        int temp = a[i];
        int j;
        // 查到合適的插入位置，插入即可
        for (j = i - 1; j >= 0 && a[j] > temp; j--) {
            a[j + 1] = a[j];
        }
        a[j + 1] = temp;
    }
}

public static void shellSort(int[] a) {
    for (int step = a.length / 2; step > 0; step /= 2) {
    //接下來(lái)的過(guò)程類(lèi)似于插入排序
        for (int i = step; i < a.length; i++) {
            int temp = a[i];
            int j;
            for (j = i - step; j >= 0 && a[j] > temp ; j -= step) {
                a[j + step] = a[j];
            }
            a[j + step] = temp;
        }
    }
}

public static void mergeSort(int[] a, int left, int right) {
    // 將數(shù)組分段成只有一個(gè)元素
    if (left == right) {
        return;
    }
    int mid = (left + right) / 2;
    mergeSort(a, left, mid);//遞歸
    mergeSort(a, mid + 1, right);
    merge(a, left, mid, right);
}

public static void merge(int[] a, int left, int mid, int right) {
    int[] temp = new int[right - left + 1];
    int i = left;
    int j = mid + 1;
    int k = 0;
    while (i <= mid && j <= right) {
        if (a[i] < a[j]) {
            temp[k++] = a[i++];
        } else {
            temp[k++] = a[j++];
        }
    }
    // 復(fù)制左邊數(shù)組剩余的值
    while (i <= mid) {
        temp[k++] = a[i++];
    }
    // 復(fù)制右邊數(shù)組剩余的值
    while (j <= right) {
        temp[k++] = a[j++];
    }
    int index = 0;
    //把temp全部復(fù)制給數(shù)組
    while (left <= right) {
        a[left++] = temp[index++];
    }
}

public static void quickSort(int[] a, int left, int right) {
    if (left >= right) {
        return;
    }
    int index = sort(a, left, right);
    //得到中間值index，然后一分為二，繼續(xù)分
    quickSort(a, left, index - 1);
    quickSort(a, index + 1, right);
}

public static int sort(int[] a, int left, int right) {
//以左邊的a[left]為基準(zhǔn)數(shù)
    int key = a[left];
    while (left < right) {
        // 從right所指位置向前搜索找到第一個(gè)關(guān)鍵字小于key的記錄和key互相交換
        while (left < right && a[right] >= key) {
            right--;
        }
        a[left] = a[right];
        // 從left所指位置向后搜索，找到第一個(gè)關(guān)鍵字大于key的記錄和key互相交換
        while (left < right && a[left] <= key) {
            left++;
        }
        a[right] = a[left];
    }
    // 放key值，此時(shí)left和right相同
    a[left] = key;
    return left;
}