《排序算法纲领》
《算法与数据结构：排序算法纲领》
排序算法概览
排序算法的概念
排序算法是一类算法，用于将一组数据元素（通常是数组）按照特定的顺序（如升序或降序）重新排列。排序是计算机科学中基本的操作之一，广泛应用于数据处理、数据库系统、算法设计等领域。
排序算法的本质
排序算法的本质是比较和交换（或移动）数据元素，以达到预定的顺序。这个过程通常涉及以下基本操作：
- 比较：判断两个元素之间的顺序关系。
- 交换 / 移动：将元素置于正确的位置，确保它们符合排序顺序。
- 迭代 / 递归：重复执行比较和交换 / 移动步骤，直到整个序列有序。
排序算法的技巧
选择合适的算法
- 数据大小：对于小型数组，简单的算法（如插入排序）通常足够高效。对于大型数据集，更高效的算法（如快速排序、归并排序）更为合适。
- 数据结构：不同的数据结构可能更适合特定的排序算法。例如，链表排序可能更适合归并排序。
- 数据特性：如果数据已部分排序，某些算法（如插入排序、冒泡排序）可能会更快。
稳定性考虑
- 稳定排序：保持相等元素的原始顺序。
- 非稳定排序：不保证相等元素的原始顺序。
空间复杂度
- 原地排序：如快速排序，空间复杂度低，不需要额外的存储空间。
- 非原地排序：如归并排序，需要额外的存储空间。
时间复杂度
- 最好、最坏和平均情况性能：了解不同情况下算法的时间复杂度。
- 递归与非递归：递归算法（如快速排序、归并排序）与非递归算法（如堆排序）在性能上有所不同。
算法优化
- 减少比较次数：如在快速排序中选择合适的枢轴。
- 减少交换次数：如使用插入排序时进行移动而不是交换。
- 混合使用排序算法：对于特定数据集，混合使用不同的排序算法可能会提高效率。
排序算法的起点和终点就是遍历
技巧实战
遍历数组，一维数组遍历
1
2
3
4
5
6
7
8
9
10
11
12int[] nums = new int[]{2, 4, 6, 1, 2, 3};
int len = nums.length;
// 遍历数组 nums[0,6) 左闭右开区间
for (int i = 0; i < len; i++) {
}
int[] nums = new int[]{2, 4, 6, 1, 2, 3};
int len = nums.length;
// 遍历数组 nums[0,5] 左闭右闭区间
for (int i = 0; i <= len - 1; i++) {
}
遍历数组，寻找数组中最小的值1
2
3
4
5
6
7
8
9int[] nums = new int[]{2, 4, 6, 1, 2, 3};
int len = nums.length;
// 遍历数组 寻找数组中最小的元素
int minIndex = 0;
for (int i = 0; i < len; i++) {
if (nums[minIndex] > nums[i]) {
minIndex = i;
}
}
交换数组，交换指定位置的两个元素1
2
3
4
5private static void swap(int[] nums, int low, int high) {
int temp = nums[low];
nums[low] = nums[high];
nums[high] = temp;
}
范型实现1
2
3
4
5
6
7private static <E extends Comparable<? super E>> void swap(E[] nums, int low, int high) {
E temp = nums[low];
nums[low] = nums[high];
nums[high] = temp;
// help gc
temp = null;
}
一维数组扩容
1
2
3
4
5
6
7
8
9
10
11
12
13
14private void grow(int minCapacity) {
int oldCapacity = elementData.length;
// 默认增加原有素组大小的一半
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 选择 newCapacity 和 minCapacity 中的较大者
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// 如果新数组大于我们设定的最大数组长度 MAX_ARRAY_SIZE 则重新计算新数组大小
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// 申请一个新的数组 数组大小为 newCapacity 并将原来数组的中数据拷贝到新数组
elementData = Arrays.copyOf(elementData, newCapacity);
}