堆排序；快速排序；归并排序

快速排序算法

堆排序

时间复杂度：0（N*log(N)）
空间复杂度：0（1）
稳定性：不稳定

privatestaticvoidheapSort(int[] arr){//建堆crearHeap(arr);for(int i =0; i < arr.length-1; i++){int heapSize=arr.length-i;swap(arr,heapSize-1,0);
            heapSize--;shiftDown(arr,heapSize,0);}System.out.println(Arrays.toString(arr));}privatestaticvoidcrearHeap(int[] arr){// 从后往前遍历(右边非叶子节点开始), 依次进行向下调整for(int i =(arr.length-1-1)/2; i >=0; i--){shiftDown(arr,arr.length,i);}}//向下调整，形成大堆privatestaticvoidshiftDown(int[] arr,int size,int i){int parent = i;int child = parent*2+1;while(child<size){if(child +1< size && arr[child +1]> arr[child]){
                child=child+1;}if(arr[child]>arr[parent]){swap(arr,child,parent);}else{break;}
            parent=child;
            child=parent*2+1;}}//交换privatestaticvoidswap(int[] arr,int child,int parent){int tmp =arr[child];
        arr[child]=arr[parent];
        arr[parent]=tmp;}

快速排序

时间复杂度:O(N^ logN) 最坏的时候O(N^2) 和基准值密切相关
空间复杂度:0(logN) 最坏的时候O(N)
稳定性:不稳定

递归

privatestaticvoidquick(int[] arr){quickSortHelper(arr,0,arr.length-1);System.out.println(Arrays.toString(arr));}privatestaticvoidquickSortHelper(int[] arr,int left,int right){if(left>=right){//区间只有一个元素，或者零个元素return;}int index =partition(arr,left,right);quickSortHelper(arr,left,index-1);quickSortHelper(arr,index+1,right);}privatestaticintpartition(int[] arr,int left,int right){int i=left;int j=right;int baseValue=arr[right];while(i<j){while(i<j && arr[i]<=baseValue){
                i++;}while(i<j && arr[j]>=baseValue){
                j--;}if(i<j){swap(arr,i,j);}}swap(arr,i,right);return i;}privatestaticvoidswap(int[] arr,int i,int j){int tmp =arr[i];
        arr[i]=arr[j];
        arr[j]=tmp;}

非递归

publicstaticvoidquickSortByLoop(int[] arr){Stack<Integer> stack =newStack<>();
        stack.push(0);
        stack.push(arr.length-1);while(!stack.isEmpty()){int right = stack.pop();int left = stack.pop();if(left>=right){continue;}int index =partition(arr,left,right);//右子树
            stack.push(index+1);
            stack.push(right);//左子树
            stack.push(left);
            stack.push(index-1);}System.out.println(Arrays.toString(arr));}privatestaticintpartition(int[] arr,int left,int right){int baseValue =arr[right];int i =left;int j =right;while(i<j){while(i<j && arr[i]<=baseValue){
                i++;}while(i<j && arr[j]>=baseValue){
                j--;}if(i<j){swap(arr,i,j);}}swap(arr,i,right);return i;}privatestaticvoidswap(int[] arr,int i,int j){int tmp = arr[i];
        arr[i]= arr[j];
        arr[j]= tmp;}

归并排序

时间复杂度:O(NlogN)
空间复杂度:O(N） 如果是链表，可以为O(1)
稳定性:稳定

递归

publicstaticvoidmergeSort(int[] arr){mergeSortHelper(arr,0,arr.length);System.out.println(Arrays.toString(arr));}privatestaticvoidmergeSortHelper(int[] arr,int left,int right){if(right-left<=1){return;}int mid =(right+left)/2;mergeSortHelper(arr,left,mid);mergeSortHelper(arr,mid,right);merge(arr,left,mid,right);}privatestaticvoidmerge(int[] arr,int left,int mid,int right){int cur1 =left;int cur2 =mid;//两个数组合并后的结果int[] output=newint[right-left];int outputIndex=0;while(cur1<mid && cur2<right){if(arr[cur1]<=arr[cur2]){
                output[outputIndex++]= arr[cur1++];}else{
                output[outputIndex++]= arr[cur2++];}}while(cur1<mid){
            output[outputIndex++]= arr[cur1++];}while(cur2<right){
            output[outputIndex++]= arr[cur2++];}for(int i =0; i < right-left ; i++){
            arr[left+i]= output[i];}}

非递归

publicstaticvoidmergeSortByLoop(int[] arr){// gap 当前每个组中的元素个数.for(int gap =1;gap<arr.length;gap*=2){for(int i =0; i <arr.length ; i+=2*gap){//相当于把两个长度为 gap 的相邻组进行了合并int left =i;int mid =i+gap;int right=i+2*gap;if(mid > arr.length){
                    mid =arr.length;}if(right>arr.length){
                    right=arr.length;}merge(arr,left,mid,right);}}System.out.println(Arrays.toString(arr));}