一文搞懂编程界中最基础最常见【必知必会】的十一个算法，再也别说你只是听说过【建议收藏+关注】_编程基础算法讲解_程序算法有哪些

直接插入排序的基本思想是将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增加1的有序表。在代码中，我们假设数组的第一个元素已经是有序表，从第二个元素开始遍历。对于第i个元素，我们将其暂存到一个临时变量中，然后从i-1开始向前遍历，将所有比它大的元素都向后移动一个位置，直到找到第一个比它小的元素，将其插入到这个位置。重复这个过程，直到整个数组排好序为止。

Shell排序

Shell 排序⼜称缩⼩增量排序, 由D. L. Shell在1959年提出，是对直接插⼊排序的改进。
原理： Shell排序法是对相邻指定距离(称为增量)的元素进⾏⽐较，并不断把增量缩⼩⾄1，完成排序。
Shell排序开始时增量较⼤，分组较多，每组的记录数⽬较少，故在各组内采⽤直接插⼊排序较快，后来增量di逐渐缩⼩，分组数减少，各组的记录数增多，但由于已经按di−1分组排序，⽂件叫接近于有序状态，所以新的⼀趟排序过程较快。因此Shell排序在效率上⽐直接插⼊排序有较⼤的改进。
在直接插⼊排序的基础上，将直接插⼊排序中的1全部改变成增量d即可，因为Shell排序最后⼀轮的增量d就为1。

稳定性：不稳定排序。

复杂度：

时间复杂度：O(n1.3)到O(n2)。Shell排序算法的时间复杂度分析⽐较复杂，实际所需的时间取决于各次排序时增量的个数和增量的取值。
研究证明，若增量的取值⽐较合理，Shell排序算法的时间复杂度约为O(n1.3)。
对于增量的选择，Shell 最初建议增量选择为n/2，并且对增量取半直到 1；D. Knuth教授建议di+1=⌊di−13⌋序列。
注意：增量每次变化取前⼀次增量的⼀般，当增量d等于1时，shell排序就退化成了直接插⼊排序了。

示例代码：

public class ShellSort {
public static void main(String[] args) {
int arr[] = { 3, 1, 23, 3, 1, 4, 5, 199, 20 };
shellSort(arr);
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}

public static void shellSort(int[] arr) {
int n = arr.length;
for (int gap = n / 2; gap > 0; gap /= 2) {
for (int i = gap; i < n; i++) {
int temp = arr[i];
int j = i;
while (j >= gap && arr[j - gap] > temp) {
arr[j] = arr[j - gap];
j -= gap;
}
arr[j] = temp;
}
}
}
}

选择类排序

选择类排序的基本⽅法是：每步从待排序记录中选出排序码最⼩的记录，顺序放在已排序的记录序列的后⾯，知道全部排完。

简单选择排序（⼜称直接选择排序）

原理：

从所有记录中选出最⼩的⼀个数据元素与第⼀个位置的记录交换；然后在剩下的记录当中再找最⼩的与第⼆个位置的记录交换，循环到只剩下最后⼀个数据元素为⽌。

稳定性：不稳定排序

时间复杂度：

最坏、最好和平均复杂度均为O(n2)，因此，简单选择排序也是常见排序算法中性能最差的排序算法。简单选择排序的⽐较次数与⽂件的初始状态没有关系，在第i趟排序中选出最⼩排序码的记录，需要做n-i次⽐较，因此总的⽐较次数是：
∑i=1n−1(n−i)=n(n−1)/2=O(n2)。

⽰例代码：

