通过动画带你复习排序算法

1. 比较型的算法

1.1. 选择排序

1.1.1. 动画

1.1.2. 逻辑

• 从第一个位置遍历到最后一个位置，找到最小的那个元素，与第一个位置交换
  
• 从第二个位置遍历到最后一个位置，找到最小的那个元素，与第二个位置交换
  
• 重复上面的过程，直到所有位置都排好序，最前面已经排好序的位置不用再参与遍历
  

代码过于简单，不宜展示

1.2. 冒泡排序

1.2.1. 动画

1.2.2. 逻辑

• 将第一个位置与第二个位置比较，如果比后一个位置的元素大，就交换位置，否则不动
  
• 再将第二个位置与第三个位置比较，如果比后一个位置的元素大，就交换位置，否则不动
  
• 重复上面的过程一直比到最后一个位置，此时最大的值已经来到了最后
  
• 重复上面的比较过程，直到所有位置都排好序，最后面已经排好序的位置不用再参与比较
  

代码过于简单，不宜展示

3. 插入排序

1.3.1. 动画

1.3.2. 逻辑

• 从数组的第二个位置开始，依次与前一个位置比较，如果比前一个位置的元素小，就交换位置，如果比前一个位置的元素大，就停止比较
  
• 重复这个过程，一直到比完最后一个位置，此时排序结束
  

代码过于简单，不宜展示

1.4. 归并排序

1.4.1. 动画

1.4.2. 逻辑

• 找到数组的中位，中位左边和右边分别递归处理，每次递归都是找中位拆分成左右两边
  
• 以左边的递归为例，当递归到只剩下1个元素时，递归就停止，此时不用比较，直接返回
  
• 递归返回后，此时中位左边和右边分别都排好了顺序（其实递归到最深处返回时，左右两边都只有一个元素），将左右两边的元素合并，当然是按照顺序进行合并。随后，递归再往上返回
  
• 一直做递归合并的操作，直到递归到最外层，此时所有的元素都排好序了
  

1.4.3. 代码

1. class Solution {
2.     public int[] sortArray(int[] nums) {
3.         return mergeSort(nums, 0, nums.length - 1);
4.     }
6.     /**
7.      * 归并排序
8.      */
9.     public int[] mergeSort(int[] nums, int left, int right) {
10.         // 左右下标相遇时，说明范围里只有一个元素，无需排序
11.         if (left == right) {
12.             return nums;
13.         }
15.         // 找到左右下标的中点
16.         int mid = (left + right) / 2;
17.         // 排序左边和右边
18.         mergeSort(nums, left, mid);
19.         mergeSort(nums, mid + 1, right);
20.         // 合并左边和右边
21.         merge(nums, left, right, mid);
23.         return nums;
24.     }
26.     private void merge(int[] nums, int left, int right, int mid) {
27.         // 存放排序后的元素
28.         int[] sort = new int[right - left + 1];
29.         // 左右指针
30.         int l = left;
31.         int r = mid + 1;
33.         // 比较两个指针指向的数，一直到其中一个指针走到终点
34.         int i = 0;
35.         while (l <= mid && r <= right) {
36.             if (nums[l] <= nums[r]) {
37.                 sort[i++] = nums[l++];
38.             } else {
39.                 sort[i++] = nums[r++];
40.             }
41.         }
43.         // 将另一个指针移动到终点
44.         while (l <= mid) {
45.             sort[i++] = nums[l++];
46.         }
47.         while (r <= right) {
48.             sort[i++] = nums[r++];
49.         }
51.         // 将 sort 拷贝到 nums 中
52.         System.arraycopy(sort, 0, nums, left, sort.length);
53.     }
54. }

复制代码

2. 非比较型的算法

2.1. 桶排序

2.1.1. 动画

2.1.2. 逻辑

• 准备若干个桶，桶的下标根据数据来决定，一般从0～9。如果是根据员工年龄排序，可以设置100个桶，1～100。（上图桶下标设置成范围了，不如单个值好用）
  
• 遍历数组，根据数值和桶下标，将对应的元素放到对应的桶里
  
• 遍历每个桶，将元素依次倒出即可
  

桶排序对数据样本有要求，数据范围必须是有限的，因为直接关系到桶的数量，桶可以是队列、数组甚至栈。
桶排序是一种思想，下面的计数排序和基数排序是桶排序的两种实现。

2.2. 计数排序

2.2.1. 动画

2.2.2. 逻辑

• 先遍历数组，记下最小值和最大值，这关乎到桶的个数
  
• 再遍历数组，将元素对应的桶中计数+1
  
• 如果是对数字进行排序，直接遍历桶，生成一个新数组，即可得到排序后的数组
  
• 如果是对复杂对象进行排序，则需要使用上图的方式，先计算出桶中计数的前缀和数组
  
• 从后往前遍历，找到元素对应桶中的计数和，这个元素排序的位置下标就是：计数和-1
  
• 然后将桶中计数和-1后再放到桶中
  
• 一直遍历完数组，生成的新数组就是拍好序的
  

