[数据结构与算法]排序算法（待完善）java版

1、冒泡排序

思想：升序：从数组第2个数开始与前一个数比较，前大于后则交换位置，然后再比较下一位与前一位，即第三位与第2位，遍历比较一次后最末尾为最大值。然后重新遍历比较，依次选择最大值。最后即为升序数组。

时间复杂度：最好：O(n)一次交换都没有发生，最坏：O(n^2)

最好情况是第一轮比较发现无需交换，则代表数组有序。所以时间复杂度此时为O(n)

最坏则是每一轮都需要比较n次，比较n轮、则时间复杂度为O(n^2)

空间复杂度：O(1)

不需要额外空间

稳定性：是

代码：

public class BubbleSort {
    public static void main(String[] args) {
        int[] a = {1,3,2,5,8,33,77,4,2,4};
        new BubbleSort().sort(a);
        System.out.println(Arrays.toString(a));

    }

    public int[] sort(int[] a){
        int len = a.length;   // 记录数组长度
        int temp = 0;		  // 用做交换时的中间值
        boolean flag = true;  // 标志位，判定是否为最好情况。
        for (int i = 0;i < len;i++){
            for (int j =0; j < len-1;j++){
                if (a[j+1] < a[j]){				// 从数组的第二个与第一个开始比较，这样防止数组下标越界
                    flag = false;			
                    temp = a[j+1];
                    a[j+1] = a[j];
                    a[j] = temp;
                }
            }
            if (flag == true)
                break;
        }
    }
}
输出结果：[1, 2, 2, 3, 4, 4, 5, 8, 33, 77]

2、插入排序

思想：两个数组，一个数组存放无序数据，依次从无序数组中取出值放入另一数组，放入时遍历另一数组找到合适位置插入。

时间复杂度：最好O(n)，每次遍历都只执行一次，最坏：O(n^2)每次都要遍历全部数据。

空间复杂度：O(1)，，空间未增删。

稳定性：是。

代码：

public class InsertSort {
    public static void main(String[] args) {
        int[] a = {1,3,2,5,8,33,77,4,2,4};
        new InsertSort().insertSort(a);
        System.out.println(Arrays.toString(a));
    }
    public int[] insertSort(int[] a){
        // a，数组长度
        int len = a.length;
        // 定义一个需要插入的数组
        int[] b = new int[len];
        //第一个数必定有序，则不用参与比较、
        b[0] = a[0];
        for (int i = 1;i < len;i++){
            // 取出a数组值放入b数组中
            for (int j = 0;j < i;j++){                      // 每一轮插入一个数
                if (a[i] < b[j]){
               // 当a数组中的值与b数组中的值遍历比较时，如出现a值小于b值，则代表应插入到b值位置。
               // 插入操作需要先确定插入位置、然后将所有数据向后移动一位，从最后一个数据开始向后移一位。
                    int lenb=i;                             // i此时就是数组b的长度
                    for (int z = j;z < i;z++){              // i-j就是要移动的次数
                        b[lenb] = b[lenb-1];// 将最后一位移动后下一步需要将倒数第二移动到后一位
                        lenb--;             // 所以我们使用lenb--操作将操作的对象指向倒数第2位
                    }
                    b[j] = a[i];                            // 移动完成后再执行插入操作。
                    break;      // 当找到要插入的位置j后，为了防止继续循环j+1，需要结束这个循环。
                }else if (j == i-1){                        // 当a值在b数组中遍历比较全部后仍然没有合适插入位置，代表a值大于b数组中最大值，则应当直接放入b数组长度的末尾
                    b[i] = a[i];
                }
            }
        }
    }
}
结果：[1, 2, 2, 3, 4, 4, 5, 8, 33, 77]

注：

1、可不用重新创建b数组来存放a数组的值，可直接将a数组分为两部分，左边部分相当于b数组且初始大小为0，随着从右边的数组中拿一个放到左边且排序后，左边有序数组大小就变为1了。

2、在执行插入操作时，需要注意当要插入的数值a与b数组中值全部比较一遍而未发生插入时，代表a值大于b数组中所有值，此时，需要将a值直接放入b数组末尾，而不用执行插入操作。

3、在执行插入操作后需要结束当前循环，因为我们在b数组里循环遍历合适插入的位置后，如位置为3、那么将数值插入后，如果循环不结束而是继续遍历至末尾，是会发生错误的以及是额外的浪费。所以插入操作完成后需要结束此次遍历的循环。

