Java實作排序算法(暫時七個)

文章目錄

- - 冒泡排序
  - 選擇排序
  - 插入排序
  - 希爾排序
  - 快速排序
  - 歸并排序
  - 基數排序

冒泡排序

【總結：就是比較相鄰元素，逆序則交換，每一趟循環可以找出最大的元素放在數組末尾】

基本思想：通過對待排序序列從前向後（從下标較小的元素開始），依次比較相鄰元素的值，若發現逆序則交換，使值較大的元素逐漸從前向後，就像水下的氣泡一樣逐漸向上冒

因為在排序的過程中，各元素不斷的接近自己的位置，如果一趟比較下來沒有進行過交換，就說明序列有序，是以在排序的過程中設定一個标志flag判斷元素是否進行過交換，進而減少不必要的比較

思路分析：

每次都和相鄰的元素進行比較
如果相鄰的元素存在逆序的情況【升序排序】，則進行交換

/**
 * @author wjq
 * @create 2021-05-21 8:30
 * 思想：在每一次的循環排序中，相鄰的兩個元素比較，将最大的找出來，将其放在最後，即每次循環都可以找到一個最大的元素
 */
public class BubbleSort {
    public static void main(String[] args) {
        int arr[] = {3, 9, -1, 10, -2};
        System.out.println("排序前:" + Arrays.toString(arr));
        int temp;
        for (int i = 0; i < arr.length - 1; i++) {//一共是n-1次循環
            for (int j = 0; j < arr.length - i - 1; j++) {//每次排序的元素是n-1  n-1-1  n-1-1-1...
                if (arr[j] > arr[j + 1]) {//當出現逆序則交換
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
        System.out.println("排序後:" + Arrays.toString(arr));
    }
}

小結

一共進行n-1次的循環
在每一次的循環中，元素都會減少
如果在某一次循環中，發先沒有交換元素，此時可以結束冒泡排序（優化）

//優化
   @Test
    public void better() {
       int arr[] = {-1, 3, 9, 20, 10};
       System.out.println("排序前:" + Arrays.toString(arr));
       int temp;
       boolean flag = true;//用于判斷是否進入了交換元素
       for (int i = 0; i < arr.length - 1; i++) {//一共是n-1次循環
           for (int j = 0; j < arr.length - i - 1; j++) {//每次排序的元素是n-1  n-1-1  n-1-1-1...
               if (arr[j] > arr[j + 1]) {//當出現逆序則交換
                   flag = false;
                   temp = arr[j];
                   arr[j] = arr[j + 1];
                   arr[j + 1] = temp;
               }
           }
           if (flag) {
               break;//沒有進入交換，即此時有序，直接跳出循環
           }else {
               flag = true;//再将标志改為true，用于下一趟循環的判斷
           }
           System.out.println("第" + (i + 1) + "次排序後:" + Arrays.toString(arr));
       }
//       System.out.println("排序後:" + Arrays.toString(arr));
    }

對80000個資料進行排序的耗時

//耗時
    @Test
    public void time() {
        int[] arr = new int[80000];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int)(Math.random() * 80000);//[0,80000)
        }

//        long start = System.currentTimeMillis();
//        bubbleSort(arr);
//        long end = System.currentTimeMillis();
//        System.out.println("耗時為：" + (end - start));


        long start1 = System.currentTimeMillis();
        bubbleSort1(arr);
        long end1 = System.currentTimeMillis();
        System.out.println("優化後的耗時為：" + (end1 - start1));//因為随機性比較大，優化不明顯，優化是對相對有序的數組來說比較明顯
    }

Java實作排序算法(暫時七個)

選擇排序

選擇排序也屬于内部排序，是從欲排序的資料中，按指定的規則選出某一進制素，再依規定交換位置後達到排序的目的

思路分析：

先指定每一次排序的第一個元素為最小元素
與後面元素進行比較，如果有更小的則将更小的标記為最小元素
經過一輪，可知此輪的最小元素
将最小元素與a[0]進行交換
即可完成一輪的排序

@Test
    public static void selectSort(int arr[]) {
//        arr = new int[]{101, 34, 119, 1};
        for (int i = 0; i < arr.length - 1; i++) {//總共循環的次數
            int min = arr[i];//先預設将第一個元素看成最小的，進行比較
            int minIndex = i;
            for (int j = 1 + i; j < arr.length; j++) {//求出真正的最小值
                if (min > arr[j]) {//如果最小值較大，則交換
                    min = arr[j];
                    minIndex = j;
                }
            }
            if (minIndex != i) {//如果最小值與交換的值不在同一位置
                arr[minIndex] = arr[i];//實作交換，arr[minIndex]就相當于temp
                arr[i] = min;
            }
        }
//        System.out.println("排序後：" + Arrays.toString(arr));
    }

對80000個資料排序的耗時

@Test
public static void time() {
    int[] arr = new int[80000];
    for (int i = 0; i < arr.length; i++) {
        arr[i] = (int)(Math.random() * 80000);//[0,80000)
    }

    long start = System.currentTimeMillis();
    selectSort(arr);
    long end = System.currentTimeMillis();
    System.out.println("耗時為：" + (end - start));
}

Java實作排序算法(暫時七個)

插入排序

屬于内部排序，是對欲排序的元素以插入的方式找尋該元素的适當位置

思路分析：

第一個元素預設為有序的，從第二個元素開始
先定位待插入的元素以及要插入的位置
當下标越界以及待插入的元素比其前面的元素大等的時候跳出循環
1. 将大的元素後移
2. 待插入元素的下标前移
将之前儲存的待插入的元素放入跳出循環後的位置+1的地方

public static void insertSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {//第一個元素是有序的
            int insetVal  = arr[i + 1];//待插入的元素，從第二個元素開始
            int insertIndex = i;//插入的位置，在其位置的前面
            while (insertIndex >= 0 && insetVal < arr[insertIndex]) {//當下标越界(-1)或者待插入的元素大于等于其之前的元素，跳出循環
                arr[insertIndex + 1] = arr[insertIndex];//将有序的元素後移
                insertIndex--;//代插入的元素的下标前移
            }
            if (insertIndex + 1 != (i + 1)) {//當要插入的位置與插入元素的位置不同時，才插入
                arr[insertIndex + 1] = insetVal;//将待插入的元素插入，并且實作跳出循環
            }
        }
//        System.out.println("排序後：" + Arrays.toString(arr));
    }

