排序算法

冒泡排序

冒泡排序算法的运作如下：

1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
3. 针对所有的元素重复以上的步骤，除了最后一个。
4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

时间复杂度O(n^2)，空间复杂度O(1)，稳定排序：即相同的元素在排序后次序没有改变

代码实现：

static int[] bubbleSort(int[] arr) {
    for (int i=0; i<arr.length; i++) { //0~N-1 次循环
        //一轮比较后找到最大的元素，放到下标arr.length-1-i位置
        for (int j=0; j<arr.length-1-i; j++) {
            if (arr[j] > arr[j+1]) {
                swap(arr, j+1, j); //交互元素
            }
        }
    }
    return arr;
}

助记码
i∈[0,N-1)//循环N-1遍
    j∈[0,N-1-i)//每遍循环要处理的无序部分
    swap(j,j+1)  //两两排序（升序/降序）

选择排序

工作原理如下：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

时间复杂度O(n^2)，空间复杂度O(1)，不稳定的排序

代码实现：

static int[] selectSort(int[] arr) {
    for (int i=0; i<arr.length; i++) {
        int min = i;
        //找到i下标起始的序列中的最小元素
        for (int j=i+1; j<arr.length; j++) {
            if (arr[min] > arr[j]) {
                min = j;
            }
        }
        swap(arr, i, min);
    }
    return arr;
}

插入排序

工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：

1. 从第一个元素开始，该元素可以认为已经被排序
2. 取出下一个元素，在已经排序的元素序列中从后向前扫描
3. 如果该元素（已排序）大于新元素，将该元素移到下一位置
4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
5. 将新元素插入到该位置后
6. 重复步骤2~5

时间复杂度O(n^2)，空间复杂度O(1)，稳定的排序

实现代码：

static int[] insert(int[] arr) {
    for (int i=1; i<arr.length; i++) {
        int temp = arr[i], j=0;//保存当前待排序元素
        for (j=i-1; j>=0 && arr[j] > temp; j--) {//从后往前遍历
            arr[j+1] = arr[j];//对数值大的，元素后移
        }
        arr[j+1] = temp;//将待排序元素插入到正确位置
    }
    return arr;
}

  static void insertSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {//从下标1的元素开始，扫描到最后一个
            int j = i;
            while (j >= 1) { //将 i 处元素和它之前的元素比较，插入到合适的位置
                if (arr[j] < arr[j-1]) {
                    swap(arr, j, j-1);
                    j--;
                } else {
                    break;
                }
            }
        }
    }

希尔排序

希尔排序是插入排序的升级版，希尔排序是基于插入排序的以下两点性质而提出改进方法的：
1.插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率
2.但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位
希尔排序通过将比较的全部元素分为几个区域来提升插入排序的性能。这样可以让一个元素可以一次性地朝最终位置前进一大步。然后算法再取越来越小的步长进行排序，算法的最后一步就是普通的插入排序，但是到了这步，需排序的数据几乎是已排好的了（此时插入排序较快）。
假设有一个很小的数据在一个已按升序排好序的数组的末端。如果用复杂度为O(n2)的排序（冒泡排序或插入排序），可能会进行n次的比较和交换才能将该数据移至正确位置。而希尔排序会用较大的步长移动数据，所以小数据只需进行少数比较和交换即可到正确位置。
即希尔排序通过调整插入步长来实现更快速高效的数据调整。

步长的选择是希尔排序的重要部分。只要最终步长为1任何步长序列都可以工作。Donald Shell最初建议步长选择为 n/2并且对步长取半直到步长达到1。已知的最好步长序列是由Sedgewick提出的(1, 5, 19, 41, 109,...)，这项研究也表明“比较在希尔排序中是最主要的操作，而不是交换。”用这样步长序列的希尔排序比插入排序要快，甚至在小数组中比快速排序和堆排序还快，但是在涉及大量数据时希尔排序还是比快速排序慢。

时间复杂度O(nlog^2n)，括号内是n乘以logn的平方，空间复杂度O(1)，不稳定的排序

代码实现：

static int[] shellInsert(int[] arr) {
    int foot = arr.length / 2;//步长初始化
    while (foot >= 1) {
        for (int i=1; i<arr.length; i++) {
            int temp = arr[i], j=0;
            for (j=i-foot; j>=0 && arr[j] > temp; j=j-foot) {
                arr[j+foot] = arr[j];
            }
            arr[j+foot] = temp;
        }
        foot /= 2;//调整步长
    }
    
    return arr;
}

快速排序

快速排序使用分治法（Divide and conquer）策略来把一个序列（list）分为两个子序列（sub-lists）。
步骤为：

1. 从数列中挑出一个元素，称为"基准"（pivot），
2. 重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
3. 递归地（recursively）对小于基准值元素的子数列和大于基准值元素的子数列排序。

递归到最底部时，数列的大小是零或一，也就是已经排序好了。这个算法一定会结束，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。

时间复杂度O(nlogn)，，空间复杂度O(logn)，不稳定的排序

原地（in-place）分区的版本代码：
原地分区算法，它分区了标示为"左边（left）"和"右边（right）"的序列部分，借由移动小于等于a[pivotIndex]的所有元素到子序列的开头，留下所有大于的元素接在他们后面。在这个过程它也为基准元素找寻最后摆放的位置，也就是它回传的值。

static int partition(int[] arr, int left, int right) {
    int pivot = left-1;//初始基准下标设定
    //默认基准值为arr[right]
    //这里可以先随机选择一个基准值，然后将其和arr[right]交换即可
    
    for ( ;left <= right; left++) {
        //注意等号比较重要，如果不加等号，则需要在for循环结束后swap(arr, ++pivot, right);即将基准值放到正确的位置。
        if (arr[left] <= arr[right]) {
            swap(arr, ++pivot, left);//将小于等于基准值的元素移动到序列开头
        }
    }
    return pivot;//返回调整后的基准值下标
}

