文登区住房和城乡建设局网站,给wordpress注册用户发邮件,中国农村建设投资有限公司网站,电子商务有哪些工作岗位常用的八种内排序算法分别是#xff1a;
交换排序#xff1a;冒泡排序、快速排序选择排序#xff1a;简单选择排序、堆排序插入排序#xff1a;直接插入排序、希尔排序归并排序基数排序
内排序巧记#xff1a;选(选择)舰(简单选择)队(堆)的时候脚(交换)毛(冒泡)快(快速)
交换排序冒泡排序、快速排序选择排序简单选择排序、堆排序插入排序直接插入排序、希尔排序归并排序基数排序
内排序巧记选(选择)舰(简单选择)队(堆)的时候脚(交换)毛(冒泡)快(快速)需要把轨(归并)迹(基数)擦(插入)仔(直接插入)细(希尔)
一、算法的概念和编码实现Java
1、冒泡排序
冒泡排序的基本思想是对相邻的元素进行两两比较顺序相反则进行交换这样每一趟会将最小或最大的元素“浮”到顶端最终达到完全有序 代码实现升序 public static void selectSort(int[] array) {int len array.length;boolean flag true;for (int i 0; i len - 1 flag; i) {flag false;for (int j 0; j len - i - 1; j) {if (array[j] array[j 1]) {int temp array[j];array[j] array[j 1];array[j 1] temp;flag true;}}}} 最好情况的时间复杂度最坏情况的时间复杂度特点稳定性T(n)O(n)T(n)O(n2)如果数据已经排序好一次都不交换或者交换次数很少效率很高如果是完全逆序则要不停的两两交换效率很低稳定
2、简单选择排序
简单选择排序的基本思想是每一趟从待排序的数据元素中选择一个最小或者最大的元素作为首元素直到所有元素排完为止。 代码实现升序 public static void selectSort(int[] array) {int len array.length;for (int i 0; i len-1; i) {int min i;// 每趟排序默认第一个元素是最小的元素记住下标for (int j i 1; j len; j) {// 从i1的位置开始依次同最小元素比较若比最小元素小则记住当前下标if (array[j] array[min]) {min j;}}// 无序区最小元素同无序区的第一个元素交换if (min ! i) {int temp array[min];array[min] array[i];array[i] temp;}}}
时间复杂度特点稳定性T(n)O(n2)简单相对于冒泡排序来说交换次数少不稳定
3、直接插入排序
直接插入排序基本思想是不断将无序区的元素插入到有序区的适当位置直到无序区没有元素排完为止 代码实现升序 private static void insertSort(int[] array) {for (int i 1; i array.length; i) {int j ;int temp array[i];for (j i; j0 temp array[j-1]; j--) {array[j] array[j-1];}array[j] temp;}} 最好情况的时间复杂度最坏情况的时间复杂度特点稳定性T(n)O(n)T(n)O(n2)简单稳定
4、快速排序
对冒泡排序的一种改进它的思想是将元素分为两组一组的元素比另外一组的所有元素都要小然后再按照此方法对两组元素进行排序。
快速排序我这里就不写了快速排序相对于前面三种排序方式来说要复杂很多看了一些博客发现写得都不怎么样这里推荐一个讲快速排序的视频https://www.bilibili.com/video/av39519566/?redirectFromh5
附上代码实现参考视频中的
public static void quickSort(int[] arr,int left,int right){//如果左边索引比右边索引更大或者相等直接使用return结束这个方法if(left right){return;}//定义变量保存基准数int base arr[left];//定义变量i指向最左边int i left;//定义变量j指向最右边int j right;//当i和j不相遇的时候在循环中进行检索while(i!j){//先由j从右向左检索比基准数小的就停下否则继续检索while(arr[j]base ij){j--;}//在由i从左向右检索比基准数大的就停下,否则继续检索while(arr[i]base ij){i;}//代码走到这里i停下了j也停下了然后交换i和j位置的元素int temp arr[i];arr[i] arr[j];arr[j] temp;}//交换基准数和相遇位置的元素arr[left] arr[i];arr[i] base;//排基准数左边的quickSort(arr,left,i-1);//排基准数右边的quickSort(arr,j1,right);}
最好情况的时间复杂度最坏情况的时间复杂度平均时间复杂度特点稳定性T(n)O(nlogn)T(n)O(n2)T(n)O(nlogn)较复杂不稳定
5、希尔排序
希尔排序是对直接插入排序的优化原理是将数据按照步长dk分为dk个子列然后再对每个子列运用直接插入排序。
当步长为5的时候分组情况如下 每个子列排好序后变成 代码实现升序 public static void main(String[] args) {int[] array {49,38,65,97,76,13,27,49,55,4};print(array);ShellSort(array,5);print(array);ShellSort(array,3);print(array);ShellSort(array,1);print(array);}private static void print(int[] array){for (int i 0; i array.length; i) {System.out.print(array[i]\t);}System.out.println(\n);}//希尔排序,dk表示步长private static void ShellSort(int[] array,int dk) {for(int k 0;kdk;k){//每个子组做直接插入插入排序for(int i dkk;iarray.length;){int j ;int temp array[i];for (j i; j-dk0 temp array[j-dk]; ) {j - dk;//上一个元素的索引需要减去dk而不是减1array[j] array[j-dk];}array[j] temp;i dk;//下一个元素索引加上dk而不是加1}}}
说明从代码层面来看希尔排序相对于直接插入排序的不同点在于希尔排序外层多了一层循环用来将原序列分层若干个子列。内部的直接插入排序做减减或者加加时要改成减去步长或者加上步长
二、时间复杂度和空间复杂度分析
排序的稳定性根据关键字相同如果数值比较的话是指大小的记录排序前后相对位置的变化可以分为稳定性排序算法和不稳定性排序算法。在排序的序列中如果存在两个记录Ri和Rj其关键字分别为Ki和Kj,并且ij,KiKj,即记录Ri在Rj之前排序完成后如果记录Ri和Rj的相对位置不发生改变那么该算法是稳定性排序否则是不稳定排序。
排序方法时间复杂度最坏情况空间复杂度辅助空间稳定性复杂性简单选择排序O(n2)O(1)不稳定简单冒泡排序O(n2)O(1)稳定简单快速排序O(n2) 不稳定较复杂直接插入排序O(n2)O(1)稳定简单希尔排序O(n2)O(1)不稳定较复杂
