排序算法-冒泡、选择、堆、插入、归并、快速、希尔

深碍√TFBOYSˉ_ 2024-04-08 08:52 161阅读 0赞
  • 排序算法，默认是升序，左边的值是属于“小”值

理解比较大小后的交换：当前元素cur 和 左边的元素cur-1， 左边的比较大，就交换或者挪动 array[cur] = array[cur-1];

  • 编码的区间设置：建议是左闭 右开，方便 [begin, end)
  • 计算方面：使用右移 代替 除法

☺ 排序算法—重点放到比较的排序算法—冒泡、选择、堆排序 插入、归并、快速、希尔，

对于计数排序、基数排序不是面试的重点

排序算法-冒泡、选择、堆排序

一、冒泡排序：

为什么要叫冒泡排序？ 因为形象生动上，每一轮都是最大的那个数冒到结尾

定义：

① 从头开始index=1 比较每一对相邻元素，如果第1个比第2个大，就交换它们的位置；执行完一轮后，最末尾那个元素就是最大的元素。

② 忽略 ① 中曾经找到的最大元素，重复执行步骤 ①，直到全部元素有序。

【一轮的比较范围是从1 到 end，然后根据理解得到end 从最后一个元素开始不断减少】

  • 第一轮的比较，下标从1开始，左边比右边大进行交换

bb01c783d7749cca21858193e30e3916.png

  1. int array[] = {
  2.     1, 3, 5, -1, -8};
  3.         //比较 end 的结束范围，从最后一个元素-第二个元素
  4.         for(int end = array.length - 1; end > 0; end--) {
  6.             //冒泡排序-一轮的交换
  7.             for(int begin = 1; begin <= end; begin++) {
  9.                 if(array[begin] < array[begin-1]) {
  10.     //当前元素的左边元素比较大时要交换
  11.                     int temp = array[begin];
  12.                     array[begin] = array[begin-1];
  13.                     array[begin-1]=temp;
  14.                 }
  15.             }
  16.         }

优化1-冒泡排序

▪ 提前有序，终止比较（不一定有用：因为一般在随机数据中要提前有序的概率是很低的，）

  • 布尔变量：假设本轮已经有序

    //比较 end 的结束范围，从最后一个元素-第二个元素

    1.     for(int end = array.length - 1; end > 0; end--) {
    3.         boolean sorted = true;//假设提前有序
    4.         //冒泡排序-一轮的交换
    5.         for(int begin = 1; begin <= end; begin++) {
    7.             if(array[begin] < array[begin-1]) {
    8. //当前元素的左边元素比较大时要交换
    9.                 int temp = array[begin];
    10.                 array[begin] = array[begin-1];
    11.                 array[begin-1]=temp;
    12.                 sorted = false;//本轮有交换，证明假设提前有序 不成立
    13.             }
    14.         }
    15.         if(sorted) break;//果然提前有序，不用再比较了
    16.     }

优化2-冒泡排序

  • 如果序列尾部已经局部是有序的，可以记录最后一次交换的位置，从而减少比较的次数。

952257e45a8b8b399c5a9dec9d46bb47.png

  1. int array[] = {
  2.     1, 3, 5, -1, -8};
  3.         //比较 end 的结束范围，从最后一个元素-第二个元素
  4.         for(int end = array.length - 1; end > 0; end--) {
  6.             int sortedIndex = 1;//记录最后一次交换的位置，初始值为1，是为了考虑一开始数组就是完全有序的
  7.             //冒泡排序-一轮的交换
  8.             for(int begin = 1; begin <= end; begin++) {
  10.                 if(array[begin] < array[begin-1]) {
  11.     //当前元素的左边元素比较大时要交换
  12.                     int temp = array[begin];
  13.                     array[begin] = array[begin-1];
  14.                     array[begin-1]=temp;
  15.                     sortedIndex = begin;//记录最后一次交换的位置
  16.                 }
  17.             }
  18.             end = sortedIndex;//更新比较范围到最后一次交换的位置
  19.         }

