1.冒泡排序

每次比较相邻的元素，每一轮都会把未排序区的最大元素找出来，放到后面。

public void bubbleSort(int[] arr){

    for(int i = 0; i < arr.legnth - 1; i++){

        // 第i轮开始，arr[n-i, n]已排好序

        for(int j = i; j < arr.legnth - i - 1; j++){

            if(arr[j] > arr[j + 1]){

                swap(arr, j, j + 1);

            }

        }

    }

}

2.选择排序

先把小的拿出来，再把最小的拿出来...，每次选择还没处理的元素中最小的元素。

使用索引j扫描一遍数组，找到最小的元素，与第1个元素进行交换，i++

arr[0,i)已排好序，arr[i,n)未排序，把arr[i...n)中的最小值放到arr[i]的位置

public static void sort(int[] arr){

    for(int i = 0; i < arr.length; i++){

        // 选择arr[i...n)中最小值

        for(int j = i; j < arr.length; j++){

            if(arr[j] < arr[i]){

                swap(arr, j, i);

            }

        }

    }

}

3.插入排序

每次处理一张牌，把这张牌插入到前面已经排好序的牌中

i=0，i指向当前处理的元素，无需处理；

i=1，arr[1]=4，使用索引j判断当前元素是否需要插入到前面某一个位置，j初始指向4，j--，元素6比4大，4应该插入到6的前面。

i=2，j=2，arr[j-1]>arr[j]，所以当前元素2应该插入到6的前面，j--；

j=1，arr[j-1]>arr[j]，2继续插入到4的左边，j=0，此时2已经来到正确的位置，至此前三个元素已经处理完毕。

依次循环，arr[0,i)已排好序，arr[i,n)未排序，把arr[i]放到合适的位置。

public class InsertionSort {

    public static void sort(int[] arr){

        for (int i = 0; i < arr.length; i++) {

//            for (int j = i; j > 0; j--) {

//                if(arr[j-1] > arr[j]){

//                    swap(arr, j-1, j);

//                }else {

//                    break;

//                }

//            }

            for (int j = i; j > 0 && arr [j-1] > arr[j]; j--) {

                swap(arr, j-1, j);

            }

        }

    }

​

    public static void swap(int[] arr, int i, int j){

        int t = arr[i];

        arr[i] = arr[j];

        arr[j] = t;

    }

}

插入排序小优化：

为了将3到达正确的位置，6和3交换，4和3交换，3和2不交换，每一次交换涉及三次操作；

为了找到3正确的插入位置，可以先用变量t暂存3，此时i=3，j=3，arr[j-1]=6>t，将arr[j-1]=6赋值给arr[j]=3，j--;

j=2，3是否放到此时j=2这个位置呢？arr[j-1]=4>t，将arr[j-1]=4赋值给arr[j]=6，j--;

j=1，arr[j-1]=2<t，所以3应该插入到这个位置，将t赋值给arr[j]=4;

    public static void sort(int[] arr){

        for (int i = 0; i < arr.length; i++) {

            // 将arr[i]插入到合适的位置

            int t = arr[i];

            int j;

            //j从i开始向左扫描，如果arr[j-1]大于t,将arr[j-1]赋值给arr[j]

//            for (j = i; j > 0; j--) {

//                if(arr[j - 1] > t){

//                    arr[j] = arr[j - 1];

//                }else {

//                    break; // 必须写上

//                }

//            }

            // 简化写法

            for(j = i; j > 0 && arr[j - 1] > t; j--){

                arr[j] = arr[j - 1];

            }

            arr[j] = t;

        }

    }

对于有序或近乎有序的数组，插入排序的复杂度是O(n)​，但插入排序整体复杂度仍是O(n2)​;

4.归并排序

分治法：把原问题分解为规模较小的子问题，递归地解决这些子问题，然后合并子问题的结果，得到原问题的解。

合并两个有序区间arr[l, mid]和arr[mid+1, r] , merge(arr, l, mid, r):

初始化，i = l指向第一个区间初始元素， j = mid + 1指向第二个区间的初始元素，

