各大排序算法实现

冒泡、插入、选择、归并、快速、堆、基数、计数

冒泡排序

//冒泡排序：每轮遍历相邻冒出最大者，冒到最[右边]，每轮冒出一个确定数
static void bubbleSort(int[] array)
{
    //只进行length-1轮
    for (int i=0;i<array.length-1;i++)
        //每一轮中，[0,length-i]为待排序区
        //最后一个元素不参与比较，否则越界
        for (int j=0;j<array.length-i-1;j++)
            //只交换向量位置
            if (array[j]>array[j+1])
            {
                int temp = array[j];
                array[j] = array[j+1];
                array[j+1] = temp;
            }
}

插入排序

//插入排序：每轮选一个数，在已排区（在[左边]）查找合适位置插入
static void insertSort(int[] array)
{
    //array[i]为待插入数
    for (int i=1;i<array.length;i++)
        //遍历被插区（已排区）
        for (int j=0;j<i;j++)
            //左插：将i插第一个大于j的数左边，[插入点~已排区边界]进行数组位移（易错）
            if (array[j] > array[i]) {
                //注意这里怎么移动，移动的边界
                int temp = array[i];
                for (int k=i;k>j;k--)
                    array[k] = array[k-1];
                array[j] = temp;
                break;
            }
                //如果没有，插最右边，也就是待插数原地不动，不用执行其它操作
}

选择排序

//选择排序：每轮遍历交换选出最大者，从左边开始大轮遍历，与大轮计数位交换，每轮交换出一个确定数
static void chooseSort(int[] array)
{
    for (int i=0;i<array.length-1;i++)
        for (int j=i+1;j<array.length;j++)
            if (array[i]>array[j])
            {
                int temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }
}

归并排序

//归并排序：见过程，特别注意实现细节以及对递归的理解
static class mergeSort
{
    //在递归设计中，要有终止（继续）递归条件，且要有执行体（解决子问题的具体操作）；在归并中，执行体为Merge，但最小子问题是不用Merge的
    //也就是说执行体也有条件（即Left<Right），叶子结点不用执行Merge操作，与递归条件是一样的（叶子结点不用再继续递归）
    //那么我们就将执行体写如递归判断条件中去！

    //合并步骤
    static void merge(int[] array,int left,int mid, int right)
    {
        int[] array_merge = new int[array.length];
        //注意这里的初值易错，这里是截取出了一段left~right之间的数进行merge
        int i=left,j=mid+1,array_index=left;
        //比较合并
        while(i<=mid&&j<=right)
            if (array[i]<array[j])
                array_merge[array_index++] = array[i++];
            else
                array_merge[array_index++] = array[j++];

        //末尾未参与比较直接确定大小的数据
        while(i<=mid)
            array_merge[array_index++] = array[i++];
        while(j<=right)
            array_merge[array_index++] = array[j++];

        //复制回原数组
        for (int m=left; m<=right; m++)
            array[m] = array_merge[m];
    }

    //递归子问题
    static void sonMerge(int[] array,int left,int right)  //注意命名方便
    {
        //判断是否可以继续递归（切分子问题）：【本子问题可以继续切分条件：left<right】
        if (left<right)
        {
            //计算中间点位置
            int mid = (left+right)/2;    //【注意由于是从0开始标号，那么计算mid的时候是有不同之处的；注意中间点是用＋算】

            //递归入口1
            sonMerge(array,left,mid);
            //递归入口2
            sonMerge(array,mid+1,right);   //注意第二段是从mid+1起始

            //递归出口1，进行merge操作，【merge的是两段，所以递归树叶子结点不merge，放到left<right非叶子结点里】
            merge(array,left,mid,right);
        }
            //递归出口2 （最小子问题从递归出口2出口，不执行操作）
            //对于最后切分成的子问题，由于不满足left<right了，那么其执行体就直接跳过上面的if到这里来-递归出口2，也就是不执行任何操作
            //然后递归栈就推出了最小子问题（不merge），然后回到上一个子问题，即在if里的递归出口处！
            //更多递归细节见再探递归
    }

