排序.png

  • k：“桶”的个数
  • In-place：占用常数内存，不占用额外内存
  • Out-place：占用额外内存

  • 排序分类

    • 插入排序
      • 直接插入排序
      • 希尔排序
    • 选择排序
      • 简单选择排序
      • 堆排序
    • 交换排序
      • 冒泡排序
      • 快速排序
    • 比较排序：快速排序、归并排序、堆排序、冒泡排序
      • 排序依赖于元素之间的比较
      • 优势：适用于各种规模的数据
    • 非比较排序：计数排序、基数排序、桶排序
      • 通过确定每个元素之前，应该有多少个元素来排序
      • 时间复杂度低，但需要占用空间来确定唯一位置

        1、冒泡排序

  • 步骤

    • 比较相邻的元素，如果第一个比第二个大，就交换
    • 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，最后的元素应该是最大的数
    • 针对所有元素重复以上的步骤，除最后一个
    • 重复步骤 1~3，直到排序完成

冒泡排序.gif

  1. public static int[] bubbleSort(int[] array) {
  2.     if (array.length == 0)
  3.         return array;
  4.     for (int i = 0; i < array.length; i++)
  5.         for (int j = 0; j < array.length - 1 - i; j++)
  6.             if (array[j + 1] < array[j]) {
  7.                 int temp = array[j + 1];
  8.                 array[j + 1] = array[j];
  9.                 array[j] = temp;
  10.             }
  11.     return array;
  12. }

  • 优化：

    • 对冒泡排序常见的改进方法是加入标志性变量 exchange ，用于标志某一趟排序过程中是否有数据交换
    • 若进行某一趟排序没有进行数据交换，则说明数据已经有序，可立即结束排序，避免不必要的比较过程
      1. public void bubbleSort_2(int[] list) {
      2. int temp = 0;                 // 用来交换的临时数
      3. boolean bChange = false;     // 交换标志
      4. // 要遍历的次数
      5. for (int i = 0; i < list.length - 1; i++) {
      6.   bChange = false;
      7.   // 从后向前依次的比较相邻两个数的大小，遍历一次后，把数组中第i小的数放在第i个位置上
      8.   for (int j = list.length - 1; j > i; j--) {
      9.       // 比较相邻的元素，如果前面的数大于后面的数，则交换
      10.       if (list[j - 1] > list[j]) {
      11.           temp = list[j - 1];
      12.           list[j - 1] = list[j];
      13.           list[j] = temp;
      14.           bChange = true;
      15.       }
      16.   }
      17.   // 如果标志为false，说明本轮遍历没有交换，已经是有序数列，可以结束排序
      18.   if (false == bChange){
      19.       break;
      20.   }
      21.   System.out.format("第 %d 趟：\t", i);
      22.   printAll(list);
      23. }
      24. }

      2、快速排序

  • 步骤

    • 从数列中挑出一个元素，称为 “基准”（pivot ）
    • 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同数可任一边）。在这个分区退出后，基准处于数列中间，称为分区（partition）
    • 递归地把小于基准值元素的子数列和大于基准值元素的子数列排序

快速排序.gif

  1. public static int[] QuickSort(int[] array, int start, int end) {
  2.     if (array.length<1 || start<0 || end>=array.length || start>end) return null;
  3.     int smallIndex = partition(array, start, end);
  4.     if (smallIndex > start)
  5.         QuickSort(array, start, smallIndex - 1);
  6.     if (smallIndex < end)
  7.         QuickSort(array, smallIndex + 1, end);
  8.     return array;
  9. }
  11. //分区 partition
  12. public static int partition(int[] array, int start, int end) {
  13.     int pivot = (int) (start + Math.random() * (end - start + 1));
  14.     int smallIndex = start - 1;
  15.     swap(array, pivot, end);
  16.     for (int i = start; i <= end; i++)
  17.         if (array[i] <= array[end]) {
  18.             smallIndex++;
  19.             if (i > smallIndex)
  20.                 swap(array, i, smallIndex);
  21.         }
  22.     return smallIndex;
  23. }
  25. //交换数组内两个元素
  26. public static void swap(int[] array, int i, int j) {
  27.     int temp = array[i];
  28.     array[i] = array[j];
  29.     array[j] = temp;
  30. }

