排序算法

[mysterin]

冒泡排序

1. 比较相邻大小, 大的向后冒泡;
2. 循环 n 次这样的操作.

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

   改进: 如果不再发生交换操作, 说明前面的都已经排序好了, 可以终止排序了.

   public void bubbleSort(int[] a) {
   for (int i = 0; i < a.length; i++) {
       boolean flag = true;
       for (int j = 0; j < a.length-1-i; j++) {
           if (a[j] > a[j+1]) {
               int tmp = a[j];
               a[j] = a[j+1];
               a[j+1] = tmp;
               flag = false;
           }
       }
       if (flag) {
           break;
       }
   }
   }

   选择排序

3. 选择最小的数放到前面;
4. 循环 n 次这样的操作;

   public void selectionSort(int[] a) {
   for (int i = 0; i < a.length; i++) {
       for (int j = i+1; j < a.length; j++) {
           if (a[i] > a[j]) {
               int tmp = a[i];
               a[i] = a[j];
               a[j] = tmp;
           }
       }
   }
   }

插入排序

1. 假设 m-1 个数已经排好序, 把第 m 个数加入进来再排序;
2. 循环 n 次这样的操作.

   public void insertSort(int[] a) {
   for (int i = 0; i < a.length-1; i++) {
       for (int j = i+1; j > 0; j--) {
           if (a[j] < a[j-1]) {
               int tmp = a[j];
               a[j] = a[j-1];
               a[j-1] = tmp;
           } else {
               break;
           }
       }
   }
   }

[mysterin]

希尔排序

按增量划分子序列, 然后对子序列分别使用插入排序, 当增量越趋向 1 , 排序就越好.

1. 增量为increment = len/2, 对 i, i+increment, i+2increment,... 使用插入排序;
2. 增量 increment = increment/2, 重复上述步骤.

   public void shellSort(int[] a) {
   int increment = a.length;
   while (true) {
       increment = increment / 2;
       for (int i = 0; i < increment; i++) {
           for (int j = i; j < a.length - increment; j += increment) {
               for (int k = j+increment; k > i; k -= increment) {
                   if (a[k] < a[k-increment]) {
                       int tmp = a[k];
                       a[k] = a[k-increment];
                       a[k-increment] = tmp;
                   } else {
                       break;
                   }
               }
           }
       }
       if (increment <= 1) {
           break;
       }
   }
   }

[mysterin]

快速排序

选一个基准数，小于它的放到左边，大于它的放到右边，然后继续对左右子序列排序。

public void quickSort(int[] a, int left, int right) {
    if (left >= right) {
        return;
    }
    int min = left;
    int max = right;
    min++;
    while (min <= max) {
        while (min <= max && a[min] <= a[left]) {
            min++;
        }
        while (max >= min && a[max] > a[left]) {
            max--;
        }
        if (min < max) {
            int tmp = a[min];
            a[min] = a[max];
            a[max] = tmp;
            min++;
            max--;
        }
    }
    int tmp = a[left];
    a[left] = a[max];
    a[max] = tmp;
    quickSort(a, left, max-1);
    quickSort(a, min, right);
}

[mysterin]

归并排序

1. 把数列分两半, 分别排序左右两边, 然后合并;
2. 递归上面操作, 只有一个数就不用排序了;
3. 使用临时数组辅助合并排序.

public void mergeSort(int[] a, int left, int right, int[] temp) {
    if (left < right) {
        int mid = (left+right) / 2;
        mergeSort(a, left, mid, temp);
        mergeSort(a, mid+1, right, temp);
        int i = left;
        int j = mid+1;
        int k = left;
        while (i <= mid && j <= right) {
            if (a[i] < a[j]) {
                temp[k] = a[i];
                k++;
                i++;
            } else {
                temp[k] = a[j];
                k++;
                j++;
            }
        }
        while (i <= mid) {
            temp[k++] = a[i++];
        }
        while (j <= right) {
            temp[k++] = a[j++];
        }
        for (int n = left; n <= right; n++) {
            a[n] = temp[n];
        }
    }
}

[mysterin]

堆排序

把数组调整为大顶堆, 然后交换开始和末尾.

1. 找到最后一个非叶子节点位置: len/2 - 1;
2. 找出这个父节点及子节点的最大值, 然后通过交换放到父节点位置, 此时要调整子节点是否符合大顶堆;
3. 逐一往前找父节点重复这个过程, 一直到根节点, 此时这个数组就是一个大顶堆的二叉树了;
4. 交换开始数据和末尾数据, 最大的值就排在最后了, 然后再次调整根节点符合大顶堆, 对剩余数据同样交换.

public void heapSort(int[] a) {
    // 调整成大顶堆
    for (int i = a.length/2 - 1; i >= 0; i--) {
        adjectHeap(a, i, a.length);
    }
    // 最大值放到末尾, 重新调整大顶堆
    for (int i = 0; i < a.length; i++) {
        int len = a.length - i;
        int tmp = a[0];
        a[0] = a[len-1];
        a[len-1] = tmp;
        adjectHeap(a, 0, len-1);
    }
}

public void adjectHeap(int[] a, int i, int len) {
    while (true) {
        // 子节点
        int j = 2 * i + 1;
        int k = j + 1;
        if (j >= len) {
            break;
        }
        int max = j;
        if (k < len && a[k] > a[j]) {
            max = k;
        }
        if (a[max] > a[i]) {
            int tmp = a[i];
            a[i] = a[max];
            a[max] = tmp;
            i = max;
        } else {
            break;
        }
    }
}

[mysterin]

基数排序

1. 设置一个辅助数组;
2. 按原数组个位放到对应辅助数组;
3. 辅助数组从上到下, 从左到右把数据写会原数组;
4. 按十位放到辅助数组...

   /**
   *
   * @param a
   * @param d 最大数的位数
   */
   public void radixSort(int[] a, int d) {
   int len = a.length;
   int[][] temp = new int[10][len];
   // 计数每行数据数
   int[] count = new int[10];
   // 除数
   int m = 1;
   // 地位向高位排序
   for (int i = 0; i < d; i++) {
       // 计数器重置 0
       for (int j = 0; j < 10; j++) {
           count[j] = 0;
       }
       for (int j = 0; j < len; j++) {
           // 位数 d 对应的值
           int num = (a[j] / m) % 10;
           temp[num][count[num]] = a[j];
           count[num]++;
       }
       // 把 temp 数组数据写回数组 a
       int n = 0;
       for (int j = 0; j < 10; j++) {
           for (int k = 0; k < count[j]; k++) {
               a[n++] = temp[j][k];
           }
       }
       // 除数要乘以 10, 这样才能取更高位的数
       m *= 10;
   }
   }