Java 数据结构与算法 冒泡排序、快速排序、归并排序

冒泡排序和快速排序的思想是交换，而归并排序的思想是分治。先介绍交换类的排序。

    交换类的排序，少不了交换。根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。

冒泡排序

这里直接贴上冒泡排序的优化过的代码。

    //优化的冒泡排序
    public void bubbleSort(int[] array) {
        for (int i = 0; i < array.length - 1; i++) {
            boolean flg = false;
            for (int j = 0; j < array.length - 1 - j; j++) {
                if (array[j] > array[j + 1]) {
                    swap(array, i, j);
                }
            }
            if (!flg) {
                break;
            }
        }
    }
    
    private void swap(int[] array, int i, int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }

冒泡排序的特性总结

（1）冒泡排序是一种非常容易理解的排序

（2）时间复杂度：O(N^2)

（3）空间复杂度：O(1)

（4）稳定性：稳定

快速排序（递归）

    快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

    这里介绍经过优化的快速排序。快速排序的过程和二叉树的前序遍历非常像，可以在写代码前想一想二叉树前序遍历经过。整个的过程中，先找到划分的基准，然后分成左右两颗子树，进行排序操作。划分的基准分为Hoare法，挖坑法，前后指针法等。这里介绍较为简单的挖坑法。

    所谓挖坑法就是以0下标为基准，然后low和high靠近。以左边下标为基准，需要high先走。其中，high遇到比基准小的，就把low对应下标元素赋值给high，这时候开始走low，low遇到比基准大的，就把high下标元素赋值给low，一直到low和high相遇。

    这样进行多次的排序，到最后就能够将元素排成有序的。不过要注意的是基准的选法。直接以第一个元素下标为基准有时候是不合理的，会导致单二叉树生成。所以要基准的取法也是有讲究的。基准的选法通常采用三数取中法。通过数组下标计算出中间下标，然后在这三个数种选择一个比较合理，中间的数。这个数要尽可能的把二叉树分成均等的左右两颗子树。比如通过下标得出3个数分别是5  6  8，那么选择6。又如果是8  5  6，那么还是选择6。然后和左边开始下标的数字进行交换。

    在数据趋于有序的时候，可以直接采用直接插入排序。

    public void quickSort(int[] array) {
        quick(array, 0, array.length - 1);
    }
 
    //按照二叉树前序遍历的方式编写代码
    //前序遍历 根-左-右
    private void quick(int[] array, int left, int right) {
        if (left >= right) return;
 
        //在某个区间的时候，使用直接插入排序，优化的区间内的比较
        //范围选择15，完成后直接退出排序
        if (right - left + 1 <= 15) {
            //进行插入排序：
            insertSortRange(array, left, right);
            return;
        }
 
        //三数取中法,这个是优化快速排序的关键
        int index = medianOfThreeIndex(array, left, right);
        //然后和第一个下标数字进行交,好的基准在数组第一个下标处
        //保证左右子树是均等的
        swap(array, left, index);
 
        //挖坑法进行排序
        int pivot = partitionHole(array, left, right);
 
        //左子树继续排序
        quick(array, left, pivot);
        //结束后右子树继续排序
        quick(array, pivot + 1, right);
    }
 
    //三数取中法
    private int medianOfThreeIndex(int[] array, int left, int right) {
        //计算中间节点的下标
        int mid = left + ((right - left) >>> 1);
        //将left,mid,right下标的数进行比较,选出这三个数中的中间数
        //中间的数不一定是中间下标的数,比如6  5  8,中间数6要进行比较得出
        //寻找的算法不是唯一的
        if (array[left] < array[right]) {
            //中间和左边比较,是否中间比左边小
            //不能直接比较右边比如 6 5 8
            //左大于右的前提下,左大于中?中大于右?
            if (array[mid] < array[left]) {
                return left;
            } else if (array[mid] > array[right]) {
                return right;
            } else {
                return mid;
            }
        } else {
            //右大于左的前提下,右大于中?中大于左?
            if (array[mid] < array[right]) {
                return right;
            } else if (array[mid] > array[left]) {
                return left;
            } else {
                return mid;
            }
        }
 
    }
    private void swap(int[] array, int left, int right) {
        int tmp = array[left];
        array[left] = array[right];
        array[right] = tmp;
    }
    
    //挖坑法进行排序
    private int partitionHole(int[] array, int low, int high) {
        //数组第一个下标
        int tmp = array[low];
        //相遇说明结束
        while (low < high) {
            //左边作为基准要先从右边开始
            //右边寻找比基准小的才能放到左边
            //大于基准的继续寻找
            while (low < high && array[high] >= tmp) {
                --high;
            }
            //找到后给左边
            array[low] = array[high];
            //左边寻找比基准大的才能放到右边
            //小于基准的继续寻找
            while (low < high && array[low] <= tmp) {
                ++low;
            }
            //找到后给右边
            array[high] = array[low];
        }
        //最后相遇,剩下的一个赋值tmp
        array[low] = tmp;
        return low;
    }
    
    //在范围内直接插入排序
    private void insertSortRange(int[] array, int low, int end) {
        for (int i = low + 1; i <= end; ++i) {
            int tmp = array[i];
            int j = i - 1;
            for (; j >= low; j--) {
                if (array[j] >= tmp) {
                    array[j + 1] = array[j];
                } else {
                    break;
                }
            }
            array[j + 1] = tmp;
        }
    }

