排序大作战

LeetCode

选择排序（SelectSort)

• 稳定性：不稳定，一定是不稳定的。因为相等大小的数在比较时会蜜汁交换位置，虽然不是他们之间互相交换
• 复杂度：时间O(n^2)。最好情况是合乎条件的有序数组，不用交换。最坏就是合乎条件的逆序数组。每次都要交换。

public class SelectSort {
/**
* 从代码中分析选择排序就是选择一个数作为基准数然后与后面的数进行最小值或最大值的比较。
 * 至于稳定性，一定是不稳定的。因为相等大小的数在比较时会蜜汁交换位置，                           
 * 时间O(n^2)。最好情况是合乎条件的有序数组，不用交换。最坏就是合乎条件的逆序数组。每次都要交换。
*/
    public void sort(int[] nums) {
        for (int i = 0; i < nums.length - 1; i++) {
            int min = nums[i];
            for (int j = i + 1; j < nums.length; j++) {
                if (min > nums[j]) {
                    int temp = min;
                    min = nums[j];
                    nums[j] = temp;
                }
            }
            nums[i] = min;
        }
    }
    public static void main(String[] args) {
        int[] nums = {8, 2, 5, 6, 8, 2};
        SelectSort selectSort = new SelectSort();
        selectSort.sort(nums);
        System.out.println(Arrays.toString(nums));
    }
}

测试结果：

[2, 2, 5, 6, 8, 8]

插入排序（InsertSort)

• 稳定性：稳定。举例，要是前一个数字和当前数字相等，没有任何操作。指针后移。因此相等的两个数的相对位置没有发生变化
• 复杂度：时间O(n^2)。最好情况是合乎条件的有序数组，不用交换也不用移动。最坏就是合乎条件的逆序数组，每次都要交换和移动数组元素。
• 后话：插入排序对于部分有序的数组十分高效，也很适合小规模数组。插入排序也是很多高级排序的中间过程

public class InsertSort {
    /**
     * 插入排序就是结果集不断的满足条件增大。减少使用空间的话就使用原数组。但是也可以新开一个数组专门来放结果。虽然仍然要移动，但是好理解
     * 这里很有意思的利用了数组的特性，从尾部往前，有意思。用了个while循环进行移动，简练。
     * 把当前的数当作一个基准数，只要是前面有比它大的，统统后移，为基准数归位腾出位置。
     */
    public void sort(int[] nums) {
        for (int i = 1; i < nums.length; i++) {
            int temp = nums[i];//寄存nums[i]的值，这个时候就可以改变nums[i]的值了
            int j = i;//使用另一个指针方便描述
            if (nums[j - 1] > temp) {//如果a[j]的前一个数比a[j]大
                while (j >= 1 && nums[j - 1] > temp) {//a[j]前面的数一直比a[j]大，就一直向前寻找，同时移动数字。
                    nums[j] = nums[j - 1];
                    j--;
                }
            }
            nums[j] = temp;//终于找到一个。此时a[j]中的数已经移到a[j+1]中，于是归位
        }
    }
    public static void main(String[] args) {
        int[] nums = {8, 2, 5, 6, 8, 2};
        InsertSort insertSort = new InsertSort();
        insertSort.sort(nums);
        System.out.println(Arrays.toString(nums));
    }
}

测试结果：

[2, 2, 5, 6, 8, 8]

冒泡排序（BubbleSort)

• 复杂度：O（n^2)

public class BubbleSort { 
/**
*原本是最熟悉的，结果没写出来，悲哀，。，。大三了连个冒泡都费时间。原理是理解了得，相邻两个数交换下沉。从尾部开始排好顺序的。
*只是每次都是从数组起始开始，我一直以为是当前数组元素开始
*/
    public void sort(int[] nums) {
        for (int i = 0; i < nums.length - 1; i++) {
            for (int j = 0; j < nums.length - i - 1; j++) {
                if (nums[j] > nums[j + 1]) {
                    int temp = nums[j];
                    nums[j] = nums[j + 1];
                    nums[j + 1] = temp;
                }
            }
        }
    }
    public static void main(String[] args) {
        int[] nums = {8, 2, 5, 6, 8, 2};
        BubbleSort bubbleSort = new BubbleSort();
        bubbleSort.sort(nums);
        System.out.println(Arrays.toString(nums));
    }
}

测试结果：

