算法笔记（一）——排序算法

算法笔记（一）——排序算法 一、时间复杂度

完成算法按最差表现需要执行的常数 *** 作的次数，只留最高阶项并且去掉系数

二、冒泡排序、选择排序和插入排序

最简单的三个排序算法，时间复杂度O(N^2)，空间复杂度O(1)

冒泡排序：

public static void bubbleSort(int[] a) {
    for (int i = 0; i < a.length; i++) {
        for (int j = a.length - 1; j > i; j--) {
            if (a[j] < a[j - 1]) {
                swap(a, j - 1, j);
            }
        }
    }
}

选择排序：

public static void selectSort(int[] a) {
    for (int i = 0; i < a.length; i++) {
        for (int j = i + 1; j < a.length; j++) {
            if (a[i] > a[j]) {
                swap(a, i, j);
            }
        }
    }
}

插入排序：

相当于打牌摸牌的过程，比选择和冒泡稍快一些

public static int[] insertSort(int[] a){
    for (int i = 0; i <  a.length; i++){
        for (int j = i; j > 0 && a[j-1] > a[j]; j--){
            swap(a,j-1,j);
        }
    }
    return a;
}

三、swap函数与亦或 swap函数

正常的swap函数：

public static void swap(int[] arr, int a, int b) {
    int c = arr[a];
    arr[a] = arr[b];
    arr[b] = c;
}

利用亦或，可以不是用额外空间实现swap函数（前提保证a和b不能指向同一内存块，即a != b）：

public static void swap(int[] arr, int a, int b) {
    array[a] = array[a] ^ array[b];
	array[b] = array[a] ^ array[b];
	array[a] = array[a] ^ array[b];
}

亦或

亦或是相同为0不同为1，两个二进制数亦或可以认为是无进位的加法。

亦或的性质：
1）0 ^ N=N; N ^ N=0
2) 满足交换律和结合律： a ^ b=b^ a; a ^ b ^ c=a ^ (b ^ c)
3) 一组数据亦或，与亦或的顺序无关

相关例题：
例1、一个数组，其中一个数字出现了奇数次其余的数字都出现了偶数次，求这个出现了奇数次的数字。

public static int method1(int[] arraylist){
    int eor = 0;
    //利用亦或的性质，将数组中的数亦或一遍即可
    for (int i=0;i< arraylist.length;i++) {
        eor ^= arraylist[i];
    }
    return eor;
}

例2、一个数组，其中两个数字出现了奇数次其余数字都出现了偶数次，求这两个出现了奇数次的数字。

public static int[] method2(int[] arraylist){
    int eor = 0;
    for (int i=0;i< arraylist.length;i++) {
        eor ^= arraylist[i];
    }
    
    int rightone = 0;
    //取出为1的最右边的一位
    rightone = eor&(~eor+1);
    int onlyone = 0;
    for (int i=0;i< arraylist.length;i++) {
        if ((arraylist[i] & rightone) == 0) {
            onlyone ^= arraylist[i];
        }
    }
    int[] b = new int[2];
    b[0] = onlyone;
    b[1] = eor^onlyone;
    
    return b;
}

四、二分法

例1、一个有序数组，确定一个数是否存在数组中，若存在，返回数组下标，若不存在返回-1

public static int bisectionMethod1(int a[], int b){
    int front = 0;
    int end = a.length-1;
    int mid = (front + end)/2;
    while (front <= end){
        if(a[mid] == b){
            return mid;
        }else if(a[mid] < b) {
            front = mid+1;
            mid = (front + end)/2;
        }else {
            end = mid-1;
            mid = (front + end)/2;
        }
    }
    return -1;
}

例2、一个有序数组，确定一个数是否存在数组中，若存在，返回这个数第一个存在的下标，若不存在返回-1

public static int bisectionMethod2(int a[], int b){
    int front = 0;
    int end = a.length-1;
    int mid = (front + end)/2;
    int tag = -1;
    while (front <= end){
        if(a[mid] > b){
            end = mid-1;
            mid = (front + end)/2;
        }else if(a[mid] < b){
            front = mid+1;
            mid = (front + end)/2;
        }else {
            tag = mid;
            end = mid-1;
            mid = (front + end)/2;
        }
    }
    return tag;
}

例3、求局部最小值，一个无序数组，相邻两个数必不相等，求此数组中一个比相邻的数都小的数，若存在返回下标，若不存在返回-1,要求时间复杂度在O(logN)以内（不一定有序数组才能用二分）

