dw网站建设视频下载,wordpress主题教程,企业网站官网,有多少收费网站下面我们将讲述七大基于比较的排序算法的基本原理及实现。并从稳定性、时间复杂度、空间复杂度3种性能对每种排序进行分析。 重点#xff1a;快速排序和堆排序#xff1b;难点#xff1a;快速排序和归并排序
目录
一、排序概念
二、常见排序算法的实现
2.1 插入排序
2.… 下面我们将讲述七大基于比较的排序算法的基本原理及实现。并从稳定性、时间复杂度、空间复杂度3种性能对每种排序进行分析。 重点快速排序和堆排序难点快速排序和归并排序
目录
一、排序概念
二、常见排序算法的实现
2.1 插入排序
2.1.1 直接插入排序
2.1.2 希尔排序缩小增量排序
2.2 选择排序
2.2.1 直接选择排序
2.2.2 直接选择排序优化
2.2.3 堆排序
2.3 交换排序
2.3.1 冒泡排序
2.3.2 快速排序
1、Hoare 法
2、挖坑法
3、前后指针
2.3.3 快速排序优化
1、三数取中法
2、减少递归深度
2.3.4 快速排序非递归
2.4 归并排序
2.4.1
2.4.2 归并排序非递归实现
三、特性总结
四、其他非基于比较排序
4.1 计数排序 一、排序概念 稳定性假定在待排序的记录序列中存在多个具有相同的关键字的记录若经过排序这些记录的相对次序保持 不变即在原序列中r[i]r[j]且 r[i] 在 r[j] 之前而在排序后的序列中r[i] 仍在r[j] 之前则称这种排序算法是稳 定的否则称为不稳定的。 内部排序数据元素全部放在内存中的排序。
外部排序数据元素太多不能同时放在内存中根据排序过程的要求在内外村之间移动数据的排序例如磁盘上的排序。
二、常见排序算法的实现
2.1 插入排序
2.1.1 直接插入排序 基本思想把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中直到所有的记录插入完为止得到一个新的有序序列。例如玩扑克牌前对手里的牌进行整理。
比如现在你手上有一副卡牌不看花色10、2、9、4、7从左往右的第2张发现比第一张小因此将其抽出插到第一张的前面。 public class Sort {public static void insertSort(int[] array){for (int i 1; i array.length; i) {int tmp array[i];int j i-1;for (; j 0; j--) {if (array[j] tmp) { // 若此处加了 则得到的数据不稳定但实际上直接插入排序法是稳定的array[j 1] array[j];}else{array[j 1] array[j];break;}}array[j1] tmp;}}
}
直接插入排序的特性 1. 元素集合越接近有序直接插入排序算法的时间效率越高时间复杂度为O(N) 2. 时间复杂度最坏情况下是 O(N²) 3. 空间复杂度O(1)没有开辟空间 4. 稳定性稳定。 2.1.2 希尔排序缩小增量排序 基本思想先选定一个整数作为增量把待排序文件中的所有数据按照这个整数为距离分成多个组即所有距离为增量的数据分在同一组内将每一组的数据进行排序。然后取另一个小于原来增量的整数可以是原来的 1/2 或者 1/31重复上述的分组和排序规则当增量 1时所有数据在同一组内排好序。是直接插入排序的优化所以直接插入排序的代码可以直接拿来修改。如下图 public static void shellSort(int[] array){int gap array.length;while (gap 1){gap / 2; // 最后都能等于1shell(array, gap);}}private static void shell(int[] array, int gap) {for (int i gap; i array.length; i) {int tmp array[i];int j i-gap;for (; j 0 ; j - gap) {if (array[j] tmp){array[jgap] array[j];}else{array[jgap] tmp;break;}}array[jgap] tmp;}}
希尔排序的特性 1. 希尔排序是对直接插入排序的优化。 2. 当 gap 1 时都是预排序目的是让数组更接近于有序。当 gap 1 时数组已经接近有序的了这样就会很快。这样整体而言可以达到优化的效果。我们实现后可以进行性能测试的对比。 3. 希尔排序的时间复杂度不好计算因为gap的取值方法很多导致很难去计算因此在好些书中给出的希尔排 、序的时间复杂度都不固定归纳总结其时间复杂度的范围在O(n^1.3 ~ n^1.5)之间 4、空间复杂度O(1) 5、稳定性不稳定。 性能测试main() 方法中只有 testEfficiency() 测试数组是有序的或者无序时各种排序方法的效率而 testSimple() 则是查看是否排序成功。
package sort;import java.util.Arrays;
import java.util.Random;public class Test {public static void orderArray(int[] array){ // 初始化有序的数组for (int i 0; i array.length; i) {// 顺序array[i] i;// 倒序//array[i] array.length-1-i;}}public static void notOrderArray(int[] array){ // 初始化无序的数组Random random new Random();for (int i 0; i array.length; i) {array[i] random.nextInt(10_0000); // 生成0到10万的随机数}}public static void testInsertEfficiency(int[] array){array Arrays.copyOf(array, array.length); // 不改变原来数组的顺序而是将排序后的新的数组复制一份long startTime System.currentTimeMillis();Sort.insertSort(array);long finishTime System.currentTimeMillis();System.out.println(直接插入排序耗时(finishTime-startTime));}public static void testShellEfficiency(int[] array){array Arrays.copyOf(array, array.length); // 不改变原来数组的顺序而是将排序后的新的数组复制一份long startTime System.currentTimeMillis();Sort.shellSort(array);long finishTime System.currentTimeMillis();System.out.println(希尔排序耗时(finishTime-startTime));}public static void main(String[] args) {//testSimple(); // 测试例子给的数组testEfficiency(); // 测试耗时效率}public static void testSimple(){int[] array {9,3,4,7,1,5,8,6,5,2};System.out.println(排序前Arrays.toString(array));Sort.shellSort(array);System.out.println(排序后Arrays.toString(array));}public static void testEfficiency(){int[] array new int[10_0000]; // 数组元素个数为10万orderArray(array);//notOrderArray(array);testInsertEfficiency(array);testShellEfficiency(array);}
} 对于有序的数组直接插入排序耗时要比希尔排序短一点但差不了多少而如果是对无序的数组进行排序希尔排序耗时要远比直接插入排序耗时短几乎达到1100。
2.2 选择排序 基本思想每一次从待排序的数据元素中选出最小或最大的一个元素存放在序列的起始位置直到全部待排序的数据元素排完 。
2.2.1 直接选择排序
假设0下标的元素为最小值在后面的元素中找到实际最小值然后交换…… public static void DirectSelectSort(int[] array){for (int i 0; i array.length; i) {int minIndex i;for (int j i1; j array.length; j) {if (array[j] array[minIndex]){minIndex j;}}swap(array, i, minIndex);}}private static void swap(int[] array, int i, int j) {int tmp array[i];array[i] array[j];array[j] tmp;}
直接选择排序的特性 1. 直接选择排序思考非常好理解但是效率不是很好。实际中很少使用因此重要的是算法思想 2. 时间复杂度O(n²)和数组是否有序无关 3. 空间复杂度O(1) 4. 稳定性不稳定 2.2.2 直接选择排序优化
从左端点开始向右找到最小值将下标存到 minIndex 中找到最大值并将下标存到 maxIndex 中。 上图的步骤看似没毛病编写代码如下 public static void selectSort(int[] array){int left 0;int right array.length-1;while (left right) {int minIndex left;int maxIndex left;for (int i left1; i right; i) {if (array[i] array[maxIndex]){maxIndex i;}if (array[i] array[minIndex]){minIndex i;}}swap(array,left,minIndex);swap(array,right,maxIndex);left;right--;}}
但是如果我们换一组数据进行测试得到的结果如下 所以在更换完最小值之后需要增加一项条件。 public static void selectSort(int[] array){int left 0;int right array.length-1;while (left right) {int minIndex left;int maxIndex left;for (int i left1; i right; i) {if (array[i] array[maxIndex]){maxIndex i;}if (array[i] array[minIndex]){minIndex i;}}swap(array,left,minIndex);// 如果最大值正好是 left 下标那么交换 left 之后最大值给到 minIndex 下标if (maxIndex left){maxIndex minIndex;}swap(array,right,maxIndex);left;right--;}} 对于无序的数组选择排序的耗时如下 2.2.3 堆排序
利用堆这种数据结构来实现排序需要注意的是升序建大根堆降序则是建小根堆。
我的Java集合中的优先级队列堆中有提及。 public static void heapSort(int[] array){createHeap(array); // 1、建大根堆int end array.length-1;while (end 0){swap(array,0,end); // 2、交换根节点和最后一个节点的值// 3、将除了最后一个元素已是最大值的其他节点重新整理成大根堆siftDown(array,0,end);end--; // 4、倒着重复上面的操作}}public static void createHeap(int[] array){int parent (array.length-1-1)/2;for (; parent 0; parent--) {siftDown(array,parent,array.length);}}private static void siftDown(int[] array, int parent, int size) {int child 2*parent1;while (child size){if(child1 size array[child1] array[child]){child;}if (array[child] array[parent]){swap(array,child,parent);parent child;child 2*parent1;}else{break;}}}
堆排序的特性 1. 堆排序使用堆来选数效率就高了很多 2. 时间复杂度O(N*log₂N) 目前效率最快的排序方法 3. 空间复杂度O(1) 4. 稳定性不稳定 2.3 交换排序 基本思想所谓交换就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置交换排序的特点是将键值较大的记录向序列的尾部移动键值较小的记录向序列的前部移动。
2.3.1 冒泡排序
关键词趟数、循环嵌套、j1不要越界 public static void bubbleSort(int[] array){for (int i 0; i array.length-1; i) {boolean tag false;for (int j 0; j array.length-1-i; j) {if (array[j] array[j1]){swap(array,j, j1);tag true;}}if (!tag){break;}}} 1、时间复杂度 O(N²) 【一般讨论没有优化情况下的时间复杂度即没有boolean元素和 -i 的操作】 【优化之后时间复杂度可以达到 O(N)】 2、空间复杂度 O(1) 3、稳定性稳定 2.3.2 快速排序 快速排序是Hoare于1962年提出的一种二叉树结构的基于分治法的交换排序方法其基本思想为 任取待排序元素序列中的某元素作为基准值按照该排序码将待排序集合分割成两子序列左子序列中所有元素均小于基准值右子序列中所有元素均大于基准值然后最左右子序列重复该过程直到所有元素都排列在相应位置上为止。 public static void quickSort(int[] array){quick(array,0,array.length-1);}public static void quick(int[] array, int start, int end){if (start end){ // 递归结束条件return;}//按照基准值对数组进行分割//int pivot partitionHoare(array,start,end); // Hoare//int pivot partitionDig(array,start,end); // 挖坑//int pivot partitionDoublePointer(array,start,end); // 双指针解法1int pivot partitionDoublePointer2(array,start,end); // 双指针解法2// 递归左边的quick(array, start, pivot-1);// 递归右边的quick(array,pivot1,end);} 上述为快速排序递归实现的主框架与二叉树前序遍历规则非常像下面的3种分割方法都是在分割之后应用上面的递归方法进行排序的如下图右侧内容因此下面只讨论不同分割方法的主要思想。
1、Hoare 法 public static void quickSort(int[] array){quick(array,0,array.length-1);}public static void quick(int[] array, int start, int end){if (start end){ // 递归结束条件return;}int pivot partitionHoare(array,start,end);quick(array, start, pivot-1);quick(array,pivot1,end);}private static int partitionHoare(int[] array, int left, int right){int tmp array[left];int tmpIndex left;while(left right){while (left right array[right] tmp){right--;}while (left right array[left] tmp){left;}swap(array, left, right);}swap(array,left,tmpIndex);return left;}
问题画图理解 / 调试解决 1、为什么从后面开始找而不是从前面开始找 2、为什么在 while 条件中有 等于号 快排序的特性 1、时间复杂度 最坏情况下当给定数据是1 2 3 4 5 6…… / ……9 8 7 6 5 4 3 2 1这种有序的情况下是O(N² 最好情况下是 O(N*log₂N)对于满二叉树来说对上面的代码进行优化后可实现。 2、空间复杂度递归一定会开辟内存 最坏情况下 O(N)单分支二叉树 最好情况下 O(log₂N)对于满二叉树递归完左边再递归右边时左边开辟的内存会被回收。 3、稳定性不稳定 2、挖坑法
如果在题目中遇到快速排序的结果但没有明确指出是哪种快排时优先考虑挖坑法。 public static void quickSort(int[] array){quick(array,0,array.length-1);}public static void quick(int[] array, int start, int end){if (start end){ // 递归结束条件return;}int pivot partitionDig(array,start,end);quick(array, start, pivot-1);quick(array,pivot1,end);}private static int partitionDig(int[] array, int left, int right){int key array[left];while(left right){while (left right array[right] key){right--;}array[left] array[right];while (left right array[left] key){left;}array[right] array[left];}array[left] key;return left;}
3、前后指针
两种分割的方法 【对于有序的数组】当我们在测试快排序的效率时程序崩溃了这是因为递归需要开辟内存空间对于十万如此大量的且有序的数据就得开辟十万个空间。而将数据量减小比如1万并不会崩但是效率还是比较低。
2.3.3 快速排序优化
1、三数取中法
在前面测试有序数组时程序崩溃了这是因为递归有n个节点的单分支的二叉树需要开辟n个内存那么如果我们找到有序数组的中间值并将其作为分割的基准值就能将有序数组分为两部分。 public static void quick(int[] array, int start, int end){if (start end){ // 递归结束条件return;}// 三数取中法优化有序的数组不再是单分支的二叉树了//System.out.println(start: start end: end); // 打印也会耗时int midIndex getMiddleIndex(array, start, end);swap(array,start,midIndex);//int pivot partitionHoare(array,start,end); // Hoareint pivot partitionDig(array,start,end); // 挖坑//int pivot partitionDoublePointer(array,start,end); // 双指针解法1//int pivot partitionDoublePointer2(array,start,end); // 双指针解法2quick(array, start, pivot-1);quick(array,pivot1,end);}private static int getMiddleIndex(int[] array, int start, int end) {int mid (startend)/2;if (array[start] array[end]) {if (array[mid] array[start]) {return start;} else if (array[mid] array[end]) {return end;} else {return mid;}} else {if (array[mid] array[start]) {return start;} else if (array[mid] array[end]) {return end;} else {return mid;}}}
2、减少递归深度 因为在多次的预排序后数组已经趋于有序了所以当递归到小的子区间时可以考虑使用插入排序。
比如当数据量剩下的范围是0到7之间时直接使用插入排序注意修改原来编写的插入排序的开始和结束范围以及使用插入排序之后及时结束进程 public static void quick(int[] array, int start, int end){if (start end){ // 递归结束条件return;}// 减少递归深度优化if (end - start 7){insertSortRage(array, start, end);return; // 记得此处要结束循环了}// 三数取中法优化有序的数组不再是单分支的二叉树了//System.out.println(start: start end: end); // 打印也会耗时int midIndex getMiddleIndex(array, start, end);swap(array,start,midIndex);//int pivot partitionHoare(array,start,end); // Hoareint pivot partitionDig(array,start,end); // 挖坑//int pivot partitionDoublePointer(array,start,end); // 双指针解法1//int pivot partitionDoublePointer2(array,start,end); // 双指针解法2quick(array, start, pivot-1);quick(array,pivot1,end);}private static void insertSortRage(int[] array, int start, int end) {for (int i start1; i end; i) {int tmp array[i];int j i-1;for (; j start; j--){if (array[j] tmp){array[j1] array[j];}else{array[j1] tmp;break;}}array[j1] tmp;}}
2.3.4 快速排序非递归 基本思想使用一个栈来存放分割后要使用二叉树数据结构进行排序的开始下标和结束下标。再拿出下标进行分割就是不断地分割、存放下标、拿出下标、分割……的过程。 public static void quickSort(int[] array){// 非递归的方法quickNor(array,0,array.length-1);}private static void quickNor(int[] array, int start, int end) {DequeInteger stack new ArrayDeque();int pivot partitionDig(array,start,end);// 第一次分割后存放下标if (pivot start1){stack.push(start);stack.push(pivot-1);}if (pivot end-1){stack.push(pivot1);stack.push(end);}// 拿出下标再进行分割while (!stack.isEmpty()){end stack.pop();start stack.pop();pivot partitionDig(array,start,end);if (pivot start1){stack.push(start);stack.push(pivot-1);}if (pivot end-1){stack.push(pivot1);stack.push(end);}}}
快速排序的特性 1、 快速排序整体的综合性能和使用场景都是比较好的所以才敢叫快速排序 2、时间复杂度O(N*logN) 3、空间复杂度O(logN)即树的高度 4. 稳定性不稳定。 2.4 归并排序
2.4.1 基本思想归并排序MERGE-SORT是建立在归并操作上的一种有效的排序算法,该算法是采用分治法Divide and Conquer的一个非常典型的应用。将已有序的子序列合并得到完全有序的序列即先使每个子序列有序再使子序列段间有序。若将两个有序表合并成一个有序表称为二路归并。 归并排序核心步骤 public static void mergeSort(int[] array){mergeSortTmp(array, 0, array.length-1);}public static void mergeSortTmp(int[] array, int left, int right){if (left right){return;}int mid (left right)/2;mergeSortTmp(array, left, mid);mergeSortTmp(array, mid1, right);// 到这里分解结束// 下面进行合并merge(array,left,mid,right);}private static void merge(int[] array, int left, int mid, int right) {int[] tmp new int[right-left1];int k 0;int s1 left;//int e1 mid;int s2 mid1;//int e2 right;while (s1 mid s2 right){if (array[s1] array[s2]){tmp[k] array[s1];}else{tmp[k] array[s2];}}while (s1 mid){ // 要用 while 的原因是有可能有多组tmp[k] array[s1];}while (s2 right){tmp[k] array[s2];}for (int i 0; i k; i) {array[ileft] tmp[i]; // left处理巧妙解决右边下标对应问题}}
归并排序特性 1、归并的缺点在于需要O(N)的空间复杂度归并排序的思考更多的是解决在磁盘中的外部排序问题 2、时间复杂度O(N*log₂N) 3、空间复杂度O(N) 4、稳定性稳定 海量数据的排序问题 外部排序排序过程需要在磁盘等外部存储进行的排序 前提内存只有 1G需要排序的数据有 100G 因为内存中因为无法把所有数据全部放下所以需要外部排序而归并排序是最常用的外部排序 1. 先把文件切分成 200 份每个 512 M 2. 分别对 512 M 排序因为内存已经可以放的下所以任意排序方式都可以 3. 进行 2路归并同时对 200 份有序文件做归并过程最终结果就有序了 2.4.2 归并排序非递归实现 基本思想将数组多次分解之后合并为一整个数组进行排序。 private static void merge(int[] array, int left, int mid, int right) { // 合并int[] tmp new int[right-left1];int k 0;int s1 left;//int e1 mid;int s2 mid1;//int e2 right;while (s1 mid s2 right){if (array[s1] array[s2]){tmp[k] array[s1];}else{tmp[k] array[s2];}}while (s1 mid){ // 要用 while 的原因是有可能有多组tmp[k] array[s1];}while (s2 right){tmp[k] array[s2];}for (int i 0; i k; i) {array[ileft] tmp[i];}}// 归并排序非递归public static void mergeSortNor(int[] array){int gap 1;while (gap array.length) {for (int i 0; i array.length; i i gap * 2) {int left i;int mid left gap - 1;int right mid gap;merge(array, left, mid, right); // 合并}gap * 2;}} 上面的 mergeSortNor() 代码看似没有问题但是如果是如下情况该如何完善 public static void mergeSortNor(int[] array){int gap 1;while (gap array.length) {for (int i 0; i array.length; i i gap * 2) {int left i;int mid left gap - 1;if (mid array.length){ // 处理越界情况mid array.length -1;}int right mid gap;if (right array.length){right array.length -1;}merge(array, left, mid, right); // 合并}gap * 2;}}
三、特性总结
堆排序、快速排序、归并排序时间复杂度都是 O(N*log₂N)但相比空间复杂度堆排序占优势
插入排序、冒泡排序和归并排序都是稳定的
排序方法最好平均最坏空间复杂度稳定性冒泡排序O(n²)优化之后能达到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^1.3)O(n^1.5)O(1)不稳定堆排序O(n * log₂n)O(n * log₂n)O(n * log₂n)O(1)不稳定快速排序O(n * log₂n)O(n * log₂n)O(n²)O(log₂n)~O(n)不稳定归并排序O(n * log₂n)O(n * log₂n)O(n * log₂n)O(n)稳定
一些操作关键词 四、其他非基于比较排序
4.1 计数排序
应用场景 集中在某个范围内的一组数据。
操作步骤 1、新建一个计数数组来利用下标统计相同元素出现的次数 2、根据统计的结果将序列回收到原来的序列中。 public static void countSort(int[] array){// 1、找出数组中的最大值和最小值得到申请空间的大小int max array[0];int min array[0];for (int i 1; i array.length; i) {if (array[i] max){max array[i];}if (array[i] min){min array[i];}}int len max - min 1;int[] count new int[len];// 2、遍历数组计算出现的次数for (int i 0; i array.length; i) {int index array[i];count[index-min];}// 3、将计数数组中的数据按顺序拿出放到 arrayint index 0;for (int i 0; i count.length; i) {while (count[i] ! 0) {array[index] i min;index;count[i]--;}}}
计数排序的特性 1、计数排序在数据范围集中时效率很高但是适用范围及场景有限。 2、时间复杂度O(MAX(N,范围)) 3、空间复杂度O(范围) 4、稳定性稳定 其他桶排序、基数排序。
