十大经典算法详解

这个博客总结的不错。

结合其他博客与相关内容，此篇文章逐渐被完善，便于读者理解。

[TOC]

冒泡排序

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

从头开始，每次两个相邻的元素，若大者在前，则交换两元素直至数组末尾此时最大元素为数组最后的元素重复以上步骤，从头开始至上一轮比较的末尾元素；

public static void bubbleSort(int[] array) {
    if (array.length < 2) {
        return;
    }
    // 每轮询一遍，都将最大的元素移到最后一位，所以end--
    for (int end = array.length - 1; end > 0; end--) {
        // 每次都从数组的第一位开始遍历
        for (int i = 0; i < end; i++) {
            if (array[i] > array[i + 1]) {
                swap(array, i, i + 1);
            }
        }
    }
}

数据的顺序排好之后，冒泡算法仍然会继续进行下一轮的比较，直到arr.length-1次，后面的比较没有意义的设置标志位，防止后面不必要的遍历

 public static void bubbleSort2(int[] array) {
    if (array.length < 2) {
        return;
    }
    // 每轮询一遍，都将最大的元素移到最后一位，所以end--
    for (int end = array.length - 1; end > 0; end--) {
        // 这样当一轮比较结束后如果flag仍为false，即：这一轮没有发生交换，说明数据的顺序已经排好，没有必要继续进行下去。
        boolean ixExchanged = false;
        // 每次都从数组的第一位开始遍历
        for (int i = 0; i < end; i++) {
            if (array[i] > array[i + 1]) {
                swap(array, i, i + 1);
                ixExchanged = true;
            }
        }
        if (!ixExchanged) {
            break;
        }
    }
}

/**
 * 交换元素位置
 *
 * @param array
 * @param index
 * @param nextIndex
*/
private static void swap(int[] array, int index, int nextIndex) {
    int temp = array[index];
    array[index] = array[nextIndex];
    array[nextIndex] = temp;
}

选择排序

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

选择排序（Selection sort）是一种简单直观的排序算法第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾以此类推，直到全部待排序的数据元素的个数为零选择排序是不稳定的排序方法

public static void selectSort(int array[]) {
    // 每次遍历将最小值放到在下标 i 上
    for (int i = 0; i < array.length; i++) {
        int minIndex = i;
        for (int j = i + 1; j < array.length; j++) {
            if (array[minIndex] > array[j]) {
                // 选出出最小值的下标
                minIndex = j;
            }
        }
        if (minIndex != i) {
            swap(array, i, minIndex);
        }
    }
}

插入排序

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

插入排序，一般也被称为直接插入排序。对于少量元素的排序，它是一个有效的算法将第一个元素看作有序序列，后续元素当作无需序列，依次将无序序列元素插入有序序列当中；在其实现过程使用双层循环，外层循环对除了第一个元素之外的所有元素，内层循环对当前元素前面有序表进行待插入位置查找，并进行移动

InsertionSort 和打扑克牌时，从牌桌上逐一拿起扑克牌，在手上排序的进程相同。举例： Input: {4, 3, 8, 5, 2, 6, 1, 7} 首先拿起第一张牌, 手上有 {4}。拿起第二张牌 3, 把 3 insert 到手上的牌 {4}, 得到 {3 ，4}。拿起第三张牌 8, 把 8 insert 到手上的牌 {3，4 }, 得到 {3 ，4，8}。

插入排序由N-1趟排序组成。对于p=1到N-1趟排序后，插入排序保证从位置0到位置p上的元素为已排序状态。即插入排序利用了从位置0到p-1位置上已经有序的条件，将位置p上的元素向前查找适当的位置插入此元素。

public static void insertionSort(int[] array) {
    if (array.length <= 1) {
        return;
    }
    // i = 0 默认有序，所以从 i = 1 开始遍历
    for (int i = 1; i < array.length; i++) {
        // 其实就是一个往后插入的逆向冒泡排序的过程
        for (int j = i - 1; j >= 0 && array[j] > array[j + 1]; j--) {
            swap(array, j, j + 1);
        }
    }
}

// 为后面的希尔排序铺垫
public static void insertionSort2(int[] array) {
    if (array.length <= 1) {
        return;
    }
    // 待插入元素，array[0]默认排号序，作为前序子数组
    int i = 1;
    while (i < array.length) {
        // 起始位置：获取前序子数组最后一位
        int j = i - 1;
        int waitInsert = array[i];
        while (j >= 0 && array[j] > waitInsert) {
            // j-- 遍历，找到需要插入的位置
            array[j + 1] = array[j];
            j--;
        }
        // 插入前序子数组的末尾
        array[j + 1] = waitInsert;
        i++;
    }
}

