天天看點
傳回

資料庫--排序（直接插入排序 希爾排序 直接選擇排序 雙向選擇排序 堆排序 冒泡排序） 排序算法

 排序算法

1.直接插入排序

        每次從無序區間的第一和元素開始，依次與有序區間内的元素從後往前比較 。如果目前有序區間内的元素大于無序區間，則将有序區間該下标元素後移 插入 

public static void insertSort(int[] array) {
        //有序區間：[0,i)
        //無序區間：[i,array.length)
        for (int i = 1; i < array.length; i++) {//外層循環找的是無序區間
            int k = array[i];//k為無序區間第一個數
            int j;//有序區間最後一個數
            for (j = i - 1; j >= 0 && array[j] > k; j--) {//周遊的是有序區間
                array[j + 1] = array[j];
            }//從有序區間的最後一個元素開始比較
            // 如果大于無序區間元素 則将有序區間的元素後移 最後插入元素
            array[j + 1] = k;//因為最後循環退出的時候j--了 而真正要将無序區間插入的下标在後一個
        }
    }//直接插入排序

2.希爾排序

        希爾排序時直接插入排序的更新版，将數組元素分成（size/2)/((size/3)+1)各組 進行直接插入排序 然後重複上述分組過程 分組 插排 

public static void shellSort(int[] array) {
        int gap = array.length;
        while (true) {
            gap = (gap / 3) + 1;//希爾排序的分組數 也可以為gap/2
            insertSortWithGapa(array, gap);
            if (gap == 1) {
                break;
            }
        }
    }

    private static void insertSortWithGapa(int[] array, int gap) {
        for (int i = gap; i < array.length; i++) {//從第二組請開始依次周遊整個數組
            int k = array[i];
            int j;
            for (j = i - gap; j >= 0 && array[j] > k; j -= gap) {//将每一組的元素都與前面幾組相對應組的元素比較
                array[j + gap] = array[j];
            }
            array[j+gap] = k;//當循環退出的時候 j的下标減了依次gap
        }
    }//希爾排序

