前沿

假如我想買一件衣服，我想在淘寶上去搜索纳决，搜索有發(fā)現(xiàn)有很多碰逸，該如何去選擇。其實(shí)我就想買一件便宜點(diǎn)阔加，衣服質(zhì)量還可以的饵史，想找信譽(yù)好的商家，如何做？
網(wǎng)上搜索一下該如何做约急，萬能的網(wǎng)絡(luò)給我出了個(gè)注意零远，可以通過排序，可以按照信用厌蔽、價(jià)格等進(jìn)行排序之后牵辣，優(yōu)先選擇合適的放在最前面
此時(shí)就需要引入需要學(xué)習(xí)的東西---排序

排序的概念

• 排序是將一批無序的記錄（數(shù)據(jù)）重新排列成按關(guān)鍵字有序的記錄序列的過程。
• 排序的穩(wěn)定性
• 內(nèi)排序和外排序

排序的分類：

• 冒泡排序
• 選擇排序
• 直接插入排序
• 希爾排序
• 堆排序排序
• 歸并排序
• 快速排序

冒泡排序

public static void bubbleSort(int []arr) {
      for(int i =1;i<arr.length;i++) { 
          for(int j=0;j<arr.length-i;j++) {
                if(arr[j]>arr[j+1]) {
                    int temp = arr[j];
                    arr[j]=arr[j+1];
                    arr[j+1]=temp;
                }
           }    
      }
}

選擇排序

public static void selectionSort(int[] arr){
       
       for (int i = 0; i < arr.length - 1; i++) {    
            int  min = i;
            for (int j = i + 1; j < arr.length; j++) {
                  if (arr[min] > arr[j]) {
                       min = j;
                  }
            }
            if (min != i) {
               int tmp = arr[min];
               arr[min] = arr[i];
               arr[i] = tmp;
            }             
      }

}

直接插入排序

public class InsertSort{
    
    public void insertSort(int[] array){
        for(int i=1;i<array.length;i++)//第0位獨(dú)自作為有序數(shù)列奴饮，從第1位開始向后遍歷
        {
            if(array[i]<array[i-1])//0~i-1位為有序纬向，若第i位小于i-1位，繼續(xù)尋位并插入戴卜，否則認(rèn)為0~i位也是有序的逾条，忽略此次循環(huán)，相當(dāng)于continue
            {
                int temp=array[i];//保存第i位的值
                int j = i - 1;
                while(j>=0 && temp<array[j])//從第i-1位向前遍歷并移位投剥，直至找到小于第i位值停止
                {
                    array[j+1]=array[j];
                    j--;
                }
                array[j+1]=temp;//插入第i位的值
            }
        } 
    }
    
    public static void printArray(int[] array) {
          for (int i = 0; i < array.length; i++) {
               System.out.print(array[i]);
               if (i != array.length - 1) {
                System.out.print(",");
               }
          }
     }
}

希爾排序

• code

public static void main(String[] args){
    int[] array={49,38,65,97,76,13,27,49,78,34,12,64,1};
        System.out.println("排序之前：");
        for(int i=0;i<array.length;i++){
            System.out.print(array[i]+" ");
        }
        //希爾排序
        int gap = array.length;
        while (true) {    
            gap /= 2;   //增量每次減半    
            for (int i = 0; i < gap; i++) {        
                for (int j = i + gap; j < array.length; j += gap) {//這個(gè)循環(huán)里其實(shí)就是一個(gè)插入排序            
                    int temp = array[j];            
                    int k = j - gap;            
                    while (k >= 0 && array[k] > temp) {                
                        array[k + gap] = array[k];                
                        k -= gap;            
                    }            
                    array[k + gap] = temp;        
                }    
            }    
            if (gap == 1)        
                break;
        }

        System.out.println();
        System.out.println("排序之后：");
        for(int i=0;i<array.length;i++){
            System.out.print(array[i]+" ");
        }
    }

堆排序排序