4、上述代码虽然有3个for循环，好像最坏的时间复杂度应该是n ^ 3，实际上，最后两个循环执行的次数总和恒定为n次，如最好情况就是不执行插入操作，而是直接添加到末尾，那么相当于有一个关于插入的循环没有使用（即第三个循环），如最坏情况，需要插入在最前面，那么我们只需要执行n+1次，n次为插入操作时所有数据都需要后移一位，1次是第二个循环刚开始判断的一次，但在时间复杂度运算中，n+1次就相当于n次，所以最坏时间复杂度为O(n ^ 2)。

5、我们可把插入操作封装成方法，方便复用。

3、选择排序

思想：每次从无序数组中选择一个最大值/最小值放入到另一数组中，以达到排序目的

时间复杂度：最好和最坏：O(n^2)

最好、最坏：选择排序恒定需在无序数组遍历一遍选最大值且放入另一数组中，遍历n边，所以最好最坏都一样O（n ^ 2）、但如果添加判断无序数组是否本来就有序、则只需遍历一遍，即为O(n)（此情况不做代码演示）

空间复杂度：O(1)

稳定性：否

代码：

public class SelectSort {
    public static void main(String[] args) {
        int[] a = {1,3,2,5,8,33,77,4,2,4};
        new SelectSort().sort(a);
        System.out.println(Arrays.toString(a));
    }
    // 此处我们将数组a分为两份，左边为有序数组，初始数据为0、右边为无序数组，初始数据为需要排序的数组。
    // 遍历一轮获得最小值后、赋值给左边数组、即为a[0]位置，此时有序数组数据个数为1，依次循环往复添加进有序数组。
    public int[] sort(int[] a){
        int len = a.length;
        int min = 0,minX = 0; // minX用于存放最小值的数组下标
        for (int i = 0; i < len-1;i++){
            min = a[i];
            minX = i;
            for (int j = i+1;j < len;j++){
                // 保证遍历一轮后的数值最小
                if (min > a[j]) {
                    min = a[j];
                    minX = j;
                }
            }
            // 将最小值放入有序数组
            a[minX] = a[i];
            a[i] = min;

        }
    }
}
输出结果：
    [1, 2, 2, 3, 4, 4, 5, 8, 33, 77]

注：

1、我们在存放最小值下标时要考虑到如果遍历一整轮下来都没有发生交换时，即此时我们最初赋值给min的值为最小值，那么在赋值给min时也要考虑到将赋值的下标赋给minX，也将最小值下标初始化一下。

4、归并排序

思想

准备好无序数组与一个空数组，两者空间大小相同。将无序数组两两细分为若干个子数组保证最终子数组只有一个数（如：有8个数，则先分为4、 4两子数组，之后2，2，2，2四个子数组，最终1，1，1，1…八个子数组），然后将子数组两两有序合并、即判定两个子数组头部数字的数值大小，若小则放入等同空间（即两子数组空间和的大小）的空数组中，然后依次判断放入，最终合并为个数为2的四个子数组，然后重复以上方法，直到合并为一个数组，即为排序完成。

时间复杂度：最好与最坏：O(nlog2^n)

空间复杂度：O(n)

稳定性：是

代码：

public class MergeSort {
    public static void main(String[] args) {
        int[] a = {34,22,77,5,77,43,11,23,4,2,0};
        int[] b = new int[a.length];   //临时数组，用来暂时存放a数组排序时的值
        new MergeSort().mergeSort(a,0,a.length-1,b);  //a数组长度减一才为最后的索引值
        System.out.println(Arrays.toString(a));
    }

    // 将两子数组合并
    // a为原数组，left指向左边子数组的第一个，mid指向数组中间、
    // right指向右边子数组的最后一个，b数组为额外空间
    public void merge(int[] a,int left,int mid,int right,int[] b){
        int i = 0;
        
        // 比较两子数组头部数值大小并将小的放入数组b中
        int j = left,k = mid+1;     //j,k为两子数组的起始索引
        
        // 此时的mid与right为左右子数组的空间大小-1，所以需要用等于。
        while (j <= mid && k <= right){       
            if (a[j] <= a[k])
                b[i++] = a[j++];
            else
                b[i++] = a[k++];
        }

        // 可能存在还有数组未进行比较，而另一数组已全部比较、所以此时需要判断两数组是否存在未比较的数字
        // 若存在，则直接放入b数组末尾，因为剩下的数大于之前的数，又由于子数组本为有序。
        // 若左边剩余
        while (j <= mid)
            b[i++] = a[j++];
        
        //若右边剩余
        while (k <= right)
            b[i++] = a[k++];

        // 最终将b数组的值赋值回a数组
       for (int t = 0;t < i;t++){
            a[left+t] = b[t];
       }
    }