arr[i]=1<arr[j]=2，取两者更小的元素1赋值给原始数组arr[0]，i++

arr[i]=3<arr[j]=2，把arr[j]=2赋值给原始数组arr[1]，j++

依次循环，继续比较i和j指向的两个元素，取两者更小的元素赋值给arr[k]，结果为

public static void merge(arr, l, mid, r){

    // 使用了额外的存储空间，不是原地排序        l l+1... r

    // 将数组arr[l,r+1)的元素拷贝到temp数组中  0  1 ... r-l

    // 在任意时刻，CPU 只会有一个函数在执行，也就只会有一个临时的内存空间在使用。

    // 临时内存空间最大也不会超过n个数据的大小，所以空间复杂度是O(n)

    int[] temp = Arrays.copyOfRange(arr, l, r + 1);

    int i = l,j = mid + 1;

    for(int k = l; k <= r; k++){

        // i∈[l,mid]，j∈[mid+1, r] 判断索引越界情况

        if(i > mid){ // 说明arr[l, mid]的元素已经赋值完成

            arr[k] = temp[j-l];j++;

        }else if(j > r){ // 说明arr[mid+1, r]的元素已经赋值完成

            arr[k] = temp[i-l];i++;

        }else if(temp[i-l] <= temp[j-l]){

            arr[k] = temp[i-l];i++;

        }else{

            arr[k] = tmep[j-l];j++;

        }

    }

}

​

public static void sort(int[] arr, int l ,int r){

    if(l >= r) return;

    // int mid = (l + r) / 2;

    int mid = l + (r - l) / 2; // 解决l+r越界

    sort(arr, l, mid);

    sort(arr, mid + 1, r);

    merge(arr, l, mid, r);

}

假设对n个元素进行归并排序需要的时间是 T(n)，那分解成两个子数组排序的时间都是 T(n/2)，merge() 函数合并两个有序子数组的时间复杂度是 O(n)。所以归并排序时间复杂度递推式为

