排序算法

Author Avatar
Zhu Yuexin Jul 03, 2019

大纲

  1. 冒泡排序
  2. 快速排序
  3. 插入排序
  4. 希尔排序
  5. 选择排序
  6. 归并排序
  7. 基数排序
  8. 堆排序
  9. 计数排序
  10. 桶排序

冒泡排序

原理

基本原理是每次比较相邻两个元素，如果顺序不满足就交换位置。

比较次数为：(n-1) + (n-2) + … + 1 = n*(n-1) / 2，因此冒泡排序的时间复杂度为O(n^2)

BubbleSort

代码

public void bubbleSort(int[] arr) {
  // 冒泡排序
  // 每次循环时，比较相邻两个数，将大数往后交换
  for (int i=0; i arr[j+1]) {
        int temp = arr[j];
        arr[j] = arr[j+1];
        arr[j+1] = temp;
      }
    }
  }
}

快速排序

原理

采用分治的思想，每次选取一个基准数，将序列分隔成两部分（如左边部分小于基准数，右边部分大于基准数，那么左边部分每个数都小于右边部分），然后再分别对两个部分的序列继续分隔。（通常将第一个元素选为基准数，也可以随机选择一个数作为基准数）。时间复杂度：O(nlogn)

代码

填坑法

  • 选取第一个数为基准数，用两个索引如low和high分别指向数组arr的第一位和最后一位
  • 先往前移动高位索引high，直到遇到小于基准数的数；将arr[high]赋值给arr[low]
  • 向后移动低位索引low，直到遇到大于基准数的数；将arr[low]赋值给arr[high]
  • 重复执行第2，3步，直到low和high重合
  • 将基准数赋值给arr[low]
  • 这样数组arr就被分成了小于基准数和大于基准数的两部分，然后再分别递归处理这两个子数组
public static void quickSort(int[] arr, int start, int end) {
  if (start >= end) {
    return;
  }
  // 把数组中的开始数字作为标准数
  int standard = arr[start];
  // 记录需要排序的下标
  int low = start;
  int high = end;
  // 循环找比标准数大的数和比标准数小的数
  while (low < high) {
    // 右边的数字比标准数大
    while (low < high && standard <= arr[high]) {
      high--;
    }
    // 使用右边的数字替换左边的数字
    arr[low] = arr[high];
    // 如果左边的数字比标准数小
    while (low < high && standard >= arr[low]) {
      low++;
    }
    // 使用左边的数替换右边的数
    arr[high] = arr[low];
  }
  // 把标准数赋给低和高重合的位置
  arr[low] = standard;
  // 递归
  // 处理所有的小数字
  quickSort(arr, start, low);
  // 处理所有的大数字
  quickSort(arr, low+1, end);
}

指针交换法

  • 选取第一个数为基准数，用两个索引如low和high分别指向数组arr的第一位和最后一位
  • 先往前移动高位索引high，直到遇到小于基准数的数；向后移动低位索引low，直到遇到大于等于基准数的数
  • 交换arr[low]和arr[high]
  • 重复执行2，3步直到low和high重合
  • 数组被分成大小两部分后，分别递归处理这两个部分
public static void quickSort2(int[] arr, int start, int end) {
  if (start >= end) {
    return;
  }
  // 开始数字作为标准数
  int standard = arr[start];
  // 记录高低索引
  int low = start;
  int high = end;
  while (low < high) {
    // 右边完全小于标准数的要准备移到左边（防止最左和最右都等于基本数时陷入死循环）
    while (low < high && standard <= arr[high]) {
      high--;
    }
    // 左边大于等于标准数的要准备移到右边
    while (low < high && standard > arr[low]) {
      low++;
    }
    // 交换
    int temp = arr[low];
    arr[low] = arr[high];
    arr[high] = temp;
  }
  // 处理小的部分
  quickSort2(arr, start, low);
  // 处理大的部分
  quickSort2(arr, low+1, end);
}

非递归法

非递归法可以用栈来实现。递归操作可以看作是操作数的入栈和出栈。

  • 首先定义一个栈stack，第一步的操作肯定是从原数组第一位为开始索引，最后一位为结束索引。将开始和结束索引的记录入栈。
  • 当stack不为空时，重复执行以下操作：
    • 将栈顶记录的数组开始结束索引出栈
    • 采用填坑法或指针交换法将数组开始和结束索引之间的部分分为大小两个部分
    • 然后分别判断这两个部分的长度是否大于2，如果满足则将其对应的开始结束索引记录入栈