public static void selectionSort(int[] arr){
int n = arr.length;
for(int i = 0; i < n - 1; i++){
int minIndex = i;
for(int j = i + 1; j < n; j++){
if(arr[j] < arr[minIndex]){
minIndex = j;
}
}
int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
}

基本思想：

对于n个元素的序列，首先在其中找到最小的元素，然后将其放到序列的最前面；接着，再从剩余的n-1个元素中找到最小的元素，放到已排序的序列的末尾；重复这个过程，直到整个序列排好序为止。在代码中，我们通过两个嵌套的循环实现了这个过程。外层循环从第一个元素开始遍历到倒数第二个元素，内层循环从外层循环的下一个元素开始遍历到最后一个元素，找到其中最小的元素，并记录其下标minIndex。在内层循环结束后，如果minIndex不等于外层循环的下标i，说明找到了更小的元素，将其与arr[i]交换即可。重复这个过程，直到整个数组排好序为止。

堆排序

直接选择排序中，第⼀次选择经过了n-1次⽐较，只是从排序码序列中选出了⼀个最⼩的排序码，⽽没有保存其他中间⽐较结果。所以后⼀趟排序时⼜要重复许多⽐较操作，降低了效率。J. Willioms和Floyd在1964年提出了堆排序⽅法，避免这⼀缺点。

原理：

堆排序是一种基于二叉堆的排序算法，它的基本思想是将待排序的序列构建成一个大根堆（或小根堆），然后将堆顶元素与堆底元素交换位置，然后重新调整堆，将剩下的元素构建成一个新的大根堆（或小根堆），重复这个过程，直到整个序列排好序为止。在代码中，我们首先通过adjustHeap方法将待排序序列构建成一个大根堆，然后将堆顶元素与堆底元素交换位置，再将剩下的元素构建成一个新的大根堆，重复这个过程，直到整个序列排好序为止。

稳定性: 不稳定排序

在堆排序过程中，由于堆的构建和调整过程中都需要进行元素交换，因此可能会导致相同元素之间的相对位置发生改变。例如，对于序列[3, 3’, 2]，如果先将其构建成大根堆，就会得到[3’, 3, 2]，然后将堆顶元素3’与堆底元素2交换位置，得到[2, 3, 3’]，此时3和3’的相对位置就发生了改变。因此，堆排序是一种不稳定的排序算法。

复杂度：

堆排序的时间复杂度为O(nlogn)，其中n是待排序序列的长度。堆排序的基本过程可以分为两个步骤：构建堆和堆排序。构建堆的时间复杂度为O(n)，堆排序的时间复杂度为O(nlogn)。因此，堆排序的总时间复杂度为O(n+nlogn)=O(nlogn)。
堆排序的空间复杂度为O(1)，它不需要额外的存储空间来存储中间结果，只需要在原始数组上进行原地排序。因此，堆排序是一种空间复杂度为O(1)的原地排序算法。
堆排序的时间复杂度虽然不如快速排序和归并排序那么优秀，但是它具有稳定的时间复杂度，不受输入数据的影响。同时，堆排序是一种原地排序算法，不需要额外的存储空间，因此它在一些内存受限的场景下具有优势。

示例代码：

public class HeapSort {
public static void main(String[] args) {
int arr[] = { 3, 1, 23, 3, 1, 4, 5, 199, 20 };
heapSort(arr);
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
public static void heapSort(int[] arr){
int n = arr.length;
// 构建大根堆
for(int i = n / 2 - 1; i >= 0; i–){
adjustHeap(arr, i, n);
}
// 进行排序
for(int i = n - 1; i > 0; i–){
swap(arr, 0, i);
adjustHeap(arr, 0, i);
}
}
private static void adjustHeap(int[] arr, int i, int n){
int temp = arr[i];
for(int j = 2 * i + 1; j < n; j = 2 * j + 1){
if(j + 1 < n && arr[j + 1] > arr[j]){
j++;
}
if(arr[j] > temp){
arr[i] = arr[j];
i = j;
}else{
break;
}
}
arr[i] = temp;
}
private static void swap(int[] arr, int i, int j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}

归并排序

二路归并排序

算法思想：

归并排序属于⽐较类⾮线性时间排序，号称⽐较类排序中性能最佳者，在数据中应⽤中较⼴。
归并排序是分治法（Divide and Conquer）的⼀个典型的应⽤。将已有序的⼦序列合并，得到完全有序的序列；即先使每个⼦序列有序，
再使⼦序列段间有序。若将两个有序表合并成⼀个有序表，称为⼆路归并。

稳定性：稳定排序算法；

时间复杂度: 最坏，最好和平均时间复杂度都是Θ(nlgn)。

示例代码：

public class MergeSort {
public static void main(String[] args) {
int arr[] = { 3, 1, 23, 3, 1, 4, 5, 199, 20 };
mergeSort(arr);
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
public static void mergeSort(int[] arr){
int n = arr.length;
int[] temp = new int[n];
sort(arr, 0, n - 1, temp);
}
private static void sort(int[] arr, int left, int right, int[] temp){
if(left < right){
int mid = (left + right) / 2;
sort(arr, left, mid, temp);
sort(arr, mid + 1, right, temp);
merge(arr, left, mid, right, temp);
}
}
private static void merge(int[] arr, int left, int mid, int right, int[] temp){
int i = left, j = mid + 1, k = 0;
while(i <= mid && j <= right){
if(arr[i] <= arr[j]){
temp[k++] = arr[i++];
}else{
temp[k++] = arr[j++];
}
}
while(i <= mid){
temp[k++] = arr[i++];
}
while(j <= right){
temp[k++] = arr[j++];
}
for(int p = 0; p < k; p++){
arr[left + p] = temp[p];
}
}
}

算法思想：

归并排序的基本思想是：将待排序序列分成两个子序列，对这两个子序列分别进行归并排序，然后将它们合并成一个有序序列。在代码中，我们通过sort方法递归地将待排序序列分成两个子序列，然后对这两个子序列分别进行归并排序。在归并排序的过程中，我们需要用到一个临时数组temp来存储归并结果。我们通过merge方法将两个有序子序列合并成一个有序序列。具体地，我们使用三个指针i、j和k来遍历两个有序子序列和临时数组temp，比较arr[i]和arr[j]的大小，将较小的元素存入temp[k]中，并将对应的指针向后移动一位。当其中一个子序列遍历完时，我们将另一个子序列剩余的元素全部存入temp中。最后，我们将temp中的元素复制回原始数组arr中，完成归并排序的过程。

多路排序

示例代码：

public class MultMergeSort {
public static void main(String[] args) {
int arr[] = { 3, 1, 23, 3, 1, 4, 5, 199, 20 };
mergeSort(arr,3);
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
public static void mergeSort(int[] arr, int m){
int n = arr.length;
int[] temp = new int[n];
sort(arr, 0, n - 1, temp, m);
}
private static void sort(int[] arr, int left, int right, int[] temp, int m){
if(left < right){
int len = (right - left + 1) / m;
for(int i = 0; i < m; i++){
int l = left + i * len;
int r = l + len - 1;
if(i == m - 1){
r = right;
}
sort(arr, l, r, temp, m);
}
merge(arr, left, right, temp, m);
}
}
private static void merge(int[] arr, int left, int right, int[] temp, int m){
int[] p = new int[m];
int len = (right - left + 1) / m;
for(int i = 0; i < m; i++){
p[i] = left + i * len;
}
int k = left;
while(k <= right){
int min = Integer.MAX_VALUE;
int idx = -1;
for(int i = 0; i < m; i++){
if(p[i] <= left + i * len + len - 1 && arr[p[i]] < min){
min = arr[p[i]];
idx = i;
}
}
if(idx == -1){
break;
}
temp[k++] = arr[p[idx]++];
}
for(int i = left; i <= right; i++){
arr[i] = temp[i];
}
}
}

算法基本思想：

多路归并排序是归并排序的一种变种，它将待排序序列分成多个子序列，对每个子序列分别进行排序，然后将它们合并成一个有序序列。在代码中，我们通过sort方法递归地将待排序序列分成多个子序列，然后对每个子序列分别进行归并排序。在归并排序的过程中，我们需要用到一个临时数组temp来存储归并结果。我们通过merge方法将多个有序子序列合并成一个有序序列。具体地，我们首先将待排序序列分成m个子序列，对每个子序列分别进行归并排序。然后，我们通过p数组来记录每个子序列的当前位置，使用一个循环来遍历所有的子序列，每次找到当前m个子序列中最小的元素，将其存入temp中，并将对应的指针向后移动一位。当所有子序列遍历完时，我们将temp中的元素复制回原始数组arr中，完成归并排序的过程。

线性时间非比较类排序

计数排序

计数排序是⼀个⾮基于⽐较的排序算法，该算法于1954年由 Harold H. Seward 提出，它的优势在于在对于较⼩范围内的整数排序。

复杂度:

它的复杂度为Ο(n+k)（其中k是待排序数的范围），快于任何⽐较排序算法，缺点就是⾮常消耗空间。很明显，如果⽽且当O(k)>O(n*log(n))的时候其效率反⽽不如基于⽐较的排序，⽐如堆排序和归并排序和快速排序。

算法原理：

基本思想是对于给定的输⼊序列中的每⼀个元素x，确定该序列中值⼩于x的元素的个数。⼀旦有了这个信息，就可以将x直接存放到最终的输出序列的正确位置上。
例如，如果输⼊序列中只有17个元素的值⼩于x的值，则x可以直接存放在输出序列的第18个位置上。当然，如果有多个元素具有相同的值时，我们不能将这些元素放在输出序列的同⼀个位置上，在代码中作适当的修改即可。

算法步骤：

1.找出待排序的数组中最⼤的元素；
2. 统计数组中每个值为i的元素出现的次数，存⼊数组C的第i项；
3. 对所有的计数累加（从C中的第⼀个元素开始，每⼀项和前⼀项相加）；
4. 反向填充⽬标数组：将每个元素i放在新数组的第C(i)项，每放⼀个元素就将C(i)减去1。

复杂度：

时间复杂度：Ο(n+k)。
空间复杂度：Ο(k)。
要求：待排序数中最⼤数值不能太⼤。

稳定性：稳定。

代码⽰例：

public class CountSort {
public static void main(String[] args) {
int arr[] = { 3, 1, 23, 3, 1, 4, 5, 199, 20 };
countSort(arr);
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
public static void countSort(int[] arr){
int max = arr[0], min = arr[0];
for(int i = 1; i < arr.length; i++){
if(arr[i] > max){
max = arr[i];
}else if(arr[i] < min){
min = arr[i];
}
}
int[] count = new int[max - min + 1];
for(int i = 0; i < arr.length; i++){
count[arr[i] - min]++;
}
int k = 0;
for(int i = 0; i < count.length; i++){
for(int j = 0; j < count[i]; j++){
arr[k++] = i + min;
}
}
}
}

注意：计数排序是典型的以空间换时间的排序算法，对待排序的数据有严格的要求，⽐如待排序的数值中包含负数，最⼤值都有限制，请谨慎使⽤。
思想：

计数排序是一种非比较排序，它的基本思想是：统计待排序序列中每个元素出现的次数，然后根据元素的大小顺序依次输出。在代码中，我们首先通过一次遍历找到待排序序列中的最大值和最小值，然后创建一个计数数组count，用于存储每个元素出现的次数。具体地，我们遍历待排序序列，将每个元素的出现次数存储在对应的计数数组count中。然后，我们使用两个循环来输出排序结果。外层循环遍历count数组，内层循环遍历对应元素的出现次数，将元素按照出现次数依次输出。需要注意的是，在计数数组中，元素的下标i对应的是arr中的元素i + min。因此，在输出元素时，我们需要将下标i加上min才能得到正确的元素值。

基数排序

基数排序属于“分配式排序”（distribution sort），是⾮⽐较类线性时间排序的⼀种，⼜称“桶⼦法”（bucket sort）。顾名思义，它是透过键值的部分信息，将要排序的元素分配⾄某些“桶”中，藉以达到排序的作⽤。

稳定性：稳定的排序

因为在排序的过程中，对于相同的元素，它们在计数数组中的位置是相同的，所以它们在排序后的相对位置不会发生变化。

复杂度:

基数排序的时间复杂度为

O

(

d

(

n

k

)

)

O(d(n+k))

O(d(n+k))，其中

d

d

d表示数字的最大位数，

k

k

k表示基数（即每一位数字的取值范围）。可以看出，基数排序的时间复杂度与数字的位数有关，而与数字的大小无关。因此，当数字的位数不太大时，基数排序的效率非常高。另外，基数排序的空间复杂度也为

O

(

n

k

)

O(n+k)

O(n+k)，其中

k

k

k表示基数，这是由于需要使用计数数组来存储每个数字出现的次数。

示例代码：

public class RadixSort {
public static void main(String[] args) {
int arr[] = { 3, 1, 23, 3, 1, 4, 5, 199, 20 };
radixSort(arr);
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
public static void radixSort(int[] arr){
int max = arr[0];
for(int i = 1; i < arr.length; i++){
if(arr[i] > max){
max = arr[i];
}
}
int exp = 1;
int[] temp = new int[arr.length];
while(max / exp > 0){
int[] count = new int[10];
for(int i = 0; i < arr.length; i++){
count[(arr[i] / exp) % 10]++;
}
for(int i = 1; i < 10; i++){
count[i] += count[i - 1];
}
for(int i = arr.length - 1; i >= 0; i–){
temp[–count[(arr[i] / exp) % 10]] = arr[i];
}
for(int i = 0; i < arr.length; i++){
arr[i] = temp[i];
}
exp *= 10;
}
}
}

基本思想：

基数排序是一种非比较排序，它的基本思想是：从个位开始，依次对待排序序列的每一位进行排序。在代码中，我们首先通过一次遍历找到待排序序列中的最大值，然后从个位开始，依次对每一位进行排序。具体地，我们使用变量exp来表示当前排序位数，初始值为1。在每一轮排序中，我们创建一个计数数组count，用于存储每个数字出现的次数。我们遍历待排序序列，将每个数字的出现次数存储在对应的计数数组count中。然后，我们使用累加的方式将计数数组count中的值变成每个数字在排序后的数组中的最大下标。接着，我们从待排序序列的最后一位开始，将每个数字按照当前排序位数的大小放入临时数组temp中。在放置数字时，我们根据计数数组中的值，找到数字在临时数组中的下标，并将计数数组中对应的值减1。最后，我们将临时数组temp中的数字复制回原始数组arr中，完成一轮排序。需要注意的是，在每一轮排序结束后，我们需要将变量exp乘以10，以便对下一位进行排序。

桶排序

桶排序也是分配排序的⼀种，但其是基于⽐较排序的，这也是与基数排序最⼤的区别所在。

思想：

桶排序算法想法类似于散列表。⾸先要假设待排序的元素输⼊符合某种均匀分布，例如数据均匀分布在[ 0,1）区间上，则可将此区间划分为10个⼩区间，称为桶，对散布到同⼀个桶中的元素再排序。
要求：待排序数长度⼀致。

排序过程：

1. 设置⼀个定量的数组当作空桶⼦；
2. 寻访序列，并且把记录⼀个⼀个放到对应的桶⼦去；
3. 对每个不是空的桶⼦进⾏排序。
4. 从不是空的桶⼦⾥把项⽬再放回原来的序列中。
   例如待排序列K= {49、 38 、 35、 97 、 76、 73 、 27、 49 }。这些数据全部在1—100之间。因此我们定制10个桶，然后确定映射函数f(k)=k/10。则第⼀个关键字49将定位到第4个桶中(49/10=4)。依次将所有关键字全部堆⼊桶中，并在每个⾮空的桶中进⾏快速排序。

稳定性：稳定的排序算法

因为在排序的过程中，对于相同的元素，它们在同一个桶中，并且在桶内的排序不会改变它们的相对位置，所以它们在排序后的相对位置不会发生变化。

复杂度：

桶排序的时间复杂度为

O

(

n

k

)

O(n+k)

O(n+k)，其中

n

n

n表示待排序序列的长度，

k

k

k表示桶的数量。可以看出，桶排序的时间复杂度与桶的数量有关，而与待排序序列的元素大小无关。因此，当桶的数量比较大时，桶排序的效率比较低，而当桶的数量比较小时，桶排序的效率比较高。另外，桶排序的空间复杂度为

O

(

n

k

)

O(n+k)

O(n+k)，其中

k

k

k表示桶的数量，这是由于需要使用桶来存储待排序序列中的元素。

⽰例代码：

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

//桶排序
public class BucketSort {
public static void main(String[] args) {
int arr[] = { 3, 1, 23, 3, 1, 4, 5, 199, 20 };
bucketSort(arr,3);
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
public static void bucketSort(int[] arr, int bucketSize){
if(arr.length == 0){
return;
}
int max = arr[0], min = arr[0];
for(int i = 1; i < arr.length; i++){
if(arr[i] > max){
max = arr[i];
}else if(arr[i] < min){
min = arr[i];
}
}
int bucketCount = (max - min) / bucketSize + 1;
List<List> buckets = new ArrayList<>();
for(int i = 0; i < bucketCount; i++){
buckets.add(new ArrayList());
}
for(int i = 0; i < arr.length; i++){
int bucketIndex = (arr[i] - min) / bucketSize;
buckets.get(bucketIndex).add(arr[i]);
}
int k = 0;

自我介绍一下，小编13年上海交大毕业，曾经在小公司待过，也去过华为、OPPO等大厂，18年进入阿里一直到现在。

深知大多数Go语言工程师，想要提升技能，往往是自己摸索成长或者是报班学习，但对于培训机构动则几千的学费，着实压力不小。自己不成体系的自学效果低效又漫长，而且极易碰到天花板技术停滞不前！

因此收集整理了一份《2024年Go语言全套学习资料》，初衷也很简单，就是希望能够帮助到想自学提升又不知道该从何学起的朋友，同时减轻大家的负担。

既有适合小白学习的零基础资料，也有适合3年以上经验的小伙伴深入学习提升的进阶课程，基本涵盖了95%以上Golang知识点，真正体系化！

由于文件比较大，这里只是将部分目录大纲截图出来，每个节点里面都包含大厂面经、学习笔记、源码讲义、实战项目、讲解视频，并且后续会持续更新

如果你觉得这些内容对你有帮助，可以添加V获取：vip1024b （备注Go）

一个人可以走的很快，但一群人才能走的更远。不论你是正从事IT行业的老鸟或是对IT行业感兴趣的新人，都欢迎扫码加入我们的的圈子（技术交流、学习资源、职场吐槽、大厂内推、面试辅导），让我们一起学习成长！

< arr.length; i++){
int bucketIndex = (arr[i] - min) / bucketSize;
buckets.get(bucketIndex).add(arr[i]);
}
int k = 0;

自我介绍一下，小编13年上海交大毕业，曾经在小公司待过，也去过华为、OPPO等大厂，18年进入阿里一直到现在。

深知大多数Go语言工程师，想要提升技能，往往是自己摸索成长或者是报班学习，但对于培训机构动则几千的学费，着实压力不小。自己不成体系的自学效果低效又漫长，而且极易碰到天花板技术停滞不前！

因此收集整理了一份《2024年Go语言全套学习资料》，初衷也很简单，就是希望能够帮助到想自学提升又不知道该从何学起的朋友，同时减轻大家的负担。
[外链图片转存中…(img-IW4tutdU-1712932148976)]
[外链图片转存中…(img-kDS55jVX-1712932148978)]
[外链图片转存中…(img-frRBNSFx-1712932148978)]
[外链图片转存中…(img-HyFiUYnq-1712932148979)]
[外链图片转存中…(img-DAAaLd8I-1712932148979)]

既有适合小白学习的零基础资料，也有适合3年以上经验的小伙伴深入学习提升的进阶课程，基本涵盖了95%以上Golang知识点，真正体系化！

由于文件比较大，这里只是将部分目录大纲截图出来，每个节点里面都包含大厂面经、学习笔记、源码讲义、实战项目、讲解视频，并且后续会持续更新

如果你觉得这些内容对你有帮助，可以添加V获取：vip1024b （备注Go）
[外链图片转存中…(img-gc8bJbWc-1712932148980)]

一个人可以走的很快，但一群人才能走的更远。不论你是正从事IT行业的老鸟或是对IT行业感兴趣的新人，都欢迎扫码加入我们的的圈子（技术交流、学习资源、职场吐槽、大厂内推、面试辅导），让我们一起学习成长！