• 算法篇：排序算法

    一、算法概述

    1. 稳定 vs 非稳定

    • 稳定：如果a原本在b前面，同时a=b，排序之后a仍然在b前面
    • 不稳定：如果a原本在b前面，同时a=b，排序之后a不一定在b前面

    2. 内排序 vs 外排序

    • 内排序：所有排序操作都在内存中完成
    • 外排序：由于数据太大，因此将数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行

    3. 比较排序 vs 非比较排序

    • 比较排序
      • 元素之间的次序依赖于它们之间的比较，每个数必须和其他数进行比较才能确定自己的位置
      • 常见排序算法：快速排序、归并排序、堆排序、冒泡排序
    • 非比较排序
      • 通过确定每个元素之前，应该有多少个元素来进行排序
      • 常见排序算法：计数排序、基数排序、桶排序
    • 区别
      • 比较排序的时间复杂度较高，适用于各种规模的数据，也不在乎数据的分布，适用于一切需要排序的情况
      • 非比较排序的时间复杂度低，但由于需要占用空间来确定唯一的位置，所以对数据规模和数据分布有一定要求

    4. 排序算法比较

    排序算法比较

    其中：

    • n表示数量规模
    • k表示桶的数量
    • in-place表示占用常数内存
    • out-place表示占用额外内存

    二、常见排序算法

    1. 冒泡排序

    • 思路：

      • 重复走访要遍历的数列，一次比较两个元素，如果顺序错误就进行交换，直至没有需要交换的元素

    • 算法描述：

      • 比较相连两个元素，如果顺序错误则进行交换
      • 对每一对相邻的元素做同样的工作，从开始一对到最后一对，使得最后的元素是最大的数
      • 针对所有元素重复1-2，除了最后一个元素
      • 重复1-3，直至排序完成

    • 动图演示：
      冒泡排序

    • 代码演示：

    // 默认升序排列
