Solo  当前访客:0 开始使用

排序算法


  1. 冒泡排序
    是一种简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。
public static void main(String[] args) {
    int[] arrays = {5, 1, 4, 3, 2};
    int temp;
    int isChange;
    for (int i = 0; i < arrays.length - 1; i++) {
        isChange = 0;
        for (int j = 0; j < arrays.length - i - 1; j++) {
            if (arrays[j] > arrays[j + 1]) {
                temp = arrays[j];
                arrays[j] = arrays[j + 1];
                arrays[j + 1] = temp;
                isChange = 1;
            }
        }
        if (isChange == 0) {
            break;
        }
    }
    System.out.println(Arrays.toString(arrays));
}

  1. 选择排序
    是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始(末尾)位置,直到全部待排序的数据元素排完。
public static void main(String[] args) {
        int[] arrays = {5, 1, 4, 3, 2};
        int pos ;
        int temp;
        for (int i = 0; i < arrays.length - 1; i++) {
            pos = 0;
            for (int j = 0; j < arrays.length - i; j++) {
                if (arrays[j] > arrays[pos]) {
                    pos = j;
                }
            }
            temp = arrays[pos];
            arrays[pos] = arrays[arrays.length - 1 - i];
            arrays[arrays.length - 1 - i] = temp;
        }
        System.out.println(Arrays.toString(arrays));
    }

  1. 插入排序
    基本操作就是将一个数据插入到已经排好序的有序数据中,从而得到一个新的、个数加一的有序数据
public static void main(String[] args) {
        int[] arrays = {5, 1, 4, 3, 2};
        int temp;
        for (int i = 1; i < arrays.length; i++) {
            temp = arrays[i];
            int j = i - 1;
            while (j >= 0 && arrays[j] > temp) {
                arrays[j + 1] = arrays[j];
                j--;
            }
            arrays[j + 1] = temp;
        }
        System.out.println(Arrays.toString(arrays));
    }

  1. 快速排序
    通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列
public static void main(String[] args) {
        int[] arrays = {5, 1, 4, 3, 2};
        quickSort(arrays, 0, 4);
        System.out.println(Arrays.toString(arrays));

    }
    public static void quickSort(int[] arr, int L, int R) {
        int i = L;
        int j = R;
        int pivot = arr[(L + R) / 2];
        while (i <= j) {
            while (pivot > arr[i]){
                i++;
            }
            while (pivot < arr[j]){
                j--;
            }
            if (i <= j) {
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
                i++;
                j--;
            }
        }
        if (L < j){
            quickSort(arr, L, j);
        }
        if (i < R){
            quickSort(arr, i, R);
        }
    }

  1. 归并排序

是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide andConquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。

public static void main(String[] args) {
        int[] arrays = {1, 2, 4, 7, 3, 2, 9, 5, 2, 1, 8};
        mergeSort(arrays, 0, arrays.length - 1);
        System.out.println(Arrays.toString(arrays));
    }

    /**
     * 归并排序
     *
     * @param arrays
     * @param L      指向数组第一个元素
     * @param R      指向数组最后一个元素
     */
    public static void mergeSort(int[] arrays, int L, int R) {

        //如果只有一个元素,那就不用排序了
        if (L == R) {
            return;
        } else {
            //取中间的数,进行拆分
            int M = (L + R) / 2;
            //左边的数不断进行拆分
            mergeSort(arrays, L, M);
            //右边的数不断进行拆分
            mergeSort(arrays, M + 1, R);
            //合并
            merge(arrays, L, M + 1, R);
        }
    }


    /**
     * 合并数组
     *
     * @param arrays
     * @param L      指向数组第一个元素
     * @param M      指向数组分隔的元素
     * @param R      指向数组最后的元素
     */
    public static void merge(int[] arrays, int L, int M, int R) {
        //左边的数组的大小
        int[] leftArray = new int[M - L];
        //右边的数组大小
        int[] rightArray = new int[R - M + 1];
        //往这两个数组填充数据
        for (int i = L; i < M; i++) {
            leftArray[i - L] = arrays[i];
        }
        for (int i = M; i <= R; i++) {
            rightArray[i - M] = arrays[i];
        }
        int i = 0, j = 0;
        // arrays数组的第一个元素
        int k = L;
        //比较这两个数组的值,哪个小,就往数组上放
        while (i < leftArray.length && j < rightArray.length) {
            //谁比较小,谁将元素放入大数组中,移动指针,继续比较下一个
            if (leftArray[i] < rightArray[j]) {
                arrays[k] = leftArray[i];
                i++;
                k++;
            } else {
                arrays[k] = rightArray[j];
                j++;
                k++;
            }
        }
        //如果左边的数组还没比较完,右边的数都已经完了,那么将左边的数抄到大数组中(剩下的都是大数字)
        while (i < leftArray.length) {
            arrays[k] = leftArray[i];
            i++;
            k++;
        }
        //如果右边的数组还没比较完,左边的数都已经完了,那么将右边的数抄到大数组中(剩下的都是大数字)
        while (j < rightArray.length) {
            arrays[k] = rightArray[j];
            k++;
            j++;
        }
    }

  1. 希尔排序

