1、冒泡排序

  1. /**
  2. 冒泡排序算法
  3. 冒泡排序算法的运作如下：（从后往前）
  4. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
  5. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
  6. 针对所有的元素重复以上的步骤，除了最后一个。
  7. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
  8. 相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。
  9. */
  10. import java.util.Scanner;
  11. public class Test12{
  12.     public static void main(String[] args){
  14.         int[] nums = {34,4,56,56,90,65};//待排序的数列
  16.         //外循环控制轮数
  17.         for(int i=0;i<nums.length-1;i++){ //比较轮数等于数列的长度-1
  19.             for(int j=0;j<nums.length-1-i;j++){
  21.                 if(nums[j]>nums[j+1]){
  22.                     nums[j] = nums[j]+nums[j+1];
  23.                     nums[j+1] = nums[j]-nums[j+1];
  24.                     nums[j] = nums[j]-nums[j+1];
  25.                 }
  26.             }
  27.         }
  28.         //输出结果
  29.         for(int n : nums){
  31.             System.out.println(n);
  32.         }    
  33.     }
  34. }
  35. /*
  36. 34 4 56 17 90 65
  38. 4 34 17 56 65 90    //第一轮 5次
  39. 4 17 34 56 65        //第二轮 4次
  40. 4 17 34 56            //第三轮 3次
  41. 4 17 34                //第四轮 2次
  42. 4 17                //第五轮 1次
  43. */

2、选择排序

  1. /**
  2. 选择排序算法
  3. 每一趟从待排序的数据元素中选出最小（或最大）的一个元素，
  4. 顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。 
  5. 选择排序是不稳定的排序方法。
  6. */
  7. import java.util.Scanner;
  8. public class Test13{
  9.     public static void main(String[] args){
  11.         int[] nums = {34,4,56,17,90,65};//待排序的数列
  12.         int minIndex = 0;//用于记录每次比较的最小值下标
  13.         //控制轮数
  14.         for(int i=0;i<nums.length-1;i++){
  16.             minIndex = i;//每轮假设一个最小值下标
  18.             for(int j=i+1;j<nums.length;j++){
  20.                 if(nums[minIndex]>nums[j]){
  21.                     minIndex = j;
  22.                 }
  23.             }
  24.             //判断需要交换的数下标是否为自己
  25.             if(minIndex!=i){
  26.                 nums[minIndex] = nums[minIndex]+nums[i];
  27.                 nums[i] = nums[minIndex]-nums[i];
  28.                 nums[minIndex] = nums[minIndex]-nums[i];
  29.             }    
  30.         }
  31.         //输出结果：
  32.         for(int n: nums){
  33.             System.out.println(n);
  34.         }    
  35.     }
  36. }
  37. /*
  38. 34 4 56 17 90 65
  39. 4 34 56 17 90 65 第一轮 5次
  40. 4 17 56 34 90 65 第二轮 4次
  41. 4 17 34 56 90 65 第三轮 3次
  42. 4 17 34 56 90 65 第四轮 2次
  43. 4 17 34 56 65 90 第五轮 1次
  44. */

3、插入排序

  1. /**
  2. 直接插入排序算法
  3. （从后向前找到合适位置后插入）
  4. 基本思想：每步将一个待排序的记录，按其顺序码大小插入到前面已经排序的子序列的合适位置（从后向前找到
  5. 合适位置后），直到全部插入排序完为止。
  8. */
  9. import java.util.Scanner;
  10. public class Test14{
  11.     public static void main(String[] args){
  12.         int[] nums = {34,4,56,17,90,65};//待排序的数列
  13.         //控制比较的轮数：
  14.         for(int i=1;i<nums.length;i++){
  16.             int temp = nums[i];  //记录操作数
  17.             int j = 0;
  18.             for(j=i-1;j>=0;j--){
  19.                 if(nums[j]>temp){
  20.                     nums[j+1] = nums[j];
  21.                 }else{
  22.                     break;
  23.                 }
  24.             }
  25.             if(nums[j+1]!=temp){
  26.                 nums[j+1] = temp;
  27.             }
  28.         }
  29.         //输出结果：
  30.         for(int n : nums){
  31.             System.out.println(n);
  32.         }
  33.     }
  34. }
  36. /*
  37. 34 4 56 17 90 65
  39. temp=4
  40. 第一轮：i=1,4要插到34前，就要把34往后挪，变为34，34，56，17，90，65
  41.         再从temp中拿到数：4，34，56，17，90，65
  43. temp=56
  44. 第二轮：i=2，56>34，直接退出：4，34，56,17，90，65
  46. temp=17
  47. 第三轮：i=3        4,34,56,56,90,65
  48.                 4,34,34,56,90,65    
  49.                 4,17,34,56,90,65
  51. temp=90
  52. 第四轮：i=4，90>57，直接退出
  54. temp=65
  55. 第五轮：i=5        4,17,34,56,90,90
  56.                 4,17,34,56,65,90
  57. */

