排序（2）

先赞后看，养成习惯！！！ ^ _ ^ ❤️ ❤️ ❤️
码字不易，大家的支持就是我坚持下去的动力，点赞后不要忘记关注我哦

个人主页：伯明翰java
文章专栏：数据结构和算法
如有错误，请您指正批评 ^ _ ^

书接上文

交换排序

基本思想：所谓交换，就是根据序列中两个记录键值的⽐较结果来对换这两个记录在序列中的位置，
交换排序的特点是：将键值较⼤的记录向序列的尾部移动，键值较⼩的记录向序列的前部移动。

冒泡排序

/** * 冒泡排序 * 时间复杂度O(n^2) * 稳定排序 * 空间复杂度O(1) * @param array */publicstaticvoidbubbleSort(int[]array){intleft=0;intright=array.length-1;while(left<right){intminIndex=left;intmaxIndex=left;for(inti=left+1;i<=right;i++){if(array[i]<array[minIndex]){minIndex=i;}if(array[i]>array[maxIndex]){maxIndex=i;}}seap(array,minIndex,left);if(maxIndex==left){maxIndex=minIndex;}seap(array,maxIndex,right);left++;right--;}}

特点：

1. 冒泡排序是⼀种⾮常容易理解的排序
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)
4. 空间复杂度：O(1)

快速排序

快速排序是Hoare于1962年提出的⼀种⼆叉树结构的交换排序⽅法，其基本思想为：任取待排序元素
序列中的某元素作为基准值，按照该排序码将待排序集合分割成两⼦序列，左⼦序列中所有元素均⼩
于基准值，右⼦序列中所有元素均⼤于基准值，然后最左右⼦序列重复该过程，直到所有元素都排列
在相应位置上为⽌。

/** * 时间复杂度O(nlogn) * 快速排序 不稳定排序 * 空间复杂度O(logn) * @param array */publicstaticvoidquickSort(int[]array){quick(array,0,array.length-1);}publicstaticvoidquick(int[]array,intleft,intright){if(left>=right){return;}intpivot=partition(array,left,right);quick(array,left,pivot-1);quick(array,pivot+1,right);}privatestaticintpartition(int[]array,intleft,intright){inttmp=array[left];while(left<right){while(left<right&&array[right]>=tmp){right--;}array[left]=array[right];while(left<right&&array[left]<=tmp){left++;}array[right]=array[left];}array[left]=tmp;returnleft;}

特点：

1. 快速排序整体的综合性能和使⽤场景都是⽐较好的，所以才敢叫快速排序
2. 空间复杂度：O(logN)
3. 时间复杂度：O(N*logN)
4. 稳定性：不稳定

归并排序

归并排序（MERGE-SORT）是建⽴在归并操作上的⼀种有效的排序算法,该算法是采⽤分治法（Divideand Conquer）的⼀个⾮常典型的应⽤。将已有序的⼦序列合并，得到完全有序的序列；即先使每个⼦序列有序，再使⼦序列段间有序。若将两个有序表合并成⼀个有序表，称为⼆路归并。 归并排序核⼼步骤：

特点：

1. 归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(N）
4. 稳定性：稳定

排序算法复杂度及稳定性分析