/**
    * 選擇排序-堆排序
    * @param array 待排序數(shù)組
    * @return 已排序數(shù)組
    */
    public static int[] heapSort(int[] array) {
        //這里元素的索引是從0開始的,所以最后一個(gè)非葉子結(jié)點(diǎn)array.length/2 - 1
        for (int i = array.length / 2 - 1; i >= 0; i--) {  
            adjustHeap(array, i, array.length);  //調(diào)整堆
        }
  
        // 上述邏輯师脂，建堆結(jié)束
        // 下面，開始排序邏輯
        for (int j = array.length - 1; j > 0; j--) {
            // 元素交換,作用是去掉大頂堆
            // 把大頂堆的根元素江锨，放到數(shù)組的最后吃警；換句話說，就是每一次的堆調(diào)整之后啄育，都會(huì)有一個(gè)元素到達(dá)自己的最終位置
            swap(array, 0, j);
            // 元素交換之后酌心，毫無疑問，最后一個(gè)元素?zé)o需再考慮排序問題了挑豌。
            // 接下來我們需要排序的安券，就是已經(jīng)去掉了部分元素的堆了，這也是為什么此方法放在循環(huán)里的原因
            // 而這里氓英，實(shí)質(zhì)上是自上而下侯勉，自左向右進(jìn)行調(diào)整的
            adjustHeap(array, 0, j);
        }
        return array;
    }
  
    /**
    * 整個(gè)堆排序最關(guān)鍵的地方
    * @param array 待組堆
    * @param i 起始結(jié)點(diǎn)
    * @param length 堆的長度
    */
    public static void adjustHeap(int[] array, int i, int length) {
        // 先把當(dāng)前元素取出來，因?yàn)楫?dāng)前元素可能要一直移動(dòng)
        int temp = array[i];
        for (int k = 2 * i + 1; k < length; k = 2 * k + 1) {  //2*i+1為左子樹i的左子樹(因?yàn)閕是從0開始的),2*k+1為k的左子樹
            // 讓k先指向子節(jié)點(diǎn)中最大的節(jié)點(diǎn)
            if (k + 1 < length && array[k] < array[k + 1]) {  //如果有右子樹,并且右子樹大于左子樹
                k++;
            }
            //如果發(fā)現(xiàn)結(jié)點(diǎn)(左右子結(jié)點(diǎn))大于根結(jié)點(diǎn)债蓝，則進(jìn)行值的交換
            if (array[k] > temp) {
                swap(array, i, k);
                // 如果子節(jié)點(diǎn)更換了壳鹤，那么，以子節(jié)點(diǎn)為根的子樹會(huì)受到影響,所以饰迹，循環(huán)對(duì)子節(jié)點(diǎn)所在的樹繼續(xù)進(jìn)行判斷
                    i  =  k;
                        } else {  //不用交換芳誓，直接終止循環(huán)
                break;
            }
        }
    }
  
    /**
    * 交換元素
    * @param arr
    * @param a 元素的下標(biāo)
    * @param b 元素的下標(biāo)
    */
    public static void swap(int[] arr, int a, int b) {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }

歸并排序

public class MergeSort {   
    public static int[] mergeSort(int[] nums, int l, int h) {
        if (l == h)
            return new int[] { nums[l] };
        
        int mid = l + (h - l) / 2;
        int[] leftArr = mergeSort(nums, l, mid); //左有序數(shù)組
        int[] rightArr = mergeSort(nums, mid + 1, h); //右有序數(shù)組
        int[] newNum = new int[leftArr.length + rightArr.length]; //新有序數(shù)組
        
        int m = 0, i = 0, j = 0; 
        while (i < leftArr.length && j < rightArr.length) {
            newNum[m++] = leftArr[i] < rightArr[j] ? leftArr[i++] : rightArr[j++];
        }
        while (i < leftArr.length)
            newNum[m++] = leftArr[i++];
        while (j < rightArr.length)
            newNum[m++] = rightArr[j++];
        return newNum;
    }
    public static void main(String[] args) {
        int[] nums = new int[] { 9, 8, 7, 6, 5, 4, 3, 2, 10 };
        int[] newNums = mergeSort(nums, 0, nums.length - 1);
        for (int x : newNums) {
            System.out.println(x);
        }
    }
}