public static int bisectionMethod3(int a[]){
    int front = 0;
    int end = a.length-1;
    int mid = (front + end)/2;
    if(a.length == 1){
        return 0;
    }
    if(a[front] < a[front+1]){
        return front;
    }else if(a[end] < a[end-1]){
        return end;
    }else {
        while(front <= end){
            if(a[mid] > a[front]){
                end = mid -1;
                mid = (front + end)/2;
            }else if(a[mid] > a[end]){
                front = mid +1;
                mid = (front + end)/2;
            }else {
                if(a[mid] > a[mid-1]){
                    end = mid-1;
                    mid = (front + end)/2;
                }
                else if(a[mid] > a[mid+1]) {
                    front = mid + 1;
                    mid = (front + end) / 2;
                }else {
                    return mid;
                }
            }
        }
    }
    return -1;
}

五、 master公式

若一个递归算法可以表示为：

其中，T(N)为母问题的数据规模，T(N/b)为子问题的数据规模，a为子问题的执行次数，O(N^d)为剩余执行部分的时间复杂度。
则此算法的时间复杂度可直接计算
1） if log(b,a) > d -> 时间复杂度为 O(N^log(b,a))
2） if log(b,a) = d -> 时间复杂度为O((N^d)*logN)
3） if log(b,a) < d -> 时间复杂度为O(N^d)

六、归并排序

流程：先上数组前一半和后一半分别有序，然后两半归并（递归）
归并排序是外排序（需要借助外部数组的排序算法）

public static void mergeSort(int[] arr, int front, int end){
    if(end == front){
        return ;
    }

    int mid = front + ((end - front)>>1);


    mergeSort(arr, front, mid);
    mergeSort(arr, mid + 1, end);
    merge(arr, front,mid , end);

}
public static void merge(int[] arr, int front,int mid, int end){
    int[] help = new int[end - front + 1];
    int p = front;
    int q = mid + 1;
    int i = 0;
    while (p <= mid && q <= end){
        //用三元运算符代替if else
        help[i++] = arr[p] > arr[q] ? arr[q++] : arr[p++];
    }
    while (p <= mid){
        help[i++] = arr[p++];
    }
    while (q <= end){
        help[i++] = arr[q++];
    }
    for(i = 0; i < help.length; i++){
        arr[front + i] = help[i];
    }
}

归并排序符合master公式，计算时间复杂度为O(NlogN)，额外空间复杂度为O(N)

归并排序之所以可以将时间复杂度降到O(NlogN)是因为它没有浪费比较过程，每一次比较会传递到下一次归并中去。而O(N^2)的排序浪费了N次比较机会才能搞定一个数，浪费了大量的比较次数。

归并排序的应用：
例1、小和问题：一个数组中每个位置的数字左边比它小的数字的和叫小和，求这些小和的总和

public static int smallSum(int[] arr){
    if(arr == null || arr.length<2){
        return 0;
    }
    return mergeSort2(arr, 0, arr.length-1);
}

public static int mergeSort2(int arr[], int front, int end){
    if(front == end){
        return 0;
    }
    int mid = front + ((end - front)>>1);
    return mergeSort2(arr, front, mid) + mergeSort2(arr, mid + 1, end) + merge2(arr,front, mid, end);
}

public static int merge2(int[] arr, int front,int mid, int end){
    int[] help = new int[end - front + 1];
    int p = front;
    int q = mid + 1;
    int i = 0;
    int sum = 0;
    while (p <= mid && q <= end){
        if (arr[p] < arr[q]){
            sum += arr[p] * (end - q + 1);
            help[i++] = arr[p++];
        }else {
            help[i++] = arr[q++];
        }
    }
    while (p <= mid){
        help[i++] = arr[p++];
    }
    while (q <= end){
        help[i++] = arr[q++];
    }
    for (i = 0; i < help.length; i++){
        arr[front+i] = help[i];
    }
    return sum;
}

例2、逆序对问题：一个数组中，若一个数字比他右边的大，这一对数字就叫逆序对，求所有的逆序对，和小和问题一个原理。

七、快速排序 1、 荷兰国旗问题 1） 指定一个num，使数组左边的数都小于等于num，数组右边的数都大于num，要求时间复杂度O(N)，空间复杂度O(1)

步骤：数组左区指针最开始是-1，将遍历指针从0往右遍历，若此位置的数小于等于num，将其和左区右边的数互换，左区指针加一；若此位置的数大于num，则继续往下遍历。

public static void partition1(int[] arr, int num){
    int L = -1;
    for (int i = 0; i < arr.length; i++){
        if(arr[i] <= num){
            swap2(arr, ++L, i);
        }
    }
}

2） 指定一个num，使数组左边的数都小于num，数组中间的数都等于num，数组右边的数都大于num，要求时间复杂度O(N)，空间复杂度O(1)

1.0 小于区和等于区动：

