Java的七大排序

一、各个算法的时间复杂度

二，具体实现

1、直接选择排序

基本思想：在长度为n的序列中，第一次遍历找到该序列的最小值，替换掉第一个元素，接着从第二个元素开始遍历，找到剩余序列中的最小值，替换掉第二个元素，以此类推，直到剩余序列中剩下一个元素为止。

时间复杂度：O（n2）

代码实现：

 1  public static void selectSort(int[] array){
 2         //从序列的第一个元素开始遍历
 3         for(int i=0;i<array.length;i++){
 4             int p=i;//用来记录最小元素的下标
 5             //在剩余序列中查找最小元素
 6             for(int j=i;j<array.length;j++){
 7                 //当查找到比当前值小的元素，用p记录其小标
 8                 if(array[p]>array[j]){
 9                     p=j;
10                 }
11             }
12             //如果p不等于刚开始的值，说明在遍历过程中，有查到比起始值小的元素
13             //否则，起始值就是剩余序列中的最小值，不用进行调整
14             if(p!=i){
15                 int tmp=array[i];
16                 array[i]=array[p];
17                 array[p]=tmp;
18             }
19         }
20     }

2、堆排序

基本思想：将待排序列建成一个大根堆，同时保证根结点的左右子孩子也是一个大根堆，此时整个树的根节点就是该序列的最大值，然后让根节点与最底层的最后一个孩子的值进行交换后，接着将树缩小范围，同时将树的剩余部分又调整成一个大根堆，同时保证根结点的左右子孩子也是一个大根堆，然后让根节点与剩余树的最底层的最后一个孩子的值进行交换后。依次类推，直到剩余树中只剩一个元素为止。

时间复杂度：

步骤：

* 　　　 1.先从最底层的父亲节点开始，判断是否有左右孩子，若有则找出孩子中的较大值，与父亲节点相比较，
*         若值大于父亲节点的值，则与父亲节点值进行交换。
*       2.然后将父亲节点代替了的孩子的子孩子，又作为父亲结点也进行上述的调整。
*       （只对替代了父亲节点的孩子进行调整，因为对于另一个孩子，其没有与父亲结点值进行交换，而且在底下往上
*       调整的时候已经保证了该孩子结点的值是大于它的子孩子的，所以无需在进行调整。）
*       3.当对整棵树调整完后，此时树的根节点存放的值就是整棵树中的最大值。
*       4.接着将存放最大值的这个根结点与最后的那个叶子结点的值交换，并将树的大小减一，然后又将根节点
*         和它的子节点进行调整，以致根节点又存放着整棵树的最大值。以此类推，直到树的大小只剩一个，这时候
*         整棵树从上到下就是按从小到大的顺序排列的。

扩充：

代码实现：

 1     //堆排序
 2     public static void bigHeapSort(int[] array){
 3         if(array == null || array.length == 0){
 4             return;
 5         }
 6         //建立大根堆
 7         //第一次从最底层的父亲节点开始调整，保证各个父亲结点的值是大于等于孩子的值的，且根结点保存整棵树的最大值。
 8         for(int i=(array.length-1-1)/2; i >= 0; i--){     //（不管是左孩子还是右孩子，通过减一除2都可以求的其父亲结点。）
 9             //给i赋初值为(array.length-1-1)/2,是因为根据完全二叉树原理，该结点有孩子，则一定有左孩子，但不一定有右孩子
10             // 所以用左孩子来求父亲结点
11             adjust(array, i, array.length-1);
12         }
13         //将根节点与最后的叶子结点进行交换，然后将叶子节点范围缩小
14         for(int i=array.length-1; i>0; i--){
15             int tmp = array[0];
16             array[0] =array[i];
17             array[i] = tmp;
18             //交换完后，缩小范围，接着调整
19             adjust(array, 0, i-1);
20         }
21     }
22     //堆调整过程
23     public static void adjust(int[] array, int start, int end){
24         int tmp = array[start];
25         //start是根节点，当存在左孩子时，说明该结点有孩子，找出节点孩子的最大值
26         for(int i=2*start+1; i<=end; i=2*i+1){
27             //判断是否有右孩子，找出左右孩子的最大值
28             if(i+1 <= end && array[i] < array[i+1]){//右孩子存在，且右孩子值大于左孩子
29                 i++; // i保存右孩子的下标
30             }
31             //若右孩子不存在，或找到了孩子中的最大值
32             if(array[i] > tmp){ //将孩子的值又与父亲结点的值进行比较，若大于父亲结点，则交换
33                 array[start] = array[i];
34                 array[i]=tmp;
35                 start = i;//更新start,保存为替代了父亲结点的孩子的下标，然后对它的孩子进行调整
36                 //因为之前调整时，只能保证它的结点值是大于它的孩子的。但不能保证替下来的父亲结点的值也是大于它的孩子的值。
37             }else{
38                 break;
39             }
40         }
41         
42     }

3、直接插入排序

基本思想：对待排序列元素进行一个一个的遍历，将遍历到哪个元素，就将那个元素插到前面已排好序的队列的从后往前遍历的第一个小于它的元素的后面。