快速排序

    public static int[] qsort(int arr[], int start, int end) {
        int pivot = arr[start];
        int i = start;
        int j = end;
        while (i < j) {
            while ((i < j) && (arr[j] > pivot)) {
                j--;
            }
            while ((i < j) && (arr[i] < pivot)) {
                i++;
            }
            if ((arr[i] == arr[j]) && (i < j)) {
                i++;
            } else {
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        if (i - 1 > start) arr = qsort(arr, start, i - 1);
        if (j + 1 < end) arr = qsort(arr, j + 1, end);
        return (arr);
    }

    public static void main(String[] args) {
        int arr[] = new int[]{3, 3, 3, 7, 9, 122344, 4656, 34, 34, 4656, 5, 6, 7, 8, 9, 343, 57765, 23, 12321};
        int len = arr.length - 1;
        arr = qsort(arr, 0, len);
        for (int i : arr) {
            System.out.print(i + "\t");
        }
    }


    /*//////////////////////////方式二////////////////////////////////*/
    更高效點(diǎn)的代碼：(TextendsComparable和SortUtil都是自己封裝的類，里面重寫和實(shí)現(xiàn)了compareTo和swap方法)
    public <TextendsComparable<?superT>>

    T[] quickSort(T[] targetArr, int start, int end) {
        inti = start + 1, j = end;
        T key = targetArr[start];
        SortUtil<T> sUtil = new SortUtil<T>();

        if (start == end) return (targetArr);


        /*從i++和j--兩個(gè)方向搜索不滿足條件的值并交換
         *
         *條件為：i++方向小于key啊鸭，j--方向大于key
         */
        while (true) {
            while (targetArr[j].compareTo(key) > 0) j--;
            while (targetArr[i].compareTo(key) < 0 && i < j) i++;
            if (i >= j) break;
            sUtil.swap(targetArr, i, j);
            if (targetArr[i] == key) {
                j--;
            } else {
                i++;
            }
        }

        /*關(guān)鍵數(shù)據(jù)放到‘中間’*/
        sUtil.swap(targetArr, start, j);

        if (start < i - 1) {
            this.quickSort(targetArr, start, i - 1);
        }
        if (j + 1 < end) {
            this.quickSort(targetArr, j + 1, end);
        }

        returntargetArr;
    }


    /*//////////////方式三：減少交換次數(shù)锹淌，提高效率/////////////////////*/
    private<TextendsComparable<?superT>>

    voidquickSort(T[] targetArr, intstart, intend) {
        inti = start, j = end;
        Tkey = targetArr[start];

        while (i < j) {
            /*按j--方向遍歷目標(biāo)數(shù)組，直到比key小的值為止*/
            while (j > i && targetArr[j].compareTo(key) >= 0) {
                j--;
            }
            if (i < j) {
                /*targetArr[i]已經(jīng)保存在key中赠制，可將后面的數(shù)填入*/
                targetArr[i] = targetArr[j];
                i++;
            }
            /*按i++方向遍歷目標(biāo)數(shù)組赂摆，直到比key大的值為止*/
            while (i < j && targetArr[i].compareTo(key) <= 0)
                /*此處一定要小于等于零挟憔，假設(shè)數(shù)組之內(nèi)有一億個(gè)1，0交替出現(xiàn)的話烟号，而key的值又恰巧是1的話绊谭，那么這個(gè)小于等于的作用就會(huì)使下面的if語句少執(zhí)行一億次。*/ {
                i++;
            }
            if (i < j) {
                /*targetArr[j]已保存在targetArr[i]中汪拥，可將前面的值填入*/
                targetArr[j] = targetArr[i];
                j--;
            }
        }
        /*此時(shí)i==j*/
        targetArr[i] = key;//應(yīng)加判斷

        /*遞歸調(diào)用达传，把key前面的完成排序*/
        this.quickSort(targetArr, start, i - 1);


        /*遞歸調(diào)用，把key后面的完成排序*/
        this.quickSort(targetArr, j + 1, end);
//兩個(gè)遞歸應(yīng)加判斷
    }