Java常用的几种排序算法

本文预计阅读时间 12 分钟
今天七墨给大家带来的是Java中常用的几种排序算法:冒泡排序、快速排序、选择排序、插入排序、归并排序这五种排序方式。

第一种:冒泡排序

  1. /**  
  2.  * 冒泡法排序
  3.  * 比较相邻的元素。如果第一个比第二个大,就交换他们两个。 
  4.  * 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。  
  5.  * 针对所有的元素重复以上的步骤,除了最后一个。
  6.  * 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。 
  7.  * @param numbers  
  8.  * 需要排序的整型数组  
  9.  */
  10. public static void bubbleSort(int[] numbers) {
  11.     int temp; // 记录临时中间值   
  12.     int size = numbers.length; // 数组大小   
  13.     for (int i = 0; i < size - 1; i++) {
  14.         for (int j = i + 1; j < size; j++) {
  15.             if (numbers[i] < numbers[j]) { // 交换两数的位置   
  16.                 temp = numbers[i];
  17.                 numbers[i] = numbers[j];
  18.                 numbers[j] = temp;
  19.             }
  20.         }
  21.     }
  22. }

第二种:快速排序

  1. /**  
  2.  * 快速排序    
  3.  * 从数列中挑出一个元素,称为“基准",
  4.  * 重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。
  5.  * 在这个分割之后,该基准是它的最后位置。这个称为分割(partition)操作。
  6.  * 递归地把小于基准值元素的子数列和大于基准值元素的子数列排序。
  7.  * @param numbers  
  8.  * @param start  
  9.  * @param end  
  10.  */
  11. public static void quickSort(int[] numbers, int start, int end) {
  12.     if (start < end) {
  13.         int base = numbers[start]; // 选定的基准值(第一个数值作为基准值)   
  14.         int temp; // 记录临时中间值   
  15.         int i = start, j = end;
  16.         do {
  17.             while ((numbers[i] < base) && (i < end))
  18.                 i++;
  19.             while ((numbers[j] > base) && (j > start))
  20.                 j--;
  21.             if (i <= j) {
  22.                 temp = numbers[i];
  23.                 numbers[i] = numbers[j];
  24.                 numbers[j] = temp;
  25.                 i++;
  26.                 j--;
  27.             }
  28.         } while (i <= j);
  29.         if (start < j)
  30.             quickSort(numbers, start, j);
  31.         if (end > i)
  32.             quickSort(numbers, i, end);
  33.     }
  34. }

第三种:选择排序

  1. /**  
  2.  * 选择排序
  3.  * 在未排序序列中找到最小元素,存放到排序序列的起始位置  
  4.  * 再从剩余未排序元素中继续寻找最小元素,然后放到排序序列末尾。
  5.  * 以此类推,直到所有元素均排序完毕。
  6.  * @param numbers  
  7.  */
  8. public static void selectSort(int[] numbers) {
  9.     int size = numbers.length, temp;
  10.     for (int i = 0; i < size; i++) {
  11.         int k = i;
  12.         for (int j = size - 1; j >i; j--)  {
  13.             if (numbers[j] < numbers[k])  k = j;
  14.         }
  15.         temp = numbers[i];
  16.         numbers[i] = numbers[k];
  17.         numbers[k] = temp;
  18.     }
  19. }

第四种:插入排序

  1. /**  
  2.  * 插入排序
  3.  * 从第一个元素开始,该元素可以认为已经被排序
  4.  * 取出下一个元素,在已经排序的元素序列中从后向前扫描 
  5.  * 如果该元素(已排序)大于新元素,将该元素移到下一位置  
  6.  * 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置  
  7.  * 将新元素插入到该位置中 
  8.  * 重复步骤2
  9.  * @param numbers  
  10.  */
  11. public static void insertSort(int[] numbers) {
  12.     int size = numbers.length, temp, j;
  13.     for(int i=1; i<size; i++) {
  14.         temp = numbers[i];
  15.         for(j = i; j > 0 && temp < numbers[j-1]; j--)
  16.             numbers[j] = numbers[j-1];
  17.         numbers[j] = temp;
  18.     }
  19. }

第五种:归并排序

  1. /**
  2.  * 归并排序            
  3.  * 申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列   
  4.  * 设定两个指针,最初位置分别为两个已经排序序列的起始位置    
  5.  * 比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置      
  6.  * 重复步骤3直到某一指针达到序列尾    
  7.  * 将另一序列剩下的所有元素直接复制到合并序列尾                
  8.  * @param numbers      
  9.  */
  10. public static void mergeSort(int[] numbers, int left, int right) {
  11.     int t = 1;// 每组元素个数       
  12.     int size = right - left + 1;
  13.     while (t < size) {
  14.         int s = t;// 本次循环每组元素个数       
  15.         t = 2 * s;
  16.         int i = left;
  17.         while (i + (t - 1) < size) {
  18.             merge(numbers, i, i + (s - 1), i + (t - 1));
  19.             i += t;
  20.         }
  21.         if (i + (s - 1) < right)
  22.             merge(numbers, i, i + (s - 1), right);
  23.     }
  24. }
  25. /**    
  26.  * 归并算法实现    
  27.  *     
  28.  * @param data    
  29.  * @param p    
  30.  * @param q    
  31.  * @param r    
  32.  */
  33. private static void merge(int[] data, int p, int q, int r) {
  34.     int[] B = new int[data.length];
  35.     int  m= p;
  36.     int t = q + 1;
  37.     int k = p;
  38.     while (m <= q && t <= r) {
  39.         if (data[m] <= data[t]) {
  40.             B[k] = data[m];
  41.             m++;
  42.         } else {
  43.             B[k] = data[t];
  44.             t++;
  45.         }
  46.         k++;
  47.     }
  48.     if (m == q + 1)
  49.         B[k++] = data[t++];
  50.     else
  51.         B[k++] = data[m++];
  52.     for (int i = p; i <= r; i++)
  53.         data[i] = B[i];
  54. }
weinxin
七墨微信
请留下您宝贵的意见,或者每天来本站的文章页面签到,七墨将不胜感激~~
  • Java常用的几种排序算法已关闭评论
  • 279
  • A+
所属分类:Java篇
七墨