二、选择排序

为什么要叫选择排序？ 因为每一轮都是把最大的那个数的位置给选择出来

定义：

① 从序列中找出最大的那个元素，然后与最末尾的元素交换位置；执行完一轮后，最末尾的那个元素就是最大的元素。

② 忽略 ① 中曾经找到的最大元素，重复执行步骤 ①

▪ 选择排序本质上看是冒泡的优化：

因为冒泡是从头到尾：相邻两个元素比较完就交换

选择排序是从头到尾：先找到最大元素位置，然后记录位置，最后才交换

  1. int array[] = {
  2.     1, 3, 5, -1, -8};
  3.         //比较 end 的结束范围，从最后一个元素-第二个元素
  4.         for(int end = array.length - 1; end > 0; end--) {
  6.             int maxIndex = 0;
  7.             //选择排序-找出本轮的最大值
  8.             for(int begin = 1; begin <= end; begin++) {
  10.                 if(array[maxIndex] <= array[begin]) {
  11.     //取等号是为了变成稳定的排序算法 10  10()  8 --一轮比较--> 10   8   10()    
  12.                     maxIndex = begin;
  13.                 }
  14.             }
  15.             //交换，把本轮找到的最大一个数放到结尾
  16.             int temp = array[maxIndex];
  17.             array[maxIndex] = array[end];
  18.             array[end] = temp;
  19.         }

三、堆排序

▪ 堆排序本质上看是冒泡的优化：

选择排序是从头到尾：每一轮都在 从头到尾找到最大元素位置（内循环在找最大值）

-—- 找最值，可以交给堆负责（优化）

▪ 堆排序：先原地建堆，然后尾部元素放到堆顶，然后下滤

  1. int array[] = {
  2.     1, 3, 5, -1, -8};
  3. // 原地建堆
  4. heapSize = arrayay.length;
  5. for (int i = (heapSize >> 1) - 1; i >= 0; i--) {
  7.         siftDown(i);
  8. }
  10. while (heapSize > 1) {
  12.     // 交换堆顶元素和尾部元素
  13.     int temp = array[0];
  14.     array[0] = array[heapSize];
  15.     array[heapSize] = temp;
  16.     heapSize--;
  17.     // 对0位置进行siftDown（恢复堆的性质）
  18.     siftDown(0);
  19. }
  22.     /**
  23.      * 下滤
  24.     */
  25.     private void siftDown(int index) {
  27.         int half = heapSize >> 1;
  28.         Integer element = array[index];
  29.         while(index < half) {
  30.      //index 必须是非叶子节点！！！
  31.             // 默认拿是左边跟父节点比大小
  32.             int childIndex = (index << 1) + 1;
  33.             Integer childElement = array[childIndex];
  35.             int rightIndex = childIndex + 1;
  36.             if(rightIndex < size
  37.                     && compare(array[rightIndex], childElement) > 0) {
  39.                 childElement = array[childIndex = rightIndex];
  40.             }
  42.             if(compare(element, childElement) >= 0) break;
  43.             //子结点大的话
  44.             array[index] = childElement;
  45.             index = childIndex;
  46.         }
  47.         array[index] = element;
  48.     }

排序算法-插入排序

一、插入排序

插入排序非常类似于扑克牌的排序

定义：① 在执行过程中，插入排序会将序列分为2部分；头部是已经排好序的，尾部是待排序的

② 从头开始扫描每一个元素；每当扫描到一个元素，就将它插入到头部合适的位置，使得头部数据依然保持有序