對80000個資料排序的耗時

@Test
public static void time() {
    long start = System.currentTimeMillis();
    int[] arr = new int[80000];
    for (int i = 0; i < arr.length; i++) {
        arr[i] = (int) (Math.random() * 80000);
    }
    insertSort(arr);
    long end = System.currentTimeMillis();
    System.out.println("消耗的時間：" + (end - start));
}

Java實作排序算法(暫時七個)

希爾排序

分為交換法（效率低）和移動法（效率高）

也是一種插入排序，它是簡單插入排序經過改進之後的一個更高效的版本，也稱為縮小增量排序

對每組使用直接插入排序算法排序，随着增量逐漸減少，每組包含的關鍵字越來越多，當增量減至1時，整個檔案恰好被分成1組，算法終止

交換法

未優化的（交換法）

@Test    
public static void shellSort(int arr[]) {        
int temp = 0;        
for (int gap = arr.length / 2; gap > 0; gap /= 2) {//本質是增量縮減，gap表示步長，步長每次/2，            
    for (int i = gap; i < arr.length; i++) {//對每一次步長的循環次數                
	    for (int j = i - gap ; j >= 0; j -= gap) {//在gap長的情況下交換的元素                    
		    if (arr[j] > arr[j + gap]) {                        
			    temp = arr[j];                        
			    arr[j] = arr[j + gap];                        
			    arr[j + gap] = temp;                    
		    }                
	    }            
    }        
}
//        System.out.println("排序後：" + Arrays.toString(arr));   
 }

對80000個資料進行排序的時間

Java實作排序算法(暫時七個)

移動法

優化後