public static void quickSort3(int[] arr) {
  // 用栈记录每一次的操作
  Stack> stack = new Stack<>();
  // 第一次操作
  Map firstOp = new HashMap<>();
  firstOp.put("start", 0);
  firstOp.put("end", arr.length-1);
  // 第一次操作入栈
  stack.push(firstOp);
  while (!stack.isEmpty()) {
    // 取出栈中的操作
    Map op = stack.pop();
    int start = op.get("start");
    int low = start;
    int end = op.get("end");
    int high = end;
    int standard = arr[low];
    // 这里可用"填坑法"或"指针交换法"
    while (low < high) {
      while (low < high && standard <= arr[high]) {
        high--;
      }
      arr[low] = arr[high];
      while (low < high && standard >= arr[low]) {
        low++;
      }
      arr[high] = arr[low];
    }
    arr[low] = standard;
    // 存入操作数
    if (low > start) {
      Map leftOp = new HashMap<>();
      leftOp.put("start", start);
      leftOp.put("end", low);
      stack.push(leftOp);
    }
    if (low + 1 < end) {
      Map rightOp = new HashMap<>();
      rightOp.put("start", low + 1);
      rightOp.put("end", end);
      stack.push(rightOp);
    }
  }
}

插入排序

时间复杂度：O(n^2)

  • 将第一个元素看作是已排序的序列，下一个元素开始
  • 将当前数向前（已排序的序列）比较，遇到比当前元素大的数，将那个数往后挪
  • 直到遇到比当前数小的数，将当前数插入到这个数后面
  • 重复执行

public static void insertionSort(int[] arr) {
  for (int i=1; i=0 && arr[j]>temp; j--) {
      // 如果前面的数大于第i个数，则依次往后挪
      arr[j+1] = arr[j];
    }
    // 遇到小于第i个数的数了，第i个数就放在这个数后面
    arr[j+1] = temp;
  }
}

希尔排序

时间复杂度：O(n^(3/2))

1959年Shell发明，第一个突破O(n2)的排序算法，是简单插入排序的改进版。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。

先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：

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

希尔排序的核心在于间隔序列的设定。既可以提前设定好间隔序列，也可以动态的定义间隔序列。动态定义间隔序列的算法是《算法（第4版）》的合著者Robert Sedgewick提出的。

ShellSort

代码

public static void shellSort(int[] arr) {
  for (int step=arr.length/2; step>0; step/=2) {
    for (int i=step; i=0 && arr[i]>temp; j-=step) {
        arr[j+step] = arr[j];
      }
      arr[j+step] = temp;
    }
  }
}

public static void shellSort2(int[] arr) {
  for (int step=arr.length/2; step>0; step/=2) {
    for (int i=0; i=0 && arr[k]>temp; k-=step) {
          arr[k+step] = arr[k];
        }
        arr[k+step] = temp;
      }
    }
  }
}

选择排序

时间复杂度：O(n^2)

选择排序的思想非常简单，在未排序序列中寻找最小数，与未排序序列第一个数交换，重复执行这个操作。

代码

public static void selectSort(int[] arr) {
  // 每次遍历将最小数放到前面
  for (int i=0; i < arr.length-1; i++) {
    int minIndex = i;
    // 寻找i之后的最小数
    for (int j=i+1; j < arr.length; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }
    // 将最小数与i交换
    int min = arr[minIndex];
    arr[minIndex] = arr[i];
    arr[i] = min;
  }
}

归并排序

时间复杂度：O(nlogn)

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。

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

代码

