Java 实现几种排序算法

Question

一、所谓 排序 ，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。排序算法，就是如何使得记录按照要求排列的方法。排序算法在很多领域得 到相当地重视，尤其是在大量数据的处理方面。一个优秀的算法可以节省大量的资源。在各个领域中考虑到数据的各种限制和规范，要得到一个符合实际的优秀算 法，得经过大量的推理和分析。

二、排序算法可以分为内部排序和外部排序。

内部排序是数据记录在内存中进行排序。

外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。

常见的内部排序算法有： 冒泡排序 、 选择排序 、 插入排序 、 希尔排序 、 快速排序 、 归并排序 、 堆排序、 基数排序 等。

三、这里主要介绍常见的几种排序算法

1）冒泡排序

• a、冒泡排序，是通过每一次遍历获取最大/最小值
• b、将最大值/最小值放在尾部/头部
• c、然后除开最大值/最小值，剩下的数据在进行遍历获取最大/最小值

代码实现

public static void main(String[] args) {

  int arr[] = {8, 5, 3, 2, 4};

  //冒泡
  for (int i = 0; i < arr.length; i++) {
    //外层循环，遍历次数
    for (int j = 0; j < arr.length - i - 1; j++) {
      //内层循环，升序（如果前一个值比后一个值大，则交换）
      //内层循环一次，获取一个最大值
      if (arr[j] > arr[j + 1]) {
        int temp = arr[j + 1];
        arr[j + 1] = arr[j];
        arr[j] = temp;
      }
    }
  }
}

e、排序过程（红色：移动的数据）

5,3,2,4,8
3,2,4,5,8
2,3,4,5,8
2,3,4,5,8
2,3,4,5,8

2）选择排序

• a、将第一个值看成最小值
• b、然后和后续的比较找出最小值和下标
• c、交换本次遍历的起始值和最小值
• d、说明：每次遍历的时候，将前面找出的最小值，看成一个有序的列表，后面的看成无序的列表，然后每次遍历无序列表找出最小值。

代码实现

public static void main(String[] args) {

  int arr[] = {6, 5, 3, 2, 4};

  //选择
  for (int i = 0; i < arr.length; i++) {
    //默认第一个是最小的。
    int min = arr[i];
    //记录最小的下标
    int index = i;
    //通过与后面的数据进行比较得出，最小值和下标
    for (int j = i + 1; j < arr.length; j++) {
      if (min > arr[j]) {
        min = arr[j];
        index = j;
      }
    }
    //然后将最小值与本次循环的，开始值交换
    int temp = arr[i];
    arr[i] = min;
    arr[index] = temp;
    //说明：将 i 前面的数据看成一个排好的队列，i 后面的看成一个无序队列。每次只需要找无需的最小值，做替换
  }
}

f、排序过程（红色：移动的数据）

2,5,3,6,4
2,3,5,6,4
2,3,4,6,5
2,3,4,5,6
2,3,4,5,6

3）插入排序

a、默认从第二个数据开始比较。

b、如果第二个数据比第一个小，则交换。然后在用第三个数据比较，如果比前面小，则插入（狡猾）。否则，退出循环

c、说明：默认将第一数据看成有序列表，后面无序的列表循环每一个数据，如果比前面的数据小则插入（交换）。否则退出。

d、代码实现

public static void main(String[] args) {

  int arr[] = {7, 5, 3, 2, 4};

  //插入排序
  for (int i = 1; i < arr.length; i++) {
    //外层循环，从第二个开始比较
    for (int j = i; j > 0; j--) {
      //内存循环，与前面排好序的数据比较，如果后面的数据小于前面的则交换
      if (arr[j] < arr[j - 1]) {
        int temp = arr[j - 1];
        arr[j - 1] = arr[j];
        arr[j] = temp;
      } else {
        //如果不小于，说明插入完毕，退出内层循环
        break;
      }
    }
  }
}

e、排序过程（红色：有序，黑色：无序）

