选择排序

    1. @Test
    2. public void testSelectSort() {
    3.     int[] data = {1, 2, 5, 0, 2, 3, 4, 9};
    4.     for (int i = 0; i < data.length; i++) {
    5.         for (int j = i + 1; j < data.length; j++) {
    6.             if (data[j] < data[i]) {
    7.                 int tmp = data[i];
    8.                 data[i] = data[j];
    9.                 data[j] = tmp;
    10.             }
    11.         }
    12.         System.out.println("No." + i + "->" + Arrays.toString(data));
    13.     }
    14.     System.out.println("Final:" + Arrays.toString(data));
    15. }
    16. @Test
    17. public void testSelectSort2() {
    18.     int[] data = {1, 2, 5, 0, 2, 3, 4, 9};
    19.     for (int i = 0; i < data.length; i++) {
    20.         int min = i;
    21.         for (int j = i + 1; j < data.length; j++) {
    22.             if (data[j] < data[min]) {
    23.                 min = j;
    24.             }
    25.         }
    26.         int tmp = data[i];
    27.         data[i] = data[min];
    28.         data[min] = tmp;
    29.         System.out.println("No." + i + "->" + Arrays.toString(data));
    30.     }
    31.     System.out.println("Final:" + Arrays.toString(data));
    32. }

    快速排序

    1. @Test
    2. public void testQuickSort() {
    3.     int[] arr = {10, 7, 2, 4, 7, 62, 3, 4, 2, 1, 8, 9, 19};
    4.     quickSort(arr, 0, arr.length - 1);
    5.     System.out.println(Arrays.toString(arr));
    6. }
    7. public static void quickSort(int[] arr, int low, int high) {
    8.     int i, j, temp, t;
    9.     if (low > high) {
    10.         return;
    11.     }
    12.     i = low;
    13.     j = high;
    14.     //temp就是基准位
    15.     temp = arr[low];
    16.     while (i < j) {
    17.         //先看右边，依次往左递减
    18.         while (temp <= arr[j] && i < j) {
    19.             j--;
    20.         }
    21.         //再看左边，依次往右递增
    22.         while (temp >= arr[i] && i < j) {
    23.             i++;
    24.         }
    25.         //如果满足条件则交换
    26.         if (i < j) {
    27.             t = arr[j];
    28.             arr[j] = arr[i];
    29.             arr[i] = t;
    30.         }
    31.     }
    32.     //最后将基准为与i和j相等位置的数字交换
    33.     arr[low] = arr[i];
    34.     arr[i] = temp;
    35.     //递归调用左半数组
    36.     quickSort(arr, low, j - 1);
    37.     //递归调用右半数组
    38.     quickSort(arr, j + 1, high);
    39. }
    40. /**
    41.  * 快排核心算法，递归实现
    42.  *
    43.  * @param array
    44.  * @param left
    45.  * @param right
    46.  */
    47. public static int sort(int[] array, int left, int right) {
    48.     // base中存放基准数
    49.     int base = array[left];
    50.     int i = left, j = right;
    51.     while (i < j) {
    52.         // 顺序很重要，先从右边开始往左找，直到找到比base值小的数
    53.         while (array[j] >= base && i < j) {
    54.             j--;
    55.         }
    56.         // 再从左往右边找，直到找到比base值大的数
    57.         while (array[i] <= base && i < j) {
    58.             i++;
    59.         }
    60.         // 上面的循环结束表示找到了位置或者(i>=j)了，交换两个数在数组中的位置
    61.         if (i < j) {
    62.             int tmp = array[i];
    63.             array[i] = array[j];
    64.             array[j] = tmp;
    65.         }
    66.     }
    67.     // 将基准数放到中间的位置（基准数归位）
    68.     array[left] = array[i];
    69.     array[i] = base;
    70.     return i;
    71.     // 递归，继续向基准的左右两边执行和上面同样的操作
    72.     // i的索引处为上面已确定好的基准值的位置，无需再处理
    73.     //sort(array, left, i - 1);
    74.     //sort(array, i + 1, right);
    75. }