希尔排序

时间复杂度O(nlogn)，空间复杂度O(1)，不稳定。

希尔排序(Shell’s Sort)是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort）,是直接插入排序算法的一种更高效的改进版本

希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至 1 时，整个文件恰被分成一组，算法便终止

选择一个增量序列，初始增量gap=length/2，后续元素依次为前一元素除2，直至gap=1；每轮以gap为步长，在列表上进行采样，将列表分为gap个小组，在每个小组内进行选择排序；重复第二步，直至gap=1；辅助理解参考博客园

// 直接插入排序增量是 1 ，希尔排序增量是 gap
public static void shellSort(int[] array) {
    int length = array.length;
    for (int gap = length / 2; gap >= 1; gap /= 2) {
        for (int i = gap; i < length; i++) {
            // 使用插入排序算法，将元素依次插入所在小组的已排序列表中
            // 待插入元素
            int waitInsert = array[i];
            int j = i - gap;
            // 前序子数组已经排好序，反向遍历，找到合适的位置插入元素
            while (j >= 0 && array[j] >= waitInsert) {
                array[j + gap] = array[j];
                j -= gap;
            }
            array[j + gap] = waitInsert;
        }
    }
}

归并排序

时间复杂度O(nlogn)，空间复杂度O(n)，稳定。

归并排序（Merge Sort）是建立在归并操作上的一种有效，稳定的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用

将列表从正中间分为两个子列表；按照第一步，递归拆分每个子列表，直至子列表最大长度为1；按照拆分层级，依次按大小合并各子列表，直至全部合并完成。

基本思想

归并排序是用分治思想，分治模式在每一层递归上有三个步骤：

分解（Divide）：将n个元素分成个含n/2个元素的子序列。
解决（Conquer）：用合并排序法对两个子序列递归的排序。
合并（Combine）：合并两个已排序的子序列已得到排序结果

实现逻辑：

迭代法

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

递归法

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

两两合并，先比较左右子数组头部元素（大或小），将小的头部元素移动到新数组（此时移动的旧子数组头部因为已经为空，所以同数组的下一个元素晋升为新的头元素）当一个子数组为空的时候，依次将另一个子数组剩余元素移动到新数组末尾

递归版本：

public static void main(String[] args) {
    int[] array = { 6, 4, 8, 9, 2, 3, 1};
    mergeSort(array);
    for (int num : array) {
        System.out.print(num + " ");
    }
}

 // 递归版，入口方法-1
public static void mergeSort(int[] array) {
    // 先开辟一个大小相同的空数组，防止频繁申请空间
    int[] tempArray = new int[array.length];
    mergeSort(array, 0, array.length - 1, tempArray);
}

// 递归版 方法-2
public static void mergeSort(int[] array, int left, int rigth, int[] tempArray) {
    if (left < rigth) {
        int mid = (left + rigth) >> 1;
        // 分为左右两个子数组
        // { 6, 4, 8, 9, 2, 3, 1}  left = 0 ,right = 6 , mid = 3
        // {6,4,8,9} left = 0, right = 3, mid = 1; {2,3,1} left = 4, right = 6, mid = 5;
        // {6，4} {8，9} {2，3} {1}
        // {6} {4} {8} {9} {2} {3} {1} 本应该分成这样，但此时left = right, 不满足 if 条件，所以执行上面的merge合并操作
        // 上一步merger操作的 left = 0;right = 1; mid = 0
        mergeSort(array, left, mid, tempArray);
        mergeSort(array, mid + 1, rigth, tempArray);
        merge(array, left, mid, rigth, tempArray);
    }
}

