排序是一個非常經典的問題，它以一定的順序對一個數組（或一個列表）中的項進行重新排序（可以進行比較，例如整數，浮點數，字符串等）（增加，非遞減，遞減， 增加，詞典等）。
有許多不同的排序算法，每個都有其自身的優點和局限性

 

引用于 https://visualgo.net/zh

1 冒泡排序

這是來自于網上搜索的一張動態圖：

所謂冒泡排序，一句話描述就是最大的數向上冒泡

import JAVA.util.Arrays;
  //java 冒泡排序
  public void bubbleSortFunction1(){
    //待排序數組
    int arr[]={3,44,38,5,50,48};
    //記錄比較次數
    int count=0;
    //外層循環 取出每個數據
    for (int i = 0; i < arr.length-1; i++) {
      //內層循環，兩兩比較
      for (int j = 0; j < arr.length-1-i; j++) {
        //取出相鄰的數據比較
        if (arr[j]>arr[j+1]) {
          //將最大的數據放到右側
          //臨時變量記錄左側大的數據
          int temp=arr[j];
          //將右側小的數據賦值到左側
          arr[j]=arr[j+1];
          //將臨時變量保存的大的數據賦值到右側
          arr[j+1]=temp;
        }
        count++;
      }
    }
    System.out.println(Arrays.toString(arr));//[3, 5, 38, 44, 48, 50]
    System.out.println("一共比較了："+count+"次");//一共比較了：15次
  }

2 選擇排序

所謂選擇排序，一句話描述就是找出最小的，放到最左側

  public void selectSortFunction(){
    //待排序數組
    int arr[]={3,44,38,5,50,48};
    //記錄比較次數
    int count=0;
    for (int i = 0; i < arr.length-1; i++) {
      int index=i;//標記第一個為待比較的數
      for (int j = i+1; j < arr.length; j++) { //然后從后面遍歷與第一個數比較
        if (arr[j]<arr[index]) {  //如果小,就交換最小值
          index=j;//保存最小元素的下標
        }
        count++;
      }
      //找到最小值后，將最小的值放到第一的位置，進行下一遍循環
      int temp=arr[index];
      arr[index]=arr[i];
      arr[i]=temp;
    }
    System.out.println(Arrays.toString(arr));//[3, 5, 38, 44, 48, 50]
    System.out.println("一共比較了："+count+"次");//一共比較了：15次
  }

3、插入排序

  public void insertSortFunction(){
    //待排序數組
    int arr[]={3,44,38,5,50,48};
    //長度不減1，是因為要留多一個位置方便插入數
    for (int i = 0; i < arr.length; i++) {
      //記錄待插入的數
      int insertValue=arr[i];
      //找到待插入數的前一個數的下標
      int preInsertIndex=i-1;


      //因為是向前插入 所以 preInsertIndex 必須大于等于0
      //只有待插入數據 比 前一個數據小時 才進行位置遞減
      while (preInsertIndex>=0 && insertValue <arr[preInsertIndex]) {
        //將前一個數據向后移
        arr[preInsertIndex+1]=arr[preInsertIndex];
        //位置遞減
        preInsertIndex--;
      }
      //賦值插入的位置
      arr[preInsertIndex+1]=insertValue;


    }
    System.out.println(Arrays.toString(arr));//[3, 5, 38, 44, 48, 50]
  
  }

4、希爾排序

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

希爾排序的基本步驟，在此選擇增量gap=length/2，縮小增量繼續以gap = gap/2的方式。

  public void shellSortFunction(){
    //待排序數組
    int arr[]={3,44,38,5,50,48};
    //記錄比較次數
    int count=0;
    for (int gap=arr.length / 2; gap > 0; gap = gap / 2) {
      //將整個數組分為若干個子數組
      for (int i = gap; i < arr.length; i++) {
        //遍歷各組的元素
        for (int j = i - gap; j>=0; j=j-gap) {
          //交換元素
          if (arr[j]>arr[j+gap]) {
            int temp=arr[j];
            arr[j]=arr[j+gap];
            arr[j+gap]=temp;
          }
          count++;
        }
      }
    }
    System.out.println(Arrays.toString(arr));//[3, 5, 38, 44, 48, 50]
    System.out.println("一共比較了："+count+"次");//一共比較了：18次
  }