3、插入排序

  • 步骤
    • 从第一个元素开始，该元素可以认为已经被排序
    • 取出下一个元素，在已经排序的元素序列中从后向前扫描
    • 如果该元素（已排序）大于新元素，将该元素移到下一位置
    • 重复步骤 3，直到找到已排序的元素小于或者等于新元素的位置
    • 将新元素插入到该位置后
    • 重复步骤 2~5

插入排序.gif

  • 每一趟将一个待排序的记录，按照其关键字的大小插入到有序队列的合适位置里，直到全部插入完成

    1. public static int[] insertionSort(int[] array) {
    2.   if (array.length == 0)
    3.       return array;
    4.   int current;
    5.   for (int i = 0; i < array.length - 1; i++) {
    6.       current = array[i + 1];
    7.       int preIndex = i;
    8.       while (preIndex >= 0 && current < array[preIndex]) {
    9.           array[preIndex + 1] = array[preIndex];
    10.           preIndex--;
    11.       }
    12.       array[preIndex + 1] = current;
    13.   }
    14.   return array;
    15. }

    4、希尔排序（缩小增量排序）

    插入排序加强版

  • 步骤

    • 选择一个增量序列 t1，t2，…，tk，其中 ti>tj，tk=1
    • 按增量序列个数 k，对序列进行 k 趟排序
    • 每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度

希尔排序.png

  1. public static int[] ShellSort(int[] array) {
  2.     int len = array.length;
  3.     int temp, gap = len / 2;
  4.     while (gap > 0) {
  5.         for (int i = gap; i < len; i++) {
  6.             temp = array[i];
  7.             int preIndex = i - gap;
  8.             while (preIndex >= 0 && array[preIndex] > temp) {
  9.                 array[preIndex + gap] = array[preIndex];
  10.                 preIndex -= gap;
  11.             }
  12.             array[preIndex + gap] = temp;
  13.         }
  14.         gap /= 2;
  15.     }
  16.     return array;
  17. }

  • 插入排序和希尔排序比较：

    • 直接插入排序是稳定的；希尔排序是不稳定的
    • 直接插入排序更适合于原始记录基本有序的集合
    • 希尔排序的比较次数和移动次数都要比直接插入排序少，当 N 越大时，效果越明显
    • 在希尔排序中，增量序列 gap 的取法必须满足：最后一个步长必须是 1
    • 直接插入排序也适用于链式存储结构；希尔排序不适用于链式结构

      5、选择排序

  • 步骤

    • 初始状态：无序区为R[1…n]，有序区为空
    • 第 i 趟排序（i=1,2,3…n-1）开始时，当前有序区和无序区分别为 R[1…i-1] 和 R[i…n]。该趟排序从当前无序区中选出关键字最小的记录 R[k]，将它与无序区的第 1 个记录 R 交换，使 R[1…i] 和 R[i+1…n] 分别变为记录个数增加 1 个的新有序区和记录个数减少 1 个的新无序区
    • n-1 趟结束，数组有序化

选择排序.gif

  1. public static int[] selectionSort(int[] array) {
  2.     if (array.length == 0)
  3.         return array;
  4.     for (int i = 0; i < array.length; i++) {
  5.         int minIndex = i;
  6.         for (int j = i; j < array.length; j++) {
  7.             if (array[j] < array[minIndex])         //找到最小的数
  8.                 minIndex = j;                         //将最小数的索引保存
  9.         }
  10.         int temp = array[minIndex];
  11.         array[minIndex] = array[i];
  12.         array[i] = temp;
  13.     }
  14.     return array;
  15. }

6、堆排序

堆积是一个近似完全二叉树的结构，满足堆积性质：子结点键值或索引总小于（或者大于）它的父节点

  • 步骤
    • 将初始待排序关键字序列（R1,R2….Rn）构建成大顶堆，此堆为初始的无序区
    • 将堆顶元素 R[1] 与最后一个元素 R[n] 交换，得到新无序区（R1,R2,……Rn-1）和新的有序区（Rn），且满足 R[1,2…n-1] <= R[n]
    • 由于交换后新堆顶 R[1] 可能违反堆性质，需要对当前无序区（R1,R2,……Rn-1）调整为新堆，然后再次将 R[1] 与无序区最后一个元素交换，得到新无序区（R1,R2….Rn-2）和新有序区（Rn-1,Rn)）
    • 不断重复步骤 3 直到有序区的元素个数为 n-1，排序过程完成

