十种排序算法

学的东西还是要多分享，分享给别人的过程中才会知道自己原来有的地方并不是很清楚，今天就再复习一次排序算法了，我希望大家看了之后对排序算法能够有进一步的了解，也是对自己知识的巩固~
先了讲讲比较复杂的快速排序好了

快速排序

快速排序的基本思想就是用一个中间值，将待排序的内容分为：小于等于中间值的部分 大于中间值的部分，形成局部有序。然后再递归的排序小于等于中间值的部分、大于中间值的部分。
那么在算法实现上，我们需要两个指针:i、j，其中j的取值范围为0-n-1，用来遍历待分区的数组元素，而i的初始值为-1，用来指向在小于等于中间值部分中的最后一个元素的位置。这样当我们遍历j的时候，我们比较j元素和中间值的大小：如果小于等于中间值，那么意味要将j元素放在i+1的位置上，同时要将i+1，更新最后一个小于等于中间值的元素的位置；如果大于中间值，那么i不变；因此我们可以知道在【0，i】区间内的元素都是小于等于中间值的，而i+1，n-1的范围内时大于中间值的元素，这样下次递归就有目标了。

//快速排序
    public static void quickSort(int[] arrays, int start, int end){

         if(end <= start)return;

         int key = arrays[end];
         int lessIndex = start-1;

         for(int i= start; i < end; i++){

             if(arrays[i] < key){
                 lessIndex++;
                 int temp = arrays[lessIndex];
                 arrays[lessIndex] = arrays[i];
                 arrays[i] = temp;
             }
         }
         lessIndex++;
         arrays[end] = arrays[lessIndex];
         arrays[lessIndex] = key;
        quickSort(arrays, start, lessIndex-1);
        quickSort(arrays, lessIndex+1, end);

    }

堆排序

堆排序和选择排序的思想一致，只不过在堆排序中是通过堆来获得n-1个布局最大值的。所谓的堆的定义：大顶堆：左右子树根节点要小于根节点，同时左右子树也是一个大顶堆。在这个实现中，主要的一个算法是如何在更换了根节点之后，将这个元素下沉到它应该在的位置上。
percDown（int a[]，int root，int max）表示将元素root下沉到合适的位置，然后最大的指针为max。
这样在排序的时候就能够利用这个函数了。

 //8：堆排序
    public static void heapSort(int[] arrays){

         int len = arrays.length;
         if(len <= 1)return;
         for(int i= (len/2-1); i>=0; i--){

             if(2*i+1 < len){//如果存在左子树
                 int maxT = 2*i+1;
                 if(2*i+2 < len && arrays[2*i+2] > arrays[maxT])
                     maxT = 2*i+2;
                 if(arrays[maxT] > arrays[i]){

                     int temp = arrays[maxT];
                     arrays[maxT] = arrays[i];
                     arrays[i] = temp;

                 }
             }
         }
         for(int i=len-1; i>0; i--){

             int temp = arrays[i];
             arrays[i] = arrays[0];
             arrays[0] = temp;
             percDown(arrays, i);

         }
    }

    public static void percDown(int[]arrays, int len){

         int unSetV = arrays[0];
         int i=0;

         while(2*i + 1 < len){//当存在左子树当时候

             int maxT = 2*i + 1;
             if(2*i+2 < len && arrays[2*i+2] > arrays[maxT])
                 maxT = 2*i+2;
             if(arrays[maxT] > arrays[i]){
                 arrays[i] = arrays[maxT];
                 i=maxT;
             }else
                 break;

         }

         arrays[i] = unSetV;

    }

冒泡排序

冒泡排序核心思想就是要用两层for循环，第一层for循环是表明我要找n次最大值（或者最小值），把他们放在他们应该放置的位置上，而第二层for循环解决的就是我怎么找到次的最大值，在冒泡排序中第二次for循环就是通过比较并交换相邻两个元素的值来实现次最大值的寻找，在冒泡排序中交换的次数可能会比较多。

//冒泡排序