沧州专业网站建设公司,创意视频制作app,抖音小程序推荐,网站核验点查询一、 前言
最常考的是快速排序和归并排序#xff0c;并且经常有面试官要求现场写出这两种排序的代码。对这两种排序的代码一定要信手拈来才行。还有插入排序、冒泡排序、堆排序、基数排序、桶排序等。面试官对于这些排序可能会要求比较各自的优劣、各种算法的思想及其使用场景…一、 前言
最常考的是快速排序和归并排序并且经常有面试官要求现场写出这两种排序的代码。对这两种排序的代码一定要信手拈来才行。还有插入排序、冒泡排序、堆排序、基数排序、桶排序等。面试官对于这些排序可能会要求比较各自的优劣、各种算法的思想及其使用场景。还有要会分析算法的时间和空间复杂度。
二、排序算法
2.1 冒泡算法
大体思想就是通过与相邻元素的比较和交换来把小的数交换到最前面。类似于水泡向上升一样因此而得名。举个栗子对5,3,8,6,4这个无序序列进行冒泡排序。首先从后向前冒泡4和6比较把4交换到前面序列变成5,3,8,4,6。同理4和8交换变成5,3,4,8,6,3和4无需交换。5和3交换变成3,5,4,8,6,3.这样一次冒泡就完了把最小的数3排到最前面了。对剩下的序列依次冒泡就会得到一个有序序列。冒泡排序的时间复杂度为O(n^2)。
import java.util.Arrays;public class Test {public static void BubbleSort(int[] arr) {if (arr null || arr.length 0) {return;}for (int i 0; i arr.length - 1; i) {for (int j arr.length - 1; j i; j--) {if (arr[j] arr[j - 1]) {swap(arr, j - 1, j);}}}}private static void swap(int[] arr, int i, int j) {int temp arr[i];arr[i] arr[j];arr[j] temp;}public static void main(String[] args) {int[] array {0, 31, 12, 2, 8};// 执行冒泡排序BubbleSort(array);Arrays.stream(array).forEach(System.out::println);}}2.2 选择排序
选择排序的思想其实和冒泡排序有点类似都是在一次排序后把最小的元素放到最前面。但是过程不同冒泡排序是通过相邻的比较和交换。而选择排序是通过对整体的选择。举个栗子对5,3,8,6,4这个无序序列进行简单选择排序首先要选择5以外的最小数来和5交换也就是选择3和5交换一次排序后就变成了3,5,8,6,4.对剩下的序列一次进行选择和交换最终就会得到一个有序序列。其实选择排序可以看成冒泡排序的优化因为其目的相同只是选择排序只有在确定了最小数的前提下才进行交换大大减少了交换的次数。选择排序的时间复杂度为O(n^2)
import java.util.Arrays;public class Test {public static void SelectSort(int[] arr) {if (arr null || arr.length 0) {return;}int minIndex 0;for (int i 0; i arr.length - 1; i) {minIndex i;for (int j i 1; j arr.length; j) {if (arr[j] arr[minIndex]) {minIndex j;}}if (minIndex ! i) {swap(arr, i, minIndex);}}}private static void swap(int[] arr, int i, int j) {int temp arr[i];arr[i] arr[j];arr[j] temp;}public static void main(String[] args) {int[] array {0, 31, 12, 2, 8};SelectSort(array);Arrays.stream(array).forEach(System.out::println);}}2.3 插入算法
插入排序不是通过交换位置而是通过比较找到合适的位置插入元素来达到排序的目的的。相信大家都有过打扑克牌的经历特别是牌数较大的。在分牌时可能要整理自己的牌牌多的时候怎么整理呢就是拿到一张牌找到一个合适的位置插入。这个原理其实和插入排序是一样的。举个栗子对5,3,8,6,4这个无序序列进行简单插入排序首先假设第一个数的位置时正确的想一下在拿到第一张牌的时候没必要整理。然后3要插到5前面把5后移一位变成3,5,8,6,4.想一下整理牌的时候应该也是这样吧。然后8不用动6插在8前面8后移一位4插在5前面从5开始都向后移一位。注意在插入一个数的时候要保证这个数前面的数已经有序。简单插入排序的时间复杂度也是O(n^2)。
import java.util.Arrays;public class Test {public static void InsertSort(int[] arr) {if (arr null || arr.length 0) {return;}for (int i 1; i arr.length; i) {int j i;int target arr[i];while (j 0 target arr[j-1]) {arr[j]arr[j-1];j --;}arr[j] target;}}public static void main(String[] args) {int[] array {0, 31, 12, 2, 8};InsertSort(array);Arrays.stream(array).forEach(System.out::println);}}2.4 快速算法
实际应用当中快速排序确实也是表现最好的排序算法。冒泡排序虽然高端但其实其思想是来自冒泡排序冒泡排序是通过相邻元素的比较和交换把最小的冒泡到最顶端而快速排序是比较和交换小数和大数这样一来不仅把小数冒泡到上面同时也把大数沉到下面。
举个栗子对5,3,8,6,4这个无序序列进行快速排序思路是右指针找比基准数小的左指针找比基准数大的交换之。
5,3,8,6,4 用5作为比较的基准最终会把5小的移动到5的左边比5大的移动到5的右边。
5,3,8,6,4 首先设置i,j两个指针分别指向两端j指针先扫描思考一下为什么4比5小停止。然后i扫描8比5大停止。交换i,j位置。
5,3,4,6,8 然后j指针再扫描这时j扫描4时两指针相遇。停止。然后交换4和基准数。
4,3,5,6,8 一次划分后达到了左边比5小右边比5大的目的。之后对左右子序列递归排序最终得到有序序列。
上面留下来了一个问题为什么一定要j指针先动呢首先这也不是绝对的这取决于基准数的位置因为在最后两个指针相遇的时候要交换基准数到相遇的位置。一般选取第一个数作为基准数那么就是在左边所以最后相遇的数要和基准数交换那么相遇的数一定要比基准数小。所以j指针先移动才能先找到比基准数小的数。
快速排序是不稳定的其时间平均时间复杂度是O(nlgn)。
import java.util.Arrays;public class Test {public static int partition(int[]arr , int left , int right) {int pKey arr[left];int pPointer left;while (left right) {while (left right arr[right] pKey) {right --;}while (left right arr[left] pKey) {left ;}swap(arr, left, right);}swap(arr, pPointer, left);return left;}public static void QuickSort(int[] arr, int left, int right){if (left right || arr null || arr.length 0) {return;}int mid partition(arr, left, right);QuickSort(arr, left, mid - 1);QuickSort(arr,mid 1, right);}private static void swap(int[] arr, int i, int j) {int temp arr[i];arr[i] arr[j];arr[j] temp;}public static void main(String[] args) {int[] array {0, 31, 12, 2, 8};QuickSort(array, 0,array.length-1);Arrays.stream(array).forEach(System.out::println);}}总结快速排序的思想冒泡二分递归分治 2.5 堆排序
堆排序是借助堆来实现的选择排序思想同简单的选择排序以下以大顶堆为例。注意如果想升序排序就使用大顶堆反之使用小顶堆。原因是堆顶元素需要交换到序列尾部。
首先实现堆排序需要解决两个问题
1. 如何由一个无序序列键成一个堆
2. 如何在输出堆顶元素之后调整剩余元素成为一个新的堆
第一个问题可以直接使用线性数组来表示一个堆由初始的无序序列建成一个堆就需要自底向上从第一个非叶元素开始挨个调整成一个堆。
第二个问题怎么调整成堆首先是将堆顶元素和最后一个元素交换。然后比较当前堆顶元素的左右孩子节点因为除了当前的堆顶元素左右孩子堆均满足条件这时需要选择当前堆顶元素与左右孩子节点的较大者大顶堆交换直至叶子节点。我们称这个自堆顶自叶子的调整成为筛选。
从一个无序序列建堆的过程就是一个反复筛选的过程。若将此序列看成是一个完全二叉树则最后一个非终端节点是n/2取底个元素由此筛选即可。 import java.util.Arrays;public class Test {public static void AdjustHeap(int[]arr , int start , int end) {int temp arr[start];for (int i 2 * start 1; i end; i * 2) {if (i end arr[i] arr[i 1]){i;}if (temp arr[i]) {break;}arr[start] arr[i];start i;}arr[start] temp;}public static void HeapSort(int[]arr) {if ( arr null || arr.length 0) {return;}for (int i arr.length/2; i0 ; i--) {AdjustHeap(arr, i, arr.length-1);}for (int i arr.length-1; i 0 ; i--) {swap(arr, 0, i);AdjustHeap(arr, 0, i-1);}}private static void swap(int[] arr, int i, int j) {int temp arr[i];arr[i] arr[j];arr[j] temp;}public static void main(String[] args) {int[] array {0, 31, 12, 2, 8};HeapSort(array );Arrays.stream(array).forEach(System.out::println);}}2.6 希尔排序
希尔排序是插入排序的一种高效率的实现也叫缩小增量排序。简单的插入排序中如果待排序列是正序时时间复杂度是O(n)如果序列是基本有序的使用直接插入排序效率就非常高。希尔排序就利用了这个特点。基本思想是先将整个待排记录序列分割成为若干子序列分别进行直接插入排序待整个序列中的记录基本有序时再对全体记录进行一次直接插入排序。
import java.util.Arrays;public class Test {public static void shellInsert(int[] arr, int d) {for (int i d; i arr.length; i) {int j i - d;int temp arr[i];while (j 0 arr[j] temp) {arr[j d] arr[j];j j - d;}if (j ! i - d) {arr[j d] temp;}}}public static void ShellSort(int[] arr) {if (arr null || arr.length 0) {return;}int d arr.length / 2;while (d 1) {shellInsert(arr, d);d d / 2;}}private static void swap(int[] arr, int i, int j) {int temp arr[i];arr[i] arr[j];arr[j] temp;}public static void main(String[] args) {int[] array {0, 31, 12, 2, 8};ShellSort(array);Arrays.stream(array).forEach(System.out::println);}}2.7 归并排序
归并排序是另一种不同的排序方法因为归并排序使用了递归分治的思想所以理解起来比较容易。其基本思想是先递归划分子问题然后合并结果。把待排序列看成由两个有序的子序列然后合并两个子序列然后把子序列看成由两个有序序列。。。。。倒着来看其实就是先两两合并然后四四合并。。。最终形成有序序列。空间复杂度为O(n)时间复杂度为O(nlogn)。 2.8 计数排序 虽然前面基于比较的排序的下限是O(nlogn)。但是确实也有线性时间复杂度的排序只不过有前提条件就是待排序的数要满足一定的范围的整数而且计数排序需要比较多的辅助空间。其基本思想是用待排序的数作为计数数组的下标统计每个数字的个数。然后依次输出即可得到有序序列。
2.9 桶排序
假设有一组长度为N的待排关键字序列K[1....n]。首先将这个序列划分成M个的子区间(桶) 。然后基于某种映射函数 将待排序列的关键字k映射到第i个桶中(即桶数组B的下标 i) 那么该关键字k就作为B[i]中的元素(每个桶B[i]都是一组大小为N/M的序列)。接着对每个桶B[i]中的所有元素进行比较排序(可以使用快排)。然后依次枚举输出B[0]….B[M]中的全部内容即是一个有序序列。bindexf(key) 其中bindex 为桶数组B的下标(即第bindex个桶), k为待排序列的关键字。桶排序之所以能够高效其关键在于这个映射函数它必须做到如果关键字k1k2那么f(k1)f(k2)。也就是说B(i)中的最小数据都要大于B(i-1)中最大数据。很显然映射函数的确定与数据本身的特点有很大的关系。
2.10 基数排序
基数排序又是一种和前面排序方式不同的排序方式基数排序不需要进行记录关键字之间的比较。基数排序是一种借助多关键字排序思想对单逻辑关键字进行排序的方法。所谓的多关键字排序就是有多个优先级不同的关键字。比如说成绩的排序如果两个人总分相同则语文高的排在前面语文成绩也相同则数学高的排在前面。。。如果对数字进行排序那么个位、十位、百位就是不同优先级的关键字如果要进行升序排序那么个位、十位、百位优先级一次增加。基数排序是通过多次的收分配和收集来实现的关键字优先级低的先进行分配和收集。
三、总结
冒泡排序、选择排序、插入排序三种简单的排序及其变种快速排序、堆排序、希尔排序三种比较高效的排序。后面我们又分析了基于分治递归思想的归并排序还有计数排序、桶排序、基数排序三种线性排序。我们可以知道排序算法要么简单有效要么是利用简单排序的特点加以改进要么是以空间换取时间在特定情况下的高效排序。但是这些排序方法都不是固定不变的需要结合具体的需求和场景来选择甚至组合使用。才能达到高效稳定的目的。没有最好的排序只有最适合的排序。
下面就总结一下排序算法的各自的使用场景和适用场合。
排序方法平均时间最坏时间辅助存储简单排序快速排序堆排序归并排序基数排序
1. 从平均时间来看快速排序是效率最高的但快速排序在最坏情况下的时间性能不如堆排序和归并排序。而后者相比较的结果是在n较大时归并排序使用时间较少但使用辅助空间较多。
2. 上面说的简单排序包括除希尔排序之外的所有冒泡排序、插入排序、简单选择排序。其中直接插入排序最简单但序列基本有序或者n较小时直接插入排序是好的方法因此常将它和其他的排序方法如快速排序、归并排序等结合在一起使用。
3. 基数排序的时间复杂度也可以写成O(d*n)。因此它最使用于n值很大而关键字较小的的序列。若关键字也很大而序列中大多数记录的最高关键字均不同则亦可先按最高关键字不同将序列分成若干小的子序列而后进行直接插入排序。
4. 从方法的稳定性来比较基数排序是稳定的内排方法所有时间复杂度为O(n^2)的简单排序也是稳定的。但是快速排序、堆排序、希尔排序等时间性能较好的排序方法都是不稳定的。稳定性需要根据具体需求选择。
5. 上面的算法实现大多数是使用线性存储结构像插入排序这种算法用链表实现更好省去了移动元素的时间。具体的存储结构在具体的实现版本中也是不同的。