[2, 2, 5, 6, 8, 8]

错误写法：

  public void sort(int[] nums) {
        for (int i = 0; i < nums.length - 1; i++) {
            for (int j = i; j < nums.length - i - 1; j++) {//这个错误真是不好找，一开始就理解错误也是没有办法
                if (nums[j] > nums[j + 1]) {
                    int temp = nums[j];
                    nums[j] = nums[j + 1];
                    nums[j + 1] = temp;
                }
            }
        }
    }

关于冒泡排序稳定性的思考：
假设有数组[8,3,10,5,8,4],一趟排序后10肯定是在最后[x,x,x,x,x,10],第二趟排序一定会出现[x,x,x,8,8,10]这个数组的状态,这个时刻的指针指向的是第一个8.倘若交换的条件为nums[j]>nums[j+1]则第一个8和第二个8不会发生交换，跳出内循环。倘若条件为nums[j]>=nums[j+1]则第一个和第二个8发生位置交换，因此这种情况下他们的相对位置是发生了改变的，但是，。，。我也解释不了为什么说是不稳定。难道大家都倾向于使用第二种交换条件？一定是我太low了。

桶排序（BucketSort）

• 稳定性：很稳定
• 复杂度：时间O（M+N)M+N),m个桶，n个数
• 后话：时间最快，但是空间最大

public class BucketSort {
    public void sort(int[] nums) {
        int[] array = new int[1000];//桶的数量
        for (int i = 0; i < nums.length; i++) {
            array[nums[i]]++;//相同数字
        }
        for (int i = 0; i < array.length; i++) {
            for(int j=0;j<array[i];j++){
                System.out.print(i+" ");
            }
        }
    }
    public static void main(String[] args) {
        int[] nums = {8, 2, 5, 6, 8, 2};
        BucketSort bucketSort = new BucketSort();
        bucketSort.sort(nums);
    }
}

测试结果：

[2, 2, 5, 6, 8, 8]

快速排序（QiuckSort）

• 稳定性：明显的不稳定
• 复杂度：因为用到了分治的思想，因此一定是与对数有沾边。经科学家论证，快速排序的平均时间为O（NlogN).最坏情况就是数组已经排好序了。假如一个数组是从小到大的排序，走来基准数取0位上的数。从头到尾的挨个交换赶上冒泡了，此时复杂度为O(n^2)

public class QuickSort {
    public void sort(int[] nums, int left, int right) {
        int i = left;
        int j = right;
//递归调用肯定有一个结束条件，而这个结束条件就是在内部判断开始前判断left与right.最后结束的时候子数组大小为1
        if (left >= right) {
            return;
        }
        int temp = nums[left];//设置基准数,与后面两句构成三变量交换，6666
        //退出这个循环的时候，哨兵相遇
        while (i != j) {
            //一定是右边的哨兵先走，。，。，寻找到比基准数小的数停下退出
            while (nums[j] >= temp && i < j) {
                j--;
            }
            //寻找比基准数大的数停下退出
            while (nums[i] <= temp && i < j) {
                i++;
            }
            //交换各自停下的当前数
            if (i < j) {
                int t = nums[i];
                nums[i] = nums[j];
                nums[j] = t;
            }
        }
        //哨兵相遇之后就将基准数归位
        nums[left] = nums[i];
        nums[i] = temp;//到这一步基准数就已经归位了
        //一轮过后就将大数组划分为两个小数组，一边所有的数比刚刚的基准数大，一边比刚刚的基准数小。
        //接下来就是分治对两个小数组执行同样的操作
        sort(nums, left, i - 1);
        sort(nums, i + 1, right);
        return;
    }
    public static void main(String[] args) {
        int[] nums = {8, 2, 5, 6, 8, 2};
        QuickSort quickSort = new QuickSort();
        quickSort.sort(nums, 0, nums.length - 1);
        System.out.println(Arrays.toString(nums));
    }
}

测试结果：

[2, 2, 5, 6, 8, 8]

关于快排稳定性的思考：
假如有一个数组[3,8,4,8,5,10],显然会有一个时刻第一个8会与5互换位置，此时的相对位置发生了改变

希尔排序（ShellSort)

希尔排序的原理：先将待排序的数组元素分成多个子序列，使得每个子序列的元素个数相对较少，然后对各个子序列分别进行直接插入排序，待整个待排序列“基本有序后”，最后再对所有的元素进行一次插入排序。

