[数据结构与算法] 《数据结构》之八大排序

5.冒泡排序

代码实现

    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 - i; j++) {
                if(array[j] > array[j + 1]) {
                    swap(array, j, j + 1);
                    flg = true;
                }
            }
            if(!flg) {
                break;
            }
        }
    }

特性总结

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

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

3. 空间复杂度：O(1)

4. 稳定性：稳定

6.快速排序

基本思想

任取待排序元素序列中的某元 素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有 元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止 。

6.1.方法一：Hoare法

?代码实现

    public int partitionHoare(int[] array, int low, int high) {
        int key = low;//记录 key 的下标，交换要用到
        int tmp = array[low];//记录 key 的值，比较大小时用到
        while(low < high) {
            //左边做 key ，右边先走
            //从右往左找比 key 小的值
            while(low < high && array[high] >= tmp) {
                high--;
            }
            //从左往右找比 key 大的值
            while(low < high && array[low] <= tmp) {
                low++;
            }
            swap(array, low, high);
        }
        swap(array, low, key);
        return low;
    }
    public void quick(int[] array, int left, int right) {
        if(left >= right) return;//可能右边没数据
        int pivot = partitionHoare(array, left, right);
        quick(array, left, pivot - 1);
        quick(array, pivot + 1, right);
    }
    public void quickSort(int[] array) {
        quick(array,0,array.length - 1);
    }

画图分析（三个重要注意点）

?时间复杂度

好的情况 O(n*log2^n)? : 此时是一棵完全二叉树，树的高度为 log2^n，每一层左右两边递归的区间是 O(n)，所以时间复杂度为 O(n*log2^n).

?坏的情况 O(n^2) ：此时是棵只有左树或右树的二叉树，此时树的高度就是节点个数，又每一层的递归区间为 O(n)，所以时间复杂度为 O(n^2).

空间复杂度

空间复杂度同理，每一层只用到了一个变量，所以好的情况下是 O(log2^n)，坏的情况下是 O(n)

6.2.方法二：挖坑法

基本步骤

1.把最左边的 key 挖出来存放在一个单独的空间 hole 中；

2.先从右边找一个比 key 小的埋坑，再从左边找一个比 key 大的埋进右边的坑，依次埋坑直? ? ?到相遇；

3.相遇时，将最初的存在 hole 中的数据埋进相遇时的坑位

代码实现

    public int partitionHole(int[] array, int low, int high) {
        int hole = array[low];
        while(low < high) {
            while(low < high && array[high] >= hole) {
                high--;
            }
            //埋坑
            array[low] = array[high];
            while(low < high && array[low] <= hole) {
                low++;
            }
            //埋坑
            array[high] = array[low];
        }
        //把第一个挖出来的元素埋进相遇点的坑位
        array[low] = hole;
        return low;
    }

画图分析

时间复杂度?

挖坑法的patition单独的时间复杂度为 O(n);? 整个排序的时间复杂度还是 O(n*log2^n);

6.3.方法三：前后指针法

基本思想

1.两个"指针"控制除 key 之外的所有数据，一个找大于 key 的，一个找小于 key 的；

2.交换：在没有出现大于 key 之前的交换，都是自己跟自己交换，出现后才是真正的调整；

3.将 key 的值和 prev - 1的值进行交换（因为prev保存的值都是大于key的值）

代码实现

    public int partition(int[] array, int low, int high) {
        int prev = low + 1;//存下标，方便交换
        int key = array[low];//存值，方便比较
        for (int i = low + 1; i <= high; i++) {
            if(array[i] < key) {
                swap(array, prev, i);
                prev++;//当 prev 保存大于 key 值的下标时，此时才不会自己和自己交换
            }
        }
        swap(array, low, prev - 1);
        return prev - 1;
    }

画图分析

时间复杂度

O(n*log2^n)

6.4.快排的优化（三种优化）

为什么要对快排进行优化？？？

三数取中法(优化一)（对排序本身分割数据的一种优化）

代码实现

    private int medianOfThreeIndex(int[] array, int left, int right) {
        int mid = left + (right - left) >>> 1;
        if(array[left] < array[right]) {
            if(array[mid] < array[left]) {
                return left;
            } else if(array[mid] > array[right]) {
                return right;
            } else {
                return mid;
            }
        } else {
            if(array[mid] > array[left]) {
                return left;
            } else if(array[mid] < array[right]) {
                return right;
            } else {
                return mid;
            }
        }
    }
    public void quick(int[] array, int left, int right) {
        if(left >= right) return;
        //在找基准之前先调整数据是数据尽量对半分
        int index = medianOfThreeIndex(array, left, right);
        swap(array, left, index);

        int pivot = partitionHole(array, left, right);
        quick(array, left, pivot - 1);
        quick(array, pivot + 1, right);
    }

区间内的比较的优化（优化二）

     private void insertSortRange(int[] array, int left, int right) {
        for (int i = left + 1; i <= right; i++) {
            int tmp = array[i];
            int j = i - 1;
            for (; j >= 0; j--) {
                if(tmp < array[j]) {
                    array[j + 1] = array[j];
                } else {
                    break;
                }
            }
            array[j + 1] = tmp;
        }
     }   
     public void quick(int[] array, int left, int right) {
        if(left >= right) return;
        //对区间内的比较的优化
        if(right - left + 1 <= 200) {
            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 - 1);
        quick(array, pivot + 1, right);
     }