堆排序.gif

  1. //声明全局变量，用于记录数组array的长度；
  2. static int len;
  4. public static int[] HeapSort(int[] array) {
  5.     len = array.length;
  6.     if (len < 1) return array;
  7.     buildMaxHeap(array);    //构建一个最大堆
  8.     //循环将堆首位（最大值）与末位交换，然后在重新调整最大堆
  9.     while (len > 0) {
  10.         swap(array, 0, len - 1);
  11.         len--;
  12.         adjustHeap(array, 0);
  13.     }
  14.     return array;
  15. }
  17. //建立最大堆
  18. public static void buildMaxHeap(int[] array) {
  19.     //从最后一个非叶子节点开始向上构造最大堆，for循环这样写好点：i的左子树和右子树分别2i+1和2(i+1)
  20.     for (int i = (len/2- 1); i >= 0; i--) {
  21.         adjustHeap(array, i);
  22.     }
  23. }
  25. //调整成最大堆
  26. public static void adjustHeap(int[] array, int i) {
  27.     int maxIndex = i;
  28.     //如果有左子树，且左子树大于父节点，则将最大指针指向左子树
  29.     if (i  2 < len && array[i  2] > array[maxIndex])
  30.         maxIndex = i * 2 + 1;
  31.     //如果有右子树，且右子树大于父节点，则将最大指针指向右子树
  32.     if (i  2 + 1 < len && array[i  2 + 1] > array[maxIndex])
  33.         maxIndex = i * 2 + 2;
  34.     //如果父节点不是最大值，则将父节点与最大值交换，并且递归调整与父节点交换的位置。
  35.     if (maxIndex != i) {
  36.         swap(array, maxIndex, i);
  37.         adjustHeap(array, maxIndex);
  38.     }
  39. }

7、归并排序

  • 步骤
    • 把长度为 n 的输入序列分成两个长度为 n/2 的子序列
    • 对这两个子序列分别采用归并排序
    • 将两个排序好的子序列合并成一个最终的排序序列

归并排序.gif

  1. public static int[] MergeSort(int[] array) {
  2.     if (array.length < 2) return array;
  3.     int mid = array.length / 2;
  4.     int[] left = Arrays.copyOfRange(array, 0, mid);
  5.     int[] right = Arrays.copyOfRange(array, mid, array.length);
  6.     return merge(MergeSort(left), MergeSort(right));
  7. }
  9. //归并排序——将两段排序好的数组结合成一个排序数组
  10. public static int[] merge(int[] left, int[] right) {
  11.     int[] result = new int[left.length + right.length];
  12.     for (int index = 0, i = 0, j = 0; index < result.length; index++) {
  13.         if (i >= left.length)
  14.             result[index] = right[j++];
  15.         else if (j >= right.length)
  16.             result[index] = left[i++];
  17.         else if (left[i] > right[j])
  18.             result[index] = right[j++];
  19.         else
  20.             result[index] = left[i++];
  21.     }
  22.     return result;
  23. }
  • 若子表个数为奇数，最后一个子表无须和其他子表归并（即本趟处理轮空）

  • 若子表个数为偶数，最后一对子表中后一个子表区间的上限为 n-1

    8、基数排序

  • 步骤

    • 取得数组中的最大数，并取得位数
    • arr 为原始数组，从最低位开始取每个位组成 radix 数组
    • 对 radix 进行计数排序（利用计数排序适用于小范围数的特点）

基数排序.gif

  1. public static int[] RadixSort(int[] array) {
  2.     if (array == null || array.length < 2)
  3.         return array;
  4.     //先算出最大数的位数；
  5.     int max = array[0];
  6.     for (int i = 1; i < array.length; i++) {
  7.         max = Math.max(max, array[i]);
  8.     }
  9.     int maxDigit = 0;
  10.     while (max != 0) {
  11.         max /= 10;
  12.         maxDigit++;
  13.     }
  14.     int mod = 10, div = 1;
  15.     ArrayList<ArrayList> bucketList = new ArrayList<ArrayList>();
  16.     for (int i = 0; i < 10; i++)
  17.         bucketList.add(new ArrayList());
  18.     for (int i = 0; i < maxDigit; i++, mod = 10, div = 10) {
  19.         for (int j = 0; j < array.length; j++) {
  20.             int num = (array[j] % mod) / div;
  21.             bucketList.get(num).add(array[j]);
  22.         }
  23.         int index = 0;
  24.         for (int j = 0; j < bucketList.size(); j++) {
  25.             for (int k = 0; k < bucketList.get(j).size(); k++)
  26.                 array[index++] = bucketList.get(j).get(k);
  27.             bucketList.get(j).clear();
  28.         }
  29.     }
  30.     return array;
  31. }