// 递归版 方法-3
// 子数组合并实现
public static void merge(int[] array, int left, int mid, int rigth, int[] tempArray) {
    int i = left; // 左数组头元素
    int j = mid + 1; // 右数组头元素
    int k = 0; // 中间数组有序存储合并后的元素
    // 将小的头部元素移动到新数组（此时移动的旧子数组头部因为已经为空，所以下一个元素晋升为新的头元素）
    // 合并[left,mid]、[mid+1,right]两个数组
    // 所以 i 的边界是 = mid,大于mid表示左数组遍历完毕（为空）
    // j 的边界是 = right，大于 right 表示右数组遍历完毕（为空）
    while (i <= mid && j <= rigth) {
        // 比较两个子数组的头部元素，小的移动到中间数组，下标 ++ 表示后一位晋升为头部元素
        if (array[i] < array[j]) {
            tempArray[k++] = array[i++];
        } else {
            tempArray[k++] = array[j++];
        }
    }
    // 将未遍历完的子数组，依次添加到中间数组
    while (i <= mid) {
        tempArray[k++] = array[i++];
    }

    while (j <= rigth) {
        tempArray[k++] = array[j++];
    }

    // 将合并的有序中间数组替换到原数组位置中
    // 因为每次中间数组都是以 0 下标开始，所以先对 k 作初始化
    k = 0;
    while (left <= rigth) {
        array[left++] = tempArray[k++];
    }
}

迭代版本

// 第一次比2个元素，第二次4个元素，第三次8个元素，第四次16个元素，两两归并
public static void mergeSortIteration(int[] array) {
    int length = array.length;
    // 创建一个大小和目标数组相同大小的中间数组
    int[] tempArray = new int[length];
    for (int block = 1; block < length; block *= 2) { // 步长
        for (int leftMin = 0; leftMin < length - 1; leftMin += block) {
            int leftMax = leftMin + block; // 左子数组的边界
            int rightMin = leftMin + block; // 右子数组的起始位
            int rightMax = rightMin + block; // 右子数组的边界
            if (rightMax > length) { // 右子数组的边界不能超过原数组长度
                rightMax = length;
            }
            // 中间数组下标
            int k = 0;
            while (leftMin < leftMax && rightMin < rightMax) {
                if (array[leftMin] < array[rightMin]) { // 左右两子数组头部元素比较
                    tempArray[k++] = array[leftMin++];
                } else {
                    tempArray[k++] = array[rightMin++];
                }
            }
            while (leftMin < leftMax) { // 左子数组没遍历完
                tempArray[k++] = array[leftMin++];
            }

            while (rightMin < rightMax) { // 右子数组没遍历完
                tempArray[k++] = array[rightMin++];
            }
            // 将中间数组元素复制到目标数组[leftMin,rightMax]位置
            while (k > 0) {
                array[--rightMax] = tempArray[--k];
            }
        }
    }
}

迭代结果

交换前：9 8 6 4 3 2 1 
block:1 leftMin:0 leftMax:1 rightMin:1 rightMax:2
交换后8 9 6 4 3 2 1 

交换前：8 9 6 4 3 2 1 
block:1 leftMin:2 leftMax:3 rightMin:3 rightMax:4
交换后8 9 4 6 3 2 1 

交换前：8 9 4 6 3 2 1 
block:1 leftMin:4 leftMax:5 rightMin:5 rightMax:6
交换后8 9 4 6 2 3 1 

交换前：8 9 4 6 2 3 1 
block:2 leftMin:0 leftMax:2 rightMin:2 rightMax:4
交换后4 6 8 9 2 3 1 

交换前：4 6 8 9 2 3 1 
block:2 leftMin:4 leftMax:6 rightMin:6 rightMax:7
交换后4 6 8 9 1 2 3 

交换前：4 6 8 9 1 2 3 
block:4 leftMin:0 leftMax:4 rightMin:4 rightMax:7
交换后1 2 3 4 6 8 9 

快速排序

最差时间复杂度为O(n^2)，最优时间复杂度O(nlogn)，空间复杂度O(logn)【每次记录断点值，最好的情况就每次记录一半的断点，类似于二分法，左侧用完的断点用完可以释放，右侧同理，如果是最差的情况，即选择了边界值，所以最差的空间复杂度为O(n)】，不稳定。(论文级别的可以做到稳定性《01 stable sort》)

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序

从列表中选出一个元素，作为“基准”pivot，基准一般随机选择，或采用最左端、最右端和中间位置3元素的中值；
将小于基准的元素排在基准前面，大于基准的元素排在基准后面，此时基准元素所在位置即为其最终排序完成时的位置；
以基准元素为界，将列表分为两个子列表；
递归地对子列表重复上述操作。

在工程上是使用随机选择，从概率的角度讲，时间复杂度为O(nlogn)。划分值的值尽量可以等分数组，如果为边界值，则算法会退化成O(n^2)。