通过计算前缀和，倒序遍历数组计算每个元素的位置的原理解释：
以数组 [ 10 7 4 8 5 ] 为例
计算计数数组：[ 1 1 0 1 1 0 1 ]
                4 5 6 7 8 9 10
计算前缀和数组：[ 1 2 2 3 4 4 5 ]
                  4 5 6 7 8 9 10
前缀和数组每一个元素的含义是：1:小于等于4的元素个数；2（第一个）：小于等于5的元素个数；... 5：小于等于10的元素个数。
以数组中的元素 7 来说，数组中小于等于7的元素一共有3个，那么排序后7一定出现在数组的第3个位置。
为什么把一个元素排好序后，前缀和数组的计数要减1？比如说如果数组中有两个7，第一个7排序后，是第3个位置，那么下一个7排序后一定是第2个位置，所以计数要减1。
上图为什么要从后往前遍历排序？从前往后行不行？从前往后其实也是可以的，从后往前遍历是为了保持原数组中相同顺序元素的原始位置，比如说数组中有2个7，如果从前往后排序，第一个7排序后是第3位，第二个7排序后是第2位，刚好和原数组中顺序相反。而从后往前遍历，则刚好可以保持原来的顺序。这样排序算法的稳定性就比较好。
计算前缀和来排序的思路，在基数排序中也有应用。

2.3. 基数排序

2.3.1. 动画

2.3.2. 逻辑

• 找到原数组中最大的元素，计算出它的位数，比如3位数，需要排序3次
  
• 准备10个桶，对应的数值分别是0～9
  
• 先处理个位数字，根据个位数字，将元素放到对应的桶中。随后将桶中元素倒出，如果一个桶中有多个元素，按照先进先出的原则倒出
  
• 再处理十位数字，根据十位数字，将元素放到对应的桶中。随后将桶中元素倒出，如果一个桶中有多个元素，按照先进先出的原则倒出
  
• 一直处理完所有的位数，最后倒出的元素就是拍好序的
  

基数排序是计数排序的升级版，计数排序中桶的个数是按照最小值和最大值来确定的，所以不适用于数值差距较大的场景。
因此基数排序按照元素的位数分别处理，这样每一次排序的数据范围就控制在0～9，只需要10个桶即可。
这里的桶可以是一个队列，刚好满足先进先出的原则。其中这里的桶还可以用数组来实现，其实就是上面的前缀和数组。
如果保证处理十位数字时，个位数字的排序不会被打乱？其实就是靠倒出时的先进先出原则，个位数字排好序后，按照十位数字排序时，个位数小的会先进桶，个位数大的会后进桶，只要按照先进先出的原则，就不会打乱个位数字的顺序。其实换句话说，就是保持排序前数组元素的顺序，计数排序中是靠倒序遍历数组来实现的。

2.3.3. 代码

1. class Solution {
2.     public int[] sortArray(int[] nums) {
3.         quickSort(nums, 0, nums.length - 1);
4.         return nums;
5.     }
6.    
7.     /**
8.      * 快速排序
9.      * 以左边界为基准，找到基准数应该在的位置，基准数左边的数都比它小，右边的数都比它大
10.      *
11.      * @param nums  数组
12.      * @param left  待排序的左边界
13.      * @param right 待排序的右边界
14.      */
15.     public void quickSort(int[] nums, int left, int right) {
16.         // 递归终点
17.         if (left >= right) {
18.             return;
19.         }
20.    
21.         // 左边为基准数，右边为比较数
22.         int pivot = left;
23.         int go = right;
24.    
25.         // 只要两个指针未相遇，就一直比较比较
26.         while (pivot != go) {
27.             // 基准数在右边
28.             if (pivot > go) {
29.                 // 如果比较数比基准数大，则交换位置，比较数下标向左移动
30.                 if (nums[pivot] < nums[go]) {
31.                     // 交换元素位置
32.                     swap(nums, pivot, go);
33.                     // 交换指针位置
34.                     int temp = go;
35.                     go = --pivot;
36.                     pivot = temp;
37.                 }
38.                 // 如果比较数不比基准数大，则比较数下标向右移动
39.                 else {
40.                     go++;
41.                 }
42.             }
43.    
44.             // 基准数在左边
45.             else if (pivot < go) {
46.                 // 如果比较数比基准数小，则交换位置，比较数下标向右移动
47.                 if (nums[pivot] > nums[go]) {
48.                     swap(nums, pivot, go);
49.                     int temp = go;
50.                     go = ++pivot;
51.                     pivot = temp;
52.                 }
53.                 // 如果比较数不比基准数小，则比较数下标向左移动
54.                 else {
55.                     go--;
56.                 }
57.             }
58.         }
59.    
60.         // 递归处理左右两边
61.         quickSort(nums, left, pivot - 1);
62.         quickSort(nums, pivot + 1, right);
63.     }
64.    
65.     private void swap(int[] nums, int i, int j) {
66.         int temp = nums[i];
67.         nums[i] = nums[j];
68.         nums[j] = temp;
69.     }
70. }

复制代码

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！