交换类

冒泡排序

  1. public void  maopaosort(int[] a) {
  2.   // TODO Auto-generated method stub
  3.   for(int i=a.length-1;i>=0;i--)
  4.   {
  5.     for(int j=0;j<i;j++)
  6.     {
  7.       if(a[j]>a[j+1])
  8.       {
  9.         int team=a[j];
  10.         a[j]=a[j+1];
  11.         a[j+1]=team;
  12.       }
  13.     }
  14.   }
  15. }

快速排序

  1. public void quicksort(int [] a,int left,int right)
  2. {
  3.   int low=left;
  4.   int high=right;
  5.   //下面两句的顺序一定不能混，否则会产生数组越界！！！very important！！！
  6.   if(low>high)//作为判断是否截止条件
  7.     return;
  8.   int k=a[low];//额外空间k，取最左侧的一个作为衡量，最后要求左侧都比它小，右侧都比它大。
  9.   while(low<high)//这一轮要求把左侧小于a[low],右侧大于a[low]。
  10.   {
  11.     while(low<high&&a[high]>=k)//右侧找到第一个小于k的停止
  12.     {
  13.       high--;
  14.     }
  15.     //这样就找到第一个比它小的了
  16.     a[low]=a[high];//放到low位置
  17.     while(low<high&&a[low]<=k)//在low往右找到第一个大于k的，放到右侧a[high]位置
  18.     {
  19.       low++;
  20.     }
  21.     a[high]=a[low];   
  22.   }
  23.   a[low]=k;//赋值然后左右递归分治求之
  24.   quicksort(a, left, low-1);
  25.   quicksort(a, low+1, right);  
  26. }

插入类

直接插入排序

  1. public void insertsort (int a[])
  2. {
  3.   int team=0;
  4.   for(int i=1;i<a.length;i++)
  5.   {
  6.     System.out.println(Arrays.toString(a));
  7.     team=a[i];
  8.     for(int j=i-1;j>=0;j--)
  9.     {
  10.       if(a[j]>team)
  11.       {
  12.         a[j+1]=a[j];
  13.         a[j]=team; 
  14.       } 
  15.       else {
  16.         break;
  17.       }
  18.     }
  19.   } 
  20. }

希尔排序

  1. public void shellsort (int a[])
  2. {
  3.   int d=a.length;
  4.   int team=0;//临时变量
  5.   for(;d>=1;d/=2)//共分成d组
  6.     for(int i=d;i<a.length;i++)//到那个元素就看这个元素在的那个组即可
  7.     {
  8.       team=a[i];
  9.       for(int j=i-d;j>=0;j-=d)
  10.       {    
  11.         if(a[j]>team)
  12.         {
  13.           a[j+d]=a[j];
  14.           a[j]=team; 
  15.         }
  16.         else {
  17.           break;
  18.         }
  19.       }
  20.     } 
  21. }

选择类

简单选择排序

  1. public void selectSort(int[] arr) {
  2.   for (int i = 0; i < arr.length - 1; i++) {
  3.     int min = i; // 最小位置
  4.     for (int j = i + 1; j < arr.length; j++) {
  5.       if (arr[j] < arr[min]) {
  6.         min = j; // 更换最小位置
  7.       }
  8.     }
  9.     if (min != i) {
  10.       swap(arr, i, min); // 与第i个位置进行交换
  11.     }
  12.   }
  13. }
  14. private void swap(int[] arr, int i, int j) {
  15.   int temp = arr[i];
  16.   arr[i] = arr[j];
  17.   arr[j] = temp;
  18. }

堆排序

  1. static void swap(int arr[],int m,int n)
  2. {
  3.   int team=arr[m];
  4.   arr[m]=arr[n];
  5.   arr[n]=team;
  6. }
  7. //下移交换 把当前节点有效变换成一个堆(小根)
  8. static void shiftDown(int arr[],int index,int len)//0 号位置不用
  9. {
  10.   int leftchild=index*2+1;//左孩子
  11.   int rightchild=index*2+2;//右孩子
  12.   if(leftchild>=len)
  13.     return;
  14.   else if(rightchild<len&&arr[rightchild]<arr[index]&&arr[rightchild]<arr[leftchild])//右孩子在范围内并且应该交换
  15.   {
  16.     swap(arr, index, rightchild);//交换节点值
  17.     shiftDown(arr, rightchild, len);//可能会对孩子节点的堆有影响，向下重构
  18.   }
  19.   else if(arr[leftchild]<arr[index])//交换左孩子
  20.   {
  21.     swap(arr, index, leftchild);
  22.     shiftDown(arr, leftchild, len);
  23.   }
  24. }
  25. //将数组创建成堆
  26. static void creatHeap(int arr[])
  27. {
  28.   for(int i=arr.length/2;i>=0;i--)
  29.   {
  30.     shiftDown(arr, i,arr.length);
  31.   }
  32. }
  33. static void heapSort(int arr[])
  34. {
  35.   System.out.println("原始数组为         ："+Arrays.toString(arr));
  36.   int val[]=new int[arr.length]; //临时储存结果
  37.   //step1建堆
  38.   creatHeap(arr);
  39.   System.out.println("建堆后的序列为  ："+Arrays.toString(arr));
  40.   //step2 进行n次取值建堆，每次取堆顶元素放到val数组中，最终结果即为一个递增排序的序列
  41.   for(int i=0;i<arr.length;i++)
  42.   {
  43.     val[i]=arr[0];//将堆顶放入结果中
  44.     arr[0]=arr[arr.length-1-i];//删除堆顶元素，将末尾元素放到堆顶
  45.     shiftDown(arr, 0, arr.length-i);//将这个堆调整为合法的小根堆，注意(逻辑上的)长度有变化
  46.   }
  47.   //数值克隆复制
  48.   for(int i=0;i<arr.length;i++)
  49.   {
  50.     arr[i]=val[i];
  51.   }
  52.   System.out.println("堆排序后的序列为:"+Arrays.toString(arr));
  53. }