5,7,3,2,4
3,5,7,2,4
2,3,5,7,4
2,3,4,5,7

4）希尔排序（插入排序变种版）

a、基本上和插入排序一样的道理

b、不一样的地方在于，每次循环的步长，通过减半的方式来实现

c、说明：基本原理和插入排序类似，不一样的地方在于。通过间隔多个数据来进行插入排序。

d、代码实现

public static void main(String[] args) {

  int arr[] = {7, 5, 3, 2, 4};

  //希尔排序（插入排序变种版）
  for (int i = arr.length / 2; i > 0; i /= 2) {
    //i 层循环控制步长
    for (int j = i; j < arr.length; j++) {
      //j 控制无序端的起始位置
      for (int k = j; k > 0  && k - i >= 0; k -= i) {
        if (arr[k] < arr[k - i]) {
          int temp = arr[k - i];
          arr[k - i] = arr[k];
          arr[k] = temp;
        } else {
          break;
        }
      }
    }
    //j,k 为插入排序，不过步长为 i
  }
}

e、排序过程（步长 4/2/1)

4,1,3,2,6,5,8,9,7 3,1,4,2,6,5,7,9,8 1,2,3,4,5,6,7,8,9

5）快速排序

• a、确认列表第一个数据为中间值，第一个值看成空缺（低指针空缺）。
• b、然后在剩下的队列中，看成有左右两个指针（高低）。
• c、开始高指针向左移动，如果遇到小于中间值的数据，则将这个数据赋值到低指针空缺，并且将高指针的数据看成空缺值（高指针空缺）。然后先向右移动一下低指针，并且切换低指针移动。
• d、当低指针移动到大于中间值的时候，赋值到高指针空缺的地方。然后先高指针向左移动，并且切换高指针移动。重复 c、d 操作。
• e、直到高指针和低指针相等时退出，并且将中间值赋值给对应指针位置。
• f、然后将中间值的左右两边看成行的列表，进行快速排序操作。

代码实现

 public static void main(String[] args) {

  int arr[] = {7, 5, 3, 2, 4, 1, 8, 9, 6};

  //快速排序
  int low = 0;
  int high = arr.length - 1;
  quickSort(arr, low, high);  
}

public static void quickSort(int[] arr, int low, int high) {
  //如果指针在同一位置（只有一个数据时)，退出
  if (high - low < 1) {
    return;
  }
  //标记，从高指针开始，还是低指针（默认高指针）
  boolean flag = true;
  //记录指针的其实位置
  int start = low;
  int end = high;
  //默认中间值为低指针的第一个值
  int midValue = arr[low];
  while (true) {
    //高指针移动
    if (flag) {
      //如果列表右方的数据大于中间值，则向左移动
      if (arr[high] > midValue) {
        high--;
      } else if (arr[high] < midValue) {
        //如果小于，则覆盖最开始的低指针值，并且移动低指针，标志位改成从低指针开始移动
        arr[low] = arr[high];
        low++;
        flag = false;
      }
    } else {
      //如果低指针数据小于中间值，则低指针向右移动
      if (arr[low] < midValue) {
        low++;
      } else if (arr[low] > midValue) {
        //如果低指针的值大于中间值，则覆盖高指针停留时的数据，并向左移动高指针。切换为高指针移动
        arr[high] = arr[low];
        high--;
        flag = true;
      }
    }
    //当两个指针的位置相同时，则找到了中间值的位置，并退出循环
    if (low == high) {
      arr[low] = midValue;
      break;
    }
  }
  //然后出现有，中间值左边的小于中间值。右边的大于中间值。
  //然后在对左右两边的列表在进行快速排序
  quickSort(arr, start, low -1);
  quickSort(arr, low + 1, end);
}

h、排序过程（青色：中间值，蓝色：确认位置的数据，红色：移动的数据)

