排序算法
1. 插入排序：平均On2，最好On，最坏On2，稳定
提取当前元素作为基准，对当前位置前面区间进行以当前元素为基准进行升序排列，排序完成后将当前元素放入区间的后一个位置
private static void insertSort(int[] nums) { for(int i=1;i<nums.length;i++){ int insertIndex; int insertNum = nums[i]; //以insertNum为基准对[0,insertIndex-1]区间进行升序排序 for(insertIndex=i-1;insertIndex >= 0 && nums[insertIndex] > insertNum;insertIndex--){ nums[insertIndex+1] = nums[insertIndex]; } //将insertNum插入到排序好的序列的后一个 nums[insertIndex+1] = insertNum; } }
2. 冒泡排序：平均On2，最好On，最坏On2，稳定
- 前后比较，前比后大，交换前后
private static void bubbleSort(int[] nums) { for(int i=0;i<nums.length-1;i++){ for(int j=0;j<nums.length-1-i;j++){ //前后比较，前比后大，交换前后 if(nums[j] > nums[j+1]){ swap(nums,j,j+1); } } } }
3. 选择排序：平均On2，最好On2，最坏On2，不稳定
- 选择当前元素为基准，对后面的区间查找最小值，交换当前和最小值
private static void selectSort(int[] nums) { for(int i=0;i<nums.length;i++){ int min = i; for(int j=i+1;j<nums.length;j++){ if(nums[j] < nums[min]){ min = j; } } if(min != i){ swap(nums,min,i); } } }
4. 归并排序：平均Onlogn，最好Onlogn，最坏Onlogn，稳定
private static void MergeSort(int[] nums, int start, int end) {
if(start == end){
return;
}
int middle = start + (end - start)/2;
//递归排序左右
MergeSort(nums,start,middle);
MergeSort(nums,middle+1,end);
//合并左右
Merge(nums,start,middle,end);
}
private static void Merge(int[] nums, int start, int middle, int end) {
int[] temp = new int[end - start + 1];
int index = 0;
int index1 = start;
int index2 = middle+1;
while(index1 <= middle && index2 <= end){
if(nums[index1] < nums[index2]){
temp[index++] = nums[index1++];
}else{
temp[index++] = nums[index2++];
}
}
while(index1 <= middle){
temp[index++] = nums[index1++];
}
while(index2 <= end){
temp[index++] = nums[index2++];
}
for(int i=0;i<temp.length;i++){
nums[i+start] = temp[i];
}
}5. 快排：平均Onlogn，最坏On2(冒泡)，最好Onlogn，不稳定
以第一个数为基准，比基准数小的，排在基准数左边，比基准数大的，排在基准数右边。递归再对这两个数组进行快排
private static void quickSort(int[] nums, int start, int end) { if(start > end){ return; } int pivot = getPivot(nums,start,end); //根据本次基准数，排序基准数左右序列 quickSort(nums,start,pivot-1); quickSort(nums,pivot+1,end); } private static int getPivot(int[] nums, int start, int end) { int pivot = nums[start]; int left = start; int right = end; while(left <= right){ while(left <= right && nums[left] <= pivot){ left++; } while(left <= right && nums[right] > pivot){ right--; } if(left <= right){ swap(nums,left,right); } } //基准数归位，返回基准数 swap(nums,start,right); return right; }
7. 堆排：平均Onlogn，最好Onlogn，最坏Onlogn，不稳定
建堆：par和cur比较，如果par比cur小，交换，cur=par
排序：提取nums[0]，将nums[0]替换nums[index]，提取left和right，判断left越界，提取left为max，比较max和right，比较max和cur
public static void main(String[] args) { int[] nums = new int[]{10,3,5,6,7,0,2}; //建堆 for(int i=0;i<nums.length;i++){ create(nums,i); } //排序 int [] result = new int[nums.length]; int len = result.length-1; for(int i=nums.length-1;i>=0;i--){ result[i] = poll(nums,len--); } for(int i : result){ System.out.println(i); } } private static int poll(int[] nums, int index) { int result = nums[0]; nums[0] = nums[index]; int cur = 0; while(true){ int left = cur*2 + 1; int right = cur*2 + 2; //左子树越界 if(left >= index){ break; } //右子树和max比较 int max = left; if(right <= index && nums[max] < nums[right]){ max = right; } //cur和max比较 if(nums[cur] < nums[max]){ swap(nums,cur,max); }else{ break; } cur = max; } return result; } private static void create(int[] nums, int index) { //当前节点 int cur = index; while(cur > 0){ //父节点 int par = (cur-1)/2; //如果当前比父节点大，交换 if(nums[par] < nums[cur]){ swap(nums,par,cur); }else{ break; } cur = par; } }
