• 35648

    文章

  • 23

    评论

  • 20

    友链

  • 最近新加了很多技术文章,大家多来逛逛吧~~~~
  • 喜欢这个网站的朋友可以加一下QQ群,我们一起交流技术。

十大排序算法总结

欢迎来到阿八个人博客网站。本 阿八个人博客 网站提供最新的站长新闻,各种互联网资讯。 喜欢本站的朋友可以收藏本站,或者加QQ:我们大家一起来交流技术! URL链接:https://www.abboke.com/jsh/2019/0709/6697.html 1190000019697692

0. 前言

排序算法中涉及到了两个概念:

原地排序:根据算法对内存的消耗情况,可以将算法分为原地排序和非原地排序,原地排序特指空间复杂度为 O(1) 的排序。

排序算法的稳定性:例如排序一个数组 [1, 5, 3, 7, 4, 9, 5],数组中有两个 5,排序之后是 [1, 3, 4, 5, 5, 7, 9],如果排序之后的两个 5 的前后顺序没有发生变化,那么称这个排序是稳定的,反之则是不稳定的。

1. 冒泡排序

冒泡排序是很经典的排序算法了,相邻的两个数据依次进行比较并交换位置。遍历一遍数组后,则有一个数据排序完成,然后再遍历 n 次,排序完成。示意图如下:

在这里插入图片描述

代码实现:

public class BubbleSort {

    private static void bubbleSort(int[] data){
        int length = data.length;
        for (int i = length - 1; i > 0; i --) {
            //判断是否有数据交换,如果没有则提前退出
            boolean flag = false;
            for (int j = 0; j < i; j ++) {
                if (data[j] > data[j + 1]){
                    int temp = data[j];
                    data[j] = data[j + 1];
                    data[j + 1] = temp;
                    flag = true;
                }
            }
            if (!flag){
                break;
            }
        }
    }
}

2. 选择排序

将要排序的数据分为了已排序区间和未排序区间,每次从未排序区间找到最小值,然后将其放到已排序区间的末尾,循环遍历未排序区间则排序完成。

示意图如下:

在这里插入图片描述

代码实现:

public class SelectionSort {

    public static void selectionSort(int[] data){
        int length = data.length;
        for (int i = 0; i < length - 1; i++) {
            int min = i;
            for (int j = i + 1; j < length; j++) {
                if (data[min] > data[j]){
                    min = j;
                }
            }
            int temp = data[min];
            data[min] = data[i];
            data[i] = temp;
        }
    }
}

3. 插入排序

和选择排序类似,插入排序也将数据分为了已排序区间和未排序区间,遍历未排序区间,每次取一个数据,将其插入到已排序区间的合适位置,让已排序区间一直保持有序,直到未排序区间遍历完排序则完成。

示意图如下:

在这里插入图片描述

代码实现:

public class InsertionSort {

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

插入排序为什么比冒泡排序更常用?

这两种排序的时间复杂度都是一样的,最好情况是 O(n),最坏情况是 O(n2),但是在实际的生产中,插入排序使用更多,原因在于两者数据交换的次数不同。冒泡排序需要进行三次交换,插入排序只要一次:

//冒泡排序数据交换
if (data[j] > data[j + 1]){
    int temp = data[j];
    data[j] = data[j + 1];
    data[j + 1] = temp;
    flag = true;
}

//插入排序数据交换
while (j > 0 && data[j - 1] > val){
    data[j] = data[j - 1];
    j --;
}

在数据量较大的时候,两者性能差距就体现出来了。

4. 希尔排序

希尔排序其实是插入排序的一种优化,其思路是将排序的数组按照一定的增量将数据分组,每个分组用插入排序进行排序,然后增量逐步减小,当增量减小为1的时候,算法便终止,所以希尔排序又叫做“缩小增量排序”。

示意图如下:

在这里插入图片描述

图中的示例,每次依次将数组分为若干组,每组分别进行插入排序。代码实现如下:

public class ShellSort {

    public static void shellSort(int[] data) {

        int length = data.length;
        int step = length / 2;
        while (step >= 1){
            for (int i = step; i < length; i++) {
                int val = data[i];
                int j = i - step;
                for (; j >= 0; j -= step){
                    if (data[j] > val){
                        data[j + step] = data[j];
                    }
                    else {
                        break;
                    }
                }
                data[j + step] = val;
            }
            step = step / 2;
        }
    }
}

5. 归并排序

归并排序使用到了分治思想,分治思想即将大的问题分解成小的问题,小的问题解决了,大的问题也就解决了。蕴含分治思想的问题,一般可以使用递归技巧来实现。

归并排序的思路是:首先将数组分解,局部进行排序,然后将排序的结果进行合并,这样整个数组就有序了,你可以结合下图理解:

在这里插入图片描述

代码实现:

public class MergeSort {