6,5,3,2,4,1,7,9,8
1,5,3,2,4,6,7,9,8
1,5,3,2,4,6,7,9,8
1,4,3,2,5,6,7,9,8
1,2,3,4,5,6,7,9,8
1,2,3,4,5,6,7,9,8
1,2,3,4,5,6,7,8,9

6）归并排序

• a、将列表按照对等的方式进行拆分
• b、拆分小最小快的时候，在将最小块按照原来的拆分，进行合并
• c、合并的时候，通过左右两块的左边开始比较大小。小的数据放入新的块中
• d、说明：简单一点就是先对半拆成最小单位，然后将两半数据合并成一个有序的列表。

代码实现

public static void main(String[] args) {

  int arr[] = {7, 5, 3, 2, 4, 1，6};

  //归并排序
  int start = 0;
  int end = arr.length - 1;
  mergeSort(arr, start, end);
}

public static void mergeSort(int[] arr, int start, int end) {
  //判断拆分的不为最小单位
  if (end - start > 0) {
    //再一次拆分，知道拆成一个一个的数据
    mergeSort(arr, start, (start + end) / 2);
    mergeSort(arr, (start + end) / 2 + 1, end);
    //记录开始/结束位置
    int left = start;
    int right = (start + end) / 2 + 1;
    //记录每个小单位的排序结果
    int index = 0;
    int[] result = new int[end - start + 1];
    //如果查分后的两块数据，都还存在
    while (left <= (start + end) / 2 && right <= end) {
      //比较两块数据的大小，然后赋值，并且移动下标
      if (arr[left] <= arr[right]) {
        result[index] = arr[left];
        left++;
      } else {
        result[index] = arr[right];
        right++;
      }
      //移动单位记录的下标
      index++;
    }
    //当某一块数据不存在了时
    while (left <= (start + end) / 2 || right <= end) {
      //直接赋值到记录下标
      if (left <= (start + end) / 2) {
        result[index] = arr[left];
        left++;
      } else {
        result[index] = arr[right];
        right++;
      }
      index++;
    }
    //最后将新的数据赋值给原来的列表，并且是对应分块后的下标。
    for (int i = start; i <= end; i++) {
      arr[i] = result[i - start];
    }
  }
}

f、排序过程

5,7,3,2,4,1,6
5,7,2,3,4,1,6
2,3,5,7,4,1,6
2,3,5,7,1,4,6
2,3,5,7,1,4,6
1,2,3,4,5,6,7

7）堆排序

　

• a、先将初始序列 K[1..n]K[1..n]建成一个大顶堆, 那么此时第一个元素 K1K1 最大, 此堆为初始的无序区.
• b、再将关键字最大的记录 K1K1 (即堆顶, 第一个元素) 和无序区的最后一个记录 KnKn 交换, 由此得到新的无序区 K[1..n−1]K[1..n−1]和有序区 K[n]K[n], 且满足 K[1..n−1].keys⩽K[n].key
• c、交换 K1K1 和 KnKn 后, 堆顶可能违反堆性质, 因此需将 K[1..n−1]K[1..n−1]调整为堆. 然后重复步骤 2, 直到无序区只有一个元素时停止。
• d、说明：此处以大顶堆为例，堆排序的过程就是将待排序的序列构造成一个堆，选出堆中最大的移走，再把剩余的元素调整成堆，找出最大的再移走，重复直至有序。

从算法描述来看，堆排序需要两个过程，一是建立堆，二是堆顶与堆的最后一个元素交换位置。所以堆排序有两个函数组成。一是建堆函数，二是反复调用建堆函数以选择出剩余未排元素中最大的数来实现排序的函数。

总结起来就是定义了以下几种操作：

• 最大堆调整（Max_Heapify）：将堆的末端子节点作调整，使得子节点永远小于父节点
• 创建最大堆（Build_Max_Heap）：将堆所有数据重新排序
• 堆排序（HeapSort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算

对于堆节点的访问：