public static void mergeSort(int[] arr, int left, int mid, int right) {
  if (left == right - 1) {
    return;
  }
  mergeSort(arr, left, left + (mid - left)/2, mid);
  mergeSort(arr, mid, mid + (right - mid)/2, right);
  int[] result = new int[right - left];
  int i = left, j = mid;
  while (i < mid || j < right) {
    int index = i - left + j - mid;
    if (j == right || (i < mid && arr[i] < arr[j])) {
      result[index] = arr[i++];
    } else if (i == mid || (j < right && arr[i] > arr[j])){
      result[index] = arr[j++];
    } else {
      result[index] = arr[i++];
      result[index+1] = arr[j++];
    }
  }
  for (int k=0; k

基数排序

基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。

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

代码

二维数组实现

public static void radixSort(int[] arr) {
  // 寻找最大值
  int max = Integer.MIN_VALUE;
  for (int v : arr) {
    if (v > max) {
      max = v;
    }
  }
  // 最大值的位数
  int maxLength = String.valueOf(max).length();
  // 二维数组保存每个基数对应的值
  int[][] temp = new int[10][arr.length];
  // 记录每个基数的值的个数
  int[] number = new int[10];
  for (int i=0, m=1; i

队列实现

public static void radixSort2(int[] arr) {
  // 寻找最大值
  int max = Integer.MIN_VALUE;
  for (int v : arr) {
    if (v > max) {
      max = v;
    }
  }
  // 最大值的位数
  int maxLength = String.valueOf(max).length();
  // 用队列保存每个基数对应的值
  Queue[] temp = new LinkedBlockingQueue[10];
  for (int i=0; i();
  }
  for (int i=0, m=1; i queue : temp) {
      while (!queue.isEmpty()) {
        arr[index++] = queue.poll();
      }
    }
  }
}

堆排序

时间复杂度：O(nlogn)

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

  • 将初始待排序关键字序列(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)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。

代码

public static void heapSort(int[] arr, int end) {
  if (end < 1) {
    return;
  }
  // 找到堆中最后一个有子节点的顶点位置，从后往前遍历每一个有子节点的顶点
  for (int i = (end - 1) / 2; i >= 0; i--) {
    // 左子节点的位置
    int left = i*2 + 1;
    // 右子节点的位置
    int right = i*2 + 2;
    // 将子树的最大数交换到顶点处
    if (right <= end && arr[right] > arr[i]) {
      int temp = arr[right];
      arr[right] = arr[i];
      arr[i] = temp;
    }
    if (left <= end && arr[left] > arr[i]) {
      int temp = arr[left];
      arr[left] = arr[i];
      arr[i] = temp;
    }
  }
  // 交换顶点和最后一个节点
  int temp = arr[0];
  arr[0] = arr[end];
  arr[end] = temp;
  // 此时最后一个节点的值为当前堆中最大，继续处理前面的节点
  heapSort(arr, end-1);
}

计数排序

计数排序不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

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

代码

public static void countingSort(int[] arr) {
  // 最大值和最小值 可以确定这个数组的值的范围
  int max = Integer.MIN_VALUE;
  int min = Integer.MAX_VALUE;
  for (int v : arr) {
    if (v > max) {
      max = v;
    }
    if (v < min) {
      min = v;
    }
  }
  // 统计每个数出现的次数
  int[] counts = new int[max - min + 1];
  for (int v : arr) {
    counts[v - min]++;
  }
  // 将统计后的数值填充到原数组中
  int index = 0;
  for (int i=0; i 0) {
      arr[index++] = i + min;
    }
  }
}

桶排序

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排）。

  • 设置一个定量的数组当作空桶；
  • 遍历输入数据，并且把数据一个一个放到对应的桶里去；
  • 对每个不是空的桶进行排序；
  • 从不是空的桶里把排好序的数据拼接起来。

代码

public static void bucketSort(int[] arr, int bucketSize) {
  // 最大值和最小值用来确定数组的范围
  int max = Integer.MIN_VALUE;
  int min = Integer.MAX_VALUE;
  for (int v : arr) {
    if (v > max) {
      max = v;
    }
    if (v < min) {
      min = v;
    }
  }
  // 桶的数量
  int bucketCount = (max - min) / bucketSize + 1;
  // 每个桶涉及到频繁的插入，所以采用LinkedList
  List[] buckets = new LinkedList[bucketCount];
  for (int v : arr) {
    // 通过映射函数获取该值对应的桶
    int index = (v - min) / bucketSize;
    if (buckets[index] == null) {
      buckets[index] = new LinkedList<>();
    }
    // 有序放入桶中
    int i=0;
    for (; i bucket : buckets) {
    if (bucket != null) {
      for (int v : bucket) {
        arr[index++] = v;
      }
    }
  }
}