public int[] bubbleSort(int[] nums){
	int len = nums.length;
	for(int i = 0; i < len; i++){
		for(int j = 0; j < len - i - 1; j++){
			if(nums[j] > nums[j + 1]){
				int tmp = nums[j];
				nums[j] = nums[j + 1];
				nums[j + 1] = tmp;
			}
		}
	}
	return nums;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 复杂度分析：
      时间复杂度：最好：O(n2)，最差：O(n)，平均：O(n2)；空间复杂度：O(1)

    2. 选择排序

    • 思路：
      • 先从未排序序列中找出最小/最大元素，存放到有序序列的起始位置
      • 然后再从剩余的未排序序列中继续找最小/最大元素，放到已排序序列的末尾
      • 以此类推，直至所有元素已排序
    • 算法描述：
      • 初始状态：有序区为R[1, n]，有序区为空
      • 第i趟排序，有序区和无序区分别为R[1, i-1]和R[i, n]。从无序区选择关键字最小的记录R[k]，将它与无序区第一个元素交换，新的有序区和无序区为R[1, i]和R[i+1, n]
      • n-1趟排序，数组有序化
    • 动图演示：
      选择排序
    • 算法实现：
    // 默认升序排列
public int[] selectionSort(int[] nums){
	int len = nums.length;
	for(int i = 0; i < len - 1; i++){
		// 从i开始向后找最小的元素
		int minIndex = i;
		for(int j = i; j <len; j++){
			if(nums[minIndex] > nums[j]){
				minIndex = j;
			}
		}
		if(minIndex != i){
			int tmp = nums[i];
			nums[i] = nums[minIndex];
			nums[minIndex] = tmp;
		}
	}
	return nums;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 复杂度分析：
      时间复杂度：最好：O(n2)，最差：O(n2)，平均：O(n2)；空间复杂度：O(1)

    3. 插入排序

    • 思路：
      • 通过构建有序序列，对于未排序序列，在有序序列中从后向前扫描，找到相应位置插入
      • 在从后向前扫描过程中，需要反复将已排序元素向后挪位，为新元素提供插入空间
    • 算法描述：
      • 从第一个元素开始，该元素可以认已经被排序
      • 取出下一个元素，在已经排序的元素中从后向前扫描
      • 如果已排序元素大于新元素，将该元素移到下一个位置
      • 重复步骤3，直至找到已排序的元素小于或者等于新元素的位置
      • 将新元素插入该位置
      • 重复步骤2-5
    • 动图演示：
      插入排序
    • 算法实现：
    // 默认升序排列
public int[] insertionSort(int[] nums){
	int len = nums.length;
	for(int i = 1; i < len; i++){
		// i之前是有序列表，i之后是无序列表
		int tmp = nums[i];
		// 在有序列表中从后向前扫描，找到适合tmp的位置，tmp之后的位置向后移动
		for(int j = i - 1; j >= 0 && nums[j] > tmp; j--){
			// 比tmp大的元素向后移动一位
			nums[j + 1] = nums[j];
		}
		// 找到放tmp的位置
		nums[j + 1] = tmp;
	}
	return nums;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 复杂度分析：
      时间复杂度：最好：O(n)，最差：O(n2)，平均：O(n2)；空间复杂度：O(1)

    4. 希尔排序

    • 思路：
      • 对插入排序的改进，它会优先比较距离较远元素。希尔排序又称为缩小增量排序
      • 将待排序的序列按一定增量分组，对每组使用插入排序
      • 随着增量逐渐减小，每组包含的关键词越来越多，当增量减至1时，整个序列恰好被分为一组，算法终止
    • 算法描述：
      • 增量序列：待排序序列个数为n，希尔排序建议的增量序列为{n/2, (n/2)/2,…, 1}
      • 选择一个增量序列t1, t2,…tk，其中ti>tj，i > j，tk=1
      • 按照增量序列个数k，对序列进行k趟排序
      • 每趟排序，根据对应的增量ti，将待排序列分割为若干长度为m的子序列，分别对各子序列进行插入排序
    • 演示：
      希尔排序
    • 算法实现：
    // 默认升序排列
public int[] shellSort(int[] nums){
	int len = nums.length;
	for(int d = len / 2; d >= 0; d /= 2){
		// d用于控制分组
		// 对每个分组分别进行插入排序
		for(int i = d; i < len; i += d){
			int tmp = nums[i];
			for(int j = i - d; j >= 0 && nums[j] > tmp; j -= d){
				nums[j + d] = nums[j];
			}
			nums[j + d] = tmp;
		}
	}
	return nums;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 复杂度分析：
      时间复杂度：最好：O(nlogn)，最差：O(nlog2n)，平均：O(nlog2n)；空间复杂度：O(1)

    5. 归并排序

    • 思路：
      • 采用分治算法，先使得每个子序列有序，再使得子序列段间有序
    • 算法描述：
      • 将长度为n的输入序列分隔两个长度为n/2的子序列
      • 对这两个子序列分别采用归并排序，不断分隔直至只有两个元素可以直接比较
      • 合并排序好的两个子序列，成为一个最终的排序序列
    • 演示：
      归并排序
    • 算法实现：
    // 默认升序排列

// 用于存储排序的中间结果
int[] temp;

public int[] mergeSort(int[] nums){
	int len = nums.length;
	// 初始化temp
	temp = new int[len];
	mergeSort(nums, 0, len - 1);
	return nums;
}

public void mergeSort(int[] nums, int left, int right){
	if(left >= right){
		return;
	}
	int mid = (left + right) / 2;
	// 递归分治排序
	mergeSort(nums, left, mid);
	mergeSort(nums, mid + 1, right);
	// 合并排序的中间结果
	merge(nums, left, mid + 1, right);
}

public void merge(int[] nums, int i, int j, int k){
	// temp记录中间结果
	for(int index = i; index <= k; index++){
		temp[index] = nums[index];
	}
	// 合并结果
	int index = i, mid = j - 1;
	while(i <= mid && j <= k){
		if(temp[i] > temp[j]){
			nums[index++] = temp[j++];
		} else {
			nums[index++] = temp[i++];
		}
	}
	// i或者j还有剩
	while(i <= mid){
		nums[index++] = temp[i++];
	}
	while(j <= k){
		nums[index++] = temp[j++];
	}
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 复杂度分析：
      时间复杂度：最好：O(nlogn)，最差：O(nlogn)，平均：O(nlogn)；空间复杂度：O(n)

    6. 快速排序

    • 思路：
      • 通过一趟排序将待排序列分割成两个独立的部分，其中一部分关键字均比另一部分小，再分别对这两部分进行快速排序
    • 算法描述：
      • 从待排序列中选择一个基准
      • 重新排列序列，比基准小的放在基准前面，比基准大的放在基准后面
      • 递归地对小于基准的序列和大于基准的序列进行快速排序
    • 动图演示：
      快速排序
    • 算法实现：
    // 默认升序排列
public int[] quickSort(int[] nums){
	int len = nums.length;
	quickSort(nums, 0, len - 1);
	return nums;
}

public void quickSort(int[] nums, int left, int right){
	if(left >= right){
		return;
	}
	// 以left位置的元素为基准
	int tmp = nums[left];
	int i = left, j = right;
	while(i < j){
		// j往左找到第一个小于tmp的数，将该数放到left的位置
		while(i < j && nums[j] >= tmp){
			j--;
		}
		nums[i] = nums[j];
		// i往右找到第一个大于tmp的数，将该数放到right的位置
		while(i < j && nums[i] <= tmp){
			i++;
		}
		nums[j] = nums[i]; 
	}
	// i和j重合的位置，放置temp
	// temp左侧都是小于于temp的数，temp右侧都是大于temp的数
	nums[i] = tmp;
	quickSort(nums, left, i);
	quickSort(nums, i + 1, right);
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 复杂度分析：
      时间复杂度：最好：O(nlogn)，最差：O(n2)，平均：O(nlogn)；空间复杂度：O(logn)

    7. 堆排序

    • 思路：
      • 将待排序列构造成一个大顶堆/小顶堆，序列的最大值/最小值就在堆顶的根节点
      • 交换根节点和对数组的末尾元素，末尾元素就是最大/最小值
      • 将剩余的n-1个序列重新构造成一个堆，得到次大值/次小值，反复执行，得到有序序列
    • 算法描述：
      • 将待排序列(R[1], R[2],…R[n])构造成大顶堆
      • 将堆顶元素R[1]和最后一个元素R[n]交换，得到新的无序区(R[1], R[2],…R[n-1])和有序区(R[n])
      • 对无序区进行调整，再将R[1]和无序区最后一个元素交换，得到新的无序区(R[1], R[2],…R[n-2])和有序区(R[n-1], R[n])
      • 不断重复步骤3，直到整个排序完成
    • 动图演示：
      堆排序
    • 算法实现：
    // 默认升序排列
// 升序用大顶堆，降序用小顶堆
public int[] heapSort(int[] nums){
	int len = nums.length;
	// 构建大顶堆
	buildHeap(nums, len);
	// 交换大顶堆的堆顶元素和堆底元素，再调整大顶堆，循环往复
	for(int i = len - 1; i >= len / 2; i--){
		swap(nums, i, 0);
		len--;
		maxifyHeap(nums, 0, len);
	}
	return nums;
}

public void buildHeap(int[] nums, int len){
	for(int i = len / 2; i >= 0; i--){
		maxifyHeap(nums, i, len);
	}
}

public void maxifyHeap(int[] nums, int parent, int len){
	int left = 2 * parent + 1, right = left + 1, largest = parent;
	if(left < len && nums[left] > nums[largest]){
		largest = left;
	}
	if(right < len && nums[right] > nums[largest]){
		largest = right;
	}
	if(largest != parent){
		swap(nums, largest, parent);
		maxifyHeap(nums, largest, len);
	}
}

public void swap(int[] nums, int index1, int index2){
    int temp = nums[index1];
    nums[index1] = nums[index2];
    nums[index2] = temp;
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 复杂度分析：
      时间复杂度：最好：O(nlogn)，最差：O(nlogn)，平均：O(nlogn)；空间复杂度：O(1)

    8. 计数排序

    • 思路：
      • 使用一个额外的数组C，其中第i个元素是待排序数组A中值等于i的元素的个数
      • 再根据数组C来将A中的元素排到正确的位置
      • 只能对整数进行排序
    • 算法描述：
      • 找出待排序数组中最大和最小的值
      • 统计数组中每个值为i的元素出现的次数，存入数组C中的第i项
      • 对所有计数累加(从C中第一个元素开始，每一项和前一项相加)
      • 反向填充目标数组，将每个元素放在新数组的第C[i]项，每放一条将C[i]减1
    • 动图演示：
      计数排序
    • 算法实现：
    public int[] countingSort(int[] nums){
	 // 统计序列的最大值和最小值
	 int min = nums[0], max = nums[0], len = nums.length;
	 for(int num : nums){
	 	min = Math.min(min, num );
	 	max = Math.max(max, num );
	 }
	 // 根据最大值和最小值构造新数组
	 int newLen = max - min + 1;
	 int[] countArray = new int[newLen];
	 // 统计nums中的元素出现频率
	 for(int num : nums){
	 	countArray[num - min]++;
	 }
	 // 循环每一个元素，根据出现的次数，放入新的数组
	 int[] res = new int[len];
	 int index = 0;
	 for(int i = 0; i < newLen; i++){
	 	for(int j = 0; j < countArray[i]; j++){
			res[index++] = i + min;
		}
	 }
	 return res;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 复杂度分析：
      时间复杂度：最好：O(n+k)，最差：O(n+k)，平均：O(n+k)；空间复杂度：O(k)，k是桶的数量

    9. 桶排序

    • 思路：
      • 假设待排序列满足均匀分布，基于映射函数将数据分到有限数量的桶里，每个桶分别排序(有可能使用别的排序算法或者递归进行桶排序)
      • 在额外空间充足的情况下，尽量增大桶的数量
      • 使用的映射函数能够将待排序列均匀分配到桶中
    • 算法描述：
      • 设置一个定量的数组作为空桶
      • 遍历待排序列，将元素放入对应的桶中
      • 对每个不是空的桶进行排序
      • 从不是空的桶中将排好序的数据拼接起来
    • 演示：
      桶排序
    • 算法实现：
    public List<Integer> bucketSort(List<Integer> list){
	// 统计序列的最大值和最小值
    int max = list.get(0), min = list.get(0);
    for (Integer value : list) {
        max = Math.max(max, value);
        min = Math.min(min, value);
    }
    // 确定桶的数量，创建桶
    int bucketNum = (max - min) / list.size() + 1;
    List<List<Integer>> buckets = new ArrayList<>(bucketNum);
    for (int i = 0; i < bucketNum; i++) {
        buckets.add(new ArrayList<>());
    }
    // 将待排序元素放入桶中
    for (int i = 0; i < list.size(); i++) {
        int index = (list.get(i) - min) / list.size();
        buckets.get(index).add(list.get(i));
    }
    // 对每个桶内的元素进行排序  -- 这里采用快速排序
    for (List<Integer> bucket : buckets) {
        quickSort(bucket);
    }
    // 将桶排序结果进行合并
    return buckets.stream().flatMap(Collection::parallelStream).collect(Collectors.toList());
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 复杂度分析：
      时间复杂度：最好：O(n+k)，最差：O(n2)，平均：O(n+k)；空间复杂度：O(n + k)，k是桶的数量

    10. 基数排序

    • 思路：
      • 将待排序列按照低位先排序，然后收集
      • 再按照高位排序，然后收集
      • 以此类推，直至最高位
    • 算法描述：
      • 取得待排序列的最大数，并取得位数
      • arr为原始数组，从低位开始每个位组成radix数组
      • 对radix进行计数排序
      • 逐渐从高的位数开始，重复2-3
    • 动图演示：
      基尔排序
    • 算法实现：
    public List<Integer> radixSort(List<Integer> list){
	// 先确定最大的位数
	int digit = getMaxDigit(list);
	// 对每个位数进行同桶排序
	for(int i = 0; i < digit; i++){
		list = bucketSort(list, i);
	}
	return list;
}

public int getMaxDigit(List<Integer> list){
	int digit = 1, base = 10;
	for(int value : list){
		while(value > base){
			digit++;
			base *= 10;
		}
	}
	return digit;
}

public List<Integer> bucketSort(List<Integer> list, int digit){
	int base = (int)Math.pow(10, digit);
	// 初始化桶
	List<List<Integer>> buckets = new ArrayList<>(10);
    for (int i = 0; i < 10; i++) {
        buckets.add(new ArrayList<>());
    }
   	// 将元素放入桶中
   	for(int val : list){
   		int index = (val / base) % 10;
   		buckets.get(index).add(val);
   	}
   	// 合并桶内的元素
   	return buckets.stream().flatMap(Collection::parallelStream).collect(Collectors.toList());
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 复杂度分析：
      时间复杂度：最好：O(n x k)，最差：O(n x k)，平均：O(n x k)；空间复杂度：O(n + k)，k是桶的数量

    11. 计数排序 vs 桶排序 vs 基数排序

    三种排序算法都用到了桶排序，但是对于桶的使用方法不同：

    • 计数排序：每个桶只使用单一的键值
    • 桶排序：每个桶存储一定范围内的数值
    • 基数排序：根据键值的每位数字来分配桶
  • 相关阅读:
    【c ++ primer 笔记】第 14章 重载运算符
    Django REST项目实战：在线中文字符识别
    连接数据库报错2003-Can‘t connect to MySQL server on ‘localhost‘(10061）
    python-Matplotlib画图那些你不知道的事
    Ubuntu20.04安装EasyConnect后兼容性问题无法启动的解决方法
    在迁移测试中，源表、中间表、目标表的迁移规则
    Linux “挂载” 的概念
    C#异步TCP客户端连接
    极客日报：华为称不会退出海外市场；英伟达证实遭遇黑客攻击；TypeScript 4.6发布 | 极客头条
    Redis持久化（RDB和AOF）
  • 原文地址：https://blog.csdn.net/weixin_41402069/article/details/126241170