• 父节点 i 的左子节点在位置： (2*i+1) ;
• 父节点 i 的右子节点在位置： (2*i+2) ;
• 子节点 i 的父节点在位置： floor((i-1)/2) ;

/**
* @param a
*/
public static void sort(int[] a) {

　　for (int i = a.length - 1; i > 0; i--) {
　　　　max_heapify(a, i);
　　　　//堆顶元素（第一个元素) 与 Kn 交换
　　　　int temp = a[0];
　　　　a[0] = a[i];
　　　　a[i] = temp;
　　}
}

/*** * * 将数组堆化 * i = 第一个非叶子节点。 * 从第一个非叶子节点开始即可。无需从最后一个叶子节点开始。 * 叶子节点可以看作已符合堆要求的节点，根节点就是它自己且自己以下值为最大。 * * @param a * @param n */
public static void max_heapify(int[] a, int n) {
　　int child;
　　for (int i = (n - 1) / 2; i >= 0; i--) {
　　　　//左子节点位置
　　　　child = 2 * i + 1;
　　　　//右子节点存在且大于左子节点，child 变成右子节点
　　　　if (child != n && a[child] < a[child + 1]) {
　　　　　　child++;
　　　　}
　　　　//交换父节点与左右子节点中的最大值
　　　　if (a[i] < a[child]) {
　　　　　　int temp = a[i];
　　　　　　a[i] = a[child];
　　　　　　a[child] = temp;
　　　　}
　　}
}

f、排序过程（）

1. 建立堆的过程, 从 length/2 一直处理到 0, 时间复杂度为 O(n);
2. 调整堆的过程是沿着堆的父子节点进行调整, 执行次数为堆的深度, 时间复杂度为 O(lgn);
3. 堆排序的过程由 n 次第 2 步完成, 时间复杂度为 O(nlgn).
4. 由于堆排序中初始化堆的过程比较次数较多, 因此它不太适用于小序列。 同时由于多次任意下标相互交换位置, 相同元素之间原本相对的顺序被破坏了, 因此, 它是不稳定的排序。

8）基数排序

基本思想

它是这样实现的：将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后，数列就变成一个有序序列。

基数排序按照优先从高位或低位来排序有两种实现方案：

• MSD（Most significant digital） 从最左侧高位开始进行排序。先按 k1 排序分组, 同一组中记录, 关键码 k1 相等, 再对各组按 k2 排序分成子组, 之后, 对后面的关键码继续这样的排序分组, 直到按最次位关键码 kd 对各子组排序后. 再将各组连接起来, 便得到一个有序序列。MSD 方式适用于位数多的序列。

• LSD （Least significant digital）从最右侧低位开始进行排序。先从 kd 开始排序，再对 kd-1 进行排序，依次重复，直到对 k1 排序后便得到一个有序序列。LSD 方式适用于位数少的序列。

我们以 LSD 为例，从最低位开始，具体算法描述如下：

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

代码实现　　

基数排序：通过序列中各个元素的值，对排序的 N 个元素进行若干趟的“分配”与“收集”来实现排序。

• 分配：我们将 L[i]中的元素取出，首先确定其个位上的数字，根据该数字分配到与之序号相同的桶中

• 收集：当序列中所有的元素都分配到对应的桶中，再按照顺序依次将桶中的元素收集形成新的一个待排序列 L[]。对新形成的序列 L[]重复执行分配和收集元素中的十位、百位...直到分配完该序列中的最高位，则排序结束