左程云算法：利用一个左边界小于区，最开始在-1位置，然后与最后一个数进行比较，然后左边的指针与最后一个数进行比较，如果比他更小，则当前的值与小于区的下一个位置进行交换，再将小于区的位置增加1。

递归版本：

简易版：

// 简易版，选数组的第一个元素作为基准
public static int[] quicksort(int[] array) {
    return quicksort(array, 0, array.length - 1);
}

public static int[] quicksort(int[] array, int left, int right) {
    int basic = array[left];
    int i = left;
    int j = right;
    // 第一趟排序，根据基准划分左右序列
    while (i < j) {
        while (i < j && array[j] > basic) { // 说明右值大于基准值，指针向前移动
            j--;
        }
        while (i < j && array[i] < basic) { // 说明左值大于基准值，指针后移
            i++;
        }
        if (i < j && array[i] == array[j]) {
            i++;
        } else {
            int temp = array[i];
            array[i] = array[j];
            array[j] = temp;
        }
    }
    if (i - 1 > left) {
        array = quicksort(array, left, i - 1);
    }
    if (j + 1 < right) {
        array = quicksort(array, j + 1, right);
    }
    return array;
}

左程云版本：

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

public static void quickSort(int[] arr, int l, int r) {
    if (l < r) {
        swap(arr, l + (int) (Math.random() * (r - l + 1)), r);
        int[] p = partition(arr, l, r);
        quickSort(arr, l, p[0] - 1);
        quickSort(arr, p[1] + 1, r);
    }
}

public static int[] partition(int[] arr, int l, int r) {
    int less = l - 1;
    int more = r;
    while (l < more) {
        if (arr[l] < arr[r]) {
            swap(arr, ++less, l++);
        } else if (arr[l] > arr[r]) {
            swap(arr, --more, l);
        } else {
            l++;
        }
    }
    swap(arr, more, r);
    return new int[] { less + 1, more };
}

迭代版本：

// 快速排序 非递归(迭代版)
void quickSortIteration(vector<int>& array) {
	stack<vector<int>> boundaries;
	int left = 0, right = array.size() - 1;
	while (left < right || !boundaries.empty()) {
		if (left >= right) {
			vector<int> boundary = boundaries.top();
			boundaries.pop();
			left = boundary[0];
			right = boundary[1];
		}
		int pivotLoction = partition(array, left, right);
		if (pivotLoction + 1 < right) {
			boundaries.push({ pivotLoction + 1, right });
		}
		right = pivotLoction - 1;
	}
}

堆排序

时间复杂度O(nlogn)，空间复杂度O(1)，不稳定。

建立堆的过程是O(n)的时间复杂度。

按层将堆转换成数组后：大顶堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2] 小顶堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]

堆排序的基本思想： 将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了（一般升序采用大顶堆，降序采用小顶堆)

将数字转化为一个堆；堆是具有以下两属性的二叉树：（1）每个节点的值大于等于其子节点的值；（2）树完全平衡，即最底层叶子节点都位于左侧（完全），且左右子树高度相差不超过1（平衡）；因为，堆是完全平衡树，因此可以用数组直接表示：堆也被称为优先队列，具有先进先出的特性，在堆底插入元素，在堆顶取出元素。
取出堆顶元素（最大元素），作为有序数数组末尾元素，并对二叉树进行调整使其满足堆的特性；
重复上一步骤，依次取出堆顶元素，并插入到有序数组中，上一插入元素之前的位置，直到堆空为止；

左程云算法：

public static void heapSort(int[] arr) {
    if (arr == null || arr.length < 2) {
        return;
    }
    for (int i = 0; i < arr.length; i++) {
        // 插入，建立一个大根堆
        heapInsert(arr, i);
    }
    int size = arr.length;
    // 让第一个数和最后一个数交换位置
    // 最后一个元素不再动了
    swap(arr, 0, --size);
    // 重复调整大根堆
    while (size > 0) {
        heapify(arr, 0, size);
        swap(arr, 0, --size);
    }
}

