鸣谢B站up主 烂牌_ 讲的很好，就是基数排序负数的时候有点问题，本篇博客进行了小小的修复。放心食用
选择排序
原理
遍历元素找到一个最小（或最大）的元素，把它放在第一个位置，然后再在剩余元素中找到最小（或最大）的元素，把它放在第二个位置，依次下去，完成排序。
时间复杂度
平均：O(nn)
最好：O(nn)
最坏：O(n*n)
空间复杂度
O(1)
代码
public static void selectSort(int[] arr){
for (int i = 0; i < arr.length - 1; i++) {
int minIdx =i;
for (int j = i+1; j < arr.length; j++) {
if (arr[j]<arr[i]){
minIdx = arr[minIdx]< arr[j]?minIdx:j;
}
}
if (minIdx!=0 && minIdx !=i){
int tmp = arr[i];
arr[i] = arr[minIdx];
arr[minIdx] = tmp;
}
}
}
或者
public static void selectSort2(int[] arr){
for (int i = 0; i < arr.length - 1; i++) {
int minIdx =i;
for (int j = i+1; j < arr.length; j++) {
if (arr[j]<arr[minIdx]){
minIdx = j;
}
}
if (minIdx!=0 && minIdx !=i){
int tmp = arr[i];
arr[i] = arr[minIdx];
arr[minIdx] = tmp;
}
}
}
归并排序
原理
分而治之的思想，先分割，再合并
时间复杂度
平均：O(nn)
最好：O(nn)
最坏：O(n*n)
空间复杂度
O(1)
代码
我这里分割的时候计算mid用了位运算，其实就相当于/2, 但效率更高。
public static void split(int[] arr, int low, int high, int[] tmp){
if (low <high){
int mid = (low+high)>>1;
split(arr, low, mid, tmp);
split(arr,mid+1,high, tmp);
// 合并
mergeSort(arr, low, mid, high, tmp);
}
}
public static void mergeSort(int[] arr, int low, int mid, int high, int[] tmp){
int i=low, j=mid+1,t=0;
// 遍历mid分隔开的两部分，将他们有序的合起来，放到tmp, 这也是为什么要保存一份low , high
while (i<=mid && j<=high){
if (arr[i] <= arr[j]){
tmp[t++] = arr[i++];
}else{
tmp[t++] = arr[j++];
}
}
// 下面的两个连续的循环，每次只有一个会进去，单边的还是有序的，所以他才有胆量只接放到tmp
// 如果左边还有
while (i<=mid){
tmp[t++] = arr[i++];
}
// 如果右边还有
while (j<=high) {
tmp[t++] = arr[j++];
}
// 填充到arr数组指定位置,
t = 0;
while ((t+low)<=high){
arr[low+t] = tmp[t];
t++;
}
}
基数排序
基数排序是比较稳定的一种排序算法，取决于最大的数的位数。
原理
将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。
时间复杂度
平均时间复杂度，最好最坏都是O(nxk)
空间复杂度
O(n+k)
代码
改进前
基础代码是这样的，但下面的代码不支持负数，需要做一下改进
public static void redixSort(int[] arr) {
int[][] bucket = new int[10][arr.length-1];
int[] bucketElementCounts = new int[10];
int max = 0;
for (int i = 0; i < arr.length; i++) {
max = arr[i] > max ? arr[i] : max;
}
// 获取最大的数的长度
int maxLength = (max + "").length();
for (int i = 0; i < maxLength; i++) {
// 将每一次取的位数的元素放到bucket中，每一次循环的bucket中存放的是当前遍历的个位十位或者百位的结果
for (int j = 0; j < arr.length; j++) {
// int digit = getDigit(arr[j], i);
int digit = arr[j]/ (int) Math.pow(10,i)%10;
bucket[digit][ bucketElementCounts[digit]] = arr[j];
bucketElementCounts[digit]++;
}
printDemision(bucket);
// 将元素从bucket中取出来
int index = 0;
for (int j = 0; j < bucketElementCounts.length; j++) {
if (bucketElementCounts[j]!=0){
for (int k = 0; k < bucketElementCounts[j]; k++) {
arr[index++] = bucket[j][k];
}
}
bucketElementCounts[j] = 0;
}
}
}
改进后
下面的代码判断了数组中是否有负数，有负数的话所有的diget+10，不会出现数组越界。
public static void redixSort(int[] arr) {
int[][] bucket = new int[20][arr.length-1];
int[] bucketElementCounts = new int[20];
int max = 0;boolean flag= false;
for (int i = 0; i < arr.length; i++) {
max = arr[i] > max ? arr[i] : max;
if (!flag){
flag = arr[i]<0;
}
}
// 获取最大的数的长度
int maxLength = (max + "").length();
for (int i = 0; i < maxLength; i++) {
// 将每一次取的位数的元素放到bucket中，每一次循环的bucket中存放的是当前遍历的个位十位或者百位的结果
for (int j = 0; j < arr.length; j++) {
// int digit = getDigit(arr[j], i);
int digit = arr[j]/ (int) Math.pow(10,i)%10;
if (flag){
digit=digit+10;
}
bucket[digit][ bucketElementCounts[digit]] = arr[j];
bucketElementCounts[digit]++;
}
printDemision(bucket);
// 将元素从bucket中取出来
int index = 0;
for (int j = 0; j < bucketElementCounts.length; j++) {
if (bucketElementCounts[j]!=0){
for (int k = 0; k < bucketElementCounts[j]; k++) {
arr[index++] = bucket[j][k];
}
}
bucketElementCounts[j] = 0;
}
}
}
工具类
private static void printDemision(int[][] arr){
int rows = arr.length;
int cols = arr[0].length;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
System.out.print(arr[i][j] + " ");
}
System.out.println();
}
}
// 一串数字2345，i=,0的时候要求取得5，i=1取得4 ，i=2取得3，i=3取得2，i=4取得0，i=5取得0，要求在不转字符串的前提下，请用java实现，2345不是固定的，请用参数number来表示
public static int getDigit(int number, int position) {
if (position < 0) {
throw new IllegalArgumentException("位置不能为负数");
}
int divisor = (int) Math.pow(10, position);
return (number / divisor) % 10;
}
