-
写在之前
-
代码实现 Java
-
设计模式 策略模式
// 接口定义
public interface Sorter {
public void sort(int []data);
}
// 测试入口函数
public static void main(String[] args) {
int []data = new int[] {2,5,6,3,4,6,1,8,9,12,56,4,3,7,9,6,8};
Sorter sorter = new //具体实现类
sorter.sort(data);
for(int i:data) {
System.out.println(i);
}
}
-
冒泡排序
似乎是这个世界上最简单的排序算法，很多Coder最初学会的排序算法， 简单思路清晰，通过一次次的循环找出最值元素将其浮到“边界”，因其过程十分相似冒泡，就得到了这个十分形象的名字。
public class BubbleSort implements Sorter{
@Override
public void sort(int[] data) {
for(int i=0; i<data.length;i++) {
for(int j=0; j<i;j++) {
if(data[i] > data[j]) {
//交换 data[i]和data[j]的值 当时突然想起了怎么在不引入中间变量交换值 0.0
data[i] = data[i]^data[j];
data[j] = data[i]^data[j];
data[i] = data[i]^data[j];
}
}
}
}
}
- 时间复杂度 O(n^2)
- 空间复杂度 O(1) （雾 如果这样写明明是0
- 稳定的排序
-
直接插入排序
一种简单暴力排序算法，将待排序的数字依次插入一个有序数组中，平时很少用到，反而在一些往已经有序的数组插入数据的场合使用。
public class InsertionSort implements Sorter{
@Override
public void sort(int[] data) {
for(int i=0; i<data.length; i++) {
for(int j = i-1;j>=0;j--) {
if(data[j] > data[j+1]) {
int temp = data[j+1];
data[j+1] = data[j];
data[j] = temp;
}else {
break;
}
}
}
}
}
- 时间复杂度 O(n^2)
- 空间复杂的有 O(1)
-
稳定 的排序
相比于冒泡排序没什么优点 还多了一句 怪不得很少人使用。
-
归并排序
一种思想简单，且具有魔力的排序，使用分治的思想 先拆分数据为2部分 分别保证左边和右边同样有序 再将其有序地归并起来，其实简而言之，我觉得归并排序本身就是在不停地拆和并。使用的情景非常丰富，是一种高效的排序手段。
- 简单举例
8,13,9,12,56,4,3,7,12;
拆成子元素
8 9 56 3 12
13 12 4 7
第一趟归并
8 13 4 56 12
9 12 3 7
第二趟
8 9 12 13 12
3 4 7 56
//中间略归并一步
3 4 7 8 9 12 12 13 56
public class MergcSort implements Sorter{
@Override
public void sort(int[] data) {
int[] temp = new int[data.length]
mergcSort(0, data.length-1, data,temp);
}
private void mergcSort(int left,int right,int[]data,int []temp) {
if(left == right) {
//当拆分到只有一个元素的时候当然有序咯
return;
}
// 拆拆拆
int mid = (left+right)/2;
// 递归拆左边
mergcSort(left, mid, data);
// 递归拆右边
mergcSort(mid+1, right, data);
int x = left,y = mid +1,loc =left;
while(x<=mid || y<=right) {
if(x <= mid &&(y>right||data[x] < data[y])) {
//分2种情形
//1. x <= mid && y <= right 这时候data[x] 的值小于data[y] 按照原则 谁小谁上
//2. x <= mid && y > right 即右边的已经全部填充到数组里了 这时候只好填左边的了
temp[loc] = data[x];
x++;
}else {
temp[loc] = data[y];
y++;
}
loc++;
}
// 毫无技巧地将中间数组的值填充回来
for(int i=left;i<=right;i++) {
data[i] = temp[i];
}
}
- 时间复杂度O(n*log(n))
- 空间复杂度 O(n)
- 稳定的排序
-
快速排序
强大的排序，是最常用的排序算法之一（目测要是是稳定排序的话使用会更丰富），快速排序其实非常简单 简单来说就是不断挖坑和填坑的过程，特点排序效率高，空间复杂度低，非常难得。
- 简单举例
8,13,9,12,56,4,3,7,12;
选取哨兵 简单取第一位挖掉 【】表示新填充 （）代表挖掉了 哨兵 = 8；
（8） 13 9 12 56 4 3 7 12 ； 挖掉哨兵
#1【7】 13 9 12 56 4 3 （7） 12 从右搜索第一个小于8的 挖掉并填充到上次挖的地方 7
#2 7 （13） 9 12 56 4 3 【13】 12 从左搜索第一个大于8的 挖掉填充到上次挖的地方 13
7 【3】9 12 56 4 （3）13 12 重复#1
7 3 （9）12 56 4 【9】 13 12 #2
7 3 【4】 12 56 （4） 9 13 12 。。。
7 3 4 （12） 56 【12】 9 13 12
最后左右重逢了 填充哨兵到相逢的地方
7 3 4 8 56 12 9 13 12
递归处理左右
[ 7 3 4 ] 8 [56 12 9 13 12]
......
- 代码实现
public class QuickSort implements Sorter{
@Override
public void sort(int[] data) {
quickSort(0, data.length-1, data);
}
private void quickSort(int left,int right,int []data) {
if(right <= left) {
return;
}
int x = left,y = right;
int temp = data[x];
while(x < y) {
while(y > x && data[y] > temp) {
y--;
}
if(y > x) {
data[x++]=data[y];
}
while(x < y && data[x] < data[y]) {
x++;
}
if(x < y) {
data[y--] = data[x];
}
}
data[x] = temp;
quickSort(left, x-1, data);
quickSort(x+1, right, data);
}
}
听起来好像很复杂 实际实现起来非常简单 其中2个if是为了保证左右指针不重逢 毕竟重逢意味着填充哨兵，本次排序的结束和分治的开始
- 时间复杂度O(n*log(n))
- 空间复杂度 O(1)
- 不稳定的排序
-
堆排序
STL中优先队列的底层实现，虽然在一次排序上表现不够优秀，但是非常适合那种不停地插入和取出最值的情景，堆排序事实上是最大堆或者最小堆，属于树形结构这里我就简单写一个堆，接下来不适合0基础的人查看。
public class Heap {
private int[] data;
private int size;
public Heap(int size) {
data = new int[size];
size = 0;
}
//得到堆顶元素
public int getTop() {
return data[0];
}
// 入堆
// 将入堆元素放到堆末尾 再从低而上做一次维护
public void push(int input) {
int current = size;
data[current] = input;
// 计算 父节点的位置
int father = (current - 1) / 2;
// 维护 这里保证堆中所有的儿子都比父亲大 否则就交换位置 继续向上维护
while (data[current] < data[father]) {
data[current] = data[current] ^ data[father];
data[father] = data[current] ^ data[father];
data[current] = data[current] ^ data[father];
current = father;
father = (father - 1) / 2;
}
size++;
}
// 最值元素出堆 首先将要出堆的元素交换到末尾 再顶定而下做一次维护
public int pop() {
int temp = data[0];
data[0] = data[size-1];
data[size-1] = temp;
size--;
update(0,size);
return data[size];
}
//自定而下维护函数 如果发现子节点大于父节点的值交换位置 再从新节点位置继续维护 专业的叫法叫 沉底
private void update(int pos,int size) {
int lchild = pos*2+1;
int rchild = pos*2+2;
int min_pos = pos;
if(lchild < size && data[lchild] < data[min_pos]) {
min_pos = lchild;
}
if(rchild < size && data[rchild] <data[min_pos]) {
min_pos = rchild;
}
if(pos != min_pos) {
int temp = data[pos];
data[pos] = data[min_pos];
data[min_pos] = temp;
update(min_pos, size);
}
}
}
- 时间复杂度O(n*log(n))
- 空间复杂度 O(1)
- 不稳定的排序
