排序1：插入排序、冒泡排序、选择排序
排序在实际生产中是一种极其常见的操作，但是通常我们会使用现成的算法实现。更多时候是库或者第三方应用给你的数据本身就是有序的。对于大量数据的操作，优先进行排序是一个良好的习惯，在你后续的操作上都能从这个有序数据中受益。
指标
时间复杂度
排序算法的时间复杂度，需要具体考虑最好、最坏和平均时间复杂度，有些数据本身就是有序的，有些数据是完全无序，有序度不同的数据对排序算法的影响是很大的。
在小规模数据的情况下，我们可能还会将时间复杂度的系数，常量，低阶项也不忽略。因为我们实际业务上需要查询的数据规模其实是蛮小的，比如用户查询自己最近的前五条订单记录。一个人的订单通常有一千条就已经很多了，总的数据规模就很小，再根据时间排序，其时间复杂度通常需要忽略的部分可能也需要重新考虑进去了。
比较与交换（移动）的次数，有些算法需要移动数据以空开位置，有些算法直接交换位置。
空间复杂度
常见的排序算法是不需要使用到额外空间的原地排序，通常他们再自己集合内部比较、移动或者交换，空间复杂度是（O(1)）。而有些特殊的排序算法需要使用到额外的空间存储数据。
稳定性
稳定排序算法可以保持排序值的两个对象，在排序之后的前后顺序不变。这使得我们可以进行多数据值排序之后依然保持稳定，比如，先让订单按照付款金额进行降序，然后对下单时间进行降序，在稳定的排序算法排序之后，如果有多个订单的下单时间一样的话，我们就可能很容易取到最近付款金额最大的订单。就是新的排序规则不会打乱旧排序规则在不违反新规则的情况下的符合旧规则的有序性。
接口
为了方便，我们定义排序接口如下
package cn.lishiyuan.algorithm.sort;
import java.util.List;
/**
* 排序接口
*/
public interface LeeSort {
<T extends Comparable<T>> List<T> sort(List<T> data);
<T extends Comparable<T>> T[] sort(T[] data);
}冒泡排序
冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系要求。如果不满足就让它俩互换。一次冒泡会让至少一个元素移动到它应该在的位置，重复 n 次，就完成了 n 个数据的排序工作。
package cn.lishiyuan.algorithm.sort;
import java.util.List;
/**
* 冒泡排序
* <br>
* 冒泡排序的思路是，比较相邻两个元素，如果满足交换条件则交换。
* <br>
* 每次遍历，会将最大或者最小的元素移动到最后。
*/
public class BubbleSort implements LeeSort{
@Override
public <T extends Comparable<T>> List<T> sort(List<T> data) {
// 第一轮就将元素放到了最后，所以最后一个元素不要遍历，如果只有一个元素那更不需要遍历了
for (int i = 0; i < data.size() - 1 ; i++) {
boolean flag = true;
for (int j = 0 ; j < (data.size() - i - 1) ; j++) {
T left = data.get(j);
T right = data.get( j + 1 );
// 也就是右边比左边大，那么要交换位置
if(right.compareTo(left) < 0){
data.set(j, right);
data.set(j+1, left);
flag = false;
}
}
// 某轮没有没有交换则提前返回
if(flag){
return data;
}
}
return data;
}
@Override
public <T extends Comparable<T>> T[] sort(T[] data) {
// 第一轮就将元素放到了最后，所以最后一个元素不要遍历，如果只有一个元素那更不需要遍历了
for (int i = 0; i < data.length - 1 ; i++) {
boolean flag = true;
for (int j = 0; j < (data.length - i - 1) ; j++) {
T left = data[j];
T right = data[ j + 1 ];
// 也就是右边比左边大，那么要交换位置
if(right.compareTo(left) < 0){
data[j] = right;
data[j+1] = left;
flag = false;
}
}
// 某轮没有没有交换则提前返回
if(flag){
return data;
}
}
return data;
}
}空间复杂度
冒泡排序是原地排序，空间复杂度是O(1)
稳定性
元素相等的时候不交换位置，是稳定的。
时间复杂度
最好时间复杂度出现在数据已经有序的情况下，只要进行n次遍历(通过flag优化后)就可以完成排序，复杂度是(O(n))
最坏时间复杂度出现在数据完全逆序的情况下，只要进行n cheng次遍历就可以完成排序，复杂度是(O(n^2))
平均时间复杂度是O(n^2)，我们的每次交换的本质是将逆序对变成有序对的过程。
有序度是数组中具有有序关系的元素对的个数。
有序元素对：a[i] <= a[j], 如果i < j。
有序度是数组中不具有有序关系的元素对的个数。
逆序元素对：a[i] > a[j], 如果i < j。对于一个倒序排列的数组，比如 6，5，4，3，2，1，有序度是 0；对于一个完全有序的数组，比如 1，2，3，4，5，6，有序度就是 n*(n-1)/2，也就是 15。我们把这种完全有序的数组的有序度叫作满有序度。
逆序度 = 满有序度 - 有序度不管算法怎么改进，交换次数总是确定的，即为逆序度，也就是n*(n-1)/2–初始有序度。此例中就是 15–3=12，要进行 12 次交换操作。
最坏情况下，初始状态的有序度是 0，所以要进行 n(n-1)/2 次交换。最好情况下，初始状态的有序度是 n(n-1)/2，就不需要进行交换。我们可以取个中间值 n(n-1)/4，来表示初始有序度既不是很高也不是很低的平均情况。换句话说，平均情况下，需要 n(n-1)/4 次交换操作，比较操作肯定要比交换操作多，而复杂度的上限是 O(n^2)，所以平均情况下的时间复杂度就是 O(n^2)。
插入排序
插入排序的思路是将一个list从逻辑上分为已排序的部分前n项，和未排序部分 。那么，我们要排序n+1位置的元素的的话，就需要在已排序的部分找出合适的index，然后插入进去。
package cn.lishiyuan.algorithm.sort;
import java.util.List;
/**
* 插入排序
* <br>
* 插入排序的思路是将一个list从逻辑上分为已排序的部分前n项，和未排序部分
* <br>
* 那么，我们要排序n+1位置的元素的的话，就需要在已排序的部分找出合适的index，然后插入进去。
*/
public class InsertionSort implements LeeSort{
@Override
public <T extends Comparable<T>> List<T> sort(List<T> data) {
for (int i = 1 ; i < data.size() ; i++) {
T nowValue = data.get(i);
// 将当前元素插入到已经有序的前x项中的上面位置
int j = i - 1;
for ( ; j >= 0 ; j--) {
T left = data.get(j);
// 也就如果当前值比当前位置的值大，则不要需要处理
if(left.compareTo(nowValue) <= 0){
break;
}
// 左边元素向后移动一位
data.set(j + 1, data.get(j));
}
data.set( j+1 , nowValue);
}
return data;
}
@Override
public <T extends Comparable<T>> T[] sort(T[] data) {
for (int i = 1 ; i < data.length ; i++) {
T nowValue = data[i];
// 将当前元素插入到已经有序的前x项中的上面位置
int j = i - 1;
for ( ; j >= 0 ; j--) {
T left = data[j];
// 也就如果当前值比当前位置的值大，则不要需要处理
if(left.compareTo(nowValue) <= 0){
break;
}
// 左边元素向后移动一位
data[j + 1]= data[j];
}
data[ j+1 ] = nowValue;
}
return data;
}
}空间复杂度
是原地排序，空间复杂度是O(1)
稳定性
是稳定的，没有交换数据。
时间复杂度
最好时间复杂度出现在本身就有序的情况下，复杂度是O(n)。
最坏情况出现在完全逆序的情况下，复杂度是(O(n^2))
平均时间复杂度是O(n^2)
选择排序
选择排序的的思路是，将列表分成已排序前n项部分和未排序部分,如果我们需要排序 n+1项，那么我们在未排序的部分里面找到最大或者最小的值放到index = n+1这个位置。
选择排序在这里是最直观却也是最糟糕的排序，在任何情况下都是O(n^2)的时间复杂度。
package cn.lishiyuan.algorithm.sort;
import java.util.List;
/**
* 选择排序，
* <br>
* 选择排序的的思路是，将列表分成已排序前n项部分和未排序部分
* <br>
* 如果我们需要排序 n+1项，那么我们在未排序的部分里面找到最大或者最小的值放到index = n+1这个位置。
*/
public class SelectionSort implements LeeSort{
@Override
public <T extends Comparable<T>> List<T> sort(List<T> data) {
for (int i = 0; i < data.size(); i++) {
// 找出最小值然后放到index = i的位置
int minIndex = i;
for (int j = i; j < data.size(); j++) {
// 最小值大于当前值则切换最小值
if(data.get(minIndex).compareTo(data.get(j)) > 0){
minIndex = j;
}
}
if(minIndex != i){
T t = data.get(i);
data.set(i, data.get(minIndex));
data.set(minIndex, t);
}
}
return data;
}
@Override
public <T extends Comparable<T>> T[] sort(T[] data) {
for (int i = 0; i < data.length; i++) {
// 找出最小值然后放到index = i的位置
int minIndex = i;
for (int j = i; j < data.length; j++) {
// 最小值大于当前值则切换最小值
if(data[minIndex].compareTo(data[j]) > 0){
minIndex = j;
}
}
if(minIndex != i){
T temp = data[i];
data[i]=data[minIndex];
data[minIndex]=temp;
}
}
return data;
}
}空间复杂度
是原地排序，空间复杂度是O(1)
稳定性
例如，有数组[4a, 4b, 1]，第一次选择最小元素1与第一个元素4a交换，变为[1, 4b, 4a]；这里原本在后面的4b在排序后跑到了前面的4a前面，破坏了相等元素的相对顺序，所以选择排序是不稳定的。时间复杂度
全部是O(n^2)，无论何种情况下都要执行n×((n+1)/2)次。
评论已关闭