快速排序算法：

static void quick(int[] arr, int left, int right) {
    if (left >= right) return;//边界检查
    int pivot = partition(arr, left, right);
    quick(arr, left, pivot-1);
    quick(arr, pivot+1, right);
}

归并排序

该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。
归并操作（merge），也叫归并算法，指的是将两个已经排序的序列合并成一个序列的操作。归并排序算法依赖归并操作。

时间复杂度O(nlogn)，，空间复杂度O(n)，稳定的排序

迭代法

1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置
3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
4. 重复步骤3直到某一指针到达序列尾
5. 将另一序列剩下的所有元素直接复制到合并序列尾

归并操作代码：

static void mergeProcess(int[] arr, int left, int mid, int right) {
    int[] temp = new int[right-left+1];//合并空间
    int l = left;//左边序列起始下标
    int r = mid+1;//右边序列起始下标
    int id = 0;//合并空间起始下标

    while (l <= mid && r <= right) {//合并
        if (arr[l] < arr[r]) {//先放入小的
            temp[id++] = arr[l++];
        } else {
            temp[id++] = arr[r++];
        }
    }
    
    //合并剩余的序列
    while (l <= mid) temp[id++] = arr[l++];
    while (r <= right) temp[id++] = arr[r++];
    
    //将排好的序列复制到原序列
    for (int i=0; i<id; i++) {
        arr[left+i] = temp[i];
    }
}

递归归并排序:
其实就是将序列先分割成一个个小的序列，然后再对小序列进行合并，同时在合并的过程中进行排序。

static void merge(int[] arr, int left, int right) {
    if (left >= right) return;
    int mid = (left+right) / 2;//找到分割点下标
    merge(arr, left, mid);//分割左
    merge(arr, mid+1, right);//分割右
    mergeProcess(arr, left, mid, right);//合并
}

非递归法 ： 边界条件不好控制，易出错。
原理如下（假设序列共有n个元素）：

1. 将序列每相邻两个数字进行归并操作，形成 floor(n/2)个序列，排序后每个序列包含两个元素
2. 将上述序列再次归并，形成floor(n/4)个序列，每个序列包含四个元素
3. 重复步骤2，直到所有元素排序完毕

static void merge2(int[] arr) {
    int step = 1;//序列合并的子序列起始长度为1
    
    while (step <= arr.length) {
        int i=0;
        //将2个step长的序列合并为一个序列，长度加倍
        for ( ; i+2*step-1<arr.length; i += 2*step) {
            mergeP(arr, i, i+step-1, i+2*step-1);//合并2个子序列
        }

        //对长度不足2*step的序列尾进行合并，且最后一次整个序列的合并也由此完成
        if (i+step-1 < arr.length) {
            mergeP(arr, i, i+ step-1, arr.length-1);
        }
        step *= 2;
    }
}

//写法二
static void merge2(int[] arr) {
    int before = 1;//合并前序列长
    int after = 0;//合并后序列长度
    
    while (before <= arr.length) {
        after = before * 2;//将2个序列合并为一个序列，长度加倍
        int i=0;
        for ( ; i+after-1<arr.length; i += after) {
            mergeProcess(arr, i, i+before-1, i+after-1);//合并2个子序列
        }
        
        //对长度不足after的序列尾进行合并，且最后一次整个序列的合并也由此完成
        if (i+before-1 < arr.length) {
            mergeProcess(arr, i, i+ before-1, arr.length-1);
        }
        before = after;
    }
}

堆排序

利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
通常堆是通过一维数组来实现的。在数组起始位置为0的情形中：
父节点i的左子节点在位置(2i+1);
父节点i的右子节点在位置(2i+2);
子节点i的父节点在位置floor((i-1)/2);

在堆的数据结构中，堆中的最大值总是位于根节点(在优先队列中使用堆的话堆中的最小值位于根节点)。
堆中定义以下几种操作：
最大堆调整（Max_Heapify）：将堆的末端子节点作调整，使得子节点永远小于父节点
创建最大堆（Build_Max_Heap）：将堆所有数据重新排序
堆排序（HeapSort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算

堆排序的过程：

1. 将数组调整为最大堆
2. 将最大堆的根节点，即当前堆的最大值和数组未排序部分的最后一个值替换
3. 重新调整最大堆，最大堆的数组长度是无序数组的长度
4. 重复2，3步骤

//最大堆调整，id是待调整的元素下标，len是待调整的数组长度
//一般调整时认为待调整节点以后的元素是符合最大堆的分布规律的    
static void heapAdjust(int[] arr, int id, int len) {
    while (id*2 + 1 < len) {
        int child = id*2 + 1;//左孩子
        if (child+1 < len && arr[child+1] > arr[child]) {
            child++;//右孩子大于左孩子情况
        }
        
        if (arr[child] > arr[id]) {//右孩子大于父节点
            swap(arr, id, child);//替换
            id = child;//在新的节点上开启下一轮比较
        } else {
            break;
        }
    }
}

static int[] heapSort(int[] arr) {
    int n = arr.length;
    for (int i= n/2; i>=0; i--) {//生成最大堆
        heapAdjust(arr, i, n);
    }
    
    for (int i=n-1; i>0; i--) {//每次调整最大堆的数组长度
        swap(arr, i, 0);//当前堆的最大值和数组未排序部分的最后一个值替换
        heapAdjust(arr, 0, i);//调整最大堆
    }
    return arr;
}