4、二分查找

  1. /**
  2.     二分法查找（折半查找）：前提是在已经排好序的数组中，
  3.     通过将待查找的元素与中间索引值对应的元素进行比较，若大于中间索引值对应的元素，
  4.     去右半部分查找，否则，去左半部分查找。
  5.     依此类推。直到找到为止；找不到返回一个负数。
  6. */
  7. import java.util.Scanner;
  8. public class Test15{
  9.     public static void main(String[] args){
  11.         //必须保正数列是有序的
  12.         int[] num = {10,20,50,65,88,90};
  13.         int index = binarySearch(num,88);
  14.         System.out.println(index);
  16.     }
  18.     //二分查找算法
  19.     public static int binarySearch(int[] num,int key){
  20.         int start = 0;//开始下标
  21.         int end = num.length-1;//结束下标
  23.         while(start<=end){
  24.             int middle = (start+end)/2; //>>>1
  25.             if(num[middle]>key){
  26.                 end = middle-1;
  27.             }else if(num[middle]<key){
  28.                 start = middle+1;
  29.             }else{
  30.                 return middle;
  31.             }
  32.         }
  33.         return -1;
  34.     }
  35. }

5、归并排序

MergeSort（归并排序）算法Java实现 - 九天高远 - 博客园 (cnblogs.com)

19、排序算法 - 图1

算法主要思想

  1. template<class T>
  2.   void merge( T r[],T r2[],int s,int mid,int t)
  3.   //s为第一个子表首元素的下标，mid为第一个子表末元素的下标
  4.   //t为第二个子表末元素的下标
  5.    { int i,j,k;
  6.      i=s;j=mid+1;k=s;   //k是r2的初始指针
  7.      while((i<=mid)&&(j<=t))
  8.        { k=k+1;
  9.          if(r[i].key<=r[j].key){r2[k]=r[i];i++;}
  10.          else{r2[k]=r[j];j++;}
  11.        }
  12.      while(i<=mid){k++;r2[k]=r[i];i++;}
  13.      while(j<=t){k++;r2[k]=r[j];j++;}
  14.   }   //merge

Java实现的二路归并排序的算法如下

  1.  package com.chang;
  3. import java.util.Arrays;
  5. public class myMergeSort {
  6.     public static void main(String[] args) {
  7.         int[] li={26, 5, 98, 108, 28, 99, 100, 56, 34, 1};
  8.         printArray("排序前：",li);
  9.         guiBingSort(li);
  10.         printArray("排序后：",li);
  11.     }
  13.     private static void printArray(String pre,int[] a) {
  14.         System.out.print(pre+"\n");
  15.         for(int i=0;i<a.length;i++)
  16.             System.out.print(a[i]+"\t");
  17.         System.out.println();
  18.     }
  20.     public static void guiBingSort(int[] li){
  21.         System.out.println("开始排序");
  22.         mergeSort(li,0,li.length-1);
  23.     }
  25.     public static void mergeSort(int[] li,int l,int r){
  26.         if(l==r){
  27.             return;
  28.         }
  29.         int mid=l+((r-l)>>1);
  30.         //二路归并排序里面有两个Sort，多路归并排序里面写多个Sort就可以了
  31.         mergeSort(li,l,mid);
  32.         mergeSort(li,mid+1,r);
  33.         merge(li,l,mid,r);
  34.     }
  36.     static int number=0;
  37.     public static void merge(int[] li, int left ,int mid,int right){
  39.         //暂存数组
  40.         int[] temp=new int[li.length];
  41.         int tIndex=left;
  43.         int cIndex=left;
  45.         int r1=mid+1;
  46.         while(left<=mid && r1<=right){
  47.             if(li[left]<=li[r1]){
  48.                 temp[tIndex++]=li[left++];
  49.             }else{
  50.                 temp[tIndex++]=li[r1++];
  51.             }
  52.         }
  53.         while(left<=mid){
  54.             temp[tIndex++]=li[left++];
  55.         }
  56.         while(r1<=right){
  57.             temp[tIndex++]=li[r1++];
  58.         }
  61.         System.out.println("第"+(++number)+"趟排序:\t");
  63.         //将暂存数组中的内容拷贝到原数组
  64.         while(cIndex<=right){
  65.             li[cIndex]=temp[cIndex];
  66.             //输出中间归并排序结果
  67.             System.out.print(li[cIndex]+"\t");
  68.             cIndex++;
  69.         }
  70.         System.out.println("");
  71.     }
  72. }
  74. /*
  75. 排序前：
  76. 26    5    98    108    28    99    100    56    34    1    
  77. 开始排序
  78. 第1趟排序:    
  79. 5    26    
  80. 第2趟排序:    
  81. 5    26    98    
  82. 第3趟排序:    
  83. 28    108    
  84. 第4趟排序:    
  85. 5    26    28    98    108    
  86. 第5趟排序:    
  87. 99    100    
  88. 第6趟排序:    
  89. 56    99    100    
  90. 第7趟排序:    
  91. 1    34    
  92. 第8趟排序:    
  93. 1    34    56    99    100    
  94. 第9趟排序:    
  95. 1    5    26    28    34    56    98    99    100    108    
  96. 排序后：
  97. 1    5    26    28    34    56    98    99    100    108    
  98. */