bf41bb91cca56f5294af78093e63b840.png

  1. private void sort(Integer[] array) {
  3. ------------------------------------------- 核心代码开始 ------------------------------------------------------------        
  4.         for(int begin = 1; begin < array.length; begin++) {
  5.     //从无序区抓起的牌
  6.             int cur = begin;
  7.             while(cur > 0 && cmp(array[cur], array[cur - 1]) < 0) {
  8.     //这张牌不断往左边走，和紧邻[cur-1]的头部有序区进行比较,小于左边就交换
  9.                 swap(array[cur], array[cur - 1]);
  10.                 cur--;//交换完，这个牌的位置
  11.             }
  12.         }
  13. ------------------------------------------- 核心代码结束 ------------------------------------------------------------        
  14.     }
  18.     protected int cmp(int v1, int v2) {
  20.         return v1 - v2;
  21.     }
  23.     protected void swap(int v1, int v2) {
  25.         int tmp = v1;
  26.         v1 = v2;
  27.         v2 = tmp;
  28.     }

优化1-插入排序

  • 优化：挪动替换交换

4f0cfc0fa6b4bd6387f8ac92799f2a3a.png

  1. private void sort(Integer[] array) {
  3.         for(int begin = 1; begin < array.length; begin++) {
  4.     //从无序区抓起的牌
  5.             int cur = begin;
  6.             Integer v = array[cur];
  7.             while(cur > 0 && cmp(v, array[cur - 1]) < 0) {
  8.     //头部有序数据中比待插入元素大的，都朝尾部方向挪动1个位置
  9.                 array[cur] = array[cur-1];//左边的值比较大就往右边挪动
  10.                 cur--;
  11.             }
  12.             //找到合适的位置，插入
  13.             array[cur] = v;
  14.         }
  15.     }