public static void sort(int[] arr) { 
　　if (arr.length <= 1) return; 

　　//取得数组中的最大数，并取得位数 
　　int max = 0; 
　　for (int i = 0; i < arr.length; i++) { 
　　　　if (max < arr[i]) { 
　　　　　　max = arr[i]; 
　　　　} 
　　} 

　　int maxDigit = 1; 
　　while (max / 10 > 0) { 
　　　　maxDigit++; 
　　　　max = max / 10; 
　　} 

　　//申请一个桶空间 
　　int[][] buckets = new int[10][arr.length]; 
　　int base = 10; 
　　//从低位到高位，对每一位遍历，将所有元素分配到桶中 
　　for (int i = 0; i < maxDigit; i++) { 
　　　　int[] bktLen = new int[10]; 
　　　　//存储各个桶中存储元素的数量 
　　　　//分配：将所有元素分配到桶中 
　　　　for (int j = 0; j < arr.length; j++) {
　　　　　　int whichBucket = (arr[j] % base) / (base / 10);
　　　　　　buckets[whichBucket][bktLen[whichBucket]] = arr[j];
　　　　　　bktLen[whichBucket]++;
　　　　} 

　　　　//收集：将不同桶里数据挨个捞出来,为下一轮高位排序做准备,由于靠近桶底的元素排名靠前,因此从桶底先捞
　　　　int k = 0;
　　　　for (int b = 0; b < buckets.length; b++) {
　　　　　　for (int p = 0; p < bktLen[b]; p++) {
　　　　　　　　arr[k++] = buckets[b][p];
　　　　　　}
　　　　}
　　　　System.out.println("Sorting: " + Arrays.toString(arr));
　　　　base *= 10;
　　}
}

f、排序过程

1. 其中，d 为位数，r 为基数，n 为原数组个数。在基数排序中，因为没有比较操作，所以在复杂上，最好的情况与最坏的情况在时间上是一致的，均为 O(d*(n + r)) 。

2. 基数排序更适合用于对时间, 字符串等这些 整体权值未知的数据 进行排序。

   基数排序不改变相同元素之间的相对顺序，因此它是稳定的排序算法。

   基数排序 vs 计数排序 vs 桶排序

   这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：

   1. 基数排序：根据键值的每位数字来分配桶
   2. 计数排序：每个桶只存储单一键值
   3. 桶排序：每个桶存储一定范围的数值

四、各种算法的实现方式，肯定有很多种，我这里只要是讲解排序的过程。主要是为了方便理解

各种排序性能对比如下：

排序类型	平均情况	最好情况	最坏情况	辅助空间	稳定性
冒泡排序	O(n²)	O(n)	O(n²)	O(1)	稳定
选择排序	O(n²)	O(n²)	O(n²)	O(1)	不稳定
直接插入排序	O(n²)	O(n)	O(n²)	O(1)	稳定
折半插入排序	O(n²)	O(n)	O(n²)	O(1)	稳定
希尔排序	O(n^1.3)	O(nlogn)	O(n²)	O(1)	不稳定
归并排序	O(nlog₂n)	O(nlog₂n)	O(nlog₂n)	O(n)	稳定
快速排序	O(nlog₂n)	O(nlog₂n)	O(n²)	O(nlog₂n)	不稳定
堆排序	O(nlog₂n)	O(nlog₂n)	O(nlog₂n)	O(1)	不稳定
计数排序	O(n+k)	O(n+k)	O(n+k)	O(k)	稳定
桶排序	O(n+k)	O(n+k)	O(n²)	O(n+k)	(不) 稳定
基数排序	O(d(n+k))	O(d(n+k))	O(d(n+kd))	O(n+kd)	稳定

从时间复杂度来说：

1. 平方阶 O(n²) 排序：各类简单排序：直接插入、直接选择和冒泡排序
2. 线性对数阶 O(nlog₂n) 排序：快速排序、堆排序和归并排序
3. O(n1+§)) 排序，§是介于 0 和 1 之间的常数：希尔排序
4. 线性阶 O(n) 排序：基数排序，此外还有桶、箱排序

论是否有序的影响：

• 当原表有序或基本有序时，直接插入排序和冒泡排序将大大减少比较次数和移动记录的次数，时间复杂度可降至 O（n）；
• 而快速排序则相反，当原表基本有序时，将蜕化为冒泡排序，时间复杂度提高为 O（n2）；
• 原表是否有序，对简单选择排序、堆排序、归并排序和基数排序的时间复杂度影响不大。