常见排序算法

引言：本篇文章主要介绍了常见的几种排序算法，选择排序、冒泡排序、归并排序等，并且有具体代码实现，感谢观看

选择排序

选择排序是一种简单直观的排序算法。它的工作原理是：第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，继续放在起始位置知道未排序元素个数为0。选择排序的步骤：1>首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。 2>再从剩余未排序元素中继续寻找最小（大）元素，然后放到未排序序列的起始位置。 3>重复第二步，直到所有元素均排序完毕。

时间复杂度

选择排序的时间复杂度为O(n²)。

代码

冒泡排序

冒泡排序是比较基础的排序算法之一，其思想是相邻的元素两两比较，较大的数下沉，较小的数冒起来，这样一趟比较下来，最大(小)值就会排列在一端。整个过程如同气泡冒起，因此被称作冒泡排序。冒泡排序的步骤是比较固定的：1>比较相邻的元素。如果第一个比第二个大，就交换他们两个。 2>每趟从第一对相邻元素开始，对每一对相邻元素作同样的工作，直到最后一对。 3>针对所有的元素重复以上的步骤，除了已排序过的元素(每趟排序后的最后一个元素)，直到没有任何一对数字需要比较。

时间复杂度

冒泡排序的最坏时间复杂度为O(n²)。

代码

---

位运算

ps:这里单独讲一下异或运算（也称无进位加法）
0^1=1
0^0=0
1^1=0
所以相同为0，不同为1
有关上述冒泡的swap讲解

经典面试题

异或的运算有很多种运用，比如求一个数组中奇数次出现的数，每一个数比上一个元素不断进行异或

还有一种情况

求一个数组中有两个数出现了奇数次，求出这两个数，具体实现是因为如果用上面的方法，最后的结果是a^b，这两个数肯定至少一位不一样，用这个原理求出最右边的1，把a和b区分开，再跟a ^ b进行异或，求出其中一个数

注意图中框出的部分，可以用来求提取一个数二进制中右边的1（01101100边成00000100）

插入排序

插入排序也是一种常见的排序算法，插入排序的思想是：将初始数据分为有序部分和无序部分，每一步将一个无序部分的数据插入到前面已经排好序的有序部分中，直到插完所有元素为止。插入排序的步骤如下：每次从无序部分中取出一个元素，与有序部分中的元素从后向前依次进行比较，并找到合适的位置，将该元素插到有序组当中。

时间复杂度

插入排序的最坏时间复杂度为O(n²)。

值得注意的是，插入算法是要优于以上两种算法的，虽然该算法的时间复杂度也是O(n²)，但是并不严格，是根据情况不同时间复杂度也不同，所以对于一些半有序的数组来说，插入排序更快

代码

归并排序

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

时间复杂度

时间复杂度是o（N*logN）

代码

下述代码值得注意的是process函数只有递归到头的时候，才会调用merge，实质上排序的函数在merge

归并排序的妙用

求小和，题目见下，该题很好的用到了归并排序，时间复杂度很低，先求左边的小和，再求右边的小和，最后归并在一起求小和

题解

代码

快速排序

快速排序也是一种较为基础的排序算法，其效率比冒泡排序算法有大幅提升。因为使用冒泡排序时，一趟只能选出一个最值，有n个元素最多就要执行n - 1趟比较。而使用快速排序时，一次可以将所有元素按大小分成两堆，也就是平均情况下需要logn轮就可以完成排序。快速排序的思想是：每趟排序时选出一个基准值，然后将所有元素与该基准值比较，并按大小分成左右两堆，然后递归执行该过程，直到所有元素都完成排序。

步骤如下：
第一步：先从数列中取出一个数作为基准数。
第二步：分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
第三步：再对左右区间重复第二步，直到各区间只有一个数。

