題目

給你一個整數(shù)數(shù)組 nums，將該數(shù)組升序排列。
示例 1：
輸入：nums = [5,2,3,1]
輸出：[1,2,3,5]

示例 2：
輸入：nums = [5,1,1,2,0,0]
輸出：[0,0,1,1,2,5]

提示：
1 <= nums.length <= 50000
-50000 <= nums[i] <= 50000

解題

1.選擇排序

這種排序方式應(yīng)該是很簡單的，容易理解，對于長度為n的數(shù)組，遍歷n-1次，每次在無序的數(shù)組段中選擇最小的一個元素和無序數(shù)組第一個元素交換位置?；蛘叻催^來，找最大的和最后一個交換，也是一樣的。在交換過程中，相同元素的位置不會變化，因此是穩(wěn)定的。不過判斷的方式不同，導(dǎo)致的穩(wěn)定性也不同。比如如果我寫成nums[j]<=nums[min]，那就變成不穩(wěn)定的了。
時間復(fù)雜度是O(n^2)

    //選擇排序
     public void selectSort(int[] arr){ 
        int min = 0;
        int minIndex = 0;
        for(int k=0;k<arr.length-1;k++){
             min = arr[k];
             minIndex = k;
            for(int i=k+1;i<=arr.length-1;i++){
                if(min>arr[i]){
                    min = arr[i];
                    minIndex = i;
                }
            }
            if(minIndex >k){
                arr[minIndex] = arr[k];
                arr[k]=min;
            }
            System.out.println("第"+(k+1)+"輪排序的結(jié)果為:"+ Arrays.toString(arr));
        }
 
    }

2.冒泡排序

這種排序方式是對一個數(shù)組遍歷n-1次，每次通過交換相鄰兩個元素位置，使得局部相對大小滿足要求，每次的結(jié)果是將最大值交換到了最后位置，就像泡泡冒到最高一樣。
時間復(fù)雜度是O(n^2)，穩(wěn)定的。

 public void bubbleSort(int[] arr){
        int temp=0;
        boolean flag = false;
        for(int i=0;i<arr.length-1;j++){
            for(int j=0;j<arr.length-1-i;j++){
                if(arr[j]>arr[j+1]){
                    flag = true;
                    temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
            
            if(flag){
              flag = false;
            }else{
              break;
            }
        }
}

3.插入排序

模擬一個插入元素的過程，在插入的過程中要找到插入的位置，使得插入之后新的數(shù)組段是有序的。在查找位置的時候，也要從后往前去遍歷，因此時間復(fù)雜度也是比較高，O(n^2)，穩(wěn)定的。

    public static void insertSort(int[] arr){
        for(int i=1;i<=arr.lenght()-1;i++){
                int insertVal = arr[i];
                int preIndex = i-1;
                while(preIndex>=0 && insertVal<arr[preIndex]){
                  arr[preIndex+1] = arr[preIndex];
                  preIndex--;
                }
                if(preIndex+1!=i){
                   arr[preIndex+1]=insertVal;
                }
         }
    }

4.希爾排序

希爾排序是插入排序的優(yōu)化，將插入排序的比較間隔擴(kuò)大，不再是相鄰元素比較大小，比插入排序優(yōu)化了一些，時間復(fù)雜度O(n^1.3-2)，因?yàn)榻粨Q的時候是跳躍式的交換，無法保證穩(wěn)定，不穩(wěn)定的。

 public void shellSort(int[] arr ) {
        int count=0;
        int preIndex =0;
        int insertVal=0;
        for(int gap=arr.length/2;gap>0;gap=gap/2){
            for(int i=gap;i<arr.length;i++){
                 preIndex = i-gap;
                 insertVal = arr[i];
                if(insertVal<arr[preIndex]){
                    while(preIndex>=0 && insertVal<arr[preIndex]){
                        arr[preIndex+gap] = arr[preIndex];
                        preIndex=preIndex-gap;
                    }
                    arr[preIndex+gap]=insertVal;
                 }
            }
            System.out.println("第"+(++count)+"輪排序結(jié)果："+ Arrays.toString(arr));
         }
     }

5.快速排序

快速排序有多種實(shí)現(xiàn)方式，這里主要給出兩種比較常用的，分別適合于不同的應(yīng)用場景。時間復(fù)雜度O(nlogn)，因?yàn)榻粨Q元素?zé)o法保證順序，是不穩(wěn)定的。
第一種實(shí)現(xiàn)，左右雙指針，交換逆序元素。
先選擇一個標(biāo)桿元素（通常是用第一個元素）。執(zhí)行：
從右向左遍歷找到第一個小于標(biāo)桿的值，從左向右遍歷找到第一個大于標(biāo)桿的值，這兩個位置的值是不滿足順序要求的，交換他們的值。
然后重復(fù)上面的過程。知道左右指針位置相同，將標(biāo)桿元素和指針交換，此時數(shù)組分為兩部分，然后遞歸進(jìn)行排序。
注意：在一些情況下，不需要我們進(jìn)行完全的排序，只需要將數(shù)組分為兩部分相對有序，如查找中位數(shù)，就是將數(shù)組分為長度相同的但是大小分開的兩個子數(shù)組，此時我們不需要完全排序，只需要執(zhí)行上面的過程，能夠降低時間復(fù)雜度。

  public static void quickSort(int[] arr, int left, int right) {
        if (left > right) {
            return;
        }
        int pivot = arr[left];
        int i = left;
        int j = right;
 
        while (i != j) {
            //先從右邊開始往左找，直到找到比pivot值小的數(shù)
            while (arr[j] >= pivot && i < j) {
                j--;
            }
            //先從左邊開始往左找，直到找到比pivot值大的數(shù)
            while (arr[i] <= pivot && i < j) {
                i++;
            }
            // 找到左邊比中軸大，右邊比中軸小的數(shù)，交換兩個數(shù)在數(shù)組中的位置
            if (i < j) {
                int temp = arr[j];
                arr[j] = arr[i];
                arr[i] = temp;
            }
        }
        // 將基準(zhǔn)數(shù)放到中間的位置（基準(zhǔn)數(shù)歸位）
        arr[left] = arr[i];
        arr[i] = pivot;
        
        // 遞歸，繼續(xù)向基準(zhǔn)的左右兩邊執(zhí)行和上面同樣的操作
        sort(arr, left, i - 1);
        sort(arr, i + 1, right);
 
    }

