数据结构中的八大排序算法

/*

    *

    * 快速排序

    *

    * 思想: 

    * 通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,

    * 则可以分别对这两部分记录继续进行排序,已达到整个序列有序的目的

    * 

    * 本质就是,找一个基位(枢轴,分水岭,作用是左边的都比它小,右边的都比它大.可随机,取名base

    * 首先从序列最右边开始找比base小的

    * ,如果小,换位置,从而base移到刚才右边(比较时比base小)的位置(记为临时的high位),这样base右边的都比base大

    * 然后,从序列的最左边开始找比base大的

    * ,如果大,换位置,从而base移动到刚才左边(比较时比base大)的位置(记为临时的low位),这样base左边的都比base小

    * 

    * 循环以上两步,直到 low == heigh, 这使才真正的找到了枢轴,分水岭. 返回这个位置,分水岭左边和右边的序列,分别再来递归

    */

    public static int[] quickSort(int[] arr, int low, int heigh) {

        if(low < heigh)

        {

            int division = partition(arr, low, heigh);

            

            quickSort(arr, low, division - 1);

            

            quickSort(arr, division + 1, heigh);

        }

        return arr;

    }



    // 分水岭,基位,左边的都比这个位置小,右边的都大

    private static int partition(int[] arr, int low, int heigh) {

        int base = arr[low]; //用子表的第一个记录做枢轴(分水岭)记录

        while (low < heigh)

        {  

            //更改下面两个while循环中的<=和>=，即可获取到从大到小排列

            //从表的两端交替向中间扫描，从小到大排列

            while (low < heigh && arr[heigh] >= base)

            {

                heigh--;

            }

            

            // 如果高位小于base,base 赋值给 当前 heigh 位,base 挪到(互换)到了这里,heigh位右边的都比base大

            swap(arr, heigh, low);

            

            while(low < heigh && arr[low] <= base)

            {

                low++;

            }

            

            // 如果低位大有base,

            swap(arr, heigh, low);

        }

        

        //现在low=heigh

        return low;

    }



    //交换大小

    private static void swap(int[] arr, int heigh, int low) {

        int temp = arr[heigh];

        arr[heigh] = arr[low];

        arr[low] = temp;

    }

/**

     * 直接选择排序

     * 直接选择排序每一趟选择出最小的值

     * @param arr

     * @return

     */

    public static int[] selectionSort(int[] arr) {

        for(int i=0;i<arr.length;i++)

        {

            for(int j=i+1;j<arr.length;j++)

            {

                if(arr[i] > arr[j])

                {

                    int temp = arr[j];

                    arr[j] = arr[i];

                    arr[i] = temp;

                }

            }

        }

        return arr;

    }

/**

     * 堆排序

     * 堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法，可以利用数组的特点快速定位指定索引的元素。

     * @param arr

     * @return

     */

    public static int[] heapSort(int[] arr) {

        int i;

        // 将arr构成一个大顶堆

        // 从 0 到 arr.length/2 ,这些都是有孩子的节点

        // 没孩子的节点构造大顶堆就无意义了

        for (i = arr.length / 2; i >= 0; i--)

        {

            heapAdjust(arr, i, arr.length - 1);

        }

        for (i = arr.length - 1; i > 0; i--)

        {

            swap(arr, 0, i);

            // 将arr[0...i-1] 重新构造成一个大顶堆

            heapAdjust(arr, 0, i - 1);

        }

        return arr;

    }



    private static void heapAdjust(int[] arr, int s, int m) {

        int temp, j;

        temp = arr[s]; // 指向临时(相对与root节点)的根节点

        for (j = 2 * s; j <= m; j *= 2) 

        {

            // 如果右节点比左节点大,当前节点移到右节点

            if (j < m && arr[j] < arr[j + 1])

            {

                // 指向右节点

                j++;

            }

            // 当前的父节点大于现在指向的节点

            // 不需要做任何处理

            if (temp >= arr[j])

            {

                break;

            }

            

            // 当前的父节点小于其下的子节点

            // 换位置,把这个子节点替换到父节点

            // 当前这个位置,如果是叶子节点,则它应该是最小的(相对于它的祖先们)

            // 这个方法目的就是交换parent与children的值,构造大根堆

             

            // 执行到这里表明当前节点的父节点(临时根节点小于当前的节点),

            // 把当前节点移到上面,换位置

            // arr[s]被覆盖无所谓,因为temp记了这个值(原来的根节点(相对的parent))

            arr[s] = arr[j];

             

            // 现在把当前的这个元素,看做是临时的parent节点

            // 为了找到此时这个元素的孩子节点,看看是否有比当前这个值还大的

            // 最后s指向 当前遍历到的这个元素

            s = j;

        }

        arr[s] = temp;

    }