    // 归并排序
    public void mergeSort(int[] a,int left,int right,int[] b){
        if (left < right){ // 如果左边数组的首索引不等于右边数组的首索引，说明此时，数组还可分化
            int mid = (left+right)/2; //若left为0，right为2，代表子数组空间大小为2，则mid为1
            mergeSort(a,left,mid,b);  // 将数组分为相等的两个子数组且对左边数组排序
            mergeSort(a,mid+1,right,b); //对右边排序
            merge(a,left,mid,right,b);  //将排序好的两数组合并
         }
    }
}
结果：
    [0, 2, 4, 5, 11, 22, 23, 34, 43, 77, 77]

5、快速排序

思想：我们取数组中一个值为基准值，小于它的放左边，大于放右边。然后在左右两边的数中各取一个值为基准值，再进行小左大右，此时最开始的基准值不参与运算，隐藏细分，直到无值可作为基准值代表排序完成。

时间复杂度：最好：O(nlog2^n)，最坏：O(n ^ 2)

空间复杂度：O(log2^n)~O(n)

稳定性：否

/*
设计思路：
       全程在原数组中操作、先取数组首元素作为基准值、准备两指针（l,r）分别指向数组首
    和尾、然后先使用尾指针（r）从后往前依次判断有没有比基准值小的数、若有、则将此数赋
    给基准值所在的数组下标中。因为此时基准值已经提前被获取到了、可以占用基准值所在的
    数组下标、
        完成赋值后、则此时尾指针指向的数组下标的值又是可被替换的，因为尾指针指向的值
    已经赋值给了首地址即首指针指向的下标。
        那么、此时首指针（l）则从前往后寻找比基准值大的数并赋值给r所在的数组下标、此时
    又存在一个可被赋值的下标，如此循环往复最终会剩下一个由（首指针）l指向的下标可被赋值，
    此时将基准值赋值在此下标下。
        在上述判断大小时，如利用首指针（l）判断比基准值大的数时，若不比基准值大，则无需
    更换位置。所以只需遍历到 r=l 时则代表分化好了，那么剩下的两个子数组也可如此进行分化
        结束标志：当子数组的 r与l开始时便相等，则代表已排序完成。
*/
public class QuickSort {
    public static void main(String[] args) {
        int a[] = {30,40,60,10,20,50};

        QuickSort.sort(a,0,a.length-1);

        System.out.println(Arrays.toString(a));

    }

    public static void sort(int[] a,int l,int r){
        // l与 r不相等则代表需继续排序,
        // 此时判断 r>l，因为已包含当两者相等时则不会继续运行
        if (l < r){
            int x,i,j; // x代表基准值，i代表首指针，j代表尾指针

            i = l;
            j = r;
            x = a[i]; // 将第一个数作为基准值

            // 开始循环判断，直到指针 i<j，代表遍历完成、遍历完成时应该是:j=i
            // 所以此时i<j为false、循环结束
            while (i < j){
                while (i < j && a[j] > x)  // 当数小于x时、a[j]>x不成立，循环结束
                    //因为 j-- 后的 j 代表的下一个需要比较的数、若
                    // 下一个比较导致循环结束，则此时的 j 就是需要的下标
                    j--;
                if (i < j)
                    a[i++] = a[j]; // i++是方便下次直接比较下一个

                while(i < j && a[i] < x)
                    i++; // 从左向右找第一个大于x的数
                if(i < j)
                    a[j--] = a[i];
            }
            // 最后将x赋值
            a[i] = x;
            sort(a, l, i-1); // 递归调用
            sort(a, i+1, r); // 递归调用
        }
    }
}

输出结果：
    [10, 20, 30, 40, 50, 60]

6、希尔排序

思想：设定一个增量（N）为数组大小的一半、将数组分为 N 个子数组，然后子数组进行直接插入排序、一轮后将增量（N）重新设置为 N/2 即一半，并按增量大小重新分割数组、且子数组进行直接插入排序。如此循环往复、最终增量变为1时，即此时分割的子数组数为1时，数组已大致有序，此时进行最后一次直接插入排序即可。因在数组有序时，直接插入排序效率非常高。

时间复杂度：最好：O(n^1.3)、最坏：O(n ^2)

空间复杂度：O(1)

稳定度：否