第二種實(shí)現(xiàn)：兩個伴隨指針
在數(shù)組排序時，采用第一種實(shí)現(xiàn)是可以的，但是如果是對鏈表排序時，無法用指針隨機(jī)訪問每個位置，只能從鏈表頭部從前往后遍歷，此時可以采用第二種實(shí)現(xiàn)。
先確定一個標(biāo)桿值，通常是第一個值。用兩個指針，指針i和指針j，指針j用于遍歷，指針i用于記錄小于標(biāo)桿值的邊界，當(dāng)j找到一個小于標(biāo)桿的值時，將i和j交換，并將i向右移動，這樣就能保證，遍歷結(jié)束時，i左邊都是小于標(biāo)桿值的，右邊都是大于的。

public static void quickSort(int[] nums,int begin, int end){
        if(begin>end||begin==end){
            return;
        }
        int i=begin+1;
        int j=begin+1;
        int target=nums[begin];
        while(j<=end){
            if(nums[j]<target){
                swap(nums,i,j);
                i++;
                j++;
            }else{
                j++;
            }
        }
        swap(nums,begin,--i);
        quickSort(nums,begin,i-1);
        quickSort(nums,i+1,end);
    }

6.歸并排序

這種排序方式采用分治的思想，將原數(shù)組先拆分成小數(shù)組，分別排序之后，再將相鄰的有序數(shù)組合并，還是比較好理解的。
一共拆分為logn層，每個層合并的過程O(n)，因此是O(nlogn)，可以保證穩(wěn)定。

public static int[] mergeSort(int[] nums, int begin, int end){
        if(begin>end){
            return new int[0];
        }
        if(begin==end){
            return new int[]{nums[begin]};
        }
        int m=begin+(end-begin)/2;
        int[] lres=mergeSort(nums,begin,m);//拆分為小數(shù)組，排序
        int[] rres=mergeSort(nums,m+1,end);
        //下面來進(jìn)行合并
        int[] res=new int[lres.length+rres.length];
        int i=0;
        int j=0;
        int index=0;
        while(i<lres.length&&j<rres.length){
            if(lres[i]<=rres[j]){
                res[index++]=lres[i++];
            }else{
                res[index++]=rres[j++];
            }
        }
        while(i<lres.length){
            res[index++]=lres[i++];
        }
        while(j<rres.length){
            res[index++]=rres[j++];
        }
        return res;
    }

9.基數(shù)排序

基數(shù)排序 是將整數(shù)按位數(shù)切割成不同的數(shù)字，然后按每個位數(shù)分別比較從而得到有序的序列。