T(n)={c if n=12T(n/2)+n if n>1​

通过主方法可以求得T(n)=nlogn​

5.快速排序

arr[l+1...j] < v, arr[j+1...i-1] >= v

选择标定点v=4，初始i=1对应的元素6>v，i++；

i=2，对应的元素5>4，i++；

i=3，对应的元素2小于4，需要扩充arr[l+1...j]的区间，此时j++，交换j和i对应的元素，i++；

i=4，对应的元素3也小于4，同理，j++，交换j和i对应的元素，i++；

i=5，8>4，i++；

i=6，7>4，i++；

i=7，1<4，所以j++，交换j和i对应的元素，i++；

最后交换l和j对应的元素，把标定点的元素放到中间

快速排序递归过程：

完全有序的数组快速排序分析

这种情况时间复杂度是O(n2)​

    private static int partition(int[] arr, int l, int r){

        // 生成[l, r]的随机索引

        int p = l + (new Random()).nextInt(r - l + 1);

        swap(arr, l, p);

​

        // arr[l+1...j] < v, arr[j+1...i-1] >= v

        int j = l;

        for (int i = l + 1; i <= r; i++) {

            if(arr[i] < arr[l]){

                j++;

                swap(arr, j, i);

            }

        }

        swap(arr, l, j);

        return j;

    }

​

    public static void sort(int[] arr, int l, int r){

        if(l >= r) return;

        int p = partition(arr, l, r);

        sort(arr, l, p-1);

        sort(arr, p+1, r);

    }

全是0的数组快速排序分析

双路快速排序

循环不变量：arr[l+1...i-1] <= v, arr[j+1...r] >= v

i负责寻找小于等于v的元素，j负责寻找大于等于v的元素

初始i=1，指向元素6>4；初始j=7，指向元素1<4；于是交换元素6和1，i++，j--；

i=2，指向元素5>4，停留在这里；j=6，指向元素7，j--继续寻找小于v的元素，直到停在3的位置。交换元素5和3，i++，j--；

i=3，指向元素2，继续i++后i>j，停止循环。最后交换l和j对应的元素，返回j。

特殊测试用例分析：

i 从左到右扫描遇到第一个大于等于v的元素就停止； j 从右到左扫描遇到第一个小于等于v的元素就停止；

初始i=1指向元素0>=0，j=7指向元素0<=0，交换i和j对应的元素，i++，j--；

i=2，j=6，此时继续交换两者对应的元素，i++，j--；

直到i和j指向同一个元素，停止循环。最后交换l和j对应的元素，返回j

    private static int partition(int[] arr, int l, int r){

        // 生成[l, r]的随机索引

        int p = l + (int)(Math.random() * (r - l + 1));

        swap(arr, l, p);

        // arr[l+1...i-1] <= v, arr[j+1...r] >= v

        int i = l + 1, j = r;

        while (true){

       // 在i<=j的条件下，如果arr[i] < arr[l]就继续循环，否则arr[i] >= arr[l]就停止

            while (i <= j && arr[i] < arr[l])

                i++;

            while (j >= i && arr[j] > arr[l])

                j--;

       // i>j已经把数组中的元素遍历完了；i=j表示指向了一个等于标定点的元素，也不需要处理；

            if(i >= j) break;

            swap(arr, i, j);

            i++;

            j--;

        }

        swap(arr, l, j);

        return j;

    }

三路快速排序

三路快排将数组分为三部分<v,=v,>v;i指向当前待处理元素e，如果e==v，i++；

如果e<v，lt++，将e和此时lt位置的元素交换，i++；

如果e>v，gt--，将e和此时gt位置的元素交换，此时i位置是交换后的元素，仍是未处理的元素。

当i>=gt时，结束循环。lt指向小于v的最后一个元素，gt指向大于v的第一个元素；

最后，交换l和lt位置的元素，此时v就放到了==v部分的第一个元素的位置。这时边界条件也发生了变化。

之后，只需要对<v和>v部分的元素进行递归快速排序就行了。

// 三路快排

public static void sort(int[] arr, int l, int r){

        if(l >= r) return;

        // 生成[l, r]的随机索引

        int p = l + (int)(Math.random() * (r - l + 1));

        swap(arr, l, p);

        // arr[l + 1, lt] < v, arr[lt + 1, i - 1] == v, arr[gt, r] > v

        int lt = l, i = l + 1, gt = r + 1;

        while (i < gt){

            if(arr[i] < arr[l]){

                lt++;

                swap(arr, i, lt);

                i++;

            }else if(arr[i] > arr[l]){

                gt--;

                swap(arr, i, gt);

            }else {

                i++;

            }

        }

        swap(arr, l, lt);

        // arr[l, lt - 1] < v, arr[lt, gt - 1] == v, arr[gt, r] > v

        sort3(arr, l, lt - 1);

        sort3(arr, gt, r);

    }

6.堆和堆排序

普通的队列是先进先出原则；优先队列则是按照优先级高低进行出队，比如将优先级最高的元素作为队头元素优先出队。

应用场景：医院门诊，优先看病情重的病人； 游戏中优先攻击最近单位，优先攻击血量最低等；售票窗口的老幼病残孕和军人优先购票等。

完全二叉树：最后一层的叶子节点都靠左排列，其他层的节点个数都要达到最大。

堆是一个完全二叉树，常用的存储方式是数组。对于每个节点的值都大于等于子树中每个节点值的堆，叫做最大堆。对于每个节点的值都小于等于子树中每个节点值的堆，叫做最小堆。

从数组索引0开始存储节点，设节点x存储在数组中下标为i的位置，则其左子节点下标为2i+1，右子节点下标为2i+2，父节点为(i-1)/2。

添加元素和siftUp

现在直接向数组中添加一个元素52，就不满足最大堆的性质了。因此，我们需要对52和其父节点做一些调整，来维护最大堆的性质。

具体方法是依次比较新添加元素和其父节点的大小，不断交换位置。这里52>16，交换52和16的位置，

交换后52>41，继续交换52和41的位置。52<62，这时就完成了调整工作。

public void add(E e){

    data.add(e);

    siftUp(data.size()-1);

}

private void siftUp(int k){

    while(k > 0 && data.get(k).compareTo(data.get(parent(k))) > 0){

        data.swap(k, (k - 1) / 2); // 交换两个索引对应的元素

        k = (k - 1) / 2;

    }

}

删除堆顶(取出最大)元素和siftDown

首先将数组最后一个元素16调整到堆顶，然后删除元素62。但此时不满足堆的性质，需要继续调整。

依次将元素16和其最大的孩子做交换，直到满足堆的性质。

第一次交换

第二次交换，调整完成。

一个包含n个节点的完全二叉树，树的高度不会超过log2⁡n​，siftDown和siftUp过程是顺着节点所在路径比较交换的，所以两者的时间复杂度跟树的高度成正比，都是log⁡n​

HeapifyO(n)

从最后一个非叶子节点开始，向前遍历，对每一个节点进行siftDown操作。

蓝色节点表示叶子节点，红色节点22表示最后一个非叶子节点。(最后一个非叶子节点的索引等于数组中最后一个元素父节点的索引)

首先对22进行siftDown操作，22只有一个左孩子且22<62，所以交换22和62的位置，交换后22是叶子节点，调整完成。

继续对13调整，结果如图所示

依次循环，不断调整

原地堆排序

public static void heapSort(int[] data){

        if(data.length <= 1) return;

        // heapify操作：从最后一个非叶子节点开始，对每一个节点siftDown操作

        for (int i = (data.length - 2) / 2; i >= 0; i--) {

            siftDown(data, i, data.length);

        }

​

        for (int i = data.length - 1; i >= 0; i--) {

          // 将堆顶元素放到最后一个位置，i--，次大的元素放到倒数第二个位置...

            swap(data,0, i); 

            siftDown(data, 0, i);

        }

    }

​

    // 对data[0, n)形成的最大堆中索引k的元素执行siftDown操作

    private static void siftDown(int[] data, int k, int n){

        while(2 * k + 1 < n){

            int j = 2 * k + 1; // j是k节点对应的左孩子索引，j+1是k节点对应的右孩子索引

            // j+1<n说明k节点有右孩子

            if(j + 1 < n && data[j + 1] > data[j])

                j++; // 此时j存储的是k节点的右孩子索引

            // 如果k节点元素值 >= 左右孩子中最大元素的值，满足堆的性质，结束循环

            if(data[k] >= data[j])

                break;

            swap(data, k, j); // 交换k，j索引对应的元素值

            k = j; // 更新k

        }

    }

​

    private static void swap(int[] arr, int i, int j){

        int t = arr[i];

        arr[i] = arr[j];

        arr[j] = t;

    }

Top K问题

LeetCode 215. 数组中的第K个最大元素

剑指 Offer 40. 最小的k个数

原地排序：不申请额外的存储空间进行排序；

稳定排序：待排序的序列中存在值相等的元素，排序之后，保持相等元素先后顺序不变。

冒泡排序、插入排序、选择排序算法的运行并不需要额外的存储空间，空间复杂度都是 O(1)，它们都是原地排序算法。

选择排序每次都要找剩余未排序元素中的最小值，并和前面的元素交换位置，这样破坏了稳定性。比如 3，3，2这样一组数据，第一次找到最小元素 2，与第一个3交换位置，那第一个3和中间的3顺序就变了，所以就不稳定了。

对于快速排序，如果输入数组中有两个相同的元素，比如数组{3，2，2，5}在经过第一次分区操作之后，两个2的相对先后顺序就会改变。所以快速排序不是稳定的。

对于堆排序，在排序的过程，存在将堆的最后一个节点跟堆顶节点互换的操作，所以就有可能改变值相同数据的原始相对顺序。

在java中，Arrays.sort方法对数组进行排序是一个综合的排序：

• 一般来讲，如果数组是基本类型的，那么直接选择快速排序，虽然不具有稳定性，但是对于每个数据来讲，并没有其他的意义，只是单纯的数字而已。

• 如果数组是引用类型的，那么选择归并排序，因为引用类型不是单纯的数字，应该选择具有稳定性的排序方式。

• 如果数组的长度是小于47(待定)的，直接选择插入排序，因为插入排序的常数操作少。