3.直接選擇排序

       整個數組看成一個無序區間  每次從無序區間中選擇最小（最大） 放入無序區間最前（最後）位置 ，一直到所有元素都排完

  1. 放在無序區間前面時 無序區間下标為[i,array,length)
  2. 放在無序區間後面時 無序區間下标為[0,array.length-i） 
public static void selectSortSmall(int[] array) {
        //無序下标：[i,array.length)
        for (int i = 0; i < array.length - 1; i++) {//外層循環 需要循環array.length-1次才可以有序
            int j;
            int minIndex = i;//設定每次的起始位置為無序序列的第一個位置
            for (j = minIndex; j < array.length; j++) {    //在無序區間查找最小元素
                if (array[j] < array[minIndex])
                    minIndex = j;
            }
            swap(array, minIndex, i);
        }
    }//直接選擇排序
    //選擇無序區間最小的元素放到無序區間第一個位置


    public static void selectSortBig(int[] array) {
        for (int i = 0; i < array.length - 1; i++) {
            // 無序區間: [0, array.length - i]
            int max = 0;
            for (int j = 1; j < array.length - i; j++) {  //無序區間
                if (array[j] > array[max]) {
                    max = j;
                }
            }
            int t = array[max];
            array[max] = array[array.length - i - 1];
            array[array.length - i - 1] = t;
        }
    }//直接選擇排序
    // 選擇無序區間最大的元素放到無序區間最後一個位置
    private static void swap(int[] array, int i, int j) {
        int t = array[i];
        array[i] = array[j];
        array[j] = t;
    }

4.雙向選擇排序

      直接從無序區間每次選出最大和最小元素 分别放在 無序區間最後和最前位置

      特殊情況：當數組中最大元素在第一個位置時 經過與min 交換 目前最大元素下标發生變更 需特殊處理 

public static void selectSortOP(int[] array) {
        int begin = 0;
        int end = array.length - 1;
        // [begin,end] 表示整個無序區間
        // 當無序區間内隻有一個數時停止排序
        while (begin <= end) {
            int minIndex = begin;
            int maxIndex = end;//無序區間的最大值和最小值 均設定為第一個元素
            for (int i = begin + 1; i <= maxIndex; i++) {
                if (array[i] < array[minIndex])
                    minIndex = i;
                if (array[i] > array[maxIndex])
                    maxIndex = i;
            }
            swap(array, minIndex, begin);
            if (maxIndex == begin) {
                maxIndex = minIndex;
            }
            swap(array, maxIndex, end);
            begin++;
            end--;
        }
    }//雙排

 5.堆排序

  1. 首先對數組進行建堆 建大堆 排升序 建小堆 排降序（我是用大堆 排升序）

  2. 每次讓目前樹頂元素與最後一個元素進行交換（每交換一次 目前樹内元素減1）

  3. 對新的樹頂進行向下調整 

public static void heapSort(int [] array){
        createHeap(array);//建大堆
        for(int i=0;i<array.length;i++) {
            swap(array, 0, array.length-1-i);
            //每次讓最大的元素與目前樹的最後一個節點交換
            //在對新的樹頂做向下調整 找大的結點
            shiftDownBig(array, array.length-i-1, 0);//目前無序期間的結點個數
        }
    }//堆排序

    private static void shiftDownBig(int[] array, int size, int index) {
        int left = 2 * index + 1;
        while (left < size)
        {
            int max = left;
            int right = left+1;
            if (right < size)
            {
                if (array[right] > array[left])
                {
                    max = right;
                }
            }
            if (array[index] < array[max])
            {
                swap(array,index,max);
                index = max;
                left = 2 * index + 1;
            }
            else
                break;
        }
    }//對指定下标元素做向下調整

    private static void createHeap(int[] array) {
        for(int j=(array.length-2)/2;j>=0;j--){
                shiftDownBig(array,array.length,j);
        }
    }//建大堆 從最後一個葉子結點的雙親結點開始 依次對其做向下調整

  6.冒泡排序

      在無序區間，通過相鄰數的比較，将最大的數冒泡到無序區間的最後，持續這個過程，直到數組整體有序 

public static void bubbleSort(int []array){
        for(int i=0;i<array.length;i++){
            for(int j=0;j<array.length-1-i;j++){
                if(array[j]>array[j+1])
                    swap(array,j,j+1);//交換
            }
        }
    }//冒泡排序

7.完整代碼  

import java.sql.SQLOutput;
import java.util.Arrays;
import java.util.Random;

public class Sort {
    public static void insertSort(int[] array) {
        //有序區間：[0,i)
        //無序區間：[i,array.length)
        for (int i = 1; i < array.length; i++) {//外層循環找的是無序區間
            int k = array[i];//k為無序區間第一個數
            int j;//有序區間最後一個數
            for (j = i - 1; j >= 0 && array[j] > k; j--) {//周遊的是有序區間
                array[j + 1] = array[j];
            }//從有序區間的最後一個元素開始比較
            // 如果大于無序區間元素 則将有序區間的元素後移 最後插入元素
            array[j + 1] = k;
        }
    }//直接插入排序

    public static void shellSort(int[] array) {
        int gap = array.length;
        while (true) {
            gap = (gap / 3) + 1;//希爾排序的分組數 也可以為gap/2
            insertSortWithGapa(array, gap);
            if (gap == 1) {
                break;
            }
        }
    }

    private static void insertSortWithGapa(int[] array, int gap) {
        for (int i = gap; i < array.length; i++) {//從第二組請開始依次周遊整個數組
            int k = array[i];
            int j;
            for (j = i - gap; j >= 0 && array[j] > k; j -= gap) {//将每一組的元素都與前面幾組相對應組的元素比較
                array[j + gap] = array[j];
            }
            array[j+gap] = k;//當循環退出的時候 j的下标減了依次gap
        }
    }//希爾排序

    private static void swap(int[] array, int i, int j) {
        int t = array[i];
        array[i] = array[j];
        array[j] = t;
    }

    public static void selectSortSmall(int[] array) {
        //無序下标：[i,array.length)
        for (int i = 0; i < array.length - 1; i++) {//外層循環 需要循環array.length-1次才可以有序
            int j;
            int minIndex = i;//設定每次的起始位置為無序序列的第一個位置
            for (j = minIndex; j < array.length; j++) {    //在無序區間查找最小元素
                if (array[j] < array[minIndex])
                    minIndex = j;
            }
            swap(array, minIndex, i);
        }
    }//直接選擇排序
    //選擇無序區間最小的元素放到無序區間第一個位置


    public static void selectSortBig(int[] array) {
        for (int i = 0; i < array.length - 1; i++) {
            // 無序區間: [0, array.length - i]
            int max = 0;
            for (int j = 1; j < array.length - i; j++) {  //無序區間
                if (array[j] > array[max]) {
                    max = j;
                }
            }
            int t = array[max];
            array[max] = array[array.length - i - 1];
            array[array.length - i - 1] = t;
        }
    }//直接選擇排序
    // 選擇無序區間最大的元素放到無序區間最後一個位置

    public static void selectSortOP(int[] array) {
        int begin = 0;
        int end = array.length - 1;
        // [begin,end] 表示整個無序區間
        // 當無序區間内隻有一個數時停止排序
        while (begin <= end) {
            int minIndex = begin;
            int maxIndex = end;//無序區間的最大值和最小值 均設定為第一個元素
            for (int i = begin + 1; i <= maxIndex; i++) {
                if (array[i] < array[minIndex])
                    minIndex = i;
                if (array[i] > array[maxIndex])
                    maxIndex = i;
            }
            swap(array, minIndex, begin);
            if (maxIndex == begin) {
                maxIndex = minIndex;
            }
            swap(array, maxIndex, end);
            begin++;
            end--;
        }
    }//雙排


    public static void heapSort(int [] array){
        createHeap(array);//建大堆
        for(int i=0;i<array.length;i++) {
            swap(array, 0, array.length-1-i);
            //每次讓最大的元素與目前樹的最後一個節點交換
            //在對新的樹頂做向下調整 找大的結點
            shiftDownBig(array, array.length-i-1, 0);//目前無序期間的結點個數
        }
    }//堆排序

    private static void shiftDownBig(int[] array, int size, int index) {
        int left = 2 * index + 1;
        while (left < size)
        {
            int max = left;
            int right = left+1;
            if (right < size)
            {
                if (array[right] > array[left])
                {
                    max = right;
                }
            }
            if (array[index] < array[max])
            {
                swap(array,index,max);
                index = max;
                left = 2 * index + 1;
            }
            else
                break;
        }
    }//對指定下标元素做向下調整

    private static void createHeap(int[] array) {
        for(int j=(array.length-2)/2;j>=0;j--){
                shiftDownBig(array,array.length,j);
        }
    }//建大堆 從最後一個葉子結點的雙親結點開始 依次對其做向下調整
    public static void bubbleSort(int []array){
        for(int i=0;i<array.length;i++){
            for(int j=0;j<array.length-1-i;j++){
                if(array[j]>array[j+1])
                    swap(array,j,j+1);
            }
        }
    }//冒泡排序
public static void testSpeed() {
    Random random = new Random(20190924);
    int[] a = new int[10 * 10000];
    for (int i = 0; i < 10 * 10000; i++) {
        a[i] = random.nextInt(10 * 10000);
    }
    long begin = System.nanoTime();
    heapSort(a);
    long end = System.nanoTime();
    double ms =(end - begin) * 1.0 / 1000 / 1000;
    System.out.printf("一共耗時：%5f毫秒%n", ms);
}

    public static void main(String[] args) {
        int []a={9,5,2,7,3,6,4,8,4,3,9};
        insertSort(a);
        System.out.println(Arrays.toString(a));
        System.out.println("b*========================");

        int []b=a.clone();
        bubbleSort(b);
        System.out.println(Arrays.toString(b));
        System.out.println("c*========================");

        int []c=a.clone();
        shellSort(c);
        System.out.println(Arrays.toString(c));
        System.out.println("d*========================");

        int []d=a.clone();
        heapSort(d);
        System.out.println(Arrays.toString(d));
        System.out.println("e*========================");

        int []e=a.clone();
        selectSortBig(e);
        System.out.println(Arrays.toString(e));
        System.out.println("f*========================");

        int []f=a.clone();
        selectSortSmall(f);
        System.out.println(Arrays.toString(f));
        System.out.println("g*========================");

        int []g=a.clone();
        selectSortOP(g);
        System.out.println(Arrays.toString(g));
    }
}
java 排序 插排 雙排 冒泡 希爾
上一篇: php怎樣讓圖檔排成一排,Ps裡怎麼給多張圖檔排版？
下一篇: Python爬蟲運用正規表達式

繼續閱讀