Arithmetic

Java-7.十种排序

PineappleCat · 3月6日 · 2021年 265次已读

冒泡排序

冒泡排序是很简答的一种排序方法。顾名思义,数组中最大的元素会像泡泡一样“浮”到队列的末端。主要的思想是通过元素的两两交换,将队列中最大的元素移动到队列的末尾。

冒泡排序是稳定的。因为它是元素两两交换,如果两个元素相等,就不会交换。这样就保证了相同元素的相对位置不变。

平均和最差情况 T(n) = O(n2),最佳情况 T(n) = O(n)。因为平均和最差情况下每次遍历这个长度为 n 数组都只能确定一个元素,所以想要确定全部 n 个元素的位置,时间复杂度就为 n×n。但最佳情况下,如果数组是有序的,那么只要遍历一次就够了,所以时间复杂度是 n

通过相邻两个元素的比较,大的交换到后面,相等的不变。
需要确定数组元素n位每一位的位置要求外层循环次数为n。
内层:
1.第一次循环是确定最后一位数即最大值。循环的次数变为 a.length-0-1
2.第二次循环是确定倒数第二位的最大值,循环的次数变为 a.length-1-1
3.第二次循环是确定倒数第三位的最大值,循环的次数变为 a.length-2-1
4.即内层的循环次数为a.length-i-1

public static void BubbleSort(int[] arr) {
        if (arr.length == 0 || arr.length == 1) {
            return ;
        }
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr.length - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
            // 打印这一轮的排序结果
            System.out.println(Arrays.toString(arr));
        }
        //打印排序后的结果
        System.out.println("排序后结果:");
        System.out.println(Arrays.toString(arr));
    }

选择排序

简单选择排序是时间复杂度上最稳定的排序算法之一。排序方法很简单,每次都从未排序的数组中找到最小的元素,然后放在最前端。

简单选择排序是不稳定的。毕竟它每趟只是选择最小的元素,选哪个可不一定,没办法保证两个相同元素的相对位置。

任何情况下 T(n) = O(n2),所以说它在时间复杂度上稳定嘛。因为无论数组有序或是无序,简单选择排序都会遍历 n 遍这个数组。

在数组里选择一个最小的与第一个互换,再选择一个次最小值与第二个互换。

外层循环次数为n,内层循环次数为i+1到数组长度减1。

        int[] a = {2, 1, 5, 6, 8};
        for (int i = 0; i < a.length; i++) {
            for (int j = i+1; j < a.length; j++) {
            //找到一个小的就和a[i]换,后面循环再与上一个小a[i]的换。
            //可能换多次,因为没有直接找到最小的数与a[i]换
                if (a[j]<a[i]){
                    int t = a[i];
                    a[i] = a[j];
                    a[j] = t;
                }
            }
        }
        for (int j : a) {
            System.out.println(j);
        }

选择排序优化:即避免不必要的比较与交换。

        int[] a = {2, 1, 5, 6, 8};
        for (int i = 0; i < a.length; i++) {
            int pos = i;
            for (int j = i + 1; j < a.length; j++) {
                if (a[pos] > a[j]) {
                    pos = j;
                }
            }
            if (pos != i) {
                int t = a[pos];
                a[pos] = a[i];
                a[i] = t;
            }
        }
        for (int j : a) {
            System.out.println(j);
        }

插入排序

直接插入排序是一种简单直观的排序方法。主要思想是对于未排序的元素,在已排序的元素中从后向前扫描,找到合适的位置后插入。

直接插入排序是稳定的。因为未排序的元素在向前扫描的过程中遇到相同的元素就不会继续向前扫描了,更不会插在它的前面。

平均和最差情况 T(n) = O(n2),最佳情况 T(n) = O(n)。如果这个数组原来就是有序的,那么只需要比较 n-1 次,不需要移动,所以最好情况下的时间复杂度是 n

把第二个插入到第一个保证前两个有序,再把第三个插入到前两个保证有序

        int[] a = {2, 1, 5, 6, 8};
        //从第二位开始插入到i-1位之前,保证i-1位前数据有序。
        for (int i = 1; i < a.length; i++) {
            for (int j = i - 1; j >= 0; j--) {
            //待排序位小于前一位则前一位后移(进行交换)
                if (a[j] > a[j + 1]) {
                    int t = a[j];
                    a[j] = a[j + 1];
                    a[j + 1] = t;
                }
            }
        }
        for (int j : a) {
            System.out.println(j);
        }