public static void partition2(int[] arr, int num){
    int L = -1;
    int M = -1;
    for (int i = 0; i < arr.length; i++){
        if(arr[i] < num){
            swap2(arr, ++L, ++M);
            swap2(arr, L, i);
        }else if(arr[i] == num){
            swap2(arr, ++M, i);
        }
    }
}

2.0：小于区和大于区动

public static void partition2_2(int[] arr, int num){
    int L = -1;
    int R = arr.length;
    int i = 0;
    while (i num){
            swap2(arr, --R, i);
        }else {
            i++;
        }
    }
}

2、快速排序算法

1.0：用数组的最后一位做划分值num，让数组左侧都为小于等于num的数，右侧都为大于num的数（最后一位不动），然后让最后一位和右侧第一位的数交换，将数组分成左右两侧，然后分别用两侧的最后一位做划分值递归调用，最终排好序。
2.0：利用荷兰国旗问题，将等于划分值的数都放在中间，然后递归调用两侧的数组。

2.0会比1.0稍快，但是两个算法的时间复杂度都是O(N^2),空间复杂度为O(N)，因为当数组本来就有序时，是最差情况，每一次递归只能解决一个数。

3.0：在数组中随机取一个数，将它与数组最尾端的数交换，然后用这个数作为划分值进行partition，这样所有的情况都为等概率事件，将这些概率事件求一个期望，最终算法时间复杂度为O(NlogN)，空间复杂度为O(logN)

public static void quickSort(int[] arr, int front, int end){

    if(end > front){
        swap2(arr, front + (int)(Math.random()*(end - front +1)), end);

        int[] a = partition(arr, front, end);
        quickSort(arr, 0, a[0]);
        quickSort(arr, a[1], end);
    }

} 
public static int[] partition(int[] arr, int front, int end){
    int L = front - 1;
    int R = end;
    int i = front;
    while (i arr[end]){
            swap2(arr, --R, i);
        }else {
            i++;
        }
    }
    swap2(arr, end, R);
    return new int[]{L, R+1};
}

八、堆和堆排序 1、完全二叉树：从左到右依次编满的二叉树叫做完全二叉树 2、大根堆和小根堆

大根堆：所有父节点都比子节点大的完全二叉树叫做大根堆
小根堆：所有父节点都比子节点小的完全二叉树叫做小根堆

3、堆的性质

一个数组从零开始的连续一段可以表示成一个堆，节点i的左孩子是2i+1，右孩子是2i+2，父节点是(i-1)/2。

4、heapinsert

一个空的数组或一个大根堆，向数组内添加一个数，通过heapinsert *** 作使数组继续保持为大根堆。
步骤：将该位置的数和父节点比较，若大于父节点则和父节点交换，直到其不大于父节点或到0位置，时间复杂度O(logN)

//index位置的数是否需要向上移动而保持数组大根堆状态
public static void heapInsert(int[] arr, int index) {

    while(arr[index] > arr[(index-1)/2]) {
        swap2(arr, index, (index-1)/2);
        index = (index-1)/2;
    }
}

5、heapify：

一个大根堆，要求把它的最大值（即0位置的数）从堆中拿出来，剩下的数仍然保持大根堆。
步骤：将数组末位的数复制到0位置，然后将其和左右孩子的最大值比，若比孩子小则和孩子交换，直到其不比孩子小或其没有孩子为止，时间复杂度O(logN)

//从index位置开始往下做heapify
public static void heapIfy(int[] arr, int index, int heapsize) {
    int left = 2*index+1;
    //index下方还有孩子的时候
    while(left < heapsize) {
        //左孩子和右孩子哪个大
        int largest = left + 1 < heapsize && arr[left] < arr[left+1] ? left+1 : left;
        //父节点和最大孩子哪个大
        largest =  arr[largest] < arr[index] ? index : largest;
        if(largest == index) {
            break;
        }
        swap2(arr, largest, index);
        index = largest;
        left = 2*index+1;

    }
}

如果将一个大根堆数组中的某一位置的值改掉，只需将该位置的数向上做一次heapinsert再向下做一次heapify即可将数组继续保持大根堆结构。

6、堆排序：

步骤：初始heapsize为0，然后一个一个数做heapinsert，heapsize++，将数组变为大根堆，然后让数组首尾位置的数交换，heapsize–，做heapify *** 作将数组再变成大根堆，然后循环做heapify直到heapsize为0排序完成。时间复杂度O(NlogN),额外空间复杂度O(1)

//堆排序
public static void heapSort(int[] arr) {
    if(arr == null || arr.length < 2) {
        return;
    }
    int heapsize = 0;
    //O(N)
    while(heapsize < arr.length) {
        //O(logN)
        heapInsert(arr, heapsize++);
    }
    //O(N)
    while(heapsize > 0) {
        O(1)
        swap2(arr, 0, --heapsize);
        //O(logN)
        heapIfy(arr, 0, heapsize);
    }
}