public static void shellSort1(int arr[]) {//移動法
        for (int gap = arr.length / 2; gap > 0; gap /= 2) {//表示gap增量
            for (int i = gap; i < arr.length; i++) {//此時開始用插入排序
                int insertIndex = (i - gap);
                int insertVal = arr[i];
                while (insertIndex >= 0 && insertVal < arr[insertIndex]) {
                    arr[insertIndex + gap] = arr[insertIndex];
                    insertIndex -= gap;
                }
                arr[insertIndex + gap] = insertVal;//為什麼要加gap，因為上面是由于多減了一個gap，越界跳出循環，這裡應該加上
            }
        }
//        System.out.println("移動法排序後：" + Arrays.toString(arr));
    }

對80000個資料進行排序

@Test
    public static void time() {
        long start = System.currentTimeMillis();
        int[] arr = new int[80000];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) (Math.random() * 80000);
        }
//        shellSort(arr);
        shellSort1(arr);

        long end = System.currentTimeMillis();
        System.out.println("消耗的時間：" + (end - start));
    }

Java實作排序算法(暫時七個)

對8000000

Java實作排序算法(暫時七個)

快速排序

是對冒泡排序的一種改進，将數字分成左右兩部分，一部分比另一部分小，然後左右分别遞歸排序，以達到整個數組有序

public static void quickSort(int[] arr, int left, int right) {
    int l = left;//左下标
    int r = right;//右下biao
    int mid = arr[(left + right) / 2];//中間元素
    while (l < r) {
        while (arr[l] < mid) {
            l++;
        }
        while (arr[r] > mid) {
            r--;
        }
        //交換元素
        int temp = arr[l];
        arr[l] = arr[r];
        arr[r] = temp;
        //當出現相同元素時，需要此步驟，否則會是死循環
        if (arr[l] == mid) {
            r--;
        }
        if (arr[r] == mid) {
            l++;
        }
    }
    //此步驟也是避免死循環
    if (l == r) {
        l++;
        r--;
    }
    //左邊遞歸
    if (left < r) {
        quickSort(arr, left, r);
    }
    //右邊遞歸
    if (right > l) {
        quickSort(arr, l, right);
    }
}

對80000個資料排序

@Test
public static void time() {
    long start = System.currentTimeMillis();
    int[] arr = new int[80000];
    for (int i = 0; i < arr.length; i++) {
        arr[i] = (int) (Math.random() * 80000);
    }
    quickSort(arr, 0, arr.length - 1);
    long end = System.currentTimeMillis();
    System.out.println("消耗的時間：" + (end - start));
}

Java實作排序算法(暫時七個)

對8000000

Java實作排序算法(暫時七個)

歸并排序

利用歸并思想實作的排序，該算法采用經典的分治政策（分：分成小子產品遞歸求解；治：分段得到的各答案“修補”在一起，即分而治之）

public class MergeSort {
    public static void main(String[] args) {
        int[] arr = {9, 8, 3, 6, 5, 9, 1, 2, 3};
        mergeSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void mergeSort(int[] arr){
        int[] temp = new int[arr.length];
        mergeSort(arr, 0, arr.length - 1, temp);
    }

    //遞歸分解+合并
    private static void mergeSort(int[] arr, int left, int right, int[] temp) {
        if (left < right) {
            int mid = (left + right) / 2;
            //左邊遞歸
            mergeSort(arr, left, mid, temp);
            //右邊遞歸
            mergeSort(arr, mid + 1, right, temp);
            merge(arr, left, mid, right, temp);
        }
    }

    //合并
    private static void merge(int[] arr, int left, int mid, int right, int[] temp) {
        //定義左邊有序數組的第一個索引
        int i = left;
        //定義右邊有序數組的第一個索引
        int j = mid + 1;
        //定義臨時數組的索引
        int t = 0;
        //将左右數組進行比較，将較小的元素放入到臨時數組中
        while (i <= mid && j <= right) {
            if (arr[i] <= arr[j]) {//将左邊較小的元素放入臨時數組
                temp[t++] = arr[i++];
            }else {
                temp[t++] = arr[j++];//将右邊較小的元素放入臨時數組
            }
        }
        //将左邊或者右邊剩餘的元素放入臨時數組
        while (i <= mid) {//左邊還有剩餘元素
            temp[t++] = arr[i++];
        }
        while (j <= right) {//右邊還有剩餘元素
            temp[t++] = arr[j++];
        }
        //将temp數組的所有元素copy到arr
        t = 0;//因為每次copy的元素個數不一樣
        while (left <= right) {
            arr[left++] = temp[t++];
        }
    }
}

對80000個資料排序

@Test
    public static void time() {
        long start = System.currentTimeMillis();
        int[] arr = new int[80000];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) (Math.random() * 80000);
        }
