往期：
JAVA 修炼秘籍第一章：《痛苦的折磨》
JAVA 修炼秘籍第二章：《逐渐魔化》
JAVA 修炼秘籍第三章：《绝地反击》
JAVA 修炼秘籍第四章：《闭关修炼》
JAVA 修炼秘籍第五章：《卧薪尝胆》
JAVA 修炼秘籍第六章：《鏖战》
JAVA 修炼秘籍第七章：《面向对象编程》
JAVA 修炼秘籍第八章：《String类》
JAVA 修炼秘籍第九章：《List / ArrayList / linkedList 》
JAVA 修炼秘籍第十章：《优先级队列（堆）PriorityQueue》
JAVA修炼秘籍（番外篇）第一章：《这四道代码题，你真的会吗？》
JAVA修炼秘籍（番外篇）第二章：《图书馆管理系统》
——————————————————————生活以痛吻我，我却报之以歌。 文章目录
- 一、插入排序
- 二、折半插入排序
- 三、希尔排序
- 四、选择排序
- 五、双向选择排序
- 六、堆排序
- 七、冒泡排序
- 八、快速排序（挖坑）
- 九、快速排序（Hoare）
- 十、快速排序（非递归）
- 十一、归并排序（递归）
- 十二、归并排序（非递归）
一、插入排序
- 时间复杂度：O(n²)。
- 空间复杂度：O(1)。
- 当一组数据，数据量不大且趋近于有序时，推荐使用插入排序更快
public static void InsertSort(int[] arr){
for(int i=1;i=0;j--){
if(arr[j]>tmp){
arr[j+1]=arr[j];
}else{
break;
}
}
arr[j+1]=tmp;
}
}
二、折半插入排序
- 时间复杂度：O(n²)。
- 空间复杂度：O(1)。
- 通过直接插入排序可以发现，每次比较时，i下标前的数据时有序的。
- 折半插入排序利用此特性将i下标的值与前面有序数据进行二分查找。
- 算是直接插入排序的一种优化。
public static void HalveInsertSort(int[] arr){
for(int i=1;i=left){
int mid=(left+right)/2;
if(arr[mid]>tmp){
right=mid-1;
}else{
left=mid+1;
}
}
for(int j=i-1;j>right;j--){
arr[j+1]=arr[j];
}
arr[right+1]=tmp;
}
}
三、希尔排序
- 时间复杂度：O(n1.3)。
- 空间复杂度：O(1)。
- 希尔排序的巧妙处与插入排序有异曲同工之处。
- 中心思想在于gap的取值，取值方法有很多中，但都大同小异，其余思想与插入排序无太大差别。
public static void shellSort(int[] arr){
int gap=arr.length;
while(gap>0){
mySort(arr,gap);
gap/=2;
}
}
public static void mySort(int[] arr,int gap){
for(int i=gap;i<=arr.length;i++){
int tmp=arr[i];
int j=i-gap;
for(;j>=0;j-=gap){
if(arr[j]>tmp){
arr[j+gap]=arr[j];
}else{
break;
}
}
arr[j+gap]=tmp;
}
}
四、选择排序
- 时间复杂度：O(n²)。
- 空间复杂度：O(1)。
- 顾名思义，选择排序，选择好了再排序。
- 每次从数组中选择一个最大或最小的数据与头或尾交换。
- 再将交换后的边界缩小。
public static void selectSort(int[] arr){
for(int i=0;iarr[max]){
max=j;
}
}
int tmp=arr[max];
arr[max]=arr[arr.length-1-i];
arr[arr.length-1-i]=tmp;
}
}
五、双向选择排序
- 时间复杂度：O(n²)。
- 空间复杂度：O(1)。
- 与选择排序中心思想相同，这次是一次找出最大与最小同时交换
- 此算法中而每次取值的最小值下标有头下标交换时，如果头下标的位置刚好时是最大值，此时交换后max下标指向则不是最大值而是最小值，最后的if()判断很重要。
public static void TwoWaySelectSort(int[] arr){
int left=0;
int right=arr.length-1;
while(left<=right){
int min=left;
int max=left;
for(int i=left+1;i<=right;i++){
if(arr[i]>arr[max]){
max=i;
}
if(arr[i]
六、堆排序
- 时间复杂度：O(logn)。
- 空间复杂度：O(1)。
- 假设要排序升序，首先将数组变为大堆存储形式。
- 再循环从后向前把每个元素与0下标元素交换。
- 每次交换后都要进行一次大堆调整。
public static void shiftDown(int[] arr,int parent,int len){
int child=parent*2+1;
while(childarr[parent]){
swap(arr,child,parent);
parent=child;
child=parent*2+1;
}else{
break;
}
}
}
public static void MySort(int[] arr){
for(int i=(arr.length-1)/2;i>=0;i--){
shiftDown(arr,i,arr.length);
}
}
public static void heapSort(int[] arr){
MySort(arr);
int end=arr.length-1;
while(end>0){
swap(arr,0,end);
shiftDown(arr,0,end);
end--;
}
}
七、冒泡排序
- 时间复杂度：O(n²)。
- 空间复杂度：O(1)。
- 两两比较，最终将数组最大元素放在最后位置。
- 调整边界，因上次循环结束后最后以为已是有序，每次比较长度-1。
- 若一次循环下来，没有任何数据交换，此时证明当前数据集已经有序，可以直接结束循环。
public static void bubbleSort(int[] arr){
for(int i=0;i
八、快速排序（挖坑）
- 时间复杂度：O(logn)。
- 空间复杂度：O(logn)。
- 顾名思义，选择一个基准值，将小于基准值大放到基准值左，大于基准值放在右。
public static int partition(int[] arr,int start,int end){
int tmp=arr[start];
while(start=tmp){
end--;
}
arr[start]=arr[end];
while(start=right){
return;
}
int pivot=partition(arr,left,right);
quickSorts(arr,left,pivot-1);
quickSorts(arr,pivot+1,right);
}
public static void quickSort(int[] arr){
quickSorts(arr,0,arr.length-1);
}
九、快速排序（Hoare）
- 时间复杂度：O(logn)。
- 空间复杂度：O(logn)。
- 思想于挖坑法大致相同，此方法只是将每次的大于基准值与小于基准值同时交换。
public static int partition(int[] arr,int start,int end){
int i=start;
int j=end;
int tmp=arr[i];
while(i=tmp){
j--;
}
while(i=right){
return;
}
int pivot=partition(arr,left,right);
quickSorts(arr,left,pivot-1);
quickSorts(arr,pivot+1,right);
}
public static void quickSort(int[] arr){
quickSorts(arr,0,arr.length-1);
}
十、快速排序（非递归）
- 时间复杂度：O(logn)。
- 空间复杂度：O(logn)。
- 非递归思想需要借助一个栈来记录基准值左右的下标。
- 代码运行流程与递归无太大差别。
public static int partition(int[] arr,int start,int end){
int tmp=arr[start];
while(start=tmp){
end--;
}
arr[start]=arr[end];
while(start stack=new Stack<>();
int pivot=partition(arr,left,right);
if(left+1pivot){
stack.add(pivot+1);
stack.add(right);
}
while(!stack.isEmpty()){
right=stack.pop();
left=stack.pop();
pivot=partition(arr,left,right);
if(left+1pivot){
stack.add(pivot+1);
stack.add(right);
}
}
}
十一、归并排序（递归）
- 时间复杂度：O(n logn)。
- 空间复杂度：O(n)。
- 把一个大问题拆分成一个一个的小问题，把每一个小问题都排序好，再组合。
public static void merge(int[] arr,int low,int mid,int high,int[] tmp){
int i = 0;
int j = low,k = mid+1;
while(j <= mid && k <= high){
if(arr[j] < arr[k]){
tmp[i++] = arr[j++];
}else{
tmp[i++] = arr[k++];
}
}
while(j <= mid){
tmp[i++] = arr[j++];
}
while(k <= high){
tmp[i++] = arr[k++];
}
for(int t=0;t
十二、归并排序（非递归）
- 时间复杂度：O(nlogn)。
- 空间复杂度：O(n)。
- 控制好边界就好。
public static void mergeSorts(int[] arr,int gap){
int s1=0;
int e1=s1+gap-1;
int s2=e1+1;
int e2=Math.min(arr.length-1,s2+gap-1);
int[] tmp=new int[arr.length];
int k=0;
while(s2 