是插入排序的一种又称“缩小增量排序”(Diminishing Increment Sort),是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。

public static void main(String[] args) {
        int[] arrays = {1, 2, 4, 7, 3, 2, 9, 5, 2, 1, 8};
        shellSort(arrays);
        System.out.println(Arrays.toString(arrays));
    }
    public static void shellSort(int[] arrays) {
        //增量每次都/2
        for (int step = arrays.length / 2; step > 0; step /= 2) {
            //从增量那组开始进行插入排序,直至完毕
            for (int i = step; i < arrays.length; i++) {
                int j = i;
                int temp = arrays[j];
                // j - step 就是代表与它同组隔壁的元素
                while (j - step >= 0 && arrays[j - step] > temp) {
                    arrays[j] = arrays[j - step];
                    j = j - step;
                }
                arrays[j] = temp;
            }
        }
    }

  1. 堆排序

堆排序(Heapsort)是指利用堆积树(堆)这种数据结构所设计的一种排序算法,它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。堆分为大根堆和小根堆,是完全二叉树。

    public static void main(String[] args) {
        int[] arrays = {1, 2, 4, 7, 3, 2, 9, 5, 2, 1, 8};
        // 完成一次建堆..
        maxHeapify(arrays, arrays.length - 1);
        int size = arrays.length - 1;

        for (int i = 0; i < arrays.length; i++) {
            //交换
            int temp = arrays[0];
            arrays[0] = arrays[(arrays.length - 1) - i];
            arrays[(arrays.length - 1) - i] = temp;
            // 调整位置
            heapify(arrays, 0, size);
            size--;
        }
        System.out.println( Arrays.toString(arrays));
    }
    /**
     * 完成一次建堆,最大值在堆的顶部(根节点)
     */
    public static void maxHeapify(int[] arrays, int size) {
        // 从数组的尾部开始,直到第一个元素(角标为0)
        for (int i = size - 1; i >= 0; i--) {
            heapify(arrays, i, size);
        }
    }

    /**
     * 建堆
     * @param arrays          看作是完全二叉树
     * @param currentRootNode 当前父节点位置
     * @param size            节点总数
     */
    public static void heapify(int[] arrays, int currentRootNode, int size) {
        if (currentRootNode < size) {
            //左子树和右字数的位置
            int left = 2 * currentRootNode + 1;
            int right = 2 * currentRootNode + 2;
            //把当前父节点位置看成是最大的
            int max = currentRootNode;
            if (left < size) {
                //如果比当前根元素要大,记录它的位置
                if (arrays[max] < arrays[left]) {
                    max = left;
                }
            }
            if (right < size) {
                //如果比当前根元素要大,记录它的位置
                if (arrays[max] < arrays[right]) {
                    max = right;
                }
            }
            //如果最大的不是根元素位置,那么就交换
            if (max != currentRootNode) {
                int temp = arrays[max];
                arrays[max] = arrays[currentRootNode];
                arrays[currentRootNode] = temp;
                //继续比较,直到完成一次建堆
                heapify(arrays, max, size);
            }
        }
    }

  1. 基数排序

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

  public static void main(String[] args) {
        int[] arrays = {1, 2, 4, 7, 3, 2, 9, 5, 2, 1, 8};
        radixSort(arrays);
        System.out.println(Arrays.toString(arrays));
    }

    /**
     * 递归,找出数组最大的值
     *
     * @param arrays 数组
     * @param L      左边界,第一个数
     * @param R      右边界,数组的长度
     * @return
     */

    public static int findMax(int[] arrays, int L, int R) {
        //如果该数组只有一个数,那么最大的就是该数组第一个值了
        if (L == R) {
            return arrays[L];
        } else {
            int a = arrays[L];
            int b = findMax(arrays, L + 1, R);//找出整体的最大值

            if (a > b) {
                return a;
            } else {
                return b;
            }
        }
    }

    public static void radixSort(int[] arrays) {
        int max = findMax(arrays, 0, arrays.length - 1);

        //需要遍历的次数由数组最大值的位数来决定
        for (int i = 1; max / i > 0; i = i * 10) {
            int[][] buckets = new int[arrays.length][10];
            //获取每一位数字(个、十、百、千位...分配到桶子里)
            for (int j = 0; j < arrays.length; j++) {
                int num = (arrays[j] / i) % 10;
                //将其放入桶子里
                buckets[j][num] = arrays[j];
            }
            //回收桶子里的元素
            int k = 0;
            //桶
            for (int j = 0; j < 10; j++) {
                //对每个桶子里的元素进行回收
                for (int l = 0; l < arrays.length; l++) {
                    //如果桶子里面有元素就回收(数据初始化会为0)
                    if (buckets[l][j] != 0) {
                        arrays[k++] = buckets[l][j];
                    }
                }
            }
        }
    }

0 0