//        shellSort(arr);
        mergeSort(arr);

        long end = System.currentTimeMillis();
        System.out.println("消耗的時間：" + (end - start));
    }

Java實作排序算法(暫時七個)

對8000000

Java實作排序算法(暫時七個)

基數排序

屬于“配置設定式排序”，又稱“桶子法”，通過鍵值的各個位的值，将要排序的元素配置設定到某些“桶”中，達到排序的作用

屬于穩定排序

是桶排序的擴充

思路分析：

算出所有數組的個位值，放入對應的桶中，再按序存入數組中
再算出所有數組的十位值，放入對應的桶中，再按序存入數組中
再算出所有數組的百位值，放入對應的桶中，再按序存入數組中
…

//對于基數排序而言是通過一個二維數組展現的用空間換時間
    //一共有10個桶用來存放0-9，每個桶又有一個一維數組，用來存放對于的資料
    public static void radixSort(int[] arr) {
        //得到數組中最大的數
         int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
        }
        //循環的次數
        int maxLength = (max + "").length();

        //一維表示10個桶，每個桶的最多元素是數組的長度，極端情況下所有元素都在一個桶中
        int[][] bucket = new int[10][arr.length];
        //指具體的哪個桶，在二維數組中指元素放入具體個桶的哪個位置，預設從0開始
        int[] realEle = new int[10];
        for (int k = 0, n = 1; k < maxLength; k++, n *= 10) {
            //将數組中的元素計算完之後放入桶的過程
            for (int i = 0; i < arr.length; i++) {
                //計算每個元素的各十百千位的值
                int value = arr[i] / n % 10;
//            int value1 = arr[i] / 1 % 10;//各位
//            int value2 = arr[i] / 10 % 10;//十位
//            int value3 = arr[i] / 100 % 10;//百位
                bucket[value][realEle[value]++] = arr[i];
            }
            //定義每個桶中元素的資料，即指向每個元素的索引
            int index = 0;
            //從桶裡面按序取出元素，放入數組中
            for (int i = 0; i < bucket.length; i++) {//循環每一個桶
                if (realEle[i] != 0) {//如果桶中有元素
                    for (int j = 0; j < realEle[i]; j++) {
                        arr[index++] = bucket[i][j];
                    }
                }
                realEle[i] = 0;
            }
        }
    }

對80000個資料排序

@Test
    public static void time() {
        long start = System.currentTimeMillis();
        int[] arr = new int[80000];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) (Math.random() * 80000);
        }
        radixSort(arr);

        long end = System.currentTimeMillis();
        System.out.println("消耗的時間：" + (end - start));
    }

Java實作排序算法(暫時七個)

對8000000

Java實作排序算法(暫時七個)

Java實作排序算法(暫時七個)

文章目錄

冒泡排序

選擇排序

插入排序

希爾排序

快速排序

歸并排序

基數排序

繼續閱讀

Codeforces 1417 D. Make Them Equal(思維+構造)

查找算法之二分查找查找算法之二分查找

查找算法學習之二分查找（Python版本）——BinarySearch

CQ V1.0分詞bates(基于雙數組tire樹)—應該是目前最快的中文分詞算法

Command Network(POJ 3164)---定根最小樹形圖模闆題題目描述輸入格式輸出格式輸入樣例輸出樣例分析源程式

開源低帶寬語音編解碼器

241 Different Ways to Add Parentheses（C代碼版）

【趨高機器視覺】機器視覺技術原了解析及解決方案

CSMA/CD1． CSMA/CD的概述2． CSMA 的工作原理3． CSMA/CD控制規程及特點4． CSMA/CD協定5． CSMA/CD的優點6．結束語

極大似然法(ML)與最大期望法(EM)

C++ 第十五周報告1--《冒泡法排序》

筆試面試題目：滑動視窗(二)

資料結構與算法（27）——排序（二）

Dijkstra--簡易版（最短路徑）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

hdu7108哈希