    public static void mergeSort(int[] data){
        mergeInternally(data, 0, data.length - 1);
    }

    private static void mergeInternally(int[] data, int p, int r){
        if (p >= r){
            return;
        }
        int q = (p + r) / 2;
        //分治递归
        mergeInternally(data, p, q);
        mergeInternally(data, q + 1, r);
        //结果合并
        merge(data, p, q, r);
    }

    private static void merge(int[] data, int p, int q, int r){
        int[] temp = new int[r - p + 1];
        int k = 0;
        int i = p;
        int j = q + 1;
        //比较并合并
        while (i <= q && j <= r){
            if (data[i] < data[j]){
                temp[k ++] = data[i ++];
            }
            else {
                temp[k ++] = data[j ++];
            }
        }
        //合并可能出现的剩余元素
        int start = i;
        int end = q;
        if (j <= r){
            start = j;
            end = r;
        }
        while (start <= end){
            temp[k ++] = data[start ++];
        }
        //拷贝回原数组
        if (r - p + 1 >= 0) {
            System.arraycopy(temp, 0, data, p, r - p + 1);
        }
    }
}

6. 快速排序

快速排序也用到了分治的思想,只不过它和归并排序的思路刚好是相反的,快速排序使用数组中一个数据作为分区点(一般可以选取数组第一个或最后一个元素),比分区点小的,放在左侧,比分区点大的,放在右侧。然后左右两侧的数据再次选择分区点,循环进行这个操作,直到排序完成。

示意图如下(图中是以第一个元素作为分区点):

在这里插入图片描述

代码实现:

public class QuickSort {
    public static void quickSort(int[] data){
        quickSortInternally(data, 0, data.length - 1);
    }

    private static void quickSortInternally(int[] data, int p, int r){
        if (p >= r){
            return;
        }
        int q = partition(data, p, r);
        quickSortInternally(data, p, q - 1);
        quickSortInternally(data, q + 1, r);
    }

    /**
     * 获取分区点函数
     */
    private static int partition(int [] data, int p, int q){
        int pivot = data[q];
        int i = 0;
        int j = 0;
        while (j < q){
            if (data[j] <= pivot){
                swap(data, i, j);
                i ++;
            }
            j ++;
        }
        swap(data, i, q);
        return i;
    }
    /**
     * 交换数组两个元素
     */
    private static void swap(int[] data, int i, int j){
        int temp = data[i];
        data[i] = data[j];
        data[j] = temp;
    }
}

7. 堆排序

基于堆的排序比较常用,时间复杂度为 O(nlogn),并且是原地排序,主要的步骤分为建堆和排序。

建堆

思路是从堆中第一个非叶子节点,依次从上往下进行堆化,如下图:

在这里插入图片描述

排序

建堆完成之后,假设堆中元素个数为 n,堆顶元素即是最大的元素,这时候直接将堆顶元素和堆中最后一个元素进行交换,然后将剩余的 n - 1 个元素构建成新的堆,依次类推,直到堆中元素减少至 1,则排序完成。示意图如下:

在这里插入图片描述

代码实现:

public class HeapSort {

    /**
     * 排序
     */
    public void heapSort(int[] data){
        int length = data.length;
        if (length <= 1){
            return;
        }
        buildHeap(data);
        while (length > 0){
            swap(data, 0, -- length);
            heapify(data, length, 0);
        }
    }

    /**
     * 建堆
     */
    private void buildHeap(int[] data){
        int length = data.length;
        for (int i = (length - 2) / 2; i >= 0; i --) {
            heapify(data, length, i);
        }
    }

    /**
     * 堆化函数
     */
    private void heapify(int[] data, int size, int i){
        while (true){
            int max = i;
            if ((2 * i + 1) < size && data[i] < data[2 * i + 1]) {
                max = 2 * i + 1;
            }
            if ((2 * i + 2) < size && data[max] < data[2 * i + 2]) {
                max = 2 * i + 2;
            }
            if (max == i){
                break;
            }
            swap(data, i, max);
            i = max;
        }
    }