/**

     * 插入排序

     * 思想:将一个记录插入到已排好序的有序表中，从而得到一个新的、记录数增1的有序表，

     * 默认将第一个元素看为有序表，一次插入后边的所欲元素

     * 时间复杂度O(n^2)

     * 空间复杂度O(1) 适用于记录数量小的

     * @param arr

     * @return

     */

    public static int[] InsertSort(int[] arr) {

        //从小到大排列

        for(int i=1;i<arr.length;i++)

        {

            //待插入元素

            int temp = arr[i];

            int j;

            for(j=i-1;j>=0 && temp < arr[j];j--)

            {

                //待插入元素小于已有的，就将已有往后挪，直到元素大于插入元素或已经到序列最首端了

                arr[j+1] = arr[j];

            }

            arr[j+1] = temp;

        }

        return arr;

    }

/**

     * 折半插入排序

     * 优点:可以减少"比较"和"移动"的次数

     * @param arr

     * @return

     */

    public static int[] BInsertSort(int[] arr){

        for(int i=1;i<arr.length;i++)

        {

            //待插入元素

            int temp = arr[i];

            int j;

            int low = 0, high = i-1;

            while(low <= high)  //在arr[low..high]中折半查找有序插入的位置

            {

                int m = (low + high)/2;//折半

                if(temp < arr[m])

                {

                    high = m-1;  //插入点在低半区

                }

                else

                {

                    low = m+1;  //插入点在高半区

                }

            }

            

            //记录后移

            for(j=i-1;j>=high+1;j--)

            {

                arr[j+1] = arr[j];

            }

            arr[j+1] = temp;

        }

        return arr;

    }

/**

     * 希尔排序(缩小增量排序)

     * 希尔排序也是插入排序的一种，只是其有增量，而且最后一次增量必须为1

     * @param arr

     * @return

     */

    public static int[] ShellInsert(int[] arr){

        int step = arr.length/2; //取增量

        //保证最后一个增量为1

        while(step >= 1)

        {

            for(int i=step;i<arr.length;i++)

            {

                int temp = arr[i];

                int j = 0;

                

                //根插入排序的区别在这里

                for(j=i-step;j>=0 && temp<arr[j];j-=step)

                {

                    arr[j+step] = arr[j];

                }

                arr[j+step] = temp;

            }

            step /= 2;

        }

        return arr;

    }

/**

     * 归并排序

     * 归并排序是将两个或两个以上的有序表组合成一个新的有序表

     * 时间复杂度 O(nlog2n)

     * @param arr

     * @param tempArray

     * @param left

     * @param right

     * @return

     */

    public static int[] mergeSort(int[] arr, int left,int right) {

        if (left < right)

        {

            // 取分割位置

            int middle = (left + right) / 2;

            // 递归划分数组左序列

            mergeSort(arr, left, middle);

            // 递归划分数组右序列

            mergeSort(arr, middle+1, right);

            //将左数组和右数组进行归并

            Merge(arr, left, middle, right);

        }

        return arr;

    }



    private static void Merge(int[] arr, int left, int middle,int right) {

        int[] tempArray = new int[arr.length];  

        int leftEnd = middle;

        int rightStart = middle+1;

        // 临时数组的下标

        int tempIndex = left;

        int tmp = left;

        

        // 先循环两个区间段都没有结束的情况

        while ((left <= leftEnd) && (rightStart <= right))

        {

            // 左边的比右边的小,先插入左边的

            if (arr[left] < arr[rightStart])

            {

                tempArray[tempIndex++] = arr[left++];

            }

            else

            {

                tempArray[tempIndex++] = arr[rightStart++];

            }

        }

        

        // 判断左序列是否结束

        while (left <= leftEnd)

        {

            tempArray[tempIndex++] = arr[left++];

        }

        

        // 判断右序列是否结束

        while (rightStart <= right)

        {

            tempArray[tempIndex++] = arr[rightStart++];

        }

        

        // 将临时数组中的内容拷贝回原数组中  

        // （原left-right范围的内容被复制回原数组）

        while (tmp <= right) {  

            arr[tmp] = tempArray[tmp++];  

        } 

    }