MSD 从高位开始进行排序 LSD 从低位开始进行排序

  • 算法分析：

    基数排序的效率和初始序列是否有序无关

    • 时间复杂度平均情况：O(d(n+r))
    • 时间复杂度最坏情况：O(Nlog_2N)
    • 时间复杂度最坏情况：O(d(n+r))
    • 时间复杂度最好情况：O(d(n+r))
    • 空间复杂度O(n+r)，对于任何位数上的基数进行“装桶”操作时都需要 n+r 个临时空间
    • 稳定性：稳定

      9、计数排序

  • 步骤

    • 找出待排序的数组中最大和最小的元素
    • 统计数组中每个值为 i 的元素出现的次数，存入数组 C 的第 i 项
    • 对所有计数累加（从 C 中第一个元素开始，每一项和前一项相加）
    • 反向填充目标数组：将每个元素 i 放在新数组的第 C(i) 项，每放一个元素就将 C(i) 减去 1

计数排序.gif

  1. public static int[] CountingSort(int[] array) {
  2.     if (array.length == 0) return array;
  3.     int bias, min = array[0], max = array[0];
  4.     for (int i = 1; i < array.length; i++) {
  5.         if (array[i] > max)
  6.             max = array[i];
  7.         if (array[i] < min)
  8.             min = array[i];
  9.     }
  10.     bias = 0 - min;
  11.     int[] bucket = new int[max - min + 1];
  12.     Arrays.fill(bucket, 0);
  13.     for (int i = 0; i < array.length; i++) {
  14.         bucket[array[i] + bias];
  15.     }
  16.     int index = 0, i = 0;
  17.     while (index < array.length) {
  18.         if (bucket[i] != 0) {
  19.             array[index] = i - bias;
  20.             bucket[i]--;
  21.             index;
  22.         } else
  23.             i++;
  24.     }
  25.     return array;
  26. }

10、桶排序

计数排序升级版

  • 步骤
    • 人为设置一个 BucketSize，作为每个桶所能放置多少个不同数值（当 BucketSize==5 时，可以存放｛1,2,3,4,5｝这几种数字，但容量不限，即可存放 100 个 3）
    • 遍历输入数据，把数据一个一个放到对应的桶里去
    • 对每个不是空的桶进行排序，可以使用其它排序方法，也可以递归使用桶排序
    • 从不是空的桶里把排好序的数据拼接起来

桶排序.png

  1. public static ArrayList BucketSort(ArrayList array, int bucketSize) {
  2.     if (array == null || array.size() < 2)
  3.         return array;
  4.     int max = array.get(0), min = array.get(0);
  5.     // 找到最大值最小值
  6.     for (int i = 0; i < array.size(); i++) {
  7.         if (array.get(i) > max)
  8.             max = array.get(i);
  9.         if (array.get(i) < min)
  10.             min = array.get(i);
  11.     }
  12.     int bucketCount = (max - min) / bucketSize + 1;
  13.     ArrayList<ArrayList> bucketArr = new ArrayList<>(bucketCount);
  14.     ArrayList resultArr = new ArrayList<>();
  15.     for (int i = 0; i < bucketCount; i++) {
  16.         bucketArr.add(new ArrayList());
  17.     }
  18.     for (int i = 0; i < array.size(); i++) {
  19.         bucketArr.get((array.get(i) - min) / bucketSize).add(array.get(i));
  20.     }
  21.     for (int i = 0; i < bucketCount; i++) {
  22.         if (bucketSize == 1) {                 // 如果带排序数组中有重复数字时
  23.             for (int j = 0; j < bucketArr.get(i).size(); j++)
  24.                 resultArr.add(bucketArr.get(i).get(j));
  25.         } else {
  26.             if (bucketCount == 1)
  27.                 bucketSize--;
  28.             ArrayList temp = BucketSort(bucketArr.get(i), bucketSize);
  29.             for (int j = 0; j < temp.size(); j++)
  30.                 resultArr.add(temp.get(j));
  31.         }
  32.     }
  33.     return resultArr;
  34. }
  • 基数排序 vs 计数排序 vs 桶排序
    • 都利用桶的概念
    • 基数排序： 根据键值的每位数字来分配桶
    • 计数排序： 每个桶只存储单一键值
    • 桶排序： 每个桶存储一定范围的数值