• 稳定性：不稳定
• 复杂度：

public class ShellSort {
    public void sort(int[] nums) {
        int length = nums.length;
        //确定步长
        for (int gap = length / 2; gap > 0; gap /= 2) {
            //确定了步长也就确定了序列，接下来对序列进行插入排序
            for (int i = gap; i < length; i++) {
                //根据gap抓住突破口，把这个数与序列中其他数进行比较，同样是采用从尾部入手的办法
                int temp = nums[i];
                int j;
                //每隔gap步长个数才是序列中的元素,这里用一个while循环更加简练
                for (j = i - gap; j >= 0; j -= gap) {
                    //如果从序列尾部开始的数比temp大，则当前数字后移，为temp中的数腾出位置
                    if (temp < nums[j]) {
                        //后移gap位才是序列中的数的位置
                        nums[j + gap] = nums[j];
                    } else {
                        break;
                    }
                }
                //已经找到了要插入的位置,j的值表示，j位置上的数比temp中的数小，因此temp中的数应该放在j的后gap位上
                nums[gap + j] = temp;
            }
        }
    }
    public static void main(String[] args) {
        int[] nums = {8, 2, 5, 6, 8, 2};
        ShellSort shellSort = new ShellSort();
        shellSort.sort(nums);
        System.out.println(Arrays.toString(nums));
    }
}

归并排序(MergeSort)

• 稳定性：归并排序是稳定的
• 复杂度：归并排序是一种基于比较排序的渐进最优算法，NlogN

/**
 * Created by XQF on 2016/11/16.
 */
public class MergeSort {
    private static int[] a;
    // 原地归并核心代码，使用辅助数组进行暂存，当然有不使用辅助就可以实现的，在书上有讲，。，没时间对吧。呵呵
    public static void merge(int[] nums, int left, int medium, int right) {
        int i = left;
        int j = medium + 1;
        for (int k = left; k <= right; k++) {// k不一定为0，这有可能是原数组中的一个子数组。因此使用直接复制数组的方法在这里不合适
            a[k] = nums[k];
        }
        for (int k = left; k <= right; k++) {
            if (i > medium) {// i本身是小于medium，但是现在已经比medium大了，说明右半部分已经消耗完了，插入左半部分
                nums[k] = a[j++];
            } else if (j > right) {// 同理,j本身应该是小于right的，但是现在已经比right大了，说明左半部分已经消耗完了，插入右半部分
                nums[k] = a[i++];
            } else if (a[i] > a[j]) {// 如果右半部分的当前值比左半部分的当前值大，则插入左半部分当前值
                nums[k] = a[j++];
            } else {
                nums[k] = a[i++];// 如果右半部分比左半部分小或者等，则插入右半部分
            }
        }
        // 一个循环结束，归并就结束了，归并就是把两个排好序的子数组合并成一个大数组。
        // 一种情况是俩个数组的大小分明
        // 一种情况是你出一张我出一张，比分交替上升
    }
    // 递归回溯的三大步
    // 结束条件
    // 选择
    // 限制(本例没有限制，只有一部分操作)
    //--------------自顶向下，理解是从整个数组入手，然后层层分割，由底往上层层归并。
    public static void sort(int[] nums, int left, int right) {
        if (right <= left) {// 结束条件，必须要右大于左，否则就说明已经排序结束了
            return;
        }
        int medium = (left + right) / 2;
        sort(nums, left, medium);// 选择1，对左半边进行排序
        sort(nums, medium + 1, right);// 选择2，对右半边进行排序
        merge(nums, left, medium, right);// 操作，归并
        //为什么这里就要使用medium这个参数，不使用的话，只知道数组的两头，理论上可以实现归并，应该是很困难,我很懒不用解释了
    }
    public static void main(String[] args) {
        int[] nums = new int[] { 1, 5, 3, 2, 8, 0 };
        a = new int[nums.length];
        sort(nums, 0, nums.length - 1);
        for (int i : nums) {
            System.out.print(" " + i);
        }
    }
}

堆排序（HeapSort)

原理：先来建树，堆是完全二叉树，因此堆又称作优先队列。然后从最后一个非叶结点逐个扫描所有结点。根据需要进行向下调整。

• 稳定性：
• 复杂度：与快排一样是NlogN