数据结构Java版的排序算法的简单实现

本是古典何须时尚 2022-06-10 12:57 175阅读 0赞

/**
     * Created by cuboo on 2017/8/16.
     *
     *                                                     |简单选择排序
     *                                     |选择排序-------
     *                                     |               |堆排序
     *                                     |
     *                                     |               |直接插入排序
     *                                     |插入排序-------
     *                                     |              |希尔排序
     *                                     |
     *                                     |              |冒泡排序
     *                内部排序------------|交换排序------
     *                |                   |              |快速排序
     *               |                   |
     *              |                   |归并排序
     *             |                    |
     *            |                    |基数排序
     * 排序 -------
     *             \
     *              \外部排序
     */
    public class SortMethod {
        public static void main(String[] agrs){
            int[] num = new int[]{20,3,1,4,6,5,8,7,9,8};
    //        Insert_Sort(num);
    //        Select_Sort(num);
    //        Select_Sort2(num);
            Insert_Shell(num);
    //        Bubble_Sort(num);
    //        Quick_Sort(num,0,num.length-1);
    //        Select_Sort(num);
    //        Select_HeapSort(num);
    //        BuildHeap(num);
    //        Merge_Sort(num,0,num.length-1);
    //        Radix_Sort(num);
    
            for (int i = 0; i < num.length; i++) {
                System.out.println(num[i]);
            }
    
        }
    
        /**
         * 简单选择排序:不稳定
         * 每次选择最小的元素交换到前面
         * 第一层循环：依次遍历待排数组当中的每一个元素
         * 第二层循环：将第一层的当前元素依次与余下的元素进行比较，交换较小的元素。
         * 时间复杂度：平均情况O(n^2)、最好情况O(n^2)、最坏情况O(n^2)
         * 空间复杂度：O(1)
         * @param num 带排序数组
         */
        public static void Select_Sort(int[] num){
            int min = 0;
            for (int i = 0; i < num.length; i++) {
                min = i;
                for (int j = i+1; j < num.length; j++) {
                    if (num[min] > num[j]){
                        //记录最小值的下标
                        min = j;
                    }
                }
                if (i != min){
                    //交换最小元素
                    int temp = num[i];
                    num[i] = num[min];
                    num[min] = temp;
                }
            }
        }
    
    
        /**
         * 选择排序2
         * @param num
         */
        public static void Select_Sort2(int[] num){
            int min,temp = 0;
            for (int i = 0; i < num.length; i++) {
                min = num[i];
                for (int j = i+1; j < num.length; j++) {
                    if (min > num[j]){
                        //每次比较比较编交换
                        temp = min;
                        min = num[j];
                        num[j] = temp;
                    }
                }
                //插入最小值
                num[i] = min;
            }
        }
    
        /**
         * 堆排序：不稳定，不适合记录较少的排序
         * 假设某个元素为序号为i(Java数组从0开始,i为0到n-1),如果它有左子树，那么左子树的位置是2i+1，如果有右子树，
         * 右子树的位置是2i+2，如果有父节点，父节点的位置是(n-1)/2取整。分为最大堆和最小堆，最大堆的任意子树根节点不小于任意子结点，
         * 最小堆的根节点不大于任意子结点。
         * 步骤1：构建大顶堆
         * 步骤二：循环交换顶和末尾元素，对交换后的n-1个数进行调整堆，使其满足大顶堆
         * 时间复杂度：平均情况O(nlog2n)、最好情况O(nlog2n)、最坏情况O(nlog2n)
         * 空间复杂度：O(1)
         * @param num 带排序数组
         */
        public static void Select_HeapSort(int num[]){
            //首先建立堆
            BuildHeap(num);
            //循环交换第一个和最后一个，调整heap
            for (int i = num.length - 1; i >= 0; i--) {
                //交换第一个和循环后的最后一个
                int temp = num[0];
                num[0] = num[i];
                num[i] = temp;
                //交换后调整heap
                AdjustHeap(num,i,0);
            }
    
        }
    
        /**
         * 建立堆：从最后一个非叶子节点（数组坐标为(num.length - 1) / 2）往上调整堆
         * @param num
         */
        public static void BuildHeap(int num[]){
            //(num.length - 1) / 2 从最后一个非叶子节点往上调整heap
            for (int i = (num.length - 1) / 2; i >= 0 ; i--) {
                //调整heap
                AdjustHeap(num,num.length,i);
            }
    
        }
    
        /**
         * 调整堆：获取当前节点的左孩子节点的坐标，初始化父节点为最大值，
         * 比较父与左孩子节点，记录最大节点坐标
         * 比较右孩子与最大节点坐标，记录最大节点坐标
         * 如果孩子节点大于父节点，则交换父与子节点的值，递归调整左右子节点中最大值的堆。
         * @param num 待排数组
         * @param heapsize 堆大小
         * @param index 当前调整节点
         */
        public static void AdjustHeap(int num[],int heapsize,int index){
            int left_child = 2*index + 1;
            int right_child = 2*index + 2;
            //定义一个int值保存当前序列最大值的下标
            int largest = index;
            //比较左孩子与父节点
            if (left_child < heapsize && num[left_child] > num[index]){
                //记录比父节点大的左孩子的下标
                largest = left_child;
            }
            //比较右孩子与（父节点和左孩子）的最大值
            if (right_child < heapsize && num[right_child] > num[largest]){
                //记录比父节点大的右孩子的下标
                largest = right_child;
            }
            //判断父节点是否小于子节点
            if (index != largest){
                //如果largest不等于index 说明当前的父节点不是最大值，需要交换
                int temp = num[index];
                num[index] = num[largest];
                num[largest] = temp;
                //递归继续调整heap
                AdjustHeap(num,heapsize,largest);
            }
    
        }
    
        /**
         * 插入排序：稳定
         * 将数组中的所有元素依次跟前面已经排好的元素相比较，如果选择的元素比已排序的元素小，则交换。
         * 第一层循环：遍历待排序所有数组元素
         * 第二层循环：将本轮选择的元素与已经排好序的元素组相比较。
         * 时间复杂度：平均情况O(n^2)、最好情况O(n)、最坏情况O(n^2)
         * 空间复杂度：O(1)
         * @param num 带排序数组
         */
        public static void Insert_Sort(int[] num){
            int tem = 0;
            for (int i = 1; i < num.length; i++) { //从1开始，0为待排好的元素
                for (int j = i - 1; j >= 0; j--) { //比较该元素与前面排序好的元素，小于前面元素则交换。
                      if (num[j+1] < num[j]){
                          tem = num[j+1];
                          num[j+1] = num[j];
                          num[j] = tem;
                      }
                }
            }
        }
    
        /**
         * 希尔排序:不稳定
         * 每次将gap折半减小，知道gap=1，初始gap=length/2。
         * 第一层循环：gap/2
         * 第二层循环：步长为gap的直接插入排序
         * 第三层循环：步长为gap的直接插入排序
         *  时间复杂度：平均情况O(n^1.3)、最好情况O(n)、最坏情况O(n^2)
         * 空间复杂度：O(1)
         * @param num 待排序数组
         */
        public static void Insert_Shell(int[] num){
            int gap = num.length / 2;
            while (gap >= 1){
                for (int i = gap; i < num.length; i = i+gap) {
                    for (int j = i-gap; j >=0; j = j-gap) {
                             if (num[j] > num[j+gap]){
                                 int temp = num[j];
                                 num[j] = num[j+gap];
                                 num[j+gap] = temp;
                             }
                    }
                }
                gap /= 2;
            }
    
        }
        /**
         * 希尔排序改进排：不稳定
         * 将待排序数组按照步长gap进行分组，如果每组第一个元素小于最后一个元素则交换每组的第一个和最后一个元素；
         * 第一层循环：gap/2
         * 第二层循环：gap第一个和最后一个比较和交换
         * 时间复杂度：(n-gap)的和 = n*log2N-n/2(1+1/2+1/4+...) = O(n*log2n)
         * 空间复杂度：O(1)
         * @param num
         */
        public static void Insert_ShellSort(int[] num){
            int gap = num.length / 2;
            while (gap >= 1){
                for (int i = 0; i < num.length - gap; i++) {
                    if (num[i] > num[i+gap]){
                        int temp = num[i];
                        num[i] = num[i+gap];
                        num[i+gap] = temp;
                    }
                }
                gap /= 2;
            }
        }
    
        /**
         * 冒泡排序:稳定
         * 将带排序序列的左右元素，依次比较，保证右边的元素始终大于左边的元素。
         * 第一层循环：循环n-1次
         * 第二层循环：一次比较，以较大的元素到右边，每次循环范围递减
         * 时间复杂度：平均情况O(n^2)、最好情况O(n^2)、最坏情况O(n^2)
         * 空间复杂度：O(1)
         * @param num
         */
        public static void Bubble_Sort(int[] num){
            for (int i = 1; i < num.length; i++) {
                for (int j = 0; j < num.length - i; j++) {
                    if (num[j] > num[j+1]){
                        int temp = num[j];
                        num[j] = num[j+1];
                        num[j+1] = temp;
                    }
                }
            }
        }
    
        /**
         * 快速排序:不稳定
         * 从带排序序列当中选择一个基准数(pivot)（一般选第一个)
         * 将序列当中的所有元素依次遍历，比pivot大的位于其右侧，小的位于其左侧
         * 重复以上直到只有一个元素子集。
         * 时间复杂度：平均情况O(nlog2N)、O(nlog2N)、最坏情况O(n^2)
         * 空间复杂度：O(logN)
         * @param num
         * @param start
         * @param end
         */
        public static void Quick_Sort(int[] num,int start,int end){
            if (start < end){
                int i = start;
                int j = end;
                int pivot = num[start];
                while (i < j){
    //                从右开始向左寻找第一个小于pivot的值
                    while (i < j && num[j] >= pivot){
                           j--;
                    }
    //                将小于pivot的值移到左边
                    if (i < j){
                        num[i] = num[j];
                        i++;
                    }
    //                从左开始向右寻找第一个大于pivot的值
                    while (i < j && num[i] < pivot){
                        i++;
                    }
    //                将大于pivot的值移到右边
                    if (i < j){
                        num[j] =  num[i];
                        j--;
                    }
                }
    //          前面循环完   i = j 时
                num[i] = pivot;
    //                左侧序列继续排序
                Quick_Sort(num,start,i-1);
    //                右侧序列继续排序
                Quick_Sort(num,i+1,end);
            }
        }
    
        /**
         * 归并排序：稳定
         * 先使每个子序列有序，再使子序列段间有序
         * @param num 待排序数组
         * @param start 待数组开始下标
         * @param end 待数组结束下标
         * 时间复杂度：平均情况O(nlog2N)、O(nlog2N)、最坏情况O(nlog2N)
         * 空间复杂度：O(n)
         * 例子：简单运行过程
         * 5 3 4 2
         * 5 3 | 4 2 分成左右两组
         * (5) (3) | 4 2 左边组递归分成两组
         * (3 5) | 4 2 合并左边两组进行排序
         * (3 5) | (4) | (2) 右边组递归分成两组
         * (3 5) | (2 4) 合并右边两组进行排序
         * (2 3 4 5) 合并左右两组
         */
        public static void Merge_Sort(int num[],int start,int end){
            if (start < end){
                int mid = (start + end) / 2;
                //左右递归分割成1个元素再进行合并
                //使左边组有序
                Merge_Sort(num,start,mid);
                //使右边组有序
                Merge_Sort(num,mid+1,end);
                //合并左右数组
                MergeArray(num,start,mid,end);
            }
        }
    
        /**
         * 合并左右两组数组并使其有序
         * @param num 待排序数组
         * @param first 左边组起始下标
         * @param mid 左边组结束下标
         * @param last 右边组结束下标，mid+1为右边组起始下标
         */
        public static void MergeArray(int num[],int first,int mid,int last){
            int temp[] = new int[last-first+1];
            int i = first,j= mid+1,k = 0;
            while(i <= mid && j <= last){
                //当左右两组都有数时进行比较，取较小的数
                if (num[i] <= num[j]){
                    temp[k++] = num[i++];
                }else {
                    temp[k++] = num[j++];
                }
            }
            //如果左边组还有数
            while (i <= mid){
                temp[k++] = num[i++];
            }
            //如果右边组还有数
            while (j <= last){
                temp[k++] = num[j++];
            }
            //temp有序数组复制到原数组的（左边组+右边组区间）
            for (int l = 0; l < temp.length; l++) {
                num[first++] = temp[l];
            }
        }
    
        /**
         * 基数排序：稳定
         * #排序的顺序跟序列中最大数的位数相关
         * 首先根据个位数的数值，在走访数值时将它们分配至编号0到9的桶子中，
         * 然后是十位，百位到最大数的位数。
         * 时间复杂度：平均情况O(d(n+rd)、最坏情况O(d(n+rd)
         * 空间复杂度：O(rd)
         * r代表基数，d代表长度，n代表关键字的个数
         * @param num
         */
        public static void Radix_Sort(int num[]){
            //寻找序列中的最大数
            int max = num[0];
            for (int i = 0; i < num.length; i++) {
                if (max < num[i]){
                    max = num[i];
                }
            }
            //确定序列中的最大元素的位数
            int times = 0;
            while (max > 0){
                max = max / 10;
                times++;
            }
            //基数排序
            //建立一个桶
            int count[][] = new int[10][num.length];
            //记录每个桶中记录个数
            int count_0[] = new int[10];
            //从低位到高位依次执行循环分配到桶
            int radix = 1;
            int l = 0;
            for (int i = 1; i <= times; i++) {
                //进行位数分配到桶
                for (int j = 0; j < num.length; j++) {
                    //计算出个、十、百位...
                    int p = (num[j] / radix) % 10;
                    //记录个、十、百位...的数据
                    count[p][count_0[p]] = num[j];
                    //记录个、十、百位...的记录数
                    count_0[p]++;
                }
                //复杂桶中数据到num
                for (int j = 0; j < 10; j++) {
                    if (count_0[j] != 0){
                        for (int k = 0; k < count_0[j]; k++) {
                            num[l++] = count[j][k];
                        }
                        //清空记录个数
                        count_0[j] = 0;
                    }
                }
                radix *= 10;
                l = 0;
            }
    
        }
    }