更快的方法：
Heapinsert步骤用heapify替换，即通过从最下层结点往前依次调用heapify来一次性将整个数组变成大根堆。此方法的时间复杂度为O(N)比heapinsert的O(logN)好
改进后：

public static void heapSort2(int[] arr) {
    if(arr == null || arr.length < 2) {
        return;
    }
    for(int i = arr.length-1; i>=0;i--) {
        heapIfy(arr, i, arr.length);
    }
    int heapsize = arr.length;
    //O(N)
    while(heapsize > 0) {
        O(1)
        swap2(arr, 0, --heapsize);
        //O(logN)
        heapIfy(arr, 0, heapsize);
    }
}

7、堆的拓展题：

一个数组几乎有序，几乎有序是指数组中的数从无序到有序移动的距离不超过k，k是一个相对于数组长度很小的数，用最小的时间复杂度排序这个数组。

*注：
1、扩容：在往小根堆里添加数字的时候，小根堆每次扩容是成倍扩的，添加N个数扩容代价是O(N（最多N次拷贝）logN（最多扩容logN次）)，平均到每个数的扩容代价是O(logN)
2、系统内置堆和手写堆的区别：内置堆实际上是一个黑盒，我们只能通过add和poll函数和它进行交互，但当有其他需求时（如需要将堆中的某一位的数改变，让其继续保持为堆），内置堆的调整效率不如手写堆，这时就需要用手写堆

步骤：准备一个小根堆（在java中优先级队列PriorityQueue底层实现就是一个小根堆），将前数组中前k+1个数加入到小根堆中，由于数字移动的距离不超过k，所以前k+1个数中一定有最小值，因此将小根堆中堆顶的数d出放在0位置上，然后将k+2位置的数加入到小根堆中，继续d出堆顶的数即为1位置的数，一直循环到数组末尾，时间复杂度为O(Nlogk)。

九、比较器

实现按不同标准排序。
比较器规则，两个参数A和B，若A要排在前面，返回一个负数，若B要排在前面，返回一个正数，若谁排前面无所谓，返回0。
应用，可以将优先级队列改为大根堆，或指定较为复杂的比较策略

public static class NodeComparator implements Comparator{

    @Override
    public int compare(Node o1, Node o2) {
        return o1.weight - o2.weight;
    }
}
PriorityQueue nodesqueue = new PriorityQueue(new EdgeComparator());

十、非比较排序

前面的排序算法都是基于比较的排序，理论时间复杂度下限是O(NlogN)，而非比较排序是可以根据数据状况进行的特殊的排序算法，可以突破O(NlogN)来到O(N)。

1、计数排序

若一组数据中的数都在j-k区间内，那么我们可以准备一个大小为k-j+1的数组，然后遍历数组，将j~k每个个数出现的次数记录在准备的数组中，然后将记录数组还原回原数组完成排序，时间复杂度为O(N+k-j)，额外空间复杂度为O(k-j),但是这种算法只在k-j比较小的情况下适用，否则空间代价会很高。

2、基数排序

准备十个桶（队列）0-9，将数字按照个位数字依次入桶，然后按照先进先出原则出桶，然后将数字按照十位数字依次入桶，以此类推，数组中为数最多的数字有多少位就循环几次，最后出桶排序完成。

十一、排序总结 1、 排序算法的稳定性：相同值的相对次序在排序完后不变。

基础类型数据排序稳定性没用，但是对对象等复杂类型数据的排序有用。

算法时间复杂度空间复杂度稳定性选择排序O(N^2)O(1)不稳定冒泡排序O(N^2)O(1)不稳定插入排序O(N^2)O(1)稳定归并排序O(NlogN)O(N)稳定快速排序（3.0）O(NlogN)O(logN)不稳定堆排序O(NlogN)O(1)不稳定桶排序O(NlogN)O(1)不稳定桶排序（计数和基数排序）稳定

排序算法优先使用快速排序，因为快速排序的常数项经过实验证明是最小的，所以理论上是最快的；若有空间要求优先使用堆排序；若有稳定性要求优先使用归并排序；根据数据状况可以考虑使用桶排序。

注：
1）基于比较的排序时间复杂度最小O(NlogN)
2）基于比较的排序时间复杂度O(NlogN)，空间复杂度小于O(N)还稳定的排序算法目前不存在。

上图的第五点，相当于快排序，为01标准的partition，性质和快排序一样，想做到稳定很难。
2、 工程上对排序的改进
1） 充分利用O(NlogN)和O(N^2)排序的各自优势，如在小样本量（<=60）时使用插入排序，可以利用插入排序常数项小的优势，大样本量使用快速排序，可以利用快速排序时间复杂度低的优势。归并排序同理。
2） 稳定性考虑