一文搞懂编程界中最基础最常见【必知必会】的十一个算法，再也别说你只是听说过【建议收藏+关注】网站首页 技术交流

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

大明子又称小码哥 2024-08-12 12:01:04

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

文章目录

常见算法分类

⾮线性时间⽐较类排序：交换类排序（快速排序和冒泡排序）、插⼊类排序（简单插⼊排序和希尔排序）、选择类排序（简单选择排序和堆排序）、归并排序（⼆路归并排序和多路归并排序）；
线性时间⾮⽐较类排序：计数排序、基数排序和桶排序。

总结：

在⽐较类排序中，归并排序号称最快，其次是快速排序和堆排序，两者不相伯仲，但是有⼀点需要注意，数据初始排序状态对堆排序不会产⽣太⼤的影响，⽽快速排序却恰恰相反。
线性时间⾮⽐较类排序⼀般要优于⾮线性时间⽐较类排序，但前者对待排序元素的要求较为严格，⽐如计数排序要求待排序数的最⼤
值不能太⼤，桶排序要求元素按照hash分桶后桶内元素的数量要均匀。线性时间⾮⽐较类排序的典型特点是以空间换时间。

在这里插入图片描述

算法复杂度

在这里插入图片描述

算法描述与实现

交换类排序

交换排序的基本⽅法是：两两⽐较待排序记录的排序码，交换不满⾜顺序要求的偶对，直到全部满⾜位置。常见的冒泡排序和快速排序就属于交换类排序。

冒泡排序

算法思想：

从数组中第⼀个数开始，依次遍历数组中的每⼀个数，通过相邻⽐较交换，每⼀轮循环下来找出剩余未排序数的中的最⼤数并”冒泡”⾄数列的顶端。

算法步骤：

从数组中第⼀个数开始，依次与下⼀个数⽐较并次交换⽐⾃⼰⼩的数，直到最后⼀个数。如果发⽣交换，则继续下⾯的步骤，如果未
发⽣交换，则数组有序，排序结束，此时时间复杂度为O(n)；
每⼀轮”冒泡”结束后，最⼤的数将出现在乱序数列的最后⼀位。重复步骤（1）。

稳定性：稳定排序

复杂度:

时间复杂度： O(n)⾄O(n2)，平均时间复杂度为O(n2)。
最好的情况：如果待排序数据序列为正序，则⼀趟冒泡就可完成排序，排序码的⽐较次数为n-1次，且没有移动，时间复杂度为O(n)。
最坏的情况：如果待排序数据序列为逆序，则冒泡排序需要n-1次趟起泡，每趟进⾏n-i次排序码的⽐较和移动，即⽐较和移动次数均达到最⼤值：
⽐较次数:Cmax=∑i=1n−1(n−i)=n(n−1)/2=O(n2)
移动次数等于⽐较次数，因此最坏时间复杂度为O(n2)。

⽰例代码：

public class BubleSort {
	public static void main(String[] args) {
		int[] arr = { 1, 3, 2, 5, 4, 6, 100, 20 };
		bubbleSort(arr);
		for (int i : arr) {
			System.out.print(i + " ");
		}
	}

	public static void bubbleSort(int[] arr) {
		for (int i = 0; i < arr.length - 1; i++) {
			// 外层循环控制遍历次数
			for (int j = 0; j < arr.length - 1 - i; j++) {
				// 内层循环控制每次遍历比较的位置
				if (arr[j] > arr[j + 1]) {
					// 如果相邻元素顺序错误，交换它们的位置
					int temp = arr[j];
					arr[j] = arr[j + 1];
					arr[j + 1] = temp;
				}
			}
		}
	}
}

具体的过程可以这样解释：

数组中有n个元素，第一次遍历从左到右，比较相邻的元素，如果左边的元素大于右边的元素，就交换它们的位置。这样每次遍历都会将最大的元素排在数组的右侧。第二次遍历从左到右，除了最后一个元素，每个元素都和后面的元素比较，依次类推，直到数组被完全排好序。

快速排序

冒泡排序是在相邻的两个记录进⾏⽐较和交换，每次交换只能上移或下移⼀个位置，导致总的⽐较与移动次数较多。快速排序⼜称分区交换排序，是对冒泡排序的改进，快速排序采⽤的思想是分治思想。

算法原理：

从待排序的n个记录中任意选取⼀个记录（通常选取第⼀个记录）为分区标准;
把所有⼩于该排序列的记录移动到左边，把所有⼤于该排序码的记录移动到右边，中间放所选记录，称之为第⼀趟排序；
然后对前后两个⼦序列分别重复上述过程，直到所有记录都排好序。

稳定性：不稳定排序

复杂度：