public static void heapInsert(int[] arr, int index) {
    // 当前节点位置比父节点位置更大，则循环交换
    while (arr[index] > arr[(index - 1) / 2]) {
        swap(arr, index, (index - 1) / 2);
        index = (index - 1) / 2;
    }
}
// 跟自己的左右孩子比较，将大的数上移
public static void heapify(int[] arr, int index, int size) {
    // 左孩子下标
    int left = index * 2 + 1;
    while (left < size) {
        // 在右孩子不越界，然后找到左右孩子中更大的孩子下标
        int largest = left + 1 < size && arr[left + 1] > arr[left]
                            ? left + 1 
                            : left;
        // 获取左右孩子下标后，判断与父节点的大小，返回一个最大值的下标
        largest = arr[largest] > arr[index] ? largest : index;
        // 如果最大值为父节点，即无需调整，退出循环
        if (largest == index) {
            break;
        }
        // 需要调整大根堆
        swap(arr, largest, index);
        // 更换父节点的下标值，继续执行左右孩子的大小比较
        index = largest;
        left = index * 2 + 1;
    }
}

计数排序

时间复杂度O(n+k)，空间复杂度O(k)，稳定。

遍历待排序数组A，找出其最小值min和最大值max；
创建一个长度为max-min+1的数组B，其所有元素初始化为0，数组首位对应数组A的min元素，索引为i位置对应A中值为min+i的元素；
遍历数组A，在B中对应位置记录A中各元素出现的次数；
遍历数组B，按照之前记录的出现次数，输出几次对应元素；

// 计数排序
void countSort(vector<int>& array){
    if (array.empty()){
        return;
    }
    //找出最大最小值
    int min = array.front(),max = array.front();
    for (int i = 1; i < array.size(); i++){
        if (min > array[i]){
            min = array[i];
        }
        else if (max < array[i]){
            max = array[i];
        }
    }

    // 记录各元素出现次数
    vector<int> counts(max - min + 1);
    for (int i = 0; i < array.size(); i++){
        counts[array[i] - min]++;
    }

    // 根据记录的次数输出对应元素
    int index = 0;
    for (int j = 0; j < counts.size(); j++){
        int n = counts[j];
        while (n--){
            array[index] = j + min;
            index++;
        }
    }
}

桶排序

时间复杂度O(n+k)，空间复杂度O(n+k)，稳定。

设置固定数量的空桶；
找出待排序数组的最大值和最小值；
根据最大最小值平均划分各桶对应的范围，并将待排序数组放入对应桶中；
为每个不为空的桶中数据进行排序（例如，插入排序）；
拼接不为空的桶中数据，得到排序后的结果。

// 桶排序
void bucketSort (vector<int>& array, int bucketCount){
    if (array.empty()){
        return;
    }
    // 找出最大最小值
    int max = array.front(), min = array.front();
    for (int i = 1; i < array.size(); i++){
        if (min > array[i]){
            min = array[i];
        }
        else if (max < array[i]){
            max = array[i];
        }
    }

    // 将待排序的各元素分入对应桶中
    vector<vector<int>> buckets(bucketCount);
    int bucketSize = ceil((double)(max - min + 1) / bucketCount);
    for (int i = 0; i < array.size(); i++){
        int bucketIndex = (array[i] - min) / bucketSize;
        buckets[bucketIndex].push_back(array[i]);
    }

    // 对各桶中元素进行选择排序
    int index = 0;
    for (vector<int> bucket : buckets){
        if (!bucket.empty()){
            // 使用选择排序算法对桶内元素进行排序
            selectSort(bucket);
            for (int value : bucket){
                array[index] = value;
                index++;
            }
        }
    }

}
// 桶排序
void bucketSort (vector<int>& array){
    bucketSort (array, array.size() / 2);
}

基数排序

时间复杂度O(n*k)，空间复杂度O(n+k)，稳定。

将各待比较元素数值统一数位长度，即对数位短者在前补零；
根据个位数值大小，对数组进行排序；
重复上一步骤，依次根据更高位数值进行排序，直至到达最高位；

jishu

// 基数排序 （只适用于正数，此处不适用）
void radixSort(vector<int>& array){
    // 当前位数
    int curdigit = 10;
    // 当前位是否已超过最高为
    bool isOverHighest = false;
    while (!isOverHighest){
        isOverHighest = true;
        // 利用分桶的思想来实现按各位进行排序
        vector<vector<int>> buckets(10);
        for (int curVal : array){
            int bucketIndex = curVal % curdigit - curVal % (curdigit / 10);
            buckets[bucketIndex].push_back(curVal);
            if (isOverHighest && curVal / curdigit){
                isOverHighest = false;
            }
        }
        // 按照桶的顺序，将各桶内元素拼接起来
        int index = 0;
        for (vector<int> bucket : buckets){
            for (int value : bucket){
                array[index] = value;
                index++;
            }
        }
        curdigit *= 10;
    }
}

Algorithm