算法之排序（Java代码）

短命女 2022-05-31 10:42 175阅读 0赞

*  冒泡排序

> 冒泡排序的思路就是在未排序的序列中从一开始对相邻的两个数依次对比小数往前冒泡，大数向后沉，第一轮结束后最后一个数的位置已经固定，所以仅仅对前面n-1的数进行第二轮排序，依此类推，最终得到的序列则为有序序列。

public int[] bubbleSort(int[] array) {
        int temp;
        for (int i = 1; i < array.length; i++) {
            for (int j = 0; j < array.length - i; j++) {
                if (array[j] > array[j + 1]) {
                    temp = array[j + 1];
                    array[j + 1] = array[j];
                    array[j] = temp;
                }
            }
        }
        return array;
    }

*  快速排序

> 找一个基准值(一般设置为序列第一个),然后让序列元素依次与之对比，将比他小的值放到他左边(前面),将比他大的值放到他右边(后面),然后再取新序列的第一个元素继续如上操作，依次递归得到最后的有序序列。

public int[] quickSort(int[] arr,int low,int height) {
        //判断初始的低位是否比高位低
        if (low < height) {
            //保存首次循环的低位和高位，一般low = 0,height = arr.length - 1
            int initLow = low;
            int initHeight = height;
            //设置基准值为数组第一位
            int base = arr[low];
            while(low < height) {
                //从数组最后依次向前与基准值比对，找到第一个比基准小的数
                while(low < height && arr[height] >= base) {
                    height--;
                }   
                //将高位值放在低位也就是左边
                if(low < height) {
                    arr[low++] = arr[height];
                }
                //从数组的左边也就是开始位置找到第一个比基准值大的数
                while(low < height && arr[low] <= base) {
                    low++;
                }
                //将大的数放到右边
                if (low < height) {
                    arr[height--] = arr[low];
                }
            }
            //将基准值放到数值中
            arr[low] = base;
            //返回调用对基准数左边的数组进行排序
            quickSort(arr, initLow, low - 1);
            //返回调用对基准数右边的数组进行排序
            quickSort(arr, low + 1, initHeight);
        } 
        return arr;
    }

*  插入排序

> 插入排序的规则就像玩扑克摸牌，每摸一张牌对比一次手上的牌，如果比手上的都大就放到最后面，比手上都小就放到最前面如果在中间就把比他大的往后移，然后把它插进去，摸完牌后手上的的牌就是有序的了。