时间复杂度： O（nlog2n）⾄O(n2)，平均时间复杂度为O（nlgn）。
最好的情况：是每趟排序结束后，每次划分使两个⼦⽂件的长度⼤致相等，时间复杂度为O（nlog2n）。
最坏的情况：是待排序记录已经排好序，第⼀趟经过n-1次⽐较后第⼀个记录保持位置不变，并得到⼀个n-1个元素的⼦记录；第⼆趟经过
n-2次⽐较，将第⼆个记录定位在原来的位置上，并得到⼀个包括n-2个记录的⼦⽂件，依次类推，这样总的⽐较次数是：
Cmax=∑i=1n−1(n−i)=n(n−1)/2=O(n2)

⽰例代码：

public class QuickSort {
	public static void main(String[] args) {
		int arr[]={3,1,23,3,1,4,5,199,20};
		new QuickSort().quickSort(arr, 0, arr.length-1);
		for(int i=0;i<arr.length;i++){
			System.out.print(arr[i]+" ");
		}
	}
	public void quickSort(int[] arr, int start, int end) {
		if (start < end) {
			int pivot = partition(arr, start, end);
			quickSort(arr, start, pivot - 1);
			quickSort(arr, pivot + 1, end);
		}
	}

	public int partition(int[] arr, int start, int end) {
		int pivot = arr[start];
		int left = start + 1;
		int right = end;
		while (left <= right) {
			while (left <= right && arr[left] < pivot) {
				left++;
			}
			while (left <= right && arr[right] >= pivot) {
				right--;
			}
			if (left < right) {
				int temp = arr[left];
				arr[left] = arr[right];
				arr[right] = temp;
			}
		}
		int temp = arr[start];
		arr[start] = arr[right];
		arr[right] = temp;
		return right;
	}
}

插⼊类排序

插⼊排序的基本⽅法是：每步将⼀个待排序的记录，按其排序码⼤⼩，插到前⾯已经排序的⽂件中的适当位置，直到全部插⼊完为⽌。

直接插入排序

原理：

从待排序的n个记录中的第⼆个记录开始，依次与前⾯的记录⽐较并寻找插⼊的位置，每次外循环结束后，将当前的数插⼊到合适的位置。

稳定性：稳定排序

复杂度：

时间复杂度： O(n)⾄O（n2），平均时间复杂度是O（n2）。
最好情况：当待排序记录已经有序，这时需要⽐较的次数是Cmin=n−1=O(n)。
最坏情况：如果待排序记录为逆序，则最多的⽐较次数为Cmax=∑i=1n−1(i)=n(n−1)2=O(n2)。

⽰例代码：

public class InsertSort {
	public static void main(String[] args) {
		int[] arr = { 1, 3, 2, 5, 4, 6, 100, 20 };
		insertionSort(arr);
		for (int i : arr) {
			System.out.print(i + " ");
		}
	}

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

说明：

直接插入排序的基本思想是将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增加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))$ ，其中 $d$ 表示数字的最大位数， $k$ 表示基数（即每一位数字的取值范围）。可以看出，基数排序的时间复杂度与数字的位数有关，而与数字的大小无关。因此，当数字的位数不太大时，基数排序的效率非常高。另外，基数排序的空间复杂度也为 $O (n + 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个⼩区间，称为桶，对散布到同⼀个桶中的元素再排序。
要求：待排序数长度⼀致。

排序过程：

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

稳定性：稳定的排序算法

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

复杂度：

桶排序的时间复杂度为 $O (n + k)$ ，其中 $n$ 表示待排序序列的长度， $k$ 表示桶的数量。可以看出，桶排序的时间复杂度与桶的数量有关，而与待排序序列的元素大小无关。因此，当桶的数量比较大时，桶排序的效率比较低，而当桶的数量比较小时，桶排序的效率比较高。另外，桶排序的空间复杂度为 $O (n + 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<Integer>> buckets = new ArrayList<>();
	    for(int i = 0; i < bucketCount; i++){
	        buckets.add(new ArrayList<Integer>());
	    }
	    for(int i = 0; i < arr.length; i++){
	        int bucketIndex = (arr[i] - min) / bucketSize;
	        buckets.get(bucketIndex).add(arr[i]);
	    }
	    int k = 0;
	    for(int i = 0; i < bucketCount; i++){
	        List<Integer> bucket = buckets.get(i);
	        Collections.sort(bucket);
	        for(int j = 0; j < bucket.size(); j++){
	            arr[k++] = bucket.get(j);
	        }
	    }
	}
}

思想：

桶排序是一种非比较排序，它的基本思想是：将待排序序列中的元素分到不同的桶中，然后对每个桶中的元素进行排序。在代码中，我们首先通过一次遍历找到待排序序列中的最大值和最小值，然后根据桶的大小计算出桶的数量，并创建桶的列表buckets。接着，我们遍历待排序序列，将每个元素放入对应的桶中。在放置元素时，我们根据元素的大小计算出桶的下标，并将元素放入对应的桶中。然后，我们对每个桶中的元素进行排序（这里使用了Java中的Collections.sort()方法），并将排好序的元素依次放回原始数组arr中。需要注意的是，在放置元素时，我们需要将元素减去最小值，以便将元素放入正确的桶中。

风语者！平时喜欢研究各种技术，目前在从事后端开发工作，热爱生活、热爱工作。