public static void radixSort(int[] arr) {
        //得到數(shù)組中最大的數(shù)的位數(shù)
        int maxNum = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > maxNum) {
                maxNum = arr[i];
            }
        }
        //得到最大數(shù)是幾位數(shù)
        int maxLength = (maxNum + "").length();
 
        //定義一個二維數(shù)組，表示10個桶, 每個桶就是一個一維數(shù)組
        int[][] bucket = new int[10][arr.length];
        //每個桶存入了幾個數(shù)字
        int[] everyBucketNum = new int[10];
 
        // n* = 10 的原因是
        //123取出個位數(shù)字是 123 % 10，即 123 / 1 %10
        //123 取出十位數(shù)字是123 / 10 % 10;
        //123 去除百位數(shù)字是123 /100 % 10
        //以此類推
        for (int i = 0, n = 1; i < maxLength; i++, n *= 10) {
            for (int j = 0; j < arr.length; j++) {
                //取出每個元素的對應(yīng)位的值
                int digit = arr[j] / n % 10;
                //放入到對應(yīng)的桶中
                bucket[digit][everyBucketNum[digit]] = arr[j];
                everyBucketNum[digit]++;
            }
            //按照這個桶的順序(一維數(shù)組的下標(biāo)依次取出數(shù)據(jù)，放入原來數(shù)組)
            int index = 0;
            //遍歷每一桶，并將桶中是數(shù)據(jù)，放入到原數(shù)組
            for (int k = 0; k < everyBucketNum.length; k++) {
                if (everyBucketNum[k] != 0) {
                    for (int l = 0; l < everyBucketNum[k]; l++) {
                        arr[index++] = bucket[k][l];
                    }
                }
                //放回原數(shù)組后，需要將每個 everyBucketNum[k] = 0
                everyBucketNum[k] = 0;
 
            }
            System.out.println("第" + (i + 1) + "輪，對個位的排序處理 arr =" + Arrays.toString(arr));
 
        }
    }

7.堆排序

堆排序?qū)懫饋砜赡鼙容^麻煩一些，基于數(shù)組的堆排序還是稍微簡單的，如果是基于節(jié)點(diǎn)的就更麻煩了。
堆排序的主要操作包括建堆，調(diào)整等。
建堆是將原始數(shù)組建成一個大頂堆或者小頂堆，調(diào)整是在排序過程中，將最大值或最小值拿掉之后，剩下的元素進(jìn)行調(diào)整。
建堆的時間復(fù)雜度是O(nlogn)，排序的時間復(fù)雜度是O(nlogn)，無法保證穩(wěn)定性。

 //堆排序
    public static int[] heapSort(int[] nums) {
        buildHeap(nums);//建堆
        int size=nums.length;
       for(int i=0;i<nums.length-1;i++){
           swap(nums,0,size-1);//得到最大元素
           size--;
           adjust(nums,0,size);//調(diào)整堆
       }
       return nums;
    }
   //建一個大頂堆
    public static void buildHeap(int[] arr){
        for(int i=1;i<arr.length;i++){
            insert(arr,i);
        }
        System.out.println(Arrays.toString(arr));
    }
  //向堆中插入元素
    public static void insert(int[] arr,int index){
        int parent=0;
        while(index!=0){//根節(jié)點(diǎn)是沒有父節(jié)點(diǎn)的
            parent=(index-1)/2;
            if(arr[parent]<arr[index]){
                swap(arr,parent,index);
            }
            index=parent;
        }
    }
 //從index開始調(diào)整大頂堆
    public static void adjust(int[] arr, int index, int size){
        int left=index*2+1;
        int right=index*2+2;
        int max=index;
        while(left<size){
            if(arr[left]>arr[max]){
                max=left;
            }
            if(right<size&&arr[right]>arr[max]){
                max=right;
            }
            if(max!=index){
                swap(arr,max,index);
            }else{
                break;
            }
            index=max;
            left=index*2+1;
            right=index*2+2;
        }
    }

8.桶排序

桶排序的思想其實(shí)是用空間換時間，在重復(fù)元素比較多的時候用桶排序能夠比較快，首先找到數(shù)組中元素的范圍，在范圍內(nèi)設(shè)置不同的桶計(jì)數(shù)每個范圍內(nèi)數(shù)字的個數(shù)，然后基于桶來排序。
時間復(fù)雜度O(n)，通常的比較排序最優(yōu)的時間復(fù)雜度不超過O(nlogn)，但是桶排序可以，計(jì)數(shù)排序也可以。無法保證穩(wěn)定。

    public int[] bucketSort(int[] nums){
        if(nums==null||nums.length==0){
            return nums;
        }
        int low= Integer.MAX_VALUE;
        int high=Integer.MIN_VALUE;
        for(int i=0;i<nums.length;i++){
            low=Math.min(low,nums[i]);
            high=Math.max(high,nums[i]);
        }
        int n=high-low+1;
        int[] buckets=new int[n];//準(zhǔn)備了最多數(shù)量的桶，每個值對應(yīng)一個
        for(int t:nums){
            buckets[t-low]++;
        }
        int[] res=new int[nums.length];
        int index=0;
        for(int i=0;i<n;i++){
            for(int j=0;j<buckets[i];j++){
                res[index++]=low+i;
            }
        }
        return res;
    }