时间复杂度：

 1  public static void InsertSort(int[] array){
 2         for(int i=0;i<array.length;i++){//对待排元素序列从前往后进行遍历
 3             int tmp=array[i];//记录当前待排元素的值
 4             int j; 
 5             for( j=i-1;j>=0;j--){//对排好序的队列从后往前遍历，找第一个小于它的元素
 6                 if(array[j]<array[i]){
 7                     break; //找到后退出，此时j+1号位就是当前待排元素要插入的位置
 8                 }
 9             }
10             for(int k=i;k>j+1;k--){//在排好序的队列中，将j号后面的元素统一移到下一位
11                 array[k]=array[k-1];  //腾出j+1号位置
12             }
13             array[j+1]=tmp;  //将当前待排元素插到j+1号位置
14         }
15 
16     }

4、希尔

基本思想：对于n个待排序的数列，取一个小于n的整数gap(gap被称为步长)将待排序元素分成若干个组子序列，所有距离为gap的倍数的记录放在同一个组中；然后，对各组内的元素进行直接插入排序。这一趟排序完成之后，每一个组的元素都是有序的。然后减小gap的值，并重复执行上述的分组和排序。重复这样的操作，当gap=1时，整个数列就是有序的。

步骤图：

代码实现：

 public static void shellSort(int[] array){
        int lenght=array.length;
        while (true){
            lenght=lenght/2;
            for(int i=0;i<lenght;i++){  //对所有元素进行排序
                for(int j=i+lenght;j<array.length;j+=lenght){//对每个组中的待排元素进行遍历(第一次是从第二个元素开始的）
                    for(int k=j;k>i;k-=lenght){//对每个组内以排好序的元素进行遍历，
                        if(array[k]<array[k-lenght]){
                            int tmp=array[k-lenght];
                            array[k-lenght]=array[k];
                            array[k]=tmp;
                        }else {
                            break;
                        }
                    }
                }

            }
            if(lenght==1){
                break;
            }
        }
    }

5、冒泡排序

基本思想：对待排序列进行遍历，遍历的同时比较相邻的两个数据，如果前一个元素大于后一个，交换位置，一趟遍历完成后，会将序列元素的最大值移到最后，然后缩小范围，接着进行第二趟遍历，直到范围中元素只剩一个为止。

时间复杂度：

步骤图：

代码实现：

 1   public static void  bubbleSort(int[] array){
 2         for(int i=0;i<array.length;i++){
 3             for(int j=0;j<array.length-i-1;j++){
 4                 //如果前一个值大于后一个，则调整两者位置
 5                 if(array[j]>array[j+1]){
 6                     int tmp=array[j];
 7                     array[j]=array[j+1];
 8                     array[j+1]=tmp;
 9                 }
10             }
11         }
12     }

6.快速排序

基本思想： 1.从队列中取一个数作为它的基准（一般选取队列的第一个值）

　　　　　　 2.将所有比基准大的元素放到它的右边分区，比基准小的元素放到她的左边分区

　　　　 3.对左右两个分区重复第二步，直到各个分区只剩一个元素

步骤图：

代码实现：

    public static void  quickSort(int[] array,int begin,int end ){
        if(array==null&&array.length==0){
            return;
        }
        int left=begin,right=end;
        int p=array[left];//定义基准
        while (left<right) { //一趟遍历结束的条件
            // 从后往前遍历，找比p小的
            while (left < right && array[right] >= p) {
                right--;
            }
            array[left] = array[right];//将查找到小的元素，赋给左指针（此时右指针元素多余）
            //从前往后遍历，找比p大的
            while (left < right && array[left] <= p) {
                left++;
            }
            array[right]=array[left]; ///将查找到大的元素，赋给右指针（此时左指针元素多余）
            array[left]=p;
        }
        //left-1>begin 说明此时左边分区的元素大于一个，要继续排。
        if(left-1>begin) {
            quickSort(array, begin, left-1); //
        }
        //同理
        if(right+1<end){
            quickSort(array,right+1,end);
        }

    }

7.归并排序

思想：将一个有n个记录的无序数组，不断的分割，直到每个分组中只剩一个元素（递的过程）

然后又将相邻的两个数组的元素分别排好序后进行合并（归的过程）

步骤图：

代码实现：

    public static void mergeSort(int[] array1,int begin,int end){
        if(array1==null&&array1.length==0){
            return;
        }
        int first=begin;
        int last=end;
        if(first>=last){
            return;
        }
           int mid=(first+last)/2;
            mergeSort(array1,first,mid);
            mergeSort(array1,mid+1,last);
            merge(array1,first,mid,last);
    }
    public static void merge(int[] array1,int first,int mid,int last){
        int[] array2=new int[last-first+1];
        int i=first;
        int m=mid;
        int j=mid+1;
        int n=last;
        int k=0;
        //当两个数组都还没有空
        while (i<=m && j<=n){
            if(array1[i]<=array1[j]){
                array2[k++]=array1[i++];
            }else {
                array2[k++] = array1[j++];
            }
        }
        while (i<=m){
            array2[k]=array1[i];
            k++;
            i++;
        }
        while (j<=n){
            array2[k]=array1[j];
            k++;
            j++;
        }
        for(int s=0;s<last-first+1;s++){
            array1[first+s]=array2[s];
        }
    }