排序

排序算法

冒泡排序

(O(n²)/O(n)/O(n²)|O(1),稳定)

依次交换相邻元素最值

public void bubbleSort(int[] arr){
    int temp = 0;
    boolean flag = false;
    for (int i = 1; i < arr.length-1; i++) {
        flag = false;
        for (int j = 0; j < arr.length-i; j++) {
            if(arr[j]>arr[j+1]){//排序顺序决断点
                temp = arr[j+1];
                arr[j+1] = arr[j];
                arr[j] = temp
                flag = true
            }
        }
        if(!flag){
            break;
        }
    }
}

选择排序

(O(n²)/O(n²)/O(n²)|O(1),不稳定)

依次查询最值放在前面

public void selectSort(int[] arr){
    int min = 0;
    int index = 0;
    for(int i= 0;i< arr.length-1;i++){
        min = arr[i];
        index = i;
        for(int j=i+1;j<arr.length;j++){
            if(min>arr[j]){//排序顺序决断点
                min = arr[j];
                index = j;
            }
        }
        if(index!=i){
            arr[index] = arr[i];
            arr[i] =min;            
        }
    }
}

插入排序

(O(n²)/O(n)/O(n²)|O(1),稳定)

序列分为有序序列和无序序列，依次从无序序列插入值到有序序列中

public void insertSort(int[] arr){
    int insertVal = 0;
    int index = 0;
    for(int i=1;i<arr.length;i++){
        insertVal = arr[i];
        index = i-1;
        while(index>=0 && insertVal < arr[index]){//排序顺序决断点
            arr[index+1] = arr[index];
            index--;
        }
        arr[index+1] = insertVal;
    }
}

快速排序-冒泡排序PRO

(O(nlog₂n)/O(nlog₂n)/O(n²)|O(nlog₂n),不稳定)

public void quickSort(int[] arr,int low,int high){
    int tmp = arr[low];
    int left = low;
    int right = high;
    
    if(left < high){
        while(left<high && tmp <= arr[right]){
            right--;
        }
        if(left<high){
            arr[left++] = arr[right];
        }
        while(left<high && tmp >= arr[left]){
            left++;
        }
        if(left<high){
            arr[right--] = arr[left];
        }
        arr[left] = tmp;
        quickSort(arr,low,left-1);
        quickSort(arr,left+1,high);
    }   
}

希尔排序-插入排序PRO

(O(n^1.3)/O(n)/O(n²)|O(1),不稳定)

//移位法
public void shellSort1(int[] arr){
    int insertVal = 0;
    int insertIndex = 0;
    for(int gap = arr.length/2 ;gap>0 ;gap/=2){
        for(int i=gap;i<arr.length;i++){
            insertVal = arr[i];
            insertIndex = i;
            while(insertIndex-gap>=0 && insertVal<arr[insertIndex-gap]){
                arr[insertIndex] = arr[insertIndex-gap];
                insertIndex-=gap;
            }
            arr[insertIndex] = insertVal; 
		}
    }
}

//交换法
public void shellSort(int[] arr){
    int tmp = 0;
    for(int gap = arr.length/2; gap >0; gap/=2){
        for(int i=gap;i<arr.length;i++){
            if(arr[i]>arr[i+gap]){
                tmp = arr[i];
                arr[i] = arr[i+gap];
                arr[i+gap] = arr[i];
            }
        }
    }
}

归并排序

(O(nlog₂n)/O(nlog₂n)/O(nlog₂n)|O(1),稳定)

//将数组分成小数组直至两两元素比较
public void mergeSort(int[] arr,int low,int high){
    if(low<high){
        int mid = (low + high)/2;
        mergeSort(arr,low,mid);
        mergeSort(arr,mid+1,high);
        merge(arr,low,mid,high);
    }
}
//合并两个已排序数组
public void merge(int[] arr,int low ,int mid,int high){
    int[] temp = new int[high-low+1];
    int tempIndex = 0;
    int i = low;
    int j = mid+1;
    while(i<=mid&&j<=high){
        if(arr[i]<=arr[j]){
            temp[tempIndex++] = arr[i++];
        }else{
            temp[tempIndex++] = arr[j++];
        }
    }
    while(i<=mid){
        temp[tempIndex++] = arr[i++];
    }
    while(j<=high){
        temp[tempIndex++] = arr[j++];
    }
    tempIndex=0;
    while(tempIndex<temp.length)){
        arr[low++] = temp[tempIndex];
    }
}

堆排序

(O(nlog₂n)/O(nlog₂n)/O(nlog₂n)|O(1),不稳定)

public void heapOrder(int[] arr){
    for(int i=arr.length/2-1;i>=0;i--){
        adjustHeap(arr,i,arr.length)
    }
    //调整好的大/小顶堆
    int temp = 0;
    for(int i = arr.length-1;i>0;i--){
        //首尾交换，最值沉降到末尾，待排序元素数量-1
        temp = arr[i];
        arr[i] = arr[0];
        arr[0] = temp;
        //因交换，顶堆被打乱，重新调整
        adjustHeap(arr,0,i);
    }
}
public void adjustHeap(int[] arr,int index,int length){
    int temp = arr[index];
    for(int i=2*index+1;i<length;i=2*i+1){
        if(i+1<length && arr[i]<arr[i+1]){
            i++;
        }
        if(temp<arr[i]){
            arr[index] = arr[i];
            index = i;
        }else{
            break;
        }
        arr[i] = temp;
    }
}