插入排序优化:减少交换的次数

        int[] a = {2, 1, 5, 6, 8};
        int i, j, tmp;
        for (i = 1; i < a.length; i++) {
            //从待插入组取出第一个元素。
            tmp = a[i];
            //i-1即为有序组最后一个元素(与待插入元素相邻)的下标
            j = i - 1;
            //注意判断条件为两个,j>=0对其进行边界限制。第二个为插入判断条件
            while (j >= 0 && tmp < a[j]) {
                //若不是合适位置,有序组元素向后移动
                a[j + 1] = a[j];
                j--;
            }
            //找到合适位置,将元素插入。
            a[j + 1] = tmp;

希尔排序

希尔排序是直接插入排序的升级版。主要思想是把一组数组分成了不同的“组”,只有同组元素才能比较和排序。随着排序的进行,“组”会慢慢减少,“组”中的元素也会慢慢增多,数组整体也会慢慢有序。

希尔排序是不稳定的。虽然是否稳定是由该算法代码的具体实现决定的,但这种元素间远距离的交换一般都很难保证相同元素的相对位置。

最差情况 T(n) = O(n2),平均情况 T(n) = O(n1.3),最佳情况 T(n) = O(n)

将数组元素分为若干组,每组元素进行插入排序。

先是大分组,至每个元素自身为一组。

    public static void shellSort(int[] arr) {
        int gap = arr.length;
        while (true) {
            gap = gap / 2;
            for (int k = 0; k < gap; k++) {
                //从分组的第二个元素开始
                for (int l = k + gap; l < arr.length; l += gap) {
                    //待插入的元素
                    int t = arr[l];
                    //有序数组的最后一个元素的下标
                    int pos = l - gap;
                    while (pos >= 0 && t < arr[pos]) {
                        arr[pos + gap] = arr[pos];
                        pos -= gap;
                    }
                    arr[pos + gap] = t;
                }
            }
            //结束条件
            if (gap == 1) {
                break;
            }
        }
    }

另一种思路:

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

快速排序

快速排序是十大排序算法中最经典的一个。主要思想是通过一趟排序将待排序的数组分为独立的两个部分,前半部分都比中间的关键元素小,后半部分都比中间的关键元素大,从而确定了中间的关键元素的位置。

快速排序是不稳定的,毕竟要远距离的调换元素。

最佳和平均情况下 T(n) = O(nlogn),最差情况下 T(n) = O(n2)。快速排序的实现依赖的是递归加二分法,但这个二分法并不是完美的二分法。如果二分法每次正好只分到一边,那么一共就有 n-1 层,所以时间复杂度是 n2;其他情况下一共有logn 层,所以时间复杂度是 n*logn

首先确定第一个元素在排完序数组中的位置,若它的左边或右边还有元素递归实现确认每一边第一个元素在排完序的数组中的位置。

    public static void quickSort(int[] arr, int start, int end) {
        //确定第一个元素的在排完序后的位置
        int temp = arr[start];
        int low = start;
        int high = end;
        while (low < high) {
            while (low < high && arr[high] >= temp) {
                --high;
            }
            arr[low] = arr[high];
            while (low < high && arr[low] <= temp) {
                ++low;
            }
            arr[high] = arr[low];
        }
        arr[low] = temp;
        if (low - 1 > start) {
            quickSort(arr, start, low - 1);
        }
        if (high + 1 < end) {
            quickSort(arr, high + 1, end);
        }
    }

归并排序

归并排序以需要额外空间作为代价,表现比简单选择排序好得多。二路归并排序就是两两排序,然后两个区域一起排序,以此类推。

归并排序是稳定的。因为在使用额外空间的时候,靠前区域的元素只要小于等于靠后区域的元素就能被放进额外空间。

任何情况下 T(n) = O(nlogn)。归并排序主要是靠递归加二分法,每一层的时间代价都是 n 相关,一共有 logn 层,所以时间复杂度是 n*logn。所以无论数组是不是有序的,都会被二分法分为前后两个部分,然后递归下去。

    public static void mergeSort(int[] arr) {
        //分配辅助数组
        int[] temp = new int[arr.length];
        msort(arr, temp, 0, arr.length - 1);
    }

    public static void msort(int[] arr, int[] temp, int left, int right) {
        //如果只有一个元素的区域,那么就不需要继续划分
        //只有元素大于等于2的时候可以进行划分
        if (left < right) {
            //找中间点
            int mid = (left + right) / 2;
            //递归划分左半区域
            msort(arr, temp, left, mid);
            //递归划分右半区域
            msort(arr, temp, mid + 1, right);
            //合并
            merge(arr, temp, left, mid, right);
        }
    }

    public static void merge(int[] arr, int[] temp, int left, int mid, int right) {
        //标记左半区第一个未排序的元素
        int l_pos = left;
        //标记右半区第一个未排序的元素
        int r_pos = mid + 1;
        //临时数组元素的下标
        int pos = left;
        //合并
        while (l_pos <= mid && r_pos <= right) {
            if (arr[l_pos] < arr[r_pos]) {
                //左半区第一个剩余元素更小
                temp[pos++] = arr[l_pos++];
            }else{
                //右半区第一个剩余元素更小
                temp[pos++] = arr[r_pos++];
            }
        }
        //合并左半区剩余的元素
        while (l_pos <= mid){
            temp[pos++] = arr[l_pos++];
        }
        //合并右半区剩余的元素
        while (r_pos <= right){
            temp[pos++] = arr[r_pos++];
        }
        //把临时数组中合并后的元素复制回原来的数组
        while (left<=right){
            arr[left] = temp[left];
            left++;
        }
    }

堆排序

堆排序是利用了最大堆这种数据结构的排序方法。因为每次将堆调整为最大堆后,堆的根结点一定是堆中最大的元素。我们通过不停的取出最大堆的根节点和重新调整为最大堆,就可以一直得到未排序数组的最大值。

堆排序是不稳定的。毕竟远距离元素交换,不好保证相同元素的相对位置。

任何情况下 T(n) = O(nlogn)

大顶堆:即父节点的值比左右孩子结点的值都大。

注意这里的下标的排列顺序。

维护堆得性质

    public static void heapSort(int[] arr, int n) {
        //建堆
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(arr, n, i);
        }
        //排序
        for (int i = n - 1; i > 0; i--) {
            //将最后一个元素与第一个元素进行交换
            int temp = arr[i];
            arr[i] = arr[0];
            arr[0] = temp;
            //重新维护堆的性质,这时最后一个元素是有序的
            //待维护的元素个数为n-1,即为i
            heapify(arr, i, 0);
        }
    }

    /**
     * 维护大顶堆的性质
     *
     * @param arr 存储堆的数组
     * @param n   数组长度
     * @param i   待维护结点的下标
     */
    public static void heapify(int[] arr, int n, int i) {
        int largest = i;
        int lson = i * 2 + 1;
        int rson = i * 2 + 2;
        if (lson < n && arr[largest] < arr[lson]) {
            largest = lson;
        }
        if (rson < n && arr[largest] < arr[rson]) {
            largest = rson;
        }
        if (largest != i) {
            int temp = arr[largest];
            arr[largest] = arr[i];
            arr[i] = temp;
            heapify(arr, n, largest);
        }
    }