聚焦与基准相等元素（优化三）

      public static int[] focusSameNum(int[] array,int left,int right,int pivot,int low,int high){
        int pLeft = pivot-1;//左子序列的右端点
        int pRight = pivot+1;//右子序列的左端点

        //聚焦左边
        for(int i = left;i < pivot - 1;i++){
            if(array[pivot] == array[i]){
                //交换之前判断一下 pLeft 位置的值是否等于基准的值
                if(array[pLeft] != array[pivot]) {
                    //不等就交换
                    swap(array, pLeft, i);
                    pLeft--;
                } else {
                    //相等就与前一个交换，继续判断
                    pLeft--;
                }
            }
        }
        low = pLeft;//聚焦后下一次待分割的左子序列的右端点
        //聚焦右边
        for(int i = right;i > pivot + 1;i--){
            if(array[pivot] == array[i]){
                //交换之前判断一下 pRight 位置的值是否等于基准的值
                if(array[pRight] != array[pivot]) {
                    //不等就交换
                    swap(array, pRight, i);
                    pRight++;
                } else {
                    //相等就与后一个交换，继续判断
                    pRight++;
                }
            }
        }
        high = pRight;//聚焦后下一次待分割的左子序列的右端点
        //将这两个端点用数组带回，为下一次分割做准备
        int[] b = new int[2];
        b[0] = left;
        b[1] = right;
        return b;
    }

画图分析优化三：

总结：优化一才是真正意义上的优化，真正解决了递归深度太深导致栈溢出的问题，优化二只是对区间内的比较的一种优化，而优化三可以缩小递归的区间，也可以有效的提高效率，相比优化二来说，优化一和优化三提高效率更明显。

6.5.非递归实现快速排序

基本思想

非递归我们需要借用栈，并且要借助在第一次划分的基础上实现，第一次划分后，将两段数据的左和右入栈，然后开始循环控制出栈入栈，弹出两元素，继续重复第一次的操作，直到栈为空。

代码实现

    public void quickSortNor(int[] array) {
        Stack<Integer> stack = new Stack<>();
        int left = 0;
        int right = array.length - 1;
        //第一次划分
        int pivot = partitionHole(array, left, right);
        //把两段数据的左和右入栈
        if(pivot > left + 1) {
            stack.push(left);
            stack.push(pivot - 1);
        }
        if(pivot < right - 1) {
            stack.push(pivot + 1);
            stack.push(right);
        }
        //弹出两元素，重复第一次的操作
        while(!stack.empty()) {
            right = stack.pop();
            left = stack.pop();

            pivot = partitionHole(array, left, right);
            if(pivot > left + 1) {
                stack.push(left);
                stack.push(pivot - 1);
            }
            if(pivot < right - 1) {
                stack.push(pivot + 1);
                stack.push(right);
            }
        }
    }

画图分析

时间复杂度

O（n log2^n）

?7.归并排序

基本思想

归并排序是一种分治思想的排序，简单来说，就是先把一堆数据分成一个一个有序，然后将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

?代码实现（递归版本）

    private void merge(int[] array, int left, int mid, int right) {
        int s1 = left;
        int s2 = mid + 1;
        int[] tmpArr = new int[right - left + 1];
        int k = 0;
        //两段数据都不为空
        while(s1 <= mid && s2 <= right) {
            // <= 说明归并排序是稳定的
            if(array[s1] <= array[s2]) {
                tmpArr[k++] = array[s1++];
            } else {
                tmpArr[k++] = array[s2++];
            }
        }
        //将剩余子序列中的元素挪到新数组中
        while(s1 <= mid) {
            tmpArr[k++] = array[s1++];
        }
        while(s2 <= right) {
            tmpArr[k++] = array[s2++];
        }
        //拷贝到原数组中
        for (int i = 0; i < tmpArr.length; i++) {
            //i + left 是防止拷贝第二段子序列时，覆盖第一段，且达不到想到的效果
            array[i + left] = tmpArr[i];
        }
    }
    private void mergeSortInternal(int[] array, int left, int right) {
        if(left >= right) return;
        int mid = left + ((right - left)>>>1);
        mergeSortInternal(array, left, mid);
        mergeSortInternal(array, mid + 1, right);
        //边分解边合并
        merge(array, left, mid, right);
    }
    public void mergeSort(int[] array) {
        mergeSortInternal(array, 0, array.length - 1);
    }

画图分析

时间复杂度：O(n log2^n )? 和数据有序无序没有关系，因为每一层都是对半分，所以递归的高度就是完全二叉树的高度，且每一层的归并都是 n。

空间复杂度：O(n)? 从最后一次归并能知道，临时数组的大小就等于原始数组的大小。

稳定性：稳定（两组数据在归并的时候，1<=2就把1放入数组，所以是稳定的）

7.1.非递归实现归并排序

7.2.归并排序的应用场景