经典排序算法
2019-04-24 本文已影响0人
Wille_Li
1. 排序算法简介
1.1 算法分类
- 比较类排序（非线性时间比较类排序）：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)。
-
非比较类排序 （线性时间非比较类排序）：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行。
排序算法
1.2 算法复杂度
名词解释：
n: 数据规模
k:“桶”的个数
In-place: 占用常数内存，不占用额外内存；（固定内存）
Out-place: 占用额外内存
稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。
时间复杂度：对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律。
空间复杂度：是指算法在计算机内执行时所需存储空间的度量，它也是数据规模n的函数。
2. 冒泡排序（Bubble Sort）
大学上过编程课的基本都写过冒泡排序的 Demo。
2.1 算法描述
从第一位开始向高位寻找最大值，往后移动，直到最后一位。
具体算法描述如下：
<1> 比较相邻的元素。如果第一个比第二个大，就交换它们两个；
<2> 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
<3> 针对所有的元素重复以上的步骤，除了最后一个；
<4> 重复步骤1~3，直到排序完成。
2.2 算法示意图
冒泡排序
2.3 代码实例
private static void bubbleSort(Integer[] arr){
// --- 冒泡排序 ---;
int length = arr.length;
for (int i = length; i >=0; i--){
for (int j = 0; j < i-1; j++) {
if (arr[j+1] < arr[j]) {
int tmp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = tmp;
}
}
printArr(arr);
}
}
2.4 算法分析
最稳定的排序算法之一，无论数据集是多少，时间复杂度是O(n) ~ O(n²)，唯一优点，不占用更多内存空前。
可以对冒泡进行改进，就是双向冒泡，时间复杂度会减半；
3. 选择排序（Selection Sort）
遍历元素，依次找到位置正确顺序的值，再交换。
3.1 算法描述
- 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置;
- 从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾;
以此类推，直到所有元素均排序完毕。
3.2 算法示意图
选择排序
3.3 代码实现
private static void selecttionSort(Integer[] arr){
logLn("--- 选择排序 ---");
int length = arr.length;
for (int i = 0; i < length; i++){
int tmpIndex = i;
for (int j = i+1; j < length; j++) {
if (arr[tmpIndex] > arr[j]) {
tmpIndex = j;
}
}
// 交换数据位置
swap(arr, i, tmpIndex);
printArr(arr);
}
}
3.4 算法分析
最稳定排序算法，无论数据集是多少，时间复杂度是O(n²)，数据量少可以考虑实用, 不占用更多内存空前。
