Java排序之排序大综合

一、最近写了一些排序，于是和和大家分享一下：（默认都是从小到大排序）

二、冒泡排序

1、什么是冒泡排序：原理是临近的两个数比较大小，将较大的数往后移，这样遍历一趟数组以后，最大的数就排在的最后面（时间复杂的为O（N2））

重复上面步骤N次。

2、原理描述：data{44,77,55,33,66}

第一次运行：data{44,55,33,66,77}

第二次运行：data{44，33，55，66，77}

。。。。。。

第N次执行：data{33，44，55，66，77}

3、参考代码：

 import java.util.Arrays;  /**  * Description:冒泡排序  * Author: Hey  * Date: 2015/12/7  */ public class BubbleSort {      public static void main(String[] args) {         int[] data = {11, 66, 33, 44, 77, 55};          for (int i = 0; i < data.length-1; i++) {             for (int j = data.length - i; j > 0; j--) {                 if (data[i] > data[i + 1]) {                     data[i] = data[i] ^ data[i + 1];                     data[i + 1] = data[i + 1] ^ data[i];                     data[i] = data[i] ^ data[i + 1];                 }             }         } //        for(int i=0;i<data.length;i++){ //            System.out.println(data[i]); //        }         System.out.println(Arrays.toString(data));     } } 

三、选择排序

1、什么是选择排序：选择排序是选择数组中最小的数将该数移动到数组最前面，将其他元素往后移动，重复N次操作（时间复杂的（O（N2）））

2、原理：data{44,77,55,33,66}

第一次运行：data{33，44，77，55，66}

第二次运行：data{33，44，77，55，66}

。。。。。。。

第N次运行：data{33，44，55，66，77}

3、参考代码：

 import java.util.Arrays;  /**  * Description:选择排序  * Author: Hey  * Date: 2015/12/7  */ public class SelectionSort {      public static void main(String [] args){         int[] data = {11, 66, 33, 44, 77, 55};          int minData=0;         for(int i=0;i<data.length;i++){             minData=data[i];             for(int j=i+1;j<data.length;j++){                 if(data[j]<minData){                     data[j]=data[j]^minData;                     minData=minData^data[j];                     data[j]=data[j]^minData;                 }                 data[i]=minData;             }         }         System.out.print(Arrays.toString(data));     } } 

四、插入排序：

1、什么是插入排序：插入排序是将数组划分为两个部分：有序部分和无序部分，将无序部分插入有序部分，重复执行N-1次,默认数组第一项就是有序的（时间复杂的O（N2））

2、插入排序的原理：data{44,77,55,33,66}

第一次：data{44，77，55，33，66}

第二次：data{44，55，77，33，66}

。。。。

第N次：data{33，44，55，66，77}

3、参考代码

 package cn.edu.insertionsort;  import java.util.Arrays;  /**  * Description:插入排序  * Author: Hey  * Date: 2015/12/7  */ public class InsertSort {      public static void main(String[]args){         int[] data = {11, 66, 33, 44, 77, 55};          int i;        // int j;          for(i=1;i<data.length;i++){             /*int temp=data[i];             for(j=i-1;j>0;j--){                 if(data[i]<data[j]){                     if(data[j]>data[i]);                     data[i]=data[j];                     data[j]=temp;                 }else{                     break;                 }             }*/               if(data[i-1]>data[i]){                 int temp=data[i];                 int j=i;                 while(j>0&&data[i]<data[j-1]){                     data[j]=data[j-1];                     j--;                 }                 data[j]=temp;             }          }     System.out.print(Arrays.toString(data));     }  } 

五、希尔排序

1、（历史）希尔排序是选择排序的进化版：插入排序算法对大致有序的数组效率比较高；

但是如果是反序，那么插入排序将会进行大量的移动复制，如果先让部分的局部有序，那么久能够减少移动的次数

（什么是希尔排序）先取一个小于n的整数d1作为第一个 增量 ，把文件的全部记录分组。

所有距离为d1的倍数的记录放在同一个组中。先在各组内进行 直接插入排序 ；然后，取第二个增量d2<d1重复上述的分组和排序，

直至所取的增量  =1(  <   …<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。

2、关于增量的选取一般用3h+1的算数公式

3参考代码：

 import java.util.Arrays;  /**  * Description:希尔排序,希尔排序的之间的间隔是使用3h+1（运行个数）来定义的。  * h代表间隔(由于排序算法是基于插入算法的，当数组大小至少为3时，插入排序才比较有效)  * Author: Hey  * Date: 2015/12/7  */ public class HillSort {      public static void main(String[]args){         int[] data = {11, 66, 33, 44, 77, 55};          //计算间隔         int length=data.length;         int h=1;         while(h<=length/3)             h=3*h+1;          while(h>0){             for(int i=h;i<length;i++){                 int temp=data[i];                 int j=i;                 while(j>h-1&&data[j-h]>temp){                     data[j]=data[j-h];                     j-=h;                 }                 data[j]=temp;             }             h=(h-1)/3;         }          System.out.print(Arrays.toString(data));     } } 

六、快速排序

1、什么事快速排序：快速排序是在数组选择一个标准位（其实也就是在数组中选择一个数做参考），将比标志位大的数右移，比标志位小的左移，让缩小范围继续比较

3、参考代码：

 package cn.edu.quicksort;  import java.util.Arrays;  /**  * Description:快速排序  * Author: Hey  * Date: 2015/12/7  */ public class QuickSort {      int[] data = {11, 66, 33, 44, 77, 55};      public void quickSort(int left, int right) {         if ((right - left) <= 0)             return;         else {             int pivot = data[right];              int parttion=recQuickSort(left,right,pivot);             quickSort(left, parttion-1);             quickSort(parttion + 1, right);         }     }      public int recQuickSort(int left, int right, int pivot) {         int leftPtr=left-1;         int rightPtr=right;         while (true) {             while (data[++leftPtr] < pivot) ;             while (data[--rightPtr] > pivot) ;             if (leftPtr >= rightPtr)                 break;             else                 swap(leftPtr, rightPtr);         }         swap(leftPtr, right);         return leftPtr;     }      public void swap(int i, int j) {         data[i] = data[i] ^ data[j];         data[j] = data[j] ^ data[i];         data[i] = data[i] ^ data[j];     }      public static void main(String[] args) {         QuickSort  q=new QuickSort();          q.quickSort(0,q.data.length-1);          System.out.print(Arrays.toString(q.data));     } } 

七：堆排序

1、什么事堆排序：堆排序(Heapsort)是指利用堆积树（堆）这种 数据结构 所设计的一种 排序算法 ，它是选择排序的一种。

可以利用 数组 的特点快速定位指定索引的元素。堆分为大根堆和小根堆，是完全二叉树。大根堆的要求是每个节点的值都不大于其父节点的值，

即A[PARENT[i]] >= A[i]。在数组的非降序排序中，需要使用的就是大根堆，因为根据大根堆的要求可知，最大的值一定在堆顶。

2、参考代码：

 package cn.edu.heapsort;  import java.util.Arrays;  /**  * Description:堆排序  * Author: Hey  * Date: 2015/12/7  */ public class HeapSort {      private int size;     private Node[]nodes;     private int elms;      public HeapSort(int size){         elms=0;         this.nodes=new Node[size];     }      public boolean insert(int value){         if(elms>=value)             return false;         Node node=new Node(value);         nodes[elms]=node;         trickUp(elms++);          return true;     }      public Node remove(){         Node temp=nodes[0];         nodes[0]=nodes[--elms];         trickDown(0);         return temp;     }      private void trickUp(int index){          int parent=(index-1)/2;         Node temp=nodes[index];         while(index>0&&nodes[parent].value<temp.value){             nodes[index]=nodes[parent];             index=parent;             parent=(parent-1)/2;         }         nodes[index]=temp;     }      private void trickDown(int index){          Node temp=nodes[0];         int largeChild=0;          while(index<elms/2){             largeChild=maxNode(index);             if(temp.value>nodes[largeChild].value)                 break;             else{                 nodes[index]=nodes[largeChild];                 index=largeChild;             }         }         nodes[index]=temp;     }      public static void main(String []args){          HeapSort h=new HeapSort(10);         h.insert(10);         h.insert(23);         h.insert(12);         h.insert(17);         h.insert(33);          h.print();         System.out.println(h.remove());         System.out.println(h.remove());         System.out.println(h.remove());         System.out.println(h.remove());         System.out.println(h.remove());      }      private void print() {         System.out.println(Arrays.toString(nodes));     }      private int maxNode(int parent){         int left=parent*2+1;         int right=parent*2+2;          if (right<elms&&nodes[left].value<nodes[right].value)             return right;         else             return left;     }       private class Node{          public int value;          public Node(int value){              this.value=value;          }           @Override          public String toString() {              return "HeapSort{" +                      "value=" + value +                      '}';          }     }  }