    static void mergeSort(int[] array)
    {
        sonMerge(array,0,array.length-1);
    }
}

快速排序

//快速排序
static class fastSort
{
    //快排子问题执行体[partition]-解荷兰国旗问题：在序列中选择一个元素（这里默认最左边元素），将小于它的放在左边，大于它的放在右边，最后再赋值给边界元素
    //函数返回值为本子问题选择元素确定的最终位置（以便切割）
    //关键点：先右后左（先右边界移动，再左边界移动）
    static int hollandFlag(int[] array,int left,int right)
    {
        int temp = array[left];
        while(left<right)
        {
            //注意边界的处理，直接赋值而没有交换，巧妙设计流程使得信息没有损失
            //赋值的顺序一定是满足【先将右边界不满足数放到左边界上】，【再将左边界不满足数放到右边界上】，【第一次发生的必然是先将右边界不满足数放到左边】
            //而左边界第一个数是基准数已被记录，可以被直接覆盖，然后边界相遇的时候的那个点必定已经赋值给左/右了，那么基准数直接覆盖相遇点即可
            while (left < right && array[right] >= temp)  //注意等于情况，不然遇到第一个等于的就无限循环了
                right--;
            array[left] = array[right];   //将不满足要求的右边界数（right指针目前指向）放左边界数（第一个为temp，默认交换）
            while (left < right && array[left] <= temp)
                left++;
            array[right] = array[left];  //将不满足要求的左边界数放右边界上
        }
        array[left] = temp;  //最后将基准值放到相遇处
        return left;
    }

        //快排递归子问题；注意与归并排序子问题的区别
        //①快排子问题的切分：left~上轮确定位置，上轮确定位置~right
        //②快排子问题是前向顺序，即先执行荷兰国旗子问题，再进行切分
    static void sonFastSort(int[] array,int left,int right)
    {
        if (left<right)
        {
            //只有非叶子节点（最小子问题）才会执行荷兰国旗问题
            int temp_index = hollandFlag(array,left,right);

            //递归入口：
            sonFastSort(array,left,temp_index);
            sonFastSort(array,temp_index+1,right);
        }
    }

    //快速排序
    static void fastSort(int[] array)
    {
        sonFastSort(array,0,array.length-1);
    }

}

堆排序

//堆排序
static class heapSort
{
    /*堆的储存结构是一个数组，从0开始（一般是一个完全二叉树，且只有完全二叉树堆才能用数组储存）
 	 * 父节点 i 的左子节点在数组中的位置 (2*i+1);
     * 父节点 i 的右子节点在位置 (2*i+2);
     * 子节点 i 的父节点在位置 (i-1)/2;
     * 结点在数组中的位置也是其完全二叉树的结点标号
     * 关键逻辑：①建堆（从最右子树父节点开始调整到根节点）
     *         ②堆排序（交换根节点与已排序区指针位置，调整根节点）
     * 关键过程：调整（若本节点孩子不符合规则，则调整完该结点继续调整孩子结点，即遍历调整该结点，直到不需要调整或到叶子结点）
     */
    
    //堆排序主函数
    //先建立堆，然后在数组末尾维持一个已排序区，将根节点取出、调整、扩大已排序区
    public static int[] heapSort(int[] array)
    {
        //先建堆
        buildMaxHeap(array, array.length - 1);
        //将堆根(最大值）与堆最末尾元素交换（已排序区在数组末尾，指针左移）
        //这里先在循环外进行一次swap，排序的最后是以swap结尾的
        swap(array, 0, array.length - 1);
        for (int i = 1; i < array.length - 1; i++)
        {
            //进行堆（数组范围0~array.length-1-i)调整，这里都是parent=0开始调整，因为删除的都是根节点
            adjustMaxHeap(array, 0, array.length-1-i);
            //将堆根(最大值）与堆最末尾元素交换（已排序区在数组末尾，指针左移）
            swap(array, 0, array.length - 1 - i);
        }
        return array;
    }