优化2-插入排序

  • 找位置–使用二分搜索法(通过挪动左右指针，不断缩小一半的可能范围)

  • 使用二分搜索优化了比较次数

    细节：二分搜素的开始-结束区间[begin, end）

    • int begin = 0； int end = array.length;
    • 为什么结束要取 end，因为方便后续其他计算，比如算出该区间有多少元素

  • 优化二分搜素[原：查找位置]为[查找待插入的位置]

    ▪ 原：查找到位置

查找目标位置的：查找过程分成三种判断条件：小于，去左边查找；大于，去右边查找；等于直接返回目标

09ddbbca6c5bc55ada120266e032fd6e.png

▪ 现：查找到待插入位置

查找待插入的目标位置的：查找过程分成两种种判断条件：小于，去左边查找；大等于，去右边查找；因为这个等于不是待插入的目标位置

  • 待插入的目标位置是第一个大于 待插入原始的值v 的元素位置

6969e2f6e6291440fd49f74c96f4d592.png

  1. /**
  2.      * 查找待插入位置的索引
  3.      */
  4.     private int search(int index) {
  5.     //index 是待插入索引
  6.         int begin = 0;
  7.         int end = index;
  8.         while(begin < end) {
  10.             int mid = (begin + end) >> 2;
  11.             if(cmp(array[index], array[mid]) < 0) {
  13.                 end = mid;
  14.             }else {
  16.                 begin = mid + 1;
  17.             }
  18.         }
  19.         return begin;
  20.     }
  23.     private void sort(Integer[] array) {
  25.         for(int begin = 1; begin < array.length; begin++) {
  26.     //从无序区抓起的牌
  27.             Integer v = array[begin];//备份插入元素
  28.             int insertIndex = search(begin);//查找到合适的插入位置
  29.             for(int i = begin; i > insertIndex; i--) {
  30.     //挪动腾出空间
  31.                 array[i] = array[i - 1];
  32.             }
  33.             array[insertIndex] = v;
  34.         }
  35.     }

排序算法-归并排序

一、归并排序

定义：

① 不断地将当前序列平均分割成2个子序列；直到不能再分割（序列中只剩1个元素）

② 不断地将2个子序列合并成一个有序序列；直到最终只剩下1个有序序列

a93a21de0752fd15989d744dd2af2825.png

  1. int[] leftArray;
  2.     int[] array;
  4.     private void sort(int begin, int end) {
  6.         if(end - begin < 2) return;//至少要有2个元素
  7.         int mid = (begin + end) >> 1;
  8.         sort(begin, mid);//左边归并
  9.         sort(mid, end);//右边归并
  10.         merge(begin, mid, end);//最后进行合并
  11.     }
  14.     /**
  15.      * 将 [begin, mid) 和 [mid, end) 范围的序列数组合并成一个有序序列 
  16.      */
  17.     private void merge(int begin, int mid, int end) {
  19.         int li = 0, le = mid - begin;//左边数组leftArray
  20.         int ri = mid, re = end;//右边数组
  21.         int ai = begin;//arrayay 的索引
  22.         for(int i = li; i < le; i++) {
  23.     //拷贝arrayay左边数组到leftArray
  24.             leftArray[i] = array[begin + i];
  25.         }
  27.         while(li < le) {
  28.     //左边还有元素
  29.             if(ri < re && cmp(array[ri], leftArray[li]) < 0) {
  30.     //右边有元素，且右边的值更加小
  31.                 array[ai++] = array[ri++];
  32.             }else {
  34.                 array[ai++] = leftArray[li++];//左边有元素，且左边的值更加小
  35.             }
  36.         }

排序算法-快速排序、希尔排序

一、快速排序

快速排序的本质：逐渐将每一个元素都转换成轴点元素

定义：

① 从序列中选择一个轴点元素（pivot）

▪ 假设每次选择 0 位置的元素为轴点元素

② 利用 pivot 将序列分割成 2 个子序列

▪ 将小于 pivot 的元素放在pivot前面（左侧）

▪ 将大于 pivot 的元素放在pivot后面（右侧）

▪ 等于pivot的元素放哪边都可以

③ 对子序列进行 ① ② 操作

▪ 直到不能再分割（子序列中只剩下1个元素）

是一个递归排序：从轴点切分成两部分，不断地对左部分进行快速排序，不断地对右部分进行快速排序

b8ff2341ef753861cd1a377ac74d760e.png

判断该元素是 “甩”到左边 还是 右边，不加等号，因为加上等号会使得轴点元素分割出来的子序列极度不均匀
  • 比如 6 6 6 6 6，轴点是6，那么取等号，全部给甩到一边了
  1. int[] array;
  3.     private void sort(int begin, int end) {
  5.         if(end - begin < 2) return;//至少要有两个元素
  6.         int mid = pivotIndex(begin, end);//轴点，以轴点分割成了左右两部分
  7.         sort(begin, mid);//对左部分进行快速排序
  8.         sort(mid + 1, end);//对右部分进行快速排序
  9.     }
  14.     /**
  15.      * 对 [begin, end) 范围内的元素进行快速排序
  16.      */
  17.     private int pivotIndex(int begin, int end) {
  19.         swap(begin, begin + (int)(Math.random() * (end - begin)));//随机交换begin位置的元素
  21.         Integer pivot = array[begin];//备份轴点元素
  22.         end--;//让右边指针直到元素上
  24. ------------------------------------------- 核心代码开始 ------------------------------------------------------------            
  25.         while(begin < end) {
  27.             //内部使用了两个while 搭配 break，实现在右边找“小”、在左边找“大”后，对数组指针指向"调头"
  28.             while(begin < end) {
  29.                   //不加等号，因为加上等号会使得轴点元素分割出来的子序列极度不均匀
  30.                 if(cmp(pivot, array[end]) < 0) {
  31.     // 右边元素>轴点元素,不是目标，要在右边找“小”
  32.                     end--;
  33.                 }else {
  35.                     array[begin++] = array[end];
  36.                     break;
  37.                 }
  38.             }
  40.             while(begin < end) {
  42.                 if(cmp(pivot, array[begin]) > 0) {
  43.     // 左边元素<轴点元素,不是目标，要在左边找“大”
  44.                     begin++;
  45.                 }else {
  47.                     array[end--] = array[begin];
  48.                     break;
  49.                 }
  50.             }
  51.         }
  52. ------------------------------------------- 核心代码结束 ------------------------------------------------------------        
  53.         array[begin] = pivot;//数组轴点元素进行赋值
  54.         return begin;
  55.     }
  58.     protected int cmp(int v1, int v2) {
  60.         return v1 - v2;
  61.     }
  63.     protected void swap(int v1, int v2) {
  65.         int tmp = v1;
  66.         v1 = v2;
  67.         v2 = tmp;
  68.     }

二、希尔排序

切分成n 列然后进行排序–> 逆序对数量逐渐减少 —> 希尔排序，底层是使用插入排序，也可以把希尔看成是对插入排序的改进版

cc9a906f30dec2476b31d4d182f233f8.png

  1. int[] array;
  3.     private void sort() {
  5.         List<Integer> stepSequence = shellStepSequence();
  6.         for(Integer step: stepSequence) {
  7.     //按照每个步长进行切割，然后进行一一对应的比较 排序
  8.             sort(step);
  9.         }
  10.     }
  12.     /**
  13.      * 按照给定的步长进行切割，然后对 step 列进行排序
  14.      */
  15.     private void sort(Integer step) {
  17.  ------------------------------------------- 核心代码开始 ------------------------------------------------------------         
  18.         // col: 第几列
  19.         for(int col = 0; col < step; col++) {
  20.     //对col列进行排序
  21.             // 第col 列中的元素: col、col+2*step、col+3*step、col+4*step
  22.             // 结合了步长的插入排序
  23.             for(int begin = col + step; begin < array.length; begin++) {
  25.                 int cur = begin;
  26.                 while(cur > col && cmp(array[cur], array[cur - step]) < 0) {
  28.                     swap(array[cur], array[cur - step]);
  29.                     cur -= step;
  30.                 }
  31.             }
  32.         }
  33. ------------------------------------------- 核心代码结束 ------------------------------------------------------------               
  34.     }
  36.     /**
  37.      * 步长序列：获取 step 步长分割数组
  38.      */
  39.     private List<Integer> shellStepSequence(){
  41.         List<Integer> stepSequence = new ArrayList<>();
  42.         int step = array.length;
  43.         while((step >>= 1) > 0) {
  45.             stepSequence.add(step);
  46.         }
  47.         return stepSequence;
  48.     }
  52.     protected int cmp(int v1, int v2) {
  54.         return v1 - v2;
  55.     }
  57.     protected void swap(int v1, int v2) {
  59.         int tmp = v1;
  60.         v1 = v2;
  61.         v2 = tmp;
  62.     }
▪ 冒泡、选择、插入、归并、快速、希尔、堆排序，都是基于比较的排序 [面试会考]
  • 平均时间复杂度目前最低是 O(nlogn)
▪ 计数排序、桶排序、基数排序，都不是基于比较的排序 [面试不考，作为了解]
  • 它们是典型的用空间换时间，在某些时候，平均时间复杂度可以比 O(nlogn) 更低

排序算法-计数排序、基数排序、桶排序

一、计数排序

72aa0d9be2ebfb8be1aa49e49dda5443.png

细节：在java 整型数组，new出数组之后，内部元素默认都是 0

int counts = new int[10]; //new 完，默认所有元素都是0

  1. int[] array;
  3.     private void sort() {
  5.         //找出最大值
  6.         int max = array[0];
  7.         for(int i = 1; i < array.length; i++) {
  9.             if(array[i] > max) {
  11.                 max = array[i];
  12.             }
  13.         }
  14.  ------------------------------------------- 核心代码开始 ------------------------------------------------------------         
  15.         // 开辟内存空间，存储每一个整数出现的次数
  16.         int[] counts = new int[1 + max];//整型数组，new出数组之后，内部元素默认都是 0 
  18.         //统计每个整数出现的次数
  19.         for(int i = 0; i < array.length; i++) {
  21.             counts[array[i]]++;
  22.         }
  24.         //根据整数出现次数，对整数进行排序
  25.         int index = 0;//整数数组上的指针
  26.         for(int i = 0; i < counts.length; i++) {
  28.             while(counts[i]-- > 0) {
  30.                 array[index++] = i;
  31.             }
  32.         }
  33. ------------------------------------------- 核心代码结束 ------------------------------------------------------------             
  34.     }

■ 计数排序缺点：

  • 无法对负整数进行排序
  • 极其浪费内存空间
  • 是个不稳定的排序

■ 计数排序的优化

3ac967ce22501fd03bfb5d05da969d29.png

  1. int[] array;
  3.     private void sort() {
  5.         // 找出最大值、最小值
  6.         int max = array[0];//最大值
  7.         int min = array[0];//最小值
  8.         for(int i = 1; i < array.length; i++) {
  10.             if(array[i] > max) {
  12.                 max = array[i];
  13.             }
  14.             if(array[i] < min) {
  16.                 min = array[i];
  17.             }
  18.         }
  19.  ------------------------------------------- 核心代码开始 ------------------------------------------------------------        
  20.         //开辟内存空间，存储次数
  21.         int[] counts = new int[max - min + 1];
  23.         //统计每个整数出现的次数
  24.         for(int i = 0; i < array.length; i++) {
  26.             counts[array[i] - min]++;
  27.         }
  28.         //累加次数
  29.         for(int i = 1; i < counts.length; i++) {
  31.             counts[i] += counts[i - 1];
  32.         }
  34.         //从后往前遍历元素，将它放到有序数组中的合适位置
  35.         int[] newArray = new int[array.length];
  36.         for(int i = array.length - 1; i >= 0; i--) {
  38.             newArray[--counts[array[i] - min]] = array[i];// 公式 count[k - min] -p 其中p是该元素k倒数着出现的次数
  39.         }
  40. ------------------------------------------- 核心代码结束 ------------------------------------------------------------              
  41.         //将有序数组赋值到array
  42.         for(int i = 0; i < newArray.length; i++) {
  44.             array[i] = newArray[i];
  45.         }
  46.     }

二、基数排序

定义：依次对个位数、十位数、百位数、千位数、万位数…进行排序（从低位到高位）

ed119e064f980579c6e8dccc1a296e3f.png

  1. int[] array;
  3.     private void sort() {
  5.         // 找出最大值
  6.         int max = array[0];
  7.         for (int i = 1; i < array.length; i++) {
  9.             if (array[i] > max) {
  11.                 max = array[i];
  12.             }
  13.         }
  14.         // max = 593
  15.         // 个位数 array[i] / 1 % 10 = 3
  16.         // 十位数 array[i] / 10 % 10 = 9
  17.         // 百位数 array[i] / 100 % 10 = 5
  18.         for (int divider = 1; divider <= array.length; divider *= 10) {
  20.             countingSort(divider);
  21.         }
  23.     }
  25.     private void countingSort(int divider) {
  27.         // 开辟内存空间，存储次数
  28.         int[] counts = new int[10];//给个位数、十位数、百位数排序，它们的范围都是 0-9
  30.         // 统计每个整数出现的次数
  31.         for (int i = 0; i < array.length; i++) {
  33. //            counts[array[i]的基数]++;
  34.             counts[array[i] / divider % 10]++;
  35.         }
  36.         // 累加次数
  37.         for (int i = 1; i < counts.length; i++) {
  39.             counts[i] += counts[i - 1];
  40.         }
  42.         // 从后往前遍历元素，将它放到有序数组中的合适位置
  43.         int[] newArray = new int[array.length];
  44.         for (int i = array.length - 1; i >= 0; i--) {
  46. //            newArray[--counts[array[i]的基数] = array[i];
  47.             newArray[--counts[array[i] / divider % 10]] = array[i];
  48.         }
  50.         // 将有序数组赋值到array
  51.         for (int i = 0; i < newArray.length; i++) {
  53.             array[i] = newArray[i];
  54.         }
  55.     }

■ 基数排序的另外一种思路：元素先存到桶里，然后再回收

acfeff93027ab627d31040995904624a.png

三、桶排序

如果本文对你有帮助的话记得给一乐点个赞哦，感谢！

发表评论

表情：
评论列表 （有 0 条评论，161人围观）

还没有评论，来说两句吧...

相关阅读