public static void insertSort(int arr[]){
        for(int i = 1;i < arr.length; i++){
            int temp = arr[i];
            int j = i - 1;
            while (j >= 0 && temp < arr[j]){
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = temp;
        }
    }

*  选择排序

> 在乱序数组中假设第一个数位最小，然后依次让后面的数与之对比，一旦有比他小的数就交换他们的位置，一趟下来第一个数就是序列中最小的一个元素了，然后从第二个元素开始重复上面的操作，最终的到就是有序序列了。

public static void selectSort(int[] arr){
        for(int i = 0; i < arr.length - 1;i++){
            for(int j = i + 1;j < arr.length;j++){
                if(arr[j] < arr[i]){
                    swap(arr[i],arr[j]);
                }
            }
        }
    }
    
    public static  void swap(int i, int j) {
        int temp = i;
        i = j;
        j = temp;
    }

*  希尔排序

> 先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为dl的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2

public  static void shellSort(int[] arr, int len) {
        int gap = len;
        while(gap > 1) {
            gap = gap / 3 + 1;
            for(int i = gap; i < len; i++) {
                int end = i - gap;
                int temp = arr[i];
                while (end >= 0) {
                    if (arr[end] < temp) {
                        break;
                    }
                    arr[end + gap] = arr[end];
                    end -= gap;
                }
                arr[end + gap] = temp;
            }
        }
    }

*  归并排序

> 归并排序就是通过递归的方式将待排序列分成若干个序列，保证每个子序列是有序的，然后再将这些有序的子序列合并成一个完整的有序序列。

public void mergeSort(int[] arr,int low,int height) {
        if(low < height) {
            //二路归并，将数组拆分成2个数组
            int mid = (low + height) / 2;
            //分别递归调用mergeSort实现排序
            mergeSort(arr, low, mid);
            mergeSort(arr, mid + 1, height);
            //最后合并两个有序序列
            merge(arr,low,mid,height);
        }else {
            return;
        }
    }
    
    public void merge(int[] arr,int low,int mid,int height) {
        //初始化一个与传入数组相同大小的临时数组
        int[] tempArr = new int[arr.length];
        //临时数组的索引
        int tempIndex = low;
        //右边数组的第一个元素下标
        int rightOne = mid + 1;
        //传入需要合并数组的最左边下标，并保存备用
        int temp = low;
        while(low <= mid && rightOne <= height) {
            if (arr[low] <= arr[rightOne]) {
                tempArr[tempIndex++] = arr[low++];
            } else {
                tempArr[tempIndex++] = arr[rightOne++];
            }
        }
        while(low <= mid) {
            tempArr[tempIndex++] = arr[low++];
        }
        while(rightOne <= height) {
            tempArr[tempIndex++] = arr[rightOne++];
        }
        while(temp <= height) {
            arr[temp] = tempArr[temp++];
        }
    }

*  基数排序

> 基数排序（radix sort）属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或bin sort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用，基数排序法是属于稳定性的排序，其时间复杂度为O (nlog(r)m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的稳定性排序法。

private static void radixSort(int[] array,int d) {
        int n = 1;// 代表位数对应的数：1,10,100...
        int k = 0;// 保存每一位排序后的结果用于下一位的排序输入
        int length = array.length;
        int[][] bucket = new int[10][length];// 排序桶用于保存每次排序后的结果，这一位上排序结果相同的数字放在同一个桶里
        int[] order = new int[length];// 用于保存每个桶里有多少个数字
        while(n<d) {
            // 将数组array里的每个数字放在相应的桶里
            for(int num : array) {
                int digit = (num / n) % 10;
                bucket[digit][order[digit]] = num;
                order[digit]++;
            }
            // 将前一个循环生成的桶里的数据覆盖到原数组中用于保存这一位的排序结果
            for(int i = 0; i < length; i++) {
                // 这个桶里有数据，从上到下遍历这个桶并将数据保存到原数组中
                if(order[i] != 0) {
                    for(int j = 0; j < order[i]; j++) {
                        array[k] = bucket[i][j];
                        k++;
                    }
                }
                order[i] = 0;// 将桶里计数器置0，用于下一次位排序
            }
            n *= 10;
            k = 0;// 将k置0，用于下一轮保存位排序结果
        }
    }

*  计数排序

> 设被排序的数组为A,排序后存储到B，C为临时数组。所谓计数，首先是通过一个数组C\[i\]计算大小等于i的元素个数，此过程只需要一次循环遍历就可以；在此基础上，计算小于或者等于i的元素个数，也是一重循环就完成。下一步是关键：逆序循环，从length\[A\]到1，将A\[i\]放到B中第C\[A\[i\]\]个位置上。原理是：C\[A\[i\]\]表示小于等于a\[i\]的元素个数，正好是A\[i\]排序后应该在的位置。而且从length\[A\]到1逆序循环，可以保证相同元素间的相对顺序不变，这也是计数排序稳定性的体现。在数组A有附件属性的时候，稳定性是非常重要的。

private static int[] countSort(int[] array,int k) {
        int[] C = new int[k+1];//构造C数组
        int length = array.length,sum = 0;//获取A数组大小用于构造B数组 
        int[] B = new int[length];//构造B数组
        for(int i = 0; i < length; i++) {
            C[array[i]] += 1;// 统计A中各元素个数，存入C数组
        }
        //修改C数组
        for(int i = 0; i < k+1; i++) {
            sum += C[i];
            C[i] = sum;    
        }
        //遍历A数组，构造B数组
        for(int i = length-1; i >= 0; i--) {
          B[C[array[i]]-1] = array[i];//将A中该元素放到排序后数组B中指定的位置
          C[array[i]]--;//将C中该元素-1，方便存放下一个同样大小的元素 
        }
        return B;//将排序好的数组返回，完成排序 
    }

*  堆排序

> 堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。堆分为大根堆和小根堆，是完全二叉树。大根堆的要求是每个节点的值都不大于其父节点的值，即A\[PARENT\[i\]\] >= A\[i\]。在数组的升序排序中，需要使用的就是大根堆，因为根据大根堆的要求可知，最大的值一定在堆顶。

public class MaxHeap {
        int[] heap;
        int heapsize;
        public MaxHeap(int[] array) {
            this.heap = array;    
            this.heapsize = heap.length;
        }
        public void BuildMaxHeap() {
            for(int i = heapsize / 2 - 1;i >= 0;i--)
            {
                Maxify(i);//依次向上将当前子树最大堆化
            }
        }
        public void HeapSort() {
            for(int i = 0; i < heap.length; i++)
            {
                //执行n次，将每个当前最大的值放到堆末尾
                int tmp = heap[0];
                heap[0] = heap[heapsize - 1];
                heap[heapsize - 1] = tmp;
                heapsize--;
                Maxify(0);
            }
        }
        public void Maxify(int i) {
            int l = Left(i);
            int r = Right(i);
            int largest;
    
            if(l < heapsize && heap[l] > heap[i])
                largest = l;
            else
                largest = i;
            if(r < heapsize && heap[r] > heap[largest])
                largest = r;
            if(largest == i || largest >= heapsize)//如果largest等于i说明i是最大元素 largest超出heap范围说明不存在比i节点大的子女
                return ;
            int tmp = heap[i];//交换i与largest对应的元素位置，在largest位置递归调用maxify
            heap[i] = heap[largest];
            heap[largest] = tmp;
            Maxify(largest);
        }
        public void IncreaseValue(int i,int val) {
            heap[i] = val;
            if(i >= heapsize || i <= 0 || heap[i] >= val)
                return;
            int p = Parent(i);
            if(heap[p] >= val)
                return;
            heap[i] = heap[p];
            IncreaseValue(p, val);
        }
    
        private int Parent(int i) {
            return (i - 1) / 2;
        }
        private int Left(int i) {
            return 2 * (i + 1) - 1;
        }
        private int Right(int i) {
            return 2 * (i + 1);
        }
    }