Présentation de sept méthodes de tri couramment utilisées en Java

Cet article présente principalement 7 méthodes de tri couramment utilisées en Java à travers des exemples. Les amis dans le besoin peuvent se référer au

Tri par insertion directe

<code class="language-java hljs ">import java.util.HashMap; 
public class InsertSort { 
 private static int contrastCount = 0;//对比次数 
 private static int swapCount = 0;//交换次数 
 public static void main(String[] args) { 
  System.out.println("直接插入排序：\n 假设前面的序列都已经排序好了，把后面未排序的数往已排好序的序列内插入,时间复杂度O(n^2),空间复杂度O(1)，稳定排序"); 
  HashMap<integer,integer> hashMap = new HashMap<integer,integer>(); 
  init(hashMap);//初始化  
  System.out.println("初始序列为："); 
  print(hashMap, 0);//打印 
  insert(hashMap);//排序 
 } 
 /** 
  * 初始化函数 
  * @param hashMap 
  */ 
 private static void init(HashMap<integer, integer=""> hashMap) { 
  hashMap.put(0, null);//第一位置空 
  hashMap.put(1, 0); 
  hashMap.put(2, 5); 
  hashMap.put(3, 11); 
  hashMap.put(4, 12); 
  hashMap.put(5, 13); 
  hashMap.put(6, 4); 
  hashMap.put(7, 1); 
  hashMap.put(8, 5); 
  hashMap.put(9, 8); 
  hashMap.put(10, 6); 
  hashMap.put(11, 4); 
  hashMap.put(12, 8);  
 } 
 /** 
  * 进行插入排序 
  * @param hashMap 待排序的表 
  */ 
 private static void insert(HashMap<integer, integer=""> hashMap){ 
  System.out.println("开始插入排序："); 
  int i,j; 
  //排序开始时间 
  long start = System.currentTimeMillis();  
  for(i=2; i<hashmap.size(); author="" code="" contrastcount="0;//对比次数" count="1;//只为统计执行次数" d="1,时间复杂度o(n^1.3),空间复杂度o(1)，不稳定排序");" end="System.currentTimeMillis();" h2="" hashmap="" hhf="" hillsort="" i="1;" id="希尔排序" import="" int="" integer="" j="" long="" n="" param="" pre="" private="" public="" start="System.currentTimeMillis();" static="" swapcount="0;//交换次数" void="" x="1;x<=d;x++){//一共有d组"></hashmap.size();></integer,></integer,></integer,integer></integer,integer></code>

Tri à bulles

<code class="language-java hljs "><code class="language-java hljs ">import java.util.HashMap; 
/** 
 * 冒泡排序 
 * @author HHF 
 * 2014年3月19日 
 */ 
public class BubbleSort { 
 private static int contrastCount = 0;//对比次数 
 private static int swapCount = 0;//交换次数 
 public static void main(String[] args) { 
  System.out.println("冒泡排序：\n 第一轮使最大值沉淀到最底下，采用从头开始的两两比较的办法，如果i大于i++则交换，下一次有从第一个开始循环，比较次数减一，然后依次重复即可," 
    + "\n 如果一次比较为发生任何交换，则可提前终止，时间复杂度O(n^2),空间复杂度O(1)，稳定排序");   
  HashMap<integer,integer> hashMap = new HashMap<integer,integer>(); 
  init(hashMap);//初始化  
  System.out.println("初始序列为："); 
  print(hashMap, 0);//打印 
  bubble(hashMap);//排序 
 } 
 /** 
  * 初始化函数 
  * @param hashMap 
  */ 
 private static void init(HashMap<integer, integer=""> hashMap) { 
  hashMap.put(0, null);//第一位置空 
  hashMap.put(1, 10); 
  hashMap.put(2, 5); 
  hashMap.put(3, 11); 
  hashMap.put(4, 12); 
  hashMap.put(5, 13); 
  hashMap.put(6, 4); 
  hashMap.put(7, 1); 
  hashMap.put(8, 5); 
  hashMap.put(9, 8); 
  hashMap.put(10, 6); 
  hashMap.put(11, 4); 
  hashMap.put(12, 8);  
 } 
 /** 
  * 进行冒泡排序 
  * @param hashMap 待排序的表 
  */ 
 private static void bubble(HashMap<integer, integer=""> hashMap){ 
  System.out.println("开始冒泡排序："); 
  //排序开始时间 
  long start = System.currentTimeMillis(); 
  boolean swap = false;//是否发生交换 
  int count = 1;//只为了计数 
  for(int i=1; i<hashmap.size(); int="" j="1;" swap="false;">hashMap.get(j+1)){//需要发生交换j 和 j+1 
     hashMap.put(0, hashMap.get(j)); 
     hashMap.put(j, hashMap.get(j+1)); 
     hashMap.put(j+1, hashMap.get(0)); 
     swap = true; 
     contrastCount++;//发生一次对比 
     swapCount++;//发生一次交换 
     swapCount++;//发生一次交换 
     swapCount++;//发生一次交换 
    } 
    contrastCount++;//跳出if还有一次对比 
   } 
   print(hashMap, count++); 
   if(!swap) 
    break; 
  }  
  //排序结束时间 
  long end = System.currentTimeMillis(); 
  System.out.println("结果为："); 
  print(hashMap, 0);//输出排序结束的序列 
  hashMap.clear();//清空 
  System.out.print("一共发生了 "+contrastCount+" 次对比\t"); 
  System.out.print("一共发生了 "+swapCount+" 次交换\t"); 
  System.out.println("执行时间为"+(end-start)+"毫秒"); 
 } 
 /** 
  * 打印已排序好的元素 
  * @param hashMap 已排序的表 
  * @param j 第j趟排序 
  */ 
 private static void print(HashMap<integer, integer=""> hashMap, int j){ 
  if(j != 0) 
   System.out.print("第 "+j+" 趟：\t"); 
  for(int i=1; i<hashmap.size(); code=""></hashmap.size();></integer,></hashmap.size();></integer,></integer,></integer,integer></integer,integer></code></code>

Tri rapide

<code class="language-java hljs "><code class="language-java hljs "><code class="language-java hljs ">import java.util.HashMap; 
public class QuickSort { 
 private static int contrastCount = 0;//对比次数 
 private static int swapCount = 0;//交换次数 
 public static void main(String[] args) { 
  System.out.println("快速排序：\n 任取一个数作为分界线，比它小的放到左边，比它大的放在其右边，然后分别对左右进行递归,时间复杂度O(nLgn),空间复杂度O(n)，不稳定排序");  
  HashMap<integer,integer> hashMap = new HashMap<integer,integer>(); 
  init(hashMap);//初始化  
  System.out.println("初始序列为："); 
  print(hashMap, 0, 0);//打印 
  System.out.println("开始快速排序：");  
  //排序开始时间 
  long start = System.currentTimeMillis(); 
  quick(hashMap, 1, hashMap.size()-1);//排序 
  //排序结束时间 
  long end = System.currentTimeMillis(); 
  System.out.println("结果为："); 
  print(hashMap, 0, 0);//输出排序结束的序列 
  hashMap.clear();//清空 
  System.out.print("一共发生了 "+contrastCount+" 次对比\t"); 
  System.out.print("一共发生了 "+swapCount+" 次交换\t"); 
  System.out.println("执行时间为"+(end-start)+"毫秒"); 
  System.out.println("(注：此输出序列为代码执行过程的序列， 即先左边递归 再 右边递归， 而教科书上的递归序列往往是左右同时进行的结果，特此说明)"); 
 } 
 /** 
  * 初始化函数 
  * @param hashMap 
  */ 
 private static void init(HashMap<integer, integer=""> hashMap) { 
  hashMap.put(0, null);//第一位置空 
  hashMap.put(1, 10); 
  hashMap.put(2, 5); 
  hashMap.put(3, 11); 
  hashMap.put(4, 12); 
  hashMap.put(5, 13); 
  hashMap.put(6, 4); 
  hashMap.put(7, 1); 
  hashMap.put(8, 5); 
  hashMap.put(9, 8); 
  hashMap.put(10, 6); 
  hashMap.put(11, 4); 
  hashMap.put(12, 8);  
 } 
 /** 
  * 进行快速排序 
  * @param hashMap 待排序的表 
  * @param low 
  * @param high 
  */ 
 static int count = 1; 
 private static void quick(HashMap<integer, integer=""> hashMap, int low, int high){ 
  if(low<high){ hashmap="" high="" int="" integer="" k="quickOnePass(hashMap," low="" param="" private="" static=""> hashMap, int low, int high){  
  hashMap.put(0, hashMap.get(low));//选择一个分界值 此时第low位元素内的值已经无所谓被覆盖了 
  swapCount++;//发生一次交换 
  while(low<high){ high="">hashMap.get(low)){//开始从左往右走 直到有不对的数据 或者 到头了   
    low++; 
    contrastCount++;//发生一次对比 
   } 
   if(low<high){ hashmap="" integer="" j="" k="" param="" private="" return="" static="" void=""> hashMap, int j, int k){ 
  if(j != 0) 
   System.out.print("第 "+j+" 趟：(分界线为"+k+")\t"); 
  for(int i=1; i<hashmap.size(); code=""></hashmap.size();></high){></high){></high){></integer,></integer,></integer,integer></integer,integer></code></code></code>

DirectTri par sélection

<code class="language-java hljs "><code class="language-java hljs "><code class="language-java hljs "><code class="language-java hljs ">import java.util.HashMap; 
public class SelectionSort { 
 private static int contrastCount = 0;//对比次数 
 private static int swapCount = 0;//交换次数 
 public static void main(String[] args) { 
  System.out.println("选择排序：\n 每次选择最小的，然后与对应的位置处元素交换,时间复杂度O(n^2),空间复杂度O(1)，不稳定排序");   
  HashMap<integer,integer> hashMap = new HashMap<integer,integer>(); 
  init(hashMap);//初始化  
  System.out.println("初始序列为："); 
  print(hashMap, 0, 0);//打印 
  select(hashMap);//排序 
 } 
 /** 
  * 初始化函数 
  * @param hashMap 
  */ 
 private static void init(HashMap<integer, integer=""> hashMap) { 
  hashMap.put(0, null);//第一位置空 
  hashMap.put(1, 10); 
  hashMap.put(2, 5); 
  hashMap.put(3, 11); 
  hashMap.put(4, 12); 
  hashMap.put(5, 13); 
  hashMap.put(6, 4); 
  hashMap.put(7, 1); 
  hashMap.put(8, 5); 
  hashMap.put(9, 8); 
  hashMap.put(10, 6); 
  hashMap.put(11, 4); 
  hashMap.put(12, 8);  
 } 
 /** 
  * 进行选择排序 
  * @param hashMap 待排序的表 
  */ 
 private static void select(HashMap<integer, integer=""> hashMap){ 
  System.out.println("开始选择排序：");  
  //排序开始时间 
  long start = System.currentTimeMillis(); 
  int count = 1;//只为统计执行次数 
  for(int i=hashMap.size()-1; i>1; i--){//需要循环查询的次数 最后一个元素不用考虑 
   int k = i;//记录本次查找序列最大值的下标 初始为该数应该要放的位置 
   for(int j=1; j<i; code="" i="1;" int="" j=""></i;></integer,></integer,></integer,integer></integer,integer></code></code></code></code>

Tri par tas

<code class="language-java hljs "><code class="language-java hljs "><code class="language-java hljs "><code class="language-java hljs "><code class="language-java hljs ">import java.util.HashMap; 
public class HeapSort { 
 private static int contrastCount = 0;//对比次数 
 private static int swapCount = 0;//交换次数 
 private static int printCount = 1;//执行打印次数 
 public static void main(String[] args) { 
  System.out.println("堆排序：\n 首先建立一个堆（方法是首先把序列排成二叉树，然后从下往上，从右往左使得每一个小子树中的父节点大于子节点，然后从上往下，从左往右记录堆入序列）," 
    + "\n 然后把堆的根节点和最底下 的孩子节点交换，整理堆，再重复交换，整理，时间复杂度O(nlgn),空间复杂度O(1)，不稳定排序");   
  HashMap<integer,integer> hashMap = new HashMap<integer,integer>(); 
  init(hashMap);//初始化  
  System.out.println("初始序列为："); 
  print(hashMap, 0);//打印 
  heap(hashMap);//排序 
 } 
 /** 
  * 初始化函数 
  * @param hashMap 
  */ 
 private static void init(HashMap<integer, integer=""> hashMap) { 
  hashMap.put(0, null);//第一位置空 
  hashMap.put(1, 10); 
  hashMap.put(2, 5); 
  hashMap.put(3, 11); 
  hashMap.put(4, 12); 
  hashMap.put(5, 13); 
  hashMap.put(6, 4); 
  hashMap.put(7, 1); 
  hashMap.put(8, 5); 
  hashMap.put(9, 8); 
  hashMap.put(10, 6); 
  hashMap.put(11, 4); 
  hashMap.put(12, 8);  
 } 
 /** 
  * 进行堆排序 
  * @param hashMap 待排序的表 
  */ 
 private static void heap(HashMap<integer, integer=""> hashMap){ 
  System.out.println("开始建堆：");   
  //排序开始时间87 
  long start = System.currentTimeMillis(); 
  for(int i=(hashMap.size()-1)/2; i>=1; i--){//开始建堆 
   sift(hashMap, i, hashMap.size()-1);//把所有的节点调好位置即可以 
  }   
  System.out.println("建堆成功"); 
  for(int j=hashMap.size()-1; j>=1; j--){//每次都把第一个元素与最后一个未排序的交换 然后再调整第一个节点即可 
   hashMap.put(0, hashMap.get(1)); 
   hashMap.put(1, hashMap.get(j)); 
   hashMap.put(j, hashMap.get(0)); 
   sift(hashMap, 1, j-1);//剩下要排序的数位为j-1 
   swapCount++;//发生一次交换 
   swapCount++;//发生一次交换 
   swapCount++;//发生一次交换 
  } 
  //排序结束时间 
  long end = System.currentTimeMillis(); 
  System.out.println("结果为："); 
  print(hashMap, 0);//输出排序结束的序列 
  hashMap.clear();//清空 
  System.out.print("一共发生了 "+contrastCount+" 次对比\t"); 
  System.out.print("一共发生了 "+swapCount+" 次交换\t"); 
  System.out.println("执行时间为"+(end-start)+"毫秒"); 
 } 
 /** 
  * 把第i位的元素移动到合适位置 与其子孩子的最大值比较 如果有发生交换 则继续往下比较 
  * @param hashMap 
  * @param i 待移动的数下标 
  * @param n 表示要查找的范围 从1到n个 
  */ 
 private static void sift(HashMap<integer, integer=""> hashMap, int i, int n){ 
  int j = 2*i;//j为i的左孩子 
  hashMap.put(0, hashMap.get(i));//当前被待排序的数 
  while(j<=n){//如果有左孩子的 
   if(hashMap.containsKey(j+1) && hashMap.get(j)<hashmap.get(j+1)){ else="" hashmap="" i="j;//转移根节点下标" integer="" j="" param="" private="" static="" void=""> hashMap, int j){ 
  if(j != 0) 
   System.out.print("第 "+j+" 趟：\t"); 
  for(int i=1; i<hashmap.size(); code=""></hashmap.size();></hashmap.get(j+1)){></integer,></integer,></integer,></integer,integer></integer,integer></code></code></code></code></code>

Tri par fusion

<code class="language-java hljs "><code class="language-java hljs "><code class="language-java hljs "><code class="language-java hljs "><code class="language-java hljs "><code class="language-java hljs ">import java.util.HashMap; 
public class MergeSort { 
 private static int contrastCount = 0;//对比次数 
 private static int swapCount = 0;//交换次数 
 private static int printCount = 1;//只为统计执行次数 
 public static void main(String[] args) { 
  System.out.println("归并尔排序：\n 先将数据分为n组，然后没两组开始合并，相邻两个合并为一个新的有序队列，重复合并直到整个队列有序,时间复杂度O(nlgn),空间复杂度O(n)，稳定排序");   
  HashMap<integer,integer> hashMap = new HashMap<integer,integer>();//未排序 
  HashMap<integer,integer> hashMapNew = new HashMap<integer,integer>();//已排序 
  hashMapNew.put(0, null);//第一位置空 
  init(hashMap);//初始化  
  System.out.println("初始序列为："); 
  print(hashMap, 0);//打印 
  System.out.println("开始归并尔排序："); 
  //排序开始时间 
  long start = System.currentTimeMillis();   
  merge(hashMap, hashMapNew, 1, hashMap.size()-1);//排序 
  //排序结束时间 
  long end = System.currentTimeMillis(); 
  System.out.println("结果为："); 
  print(hashMapNew, 0);//输出排序结束的序列 
  hashMap.clear();//清空 
  System.out.print("一共发生了 "+contrastCount+" 次对比\t"); 
  System.out.print("一共发生了 "+swapCount+" 次交换\t"); 
  System.out.println("执行时间为"+(end-start)+"毫秒"); 
  System.out.println("(注：此输出序列为代码执行过程的序列， 即先左边递归 再 右边递归， 而教科书上的递归序列往往是左右同时进行的结果，特此说明)"); 
 } 
 /** 
  * 初始化函数 
  * @param hashMap 
  */ 
 private static void init(HashMap<integer, integer=""> hashMap) { 
  hashMap.put(0, null);//第一位置空 
  hashMap.put(1, 10); 
  hashMap.put(2, 5); 
  hashMap.put(3, 11); 
  hashMap.put(4, 12); 
  hashMap.put(5, 13); 
  hashMap.put(6, 4); 
  hashMap.put(7, 1); 
  hashMap.put(8, 5); 
  hashMap.put(9, 8); 
  hashMap.put(10, 6); 
  hashMap.put(11, 4); 
  hashMap.put(12, 8);  
 } 
 /** 
  * 进行归并尔排序 
  * @param hashMap 待排序的表 
  * @param hashMapNew 已排序的表 
  */ 
 private static void merge(HashMap<integer, integer=""> hashMap, HashMap<integer, integer=""> hashMapNew, int low, int high){ 
  if(low == high){ 
   hashMapNew.put(low, hashMap.get(low)); 
   swapCount++;//发生一次交换 
  }else{ 
   int meddle = (int)((low+high)/2);//将这一序列数均分的中间值 
   merge(hashMap, hashMapNew, low, meddle);//继续对左边的序列递归 
   merge(hashMap, hashMapNew, meddle+1, high);//对右边的序列递归 
   mergeSort(hashMap, hashMapNew, low, meddle, high);//把相邻的序列组合起来 
   for(int i=low; i<=high; i++){//将已经排好序的hashMapNew【low，high】覆盖hashMap【low，high】以便进入下一次的递归归并 
    hashMap.put(i, hashMapNew.get(i)); 
    swapCount++;//发生一次交换 
   } 
  } 
 } 
 /** 
  * 进行归并尔排序 把【low，meddle】和【meddle+1，high】和并为一个有序的hashMapNew【low,high】 
  * @param hashMap 待排序的表  
  * @param hashMapNew 已排序的表 
  * @param low 低位 
  * @param meddle 中位 
  * @param high 高位 
  */ 
 private static void mergeSort(HashMap<integer, integer=""> hashMap, HashMap<integer, integer=""> hashMapNew, int low, int meddle, int high){ 
  int k = low; 
  int j = meddle+1; 
  while(low<=meddle && j<=high){//两个序列组合成一个序列 从小到达的顺序 
   if(hashMap.get(low) < hashMap.get(j)){ 
    hashMapNew.put(k++, hashMap.get(low++));//放入合适的位置 
   }else{ 
    hashMapNew.put(k++, hashMap.get(j++));//放入合适的位置 
   }    
   contrastCount++;//发生一次对比 
   swapCount++;//发生一次交换 
  } 
  //如果有一方多出来了 则直接赋值 
  while(low<=meddle){ 
   hashMapNew.put(k++, hashMap.get(low++));//放入合适的位置 
   swapCount++;//发生一次交换 
  } 
  while(j<=high){ 
   hashMapNew.put(k++, hashMap.get(j++));//放入合适的位置 
   swapCount++;//发生一次交换 
  } 
  print(hashMapNew, printCount++); 
 } 
 /** 
  * 打印已排序好的元素 
  * @param hashMap 已排序的表 
  * @param j 第j趟排序 
  */ 
 private static void print(HashMap<integer, integer=""> hashMap, int j){ 
  if(j != 0) 
   System.out.print("第 "+j+" 趟：\t"); 
  for(int i=1; i<hashmap.size(); code=""></hashmap.size();></integer,></integer,></integer,></integer,></integer,></integer,></integer,integer></integer,integer></integer,integer></integer,integer></code></code></code></code></code></code>

Bit le plus bas premier tri de base

<code class="language-java hljs "><code class="language-java hljs "><code class="language-java hljs "><code class="language-java hljs "><code class="language-java hljs "><code class="language-java hljs "><code class="language-java hljs ">/** 
 * 最低位优先基数排序 
 * @author HHF 
 * 
 */ 
public class LSDSort { 
 private static int contrastCount = 0;//对比次数 
 private static int swapCount = 0;//交换次数 
 private static int printCount = 1;//只为统计执行次数 
 
 public static void main(String[] args) { 
  System.out.println("最低位优先基数排序：\n 按个位、十位、百位排序，不需要比较，只需要对数求余然后保存到相应下标的二维数组内，然后依次读取，每一进制重复依次 ,时间复杂度O(d（n+rd）),空间复杂度O(n+rd)，稳定排序");   
  int[] data = { 173, 22, 93, 43, 55, 14, 28, 65, 39, 81, 33, 100 }; 
  System.out.println("初始序列为："); 
  print(data, 0);//打印 
  LSD(data, 3); 
 } 
 public static void LSD(int[] number, int d) {// d表示最大的数有多少位 
  int k = 0;//number的小标 
  int n = 1;//当比较十位的时候 n=10 比较百位的时候 n=100 用来吧高位降低方便求余数 
  int m = 1;//正在比较number中数据的倒数第几位 
  int[][] temp = new int[10][number.length];// 数组的第一维表示可能的余数0-9 二维依次记录该余数相同的数 
  int[] order = new int[10];// 数组orderp[i]用来表示该位的余数是i的数的个数 
  //排序开始时间 
  long start = System.currentTimeMillis(); 
  while (m <= d) {//d=5则比较五次 
   for (int i = 0; i < number.length; i++) {//把number中的数按余数插入到temp中去 
    int lsd = ((number[i] / n) % 10);//求得该数的余数 
    temp[lsd][order[lsd]] = number[i];//保存到相应的地方 
    order[lsd]++;//该余数有几个 
    swapCount++;//发生一次交换 
   } 
   for (int i = 0; i < 10; i++) {//将temp中的数据按顺序提取出来 
    if (order[i] != 0)//如果该余数没有数据则不需要考虑 
     for (int j = 0; j < order[i]; j++) {//有给余数的数一共有多少个 
      number[k] = temp[i][j];//一一赋值 
      k++; 
      swapCount++;//发生一次交换 
     } 
    order[i] = 0;//置零，以便下一次使用 
   } 
   n *= 10;//进制+1 往前走 
   k = 0;//从头开始 
   m++;//进制+1 
   print(number, printCount++); 
  } 
  //排序结束时间 
  long end = System.currentTimeMillis(); 
  System.out.println("结果为："); 
  print(number, 0);//输出排序结束的序列 
  System.out.print("一共发生了 "+contrastCount+" 次对比\t"); 
  System.out.print("一共发生了 "+swapCount+" 次交换\t"); 
  System.out.println("执行时间为"+(end-start)+"毫秒"); 
 } 
 /** 
  * 打印已排序好的元素 
  * @param data 已排序的表 
  * @param j 第j趟排序 
  */ 
 private static void print(int[] data, int j){ 
  if(j != 0) 
   System.out.print("第 "+j+" 趟：\t"); 
  for (int i = 0; i < data.length; i++) { 
   System.out.print(data[i] + " "); 
  } 
  System.out.println(); 
 } 
} </code></code></code></code></code></code></code>

[Recommandations associées]

1 Tutoriel vidéo gratuit Java

2. Manuel

3.

Tutoriel vidéo Java de la Geek Academy

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!