<dl id="3wz6h"></dl><li id="3wz6h"></li>

      1. <dl id="3wz6h"></dl>

      2. <dl id="3wz6h"><ins id="3wz6h"></ins></dl>

            <dl id="3wz6h"></dl>

            <dl id="3wz6h"><ins id="3wz6h"></ins></dl>
            1. 
              
              <output id="3wz6h"><ins id="3wz6h"><nobr id="3wz6h"></nobr></ins></output>

              <li id="3wz6h"><ins id="3wz6h"></ins></li>
              
              

            2. <output id="3wz6h"><ins id="3wz6h"><nobr id="3wz6h"></nobr></ins></output>
              首頁»Java WEB»一遍記住Java常用的八種排序算法與代碼實現

              一遍記住Java常用的八種排序算法與代碼實現

              來源:KaelQ 發布時間:2018-05-28 閱讀次數:

              1.直接插入排序

              經常碰到這樣一類排序問題:把新的數據插入到已經排好的數據列中。

              1. 將第一個數和第二個數排序,然后構成一個有序序列
              2. 將第三個數插入進去,構成一個新的有序序列。
              3. 對第四個數、第五個數……直到最后一個數,重復第二步。

              如何寫寫成代碼:

              1. 首先設定插入次數,即循環次數,for(int i=1;i<length;i++),1個數的那次不用插入。
              2. 設定插入數和得到已經排好序列的最后一個數的位數。insertNum和j=i-1。
              3. 從最后一個數開始向前循環,如果插入數小于當前數,就將當前數向后移動一位。
              4. 將當前數放置到空著的位置,即j+1。

              代碼實現如下:

              public void insertSort(int[] a){
                      int length=a.length;//數組長度,將這個提取出來是為了提高速度。
                      int insertNum;//要插入的數
                      for(int i=1;i<length;i++){//插入的次數
                          insertNum=a[i];//要插入的數
                          int j=i-1;//已經排序好的序列元素個數
                          while(j>=0&&a[j]>insertNum){//序列從后到前循環,將大于insertNum的數向后移動一格
                              a[j+1]=a[j];//元素移動一格
                              j--;
                          }
                          a[j+1]=insertNum;//將需要插入的數放在要插入的位置。
                      }
                  }
              

              2.希爾排序

              對于直接插入排序問題,數據量巨大時。

              1. 將數的個數設為n,取奇數k=n/2,將下標差值為k的書分為一組,構成有序序列。
              2. 再取k=k/2 ,將下標差值為k的書分為一組,構成有序序列。
              3. 重復第二步,直到k=1執行簡單插入排序。 

              如何寫成代碼:

              1. 首先確定分的組數。
              2. 然后對組中元素進行插入排序。
              3. 然后將length/2,重復1,2步,直到length=0為止。

              代碼實現如下:

              public  void sheelSort(int[] a){
                      int d  = a.length;
                      while (d!=0) {
                          d=d/2;
                          for (int x = 0; x < d; x++) {//分的組數
                              for (int i = x + d; i < a.length; i += d) {//組中的元素,從第二個數開始
                                  int j = i - d;//j為有序序列最后一位的位數
                                  int temp = a[i];//要插入的元素
                                  for (; j >= 0 && temp < a[j]; j -= d) {//從后往前遍歷。
                                      a[j + d] = a[j];//向后移動d位
                                  }
                                  a[j + d] = temp;
                              }
                          }
                      }
                  }
              

              3.簡單選擇排序

              常用于取序列中最大最小的幾個數時。

              (如果每次比較都交換,那么就是交換排序;如果每次比較完一個循環再交換,就是簡單選擇排序。)

              1. 遍歷整個序列,將最小的數放在最前面。
              2. 遍歷剩下的序列,將最小的數放在最前面。
              3. 重復第二步,直到只剩下一個數。 

              如何寫成代碼:

              1. 首先確定循環次數,并且記住當前數字和當前位置。
              2. 將當前位置后面所有的數與當前數字進行對比,小數賦值給key,并記住小數的位置。
              3. 比對完成后,將最小的值與第一個數的值交換。
              4. 重復2、3步。

              代碼實現如下:

                  public void selectSort(int[] a) {
                      int length = a.length;
                      for (int i = 0; i < length; i++) {//循環次數
                          int key = a[i];
                          int position=i;
                          for (int j = i + 1; j < length; j++) {//選出最小的值和位置
                              if (a[j] < key) {
                                  key = a[j];
                                  position = j;
                              }
                          }
                          a[position]=a[i];//交換位置
                          a[i]=key;
                      }
                  }
              

              4.堆排序

              對簡單選擇排序的優化。

              1. 將序列構建成大頂堆。
              2. 將根節點與最后一個節點交換,然后斷開最后一個節點。
              3. 重復第一、二步,直到所有節點斷開。 

              代碼實現如下:

              public  void heapSort(int[] a){
                      System.out.println("開始排序");
                      int arrayLength=a.length;
                      //循環建堆  
                      for(int i=0;i<arrayLength-1;i++){
                          //建堆  
              
                          buildMaxHeap(a,arrayLength-1-i);
                          //交換堆頂和最后一個元素  
                          swap(a,0,arrayLength-1-i);
                          System.out.println(Arrays.toString(a));
                      }
                  }
                  private  void swap(int[] data, int i, int j) {
                      // TODO Auto-generated method stub  
                      int tmp=data[i];
                      data[i]=data[j];
                      data[j]=tmp;
                  }
                  //對data數組從0到lastIndex建大頂堆  
                  private void buildMaxHeap(int[] data, int lastIndex) {
                      // TODO Auto-generated method stub  
                      //從lastIndex處節點(最后一個節點)的父節點開始  
                      for(int i=(lastIndex-1)/2;i>=0;i--){
                          //k保存正在判斷的節點  
                          int k=i;
                          //如果當前k節點的子節點存在  
                          while(k*2+1<=lastIndex){
                              //k節點的左子節點的索引  
                              int biggerIndex=2*k+1;
                              //如果biggerIndex小于lastIndex,即biggerIndex+1代表的k節點的右子節點存在  
                              if(biggerIndex<lastIndex){
                                  //若果右子節點的值較大  
                                  if(data[biggerIndex]<data[biggerIndex+1]){
                                      //biggerIndex總是記錄較大子節點的索引  
                                      biggerIndex++;
                                  }
                              }
                              //如果k節點的值小于其較大的子節點的值  
                              if(data[k]<data[biggerIndex]){
                                  //交換他們  
                                  swap(data,k,biggerIndex);
                                  //將biggerIndex賦予k,開始while循環的下一次循環,重新保證k節點的值大于其左右子節點的值  
                                  k=biggerIndex;
                              }else{
                                  break;
                              }
                          }
                      }
                  }
              

              5.冒泡排序

              一般不用。

              1. 將序列中所有元素兩兩比較,將最大的放在最后面。
              2. 將剩余序列中所有元素兩兩比較,將最大的放在最后面。
              3. 重復第二步,直到只剩下一個數。 

              如何寫成代碼:

              1. 設置循環次數。
              2. 設置開始比較的位數,和結束的位數。
              3. 兩兩比較,將最小的放到前面去。
              4. 重復2、3步,直到循環次數完畢。

              代碼實現如下:

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

              6.快速排序

              要求時間最快時。

              1. 選擇第一個數為p,小于p的數放在左邊,大于p的數放在右邊。
              2. 遞歸的將p左邊和右邊的數都按照第一步進行,直到不能遞歸。 

              代碼實現如下:

              public static void quickSort(int[] numbers, int start, int end) {   
                  if (start < end) {   
                      int base = numbers[start]; // 選定的基準值(第一個數值作為基準值)   
                      int temp; // 記錄臨時中間值   
                      int i = start, j = end;   
                      do {   
                          while ((numbers[i] < base) && (i < end))   
                              i++;   
                          while ((numbers[j] > base) && (j > start))   
                              j--;   
                          if (i <= j) {   
                              temp = numbers[i];   
                              numbers[i] = numbers[j];   
                              numbers[j] = temp;   
                              i++;   
                              j--;   
                          }   
                      } while (i <= j);   
                      if (start < j)   
                          quickSort(numbers, start, j);   
                      if (end > i)   
                          quickSort(numbers, i, end);   
                  }   
              }  
              

              7.歸并排序

              速度僅次于快排,內存少的時候使用,可以進行并行計算的時候使用。

              1. 選擇相鄰兩個數組成一個有序序列。
              2. 選擇相鄰的兩個有序序列組成一個有序序列。
              3. 重復第二步,直到全部組成一個有序序列。 

              代碼實現如下:

              public static void mergeSort(int[] numbers, int left, int right) {   
                  int t = 1;// 每組元素個數   
                  int size = right - left + 1;   
                  while (t < size) {   
                      int s = t;// 本次循環每組元素個數   
                      t = 2 * s;   
                      int i = left;   
                      while (i + (t - 1) < size) {   
                          merge(numbers, i, i + (s - 1), i + (t - 1));   
                          i += t;   
                      }   
                      if (i + (s - 1) < right)   
                          merge(numbers, i, i + (s - 1), right);   
                  }   
              }   
              private static void merge(int[] data, int p, int q, int r) {   
                  int[] B = new int[data.length];   
                  int s = p;   
                  int t = q + 1;   
                  int k = p;   
                  while (s <= q && t <= r) {   
                      if (data[s] <= data[t]) {   
                          B[k] = data[s];   
                          s++;   
                      } else {   
                          B[k] = data[t];   
                          t++;   
                      }   
                      k++;   
                  }   
                  if (s == q + 1)   
                      B[k++] = data[t++];   
                  else  
                      B[k++] = data[s++];   
                  for (int i = p; i <= r; i++)   
                      data[i] = B[i];   
              }  
              

              8.基數排序

              用于大量數,很長的數進行排序時。

              1. 將所有的數的個位數取出,按照個位數進行排序,構成一個序列。
              2. 將新構成的所有的數的十位數取出,按照十位數進行排序,構成一個序列。 

              代碼實現如下:

              public void sort(int[] array) {
                      //首先確定排序的趟數;     
                      int max = array[0];
                      for (int i = 1; i < array.length; i++) {
                          if (array[i] > max) {
                              max = array[i];
                          }
                      }
                      int time = 0;
                      //判斷位數;     
                      while (max > 0) {
                          max /= 10;
                          time++;
                      }
                      //建立10個隊列;     
                      List<ArrayList> queue = new ArrayList<ArrayList>();
                      for (int i = 0; i < 10; i++) {
                          ArrayList<Integer> queue1 = new ArrayList<Integer>();
                          queue.add(queue1);
                      }
                      //進行time次分配和收集;     
                      for (int i = 0; i < time; i++) {
                          //分配數組元素;     
                          for (int j = 0; j < array.length; j++) {
                              //得到數字的第time+1位數;   
                              int x = array[j] % (int) Math.pow(10, i + 1) / (int) Math.pow(10, i);
                              ArrayList<Integer> queue2 = queue.get(x);
                              queue2.add(array[j]);
                              queue.set(x, queue2);
                          }
                          int count = 0;//元素計數器;     
                          //收集隊列元素;     
                          for (int k = 0; k < 10; k++) {
                              while (queue.get(k).size() > 0) {
                                  ArrayList<Integer> queue3 = queue.get(k);
                                  array[count] = queue3.get(0);
                                  queue3.remove(0);
                                  count++;
                              }
                          }
                      }
                  }
              
              QQ群:WEB開發者官方群(515171538),驗證消息:10000
              微信群:加小編微信 849023636 邀請您加入,驗證消息:10000
              提示:更多精彩內容關注微信公眾號:全棧開發者中心(fsder-com)
              網友評論(共0條評論) 正在載入評論......
              理智評論文明上網,拒絕惡意謾罵 發表評論 / 共0條評論
              登錄會員中心
              云南十一选往期