值得注意的是，快速排序有三个版本，
<1>第一个版本只是把随机选一个数作为基值（注意这里的随机选择是自己定一个），然后放到最后面（当然这个位置也可以在最前面），从索引第一个数开始与基值进行大小对比，最后分开为一边比基值小，一边比基值大的两部分，然后将大于基数那一部分第一个数和基值进行交换，之后在这两部分继续进行上述步骤
<2>第二个版本在第一个版本的基础上增加一个等于基值的部分，总共三部分，可以加快一下速度
<3>第三个版本是将基值得数设置为随机选择的数（运用Math.Random公式），这里运用了一下概率论，在选择基准值的时候，越靠近中间，性能越好；越靠近两边，性能越差。第三版随机选一个数进行划分的目的就是让好情况和差情况都变成概率事件。把每一种情况都列出来，会有每种情况下的时间复杂度，但概率都是1/N。那么所有情况都考虑，时间复杂度就是这种概率模型下的长期期望。

时间复杂度

时间复杂度O(N*logN)

额外空间复杂度

额外空间复杂度O(logN)

代码

package Leetcode;
//注意，这里是第三个版本的快速排序
public class 快速排序 {
    public static void main(String[] args) {
        int[] arr = new int[]{3,2,5,4,6,7,3};
        process3(arr,0,arr.length - 1);
        for(int i : arr){
            System.out.print(i + ",");
        }

    }
    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
    public static int[] netherlandsFlag(int[] arr, int L, int R) {
        if (L > R) {
            return new int[] { -1, -1 };
        }
        if (L == R) {
            return new int[] { L, R };
        }
        //小于基准值的区域的右边界
        int less = L - 1;
        //大于基准值的区域的左边界
        int more = R;
        int index = L;
        while (index < more) {
            //等于基准值，不做处理，判断下一个数据
            if (arr[index] == arr[R]) {
                index++;
                //当前数小于基准值
            } else if (arr[index] < arr[R]) {
                //将当前值和小于区域右边的一个值交换：swap
                //判断下一个数据：index++
                //小于区域右移：++less（先++是为了完成swap）
                swap(arr, index++, ++less);
            } else {
                //将当前值和大于区域左边的一个值交换：swap
                //大于区域左移：--more（先--是为了完成swap）
                swap(arr, index, --more);
            }
        }
        //因为最开始是把arr[R]作为基准值的，所以在进行接下来的一步之前，
        //arr[R]实际是在大于区域的最右侧的，所以还需要进行一步交换，这样
        //整个数组就成了小于区域、等于区域、大于区域的样子
        swap(arr, more, R);
        //less + 1是等于区域的起始位置，more经过上一步的和arr[R]交换后，
        //就成了等于区域的结束位置
        return new int[] { less + 1, more };
    }
    public static void process3(int[] arr, int L, int R) {
        if (L >= R) {
            return;
        }
        swap(arr, L + (int) (Math.random() * (R - L + 1)), R);
        int[] equalArea = netherlandsFlag(arr, L, R);
        process3(arr, L, equalArea[0] - 1);
        process3(arr, equalArea[1] + 1, R);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

堆排序

首先谈到堆排序就不得不说大根堆和小根堆，下面放一张图让大家了解一下大根堆和小根堆

上图相信大家已经看出了大根堆和小根堆的区别，大根堆父节点比子节点都要大，小根堆则是父节点比子节点都小，那他是怎么做到排序呢？
我们拿大根堆来举例，头结点的数是最大的，把父节点和末尾的节点交换位置，比如上图中的88和60交换位置，之后把88弹出，然后60和它的子节点进行对比，最终再次形成大根堆，下面带大家手撕一下这个过程

代码

下面是向堆里面插入元素的代码

下面是节点间比较的代码

下面是堆排序主函数代码

重点来了！

下面介绍一个堆排序运用的场景

根据以上的题意，可以知道制作一个小根堆，长度为k，向里面插入数组前k个数，这样就可以知道小根堆的最小值一定在下标为0，这样在向小根堆里面插入数据就又有了一个下标为1的值，以此类推

代码

这里用到了java中PriorityQueue类，这个意思是优先级队列（小根堆）

桶排序

简单来说就是把一个数组中的数从个位到最高位都依次进行比较（个位数优先，依次递增）， 当然有个前提，就是每一个数的位数相同，不够的高位补0

代码

以上算法总结

目前没有找到时间复杂度O（N*logN），额外空间复杂度O（1），又稳定的排序算法

一切桶排序下的思维排序也是稳定的

结尾：此篇文章远远没有结束，后续进行补充，持续关注