    public static void buildMaxHeap(int[] data, int lastIndex)
    {
        //(lastIndex-1)/2即为最右下子树父节点；因为插入第i个节点，那就要从第i个节点开始调整到根节点
        for (int i=(lastIndex-1)/2; i>=0; i--)
            adjustMaxHeap(data, i, lastIndex);
    }
		
    //以parent为根节点，对堆data（范围为parent~lastindex）进行调整
    public static void adjustMaxHeap(int[] data, int parent, int lastIndex)
    {
        /*从parent开始进行遍历调整该子结点*/
        //【当已经没有孩子结点的时候，停止遍历】
        while (2*parent+1 <= lastIndex)
        {
            /*这一段用于找到最大孩子index，判断左右孩子存在性和谁更大*/
            //先假定最大孩子是左孩子
            int maxChildIndex = 2*parent + 1;
            // 如果当前左孩子不是末尾元素
            if (maxChildIndex < lastIndex)
            {
                // 如果左孩子小于右孩子,取右孩子下标，即
                if (data[maxChildIndex] < data[maxChildIndex + 1])
                    maxChildIndex++;
            }
            
            /**比较当前父节点和最大孩子节点**/
            if (data[parent] < data[maxChildIndex])
            {
                //不符合堆设定，交换parent和最大孩子
                swap(data, parent, maxChildIndex);
                //【继续向下调整，以maxChildIndex为根节点调整】（继续执行下一层while循环）
                parent = maxChildIndex;
            } else
                //【当该结点符合规则，停止遍历】
                break;
        }
    }

    public static void swap(int[] data, int i, int j)
    {
        int temp = data[i];
        data[i] = data[j];
        data[j] = temp;
    }
}

基数排序

public static int[] radixSort(int[] array) 
{
    //找到最大那个元素
    int max = 0;
    for (int i = 0; i < array.length; i++) {
        max = array[i] > max ? array[i] : max;
    }
 
    //记录最大那个元素的位数time
    int time = 0;
    while (max > 0) {
        time++;
        max /= 10;
    }
 	
    //一个元素类型为List的List！，List里的每个子list就是桶，有基数个桶（比如10进制排序，那就有10个桶）
    List<ArrayList<Integer>> queue = new ArrayList<>();
    //初始化【基数个桶】
    for (int i = 0; i < 10; i++) 
        queue.add(new ArrayList<>());
    
 	//循环time次，每一次排序一个位置！
    for (int i = 0; i < time; i++) 
    {
        // 按位d【对原数组】进行【一趟排序】
        for (int j = 0; j < array.length; j++) 
        {
            //使用Math.pow(10, i + 1)来方便遍历10,100,1000,10000各个位
            //先用根据外层循环的i得到【内存循环的数组元素】在【当前排序的位】的值
            int d = array[j] % (int) Math.pow(10, i + 1) / (int) Math.pow(10, i);
            //获取第d个桶
            ArrayList<Integer> list = queue.get(d);
            //将这个数加入第d个桶中
            list.add(array[j]);
            //将修改后的桶赋值回大list
            queue.set(d, list);
        }
 
        // 【把queue进行过一趟排序的数据拷贝回原数组】
        //count设计为数组下标计数
        int count = 0;
        //遍历每个桶（基数为10,所以10个桶）
        for (int k = 0; k < 10; k++) 
            //将桶内的数据复制回数组
            while (queue.get(k).size() > 0) 
            {
                array[count] = queue.get(k).get(0);
                queue.get(k).remove(0);
                count++;
            }
    }
    return array;
}

计数排序

public static int[] countingSort(int[] array) 
{
    //先找到最大元素
    int max = 0;
    for (int i = 0; i < array.length; i++) 
        max = array[i] > max ? array[i] : max;
    
    //开辟最大元素这么大的数组
    int[] count = new int[max + 1];
    for (int i = 0; i < array.length; i++) 
        count[array[i]]++;
 
    //开始计数，每个元素对应到数组下标，数组内容即为该下标的计数次数
    int sum = 0;
    for (int i = 0; i < count.length; i++) 
    {
        if (count[i] > 0) 
            for (int j = 0; j < count[i]; j++) 
                array[sum + j] = i;
        sum += count[i];
    }
    return array;
}