计数排序

计数排序是非比较排序。它的核心是将数组中的元素值转换为键存储在额外空间中。主要思想是额外创建一个数组,额外数组中元素下标是待排序数组中元素的值,而额外数组中的值是其下标的值在待排序数组中作为元素的值出现的次数。

计数排序是稳定的。因为它是非比较排序,元素之间的顺序不依赖元素之间的比较。

任何情况下 T(n) = O(n+k),其中 k 是桶的个数。

第一步:找出原数组中元素值最大的,记为max。
第二步:创建一个新数组count,其长度是max加1,其元素默认值都为0。
第三步:遍历原数组中的元素,以原数组中的元素作为count数组的索引,以原数组中的元素出现次数作为count数组的元素值。
第四步:创建结果数组result,起始索引index。
第五步:遍历count数组,找出其中元素值大于0的元素,将其对应的索引作为元素值填充到result数组中去,每处理一次,count中的该元素值减1,直到该元素值不大于0,依次处理count中剩下的元素。
第六步:返回结果数组result。
https://www.cnblogs.com/xiaochuan94/p/11198610.html
    public static int[] countSort(int[] arr) {
        // 找出数组中的最大值
        int max = Integer.MIN_VALUE;
        for (int num : arr) {
            max = Math.max(max, num);
        }
        // 初始化计数数组count
        int[] count = new int[max+1];
        // 对计数数组各元素赋值
        for (int num : arr) {
            count[num]++;
        }
        // 创建结果数组
        int[] result = new int[arr.length];
        // 创建结果数组的起始索引
        int index = 0;
        // 遍历计数数组,将计数数组的索引填充到结果数组中
        for (int i=0; i<count.length; i++) {
            while (count[i]>0) {
                result[index++] = i;
                count[i]--;
            }
        }
        // 返回结果数组
        return result;
    }

基数排序

桶排序

桶排序可以看成是计数排序的升级版,它将要排的数据分到多个有序的桶里,每个桶里的数据再单独排序,再把每个桶的数据依次取出,即可完成排序。

    public static void bucketSort(int[] arr) {
        //找最大最小值
        int max = arr[0];
        int min = arr[0];
        int length = arr.length;
        for (int i = 0; i < length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            } else if (arr[i] < min) {
                min = arr[i];
            }
        }
        //最大值和最小值的差
        int diff = max - min;
        //桶列表
        ArrayList<ArrayList<Integer>> bucketList = new ArrayList<>();
        for (int i = 0; i < length; i++) {
            bucketList.add(new ArrayList<>());
        }
        //每个桶的存数区间
        float section = (float) diff / (float) (length - 1);
        for (int i = 0; i < length; i++) {
            //当前数除以区间得出存放桶的位置 减1后得出桶的下标
            int num = (int) (arr[i] / section) - 1;
            if (num < 0) {
                num = 0;
            }
            bucketList.get(num).add(arr[i]);
        }
        //桶排序
        for (int i = 0; i < bucketList.size(); i++) {
            Collections.sort(bucketList.get(i));
        }
        int index = 0;
        for (ArrayList<Integer> arrayList : bucketList) {
            for (int value : arrayList) {
                arr[index] = value;
                index++;
            }
        }
    }

Click here to view the copyright notice of this site(点击此处查看本站版权声明)
0 条回应

必须 注册 为本站用户, 登录 后才可以发表评论!