    /**
     * 交换数组中两个元素
     */
    private void swap(int[] data, int i, int j){
        int temp = data[i];
        data[i] = data[j];
        data[j] = temp;
    }
}

8. 桶排序

桶排序并不是基于数据比较的,因此比较的高效,时间复杂度接近 O(n),但是相应地,应用的条件十分苛刻。其思路非常的简单:将要排序的数据分到各个有序的桶内,数据在桶内进行排序,然后按序取出,整个数据就是有序的了。

最好情况下,数据被均匀的分到各个桶中,最坏情况是数据全都被分到一个桶中。

下面是一个桶排序的示例:

public class BucketSort {

    /**
     * 测试场景:数组中有10000个数据,范围在(0-100000)
     * 使用100个桶,每个桶存放的数据范围为:0-999, 1000-1999, 2000-2999,依次类推
     */
    public static void bucketSort(int[] data){
        //新建100个桶
        int bucketSize = 100;
        ArrayList<ArrayList<Integer>> buckets = new ArrayList<>(bucketSize);
        for (int i = 0; i < bucketSize; i++) {
            buckets.add(new ArrayList<>());
        }
        //遍历数据,将数据放到桶中
        for (int i : data) {
            buckets.get(i / 1000).add(i);
        }
        //在桶内部进行排序
        int k = 0;
        for (int i = 0; i < bucketSize; i++) {
            ArrayList<Integer> list = buckets.get(i);
            Integer[] num = list.toArray(new Integer[1]);
            Arrays.sort(num);
            //拷贝到data中
            for (int n : num) {
                data[k++] = n;
            }
        }
    }
    //测试
    public static void main(String[] args) {
        Random random = new Random();
        int[] data = new int[10000];
        for (int i = 0; i < data.length; i++) {
            data[i] = random.nextInt(100000);
        }
        BucketSort.bucketSort(data);
        System.out.println(Arrays.toString(data));
    }
}

9. 计数排序

计数排序其实是一种特殊的桶排序,适用于数据的区间不是很大的情况。

例如给 10 万人按照年龄进行排序,我们知道年龄的区间并不是很大,最小的 0 岁,最大的可以假设为 120 岁,那么我们可以新建 121 个桶,扫描一遍数据,将年龄相同的放到一个桶中,然后按序从桶中将数据取出,这样数据就有序了。

计数排序的基本思路如下:

在这里插入图片描述

代码实现:

public class CountingSort {

    private static void countingSort(int[] data){
        int length = data.length;
        //找到数组的最大值
        int max = data[0];
        for (int i : data){
            if (max < i){
                max = i;
            }
        }
        //新建一个计数数组,大小为max+1
        //count数组的下标对应data的值,存储的值为对应data值的个数
        int[] count = new int[max + 1];
        for (int i : data){
            count[i] ++;
        }
        //根据count数组取出数据
        int k = 0;
        for (int i = 0; i < count.length; i++) {
            while (count[i] != 0){
                data[k ++] = i;
                count[i] --;
            }
        }
    }
}

10. 基数排序

基数排序适用于位数较多的数字或者字符串,思路是将排序的数据按位拆分,每一位单独按照稳定的排序算法进行比较,如下图:

在这里插入图片描述

图中的示例,以每个数字为下标,建了 10 个 “桶”,每个桶是一个队列(也可以是数组),然后将要排序的数据按位加入到队列中,然后出队,比较完每一位,则排序完成。

代码实现:

public class RadixSort {

    private static void radixSort(int[] data) {
        int maxDigit = maxDigit(data);

        //新建并初始化10个桶
        Queue<Integer>[] queues = new LinkedList[10];
        for (int i = 0; i < queues.length; i++) {
            queues[i] = new LinkedList<>();
        }

        for (int i = 0, mod = 1; i < maxDigit; i ++, mod *= 10) {
            for (int n : data){
                int m = (n / mod) % 10;
                queues[m].add(n);
            }

            int count = 0;
            for (Queue<Integer> queue : queues) {
                while (queue.size() > 0) {
                    data[count++] = queue.poll();
                }
            }
        }
    }

    /**
     * 获取数组最大位数
     */
    private static int maxDigit(int[] data){
        int maxDigit = data[0];
        for (int i : data){
            if (maxDigit < i){
                maxDigit = i;
            }
        }
        return String.valueOf(maxDigit).length();
    }
}
在我的 Github 上面有更加详细的数据结构与算法代码

相关文章

暂住......别动,不想说点什么吗?
  • 全部评论(0
    还没有评论,快来抢沙发吧!