快速排序的特性总结

（1）快速排序的综合性能和使用场景都是比较好的，代码看起来长，但是实际上不长；

（2）时间复杂度：O(N*logN)，和二叉树的高度有关；

（3）空间复杂度：O(logN)

（4）稳定性：不稳定

归并排序（递归）

    归并排序是典型的采用分治法的应用。是建立在归并操作上的一种有效的排序算法，将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

    //归并排序
    public void mergeSort(int[] array) {
        //要找到中间的值，需要传入长度
        mergeIntArray(array, 0, array.length - 1);
    }
 
    private void mergeIntArray(int[] array, int low, int high) {
        //分到最后的时候,左边和右边相遇或超过
        //说明到了最后一个了,就直接返回,单个不用排序
        if (low >= high) return;
 
        //寻找中间的值分开
        int mid = low + ((high - low) >>> 1);
        //找到中间的值后,继续分开,一直到成为了单独的一个
        //先去分左边
        mergeIntArray(array, low, mid);
        //左边分完就去分右边
        mergeIntArray(array, mid + 1, high);
        //两边都分完了,就进行排序,使用方法
        //需要传进去low mid high 分别是要排序的开始和结束位置
        merge(array, low, mid, high);
    }
 
    private void merge(int[] array, int low, int mid, int high) {
        //第一个要排序数组的开始和结束位置
        int s1 = low;
        int e1 = mid;
        //第二个要排序数组的开始和结束位置
        int s2 = mid + 1;
        int e2 = high;
 
        //需要在临时变量中进行排序,然后拷贝
        int[] tmpArr = new int[high - low + 1];
        //临时数组的下标
        int tmpArrIndex = 0;
 
        //每一个数组在排序的时候都不能越界,越界了说明排完了
        while (s1 <= e1 && s2 <= e2) {
            //如果第一个数组值大于第二个,就放入第二个
            if (array[s1] > array[s2]) {
                tmpArr[tmpArrIndex++] = array[s2++];
                //否则就是第一个放进去
            } else if (array[s1] < array[s2]) {
                tmpArr[tmpArrIndex++] = array[s1++];
            }
        }
 
        //到这里,说明一个数组完了,但是另一个没有,直接拷贝过去
        while (s1 <= e1) {
            tmpArr[tmpArrIndex++] = array[s1++];
        }
        while (s2 <= e2) {
            tmpArr[tmpArrIndex++] = array[s2++];
        }
 
        //到这里说明数组全部完了,把临时数组数组拷贝到原来数组中
        for (int i = 0; i < tmpArrIndex; i++) {
            //注意原数组不能直接从0下标拷贝,会发生覆盖
            array[i + low] = tmpArr[i];
        }
    }

归并排序特性总结

（1）归并排序思考的更多的是解决在磁盘外排序的问题

（2）时间复杂度：O(N*logN)

（3）空间复杂度：O(N)

（4）稳定性：稳定（三个稳定的排序：直接插入，冒泡，归并）