冒泡排序
平均时间复杂度： o(n^2)
最好时间： o(n)
最坏时间： o(n^2)
空间复杂度： o(1)
是否稳定： 稳定
简单的冒泡排序
public int[] bubbleSort(int [] nums){ int len = nums.length; if(len <= 1) return nums; for(int i = 0;i < len;i++){ for(int j = 0;j < len-i-1;j++){ if(nums[j] > nums[j+1]){ int temp = nums[j+1]; nums[j+1] = nums[j]; nums[j] = temp; } } } return nums; }
冒泡排序的优化
设置标志位
设置一个标志位来标识这次遍历是否进行过交换
如果没有进行过交换则表示数组已经有序，直接退出
public int[] binarySort(int [] nums){ int len = nums.length; if(len <= 1) return nums; for(int i = 0;i < len-1;i++){ boolean isSort = true; //是否有序 for(int j = 0;j < len-i-1;j++){ if(nums[j] > nums[j+1]){ int temp = nums[j+1]; nums[j+1] = nums[j]; nums[j] = temp; isSort = false; } } if(isSort) break; } return nums; }
设置结束位置
比如初始数组为[4,3,2,1,5,6]
经过第一次排序后数组变为[3,2,1,4,5,6]
如果按照普通冒泡排序下次需要遍历的下标范围为[0,4]
但是[3,4]是已经有序的，所以可以减少比较，保存上次交换的结束位置
public int[] bubbleSort(int [] nums){ int len = nums.length; if(len <= 1) return nums; int max_index = len-1; int index = max_index; for(int i = 0;i < len-1;i++){ boolean isSort = true; //是否有序 for(int j = 0;j < index;j++){ if(nums[j] > nums[j+1]){ int temp = nums[j+1]; nums[j+1] = nums[j]; nums[j] = temp; isSort = false; max_index=j; } } if(isSort) break; index = max_index; } return nums; }
双向冒泡排序
与设置结束位置类似，这个是也设置了起始位置
使得在left之前的都是已经排好序的
public int[] bubbleSort(int [] nums){ int len = nums.length; if(len <= 1) return nums; int left = 0; int right = len-1; int tleft = 0,tright = 0; while(left < right){ boolean isSort = true; for(int i = left;i < right;i++){ if(nums[i+1] < nums[i]){ int temp = nums[i]; nums[i] = nums[i+1]; nums[i+1] = temp; isSort = false; tright = i; } } if(isSort)break; right = tright; isSort = true; for(int i = right;i > left;i--){ if(nums[i] < nums[i-1]){ int temp = nums[i]; nums[i] = nums[i-1]; nums[i-1] = temp; isSort = false; tleft = i; } } if(isSort)break; left = tleft; } return nums; }
选择排序
平均时间复杂度： o(n^2)
最好时间： o(n^2)
最坏时间： o(n^2)
空间复杂度： o(1)
是否稳定： 不稳定
选择排序
public int[] selectSort(int [] nums){ int len = nums.length; if(len <= 1) return nums; for(int i = 0;i < len;i++){ int minIndex = i; for(int j = i;j < len;j++){ if(nums[j] < nums[minIndex]){ minIndex = j; } } int t = nums[minIndex]; nums[minIndex] = nums[i]; nums[i] = t; } return nums; }
插入排序
平均时间复杂度： o(n^2)
最好时间： o(n)
最坏时间： o(n^2)
空间复杂度： o(1)
是否稳定： 稳定
插入排序
public int[] insertSort(int [] nums){ int len = nums.length; if(len <= 1) return nums; for(int i = 1;i < len;i++){ int cur = nums[i]; int preIndex = i - 1; while(preIndex >= 0 && nums[preIndex] > cur){ nums[preIndex+1] = nums[preIndex]; preIndex--; } nums[preIndex+1] = cur; } return nums; }
快速排序
平均时间复杂度： o(nlogn)
最好时间： o(nlogn)
最坏时间： o(n^2)
空间复杂度： o(logn)
是否稳定： 不稳定
快速排序
public void quickSort(int [] nums,int left,int right){ if(left >= right) return; int l = left - 1; int r = right + 1; int t = nums[left]; while(l < r){ do l++;while(nums[l] < t); do r--;while(nums[r] > t); if(l < r){ int temp = nums[l]; nums[l] = nums[r]; nums[r] = temp; } } quickSort(nums,left,r); quickSort(nums,r+1,right); }
归并排序
平均时间复杂度： o(nlogn)
最好时间： o(nlogn)
最坏时间： o(nlogn)
空间复杂度： o(n)
是否稳定： 稳定
public void mergeSort(int [] nums,int left,int right){ if(left >= right) return; int mid = left + right >> 1; mergeSort(nums,left,mid); mergeSort(nums,mid+1,right); //需要合并 [left,mid] [mid+1,right] int []temp = new int[right-left+1]; int l = left,r = mid+1,k = 0; while(l <= mid && r <= right){ if(nums[l] < nums[r]) temp[k++] = nums[l++]; else temp[k++] = nums[r++]; } while(l <= mid) temp[k++] = nums[l++]; while(r <= right) temp[k++] = nums[r++]; for(int i = right;i >= left;i--){ nums[i] = temp[--k]; } }
堆排序
平均时间复杂度： o(nlogn)
最好时间： o(nlogn)
最坏时间： o(nlogn)
空间复杂度： o(1)
是否稳定： 不稳定
public void heapSort(int [] nums){ int len = nums.length; if(len <= 1) return; //构造大根堆 for(int i = (len-1)/2; i>=0 ;i--){ heap(nums,i,len); } //将根弄到最后 for(int i = len-1;i >=0; i--){ int t = nums[0]; nums[0] = nums[i]; nums[i] = t; heap(nums,0,i); } } //子树构建大顶堆 public void heap(int[] nums,int index,int size){ int max = index; int left = 2 * index + 1; int right = 2 * index + 2; if(left < size && nums[left] > nums[max]) max = left; if(right < size && nums[right] > nums[max]) max = right; if(max != index){ int t = nums[index]; nums[index] = nums[max]; nums[max] = t; heap(nums,max,size); } }
