简单的看一下关于常用的排序结构,如图
本章代码重点实现: 插入排序 、选择排序、交换排序 这三类。
冒泡排序
原理:一次性用两个元素进行比较,如果小/大的就交换。走访数列的工作是重复地进行直到没有再需要交换位置。
代码:
/**
* 冒泡排序
*
* @author cjl
*
*/
public class BubblingSort {
public int[] BubblingSort(int[] res) {
for (int i = 0; i < res.length; i++) {
// 设置循环的次数
for (int j = 0; j < res.length - i - 1; j++) {
// 排序次数
if (res[j] > res[j + 1]) {
// 判断第一个值是否》大于第二个值
// 交换两个值就行
int temp = res[j]; // 先找一个值记录其中一个值
res[j] = res[j + 1];// 把大的值赋值过去
res[j + 1] = temp;// 替换位置
}
}
}
return res;
}
}
快速排序
快速排序 流程方法:
- 设置一个基数,通常默认第一个排序。
- 【顺序逻辑】从后往前比较,基数小于等于后面的值,把该数放在基数对应的位置上(前一个位置坑里)从前往后比较,基数大于前面某个值,把该数放在基数对应的位置上(前一个位置坑里)。
- 【倒序逻辑】 从后往前比较 ,基数大于后面的值,把该数放到基数对应的位置上(前一个位置坑里),从前往后比较,基数小于等于某个值,把该数放在基数对应的位置上(前一个位置里面)
- 循环 2.3 步骤
通过图我详细解释一下:
绿色位置 是设置的当前基础值【坑位1】。黄色表示的是坑位。顶上粉红色和蓝色表示 移动游标位置
1、 从后往前比较 比较小于基础值。 5 这个数先从后往前 比较 ,0小于5 因此0 下面挖一个坑2此时将 坑位2 对应 0这个数放到坑位1 对应的数上。
2、 从前往后比较 比较大于等于基础值。 9大于5 挖坑,坑位3,把坑位3对应数字9 填入之前坑位2的位置。
3、 当前最顶部两个游标贴在一起的时候,此时7 坑位 没有数字,把基数放到当前7坑位对应数值下 如图 蓝色5表示。
4、 此时数组就分成3 部分 黄色 + 基数+绿色,再次递归黄色部分 或者绿色部分。每次递归的时候 主要找到 黄色和红色基础值的位置
/**
* 快速排序
* <li> 【顺序】 基数大于前者 ,小于等于后者 </li>
* <li> 【倒序】 基数小于等于前者 ,大于后者 </li>
* <li>设置一个基础key值</li>
* <li>从后往前找到比他小/大于等于他的数,找到这个数字,填写到前一个坑里</li>
* <li>在从前往后找到比它大或者等于/小于等于他的数字,找到后放到填写到前面那个坑里</li>
*
*
*
*
* @author cjl
*
*/
public class QuickSort {
/**
* 顺序逻辑
*
* @param array
* 数组
* @param start
* 数组索引0
* @param end
* 数组索引最后一位array.length-1
* @return
*/
public void QuickSort(int[] array, int start, int end) {
// 当前游标索引值相等的时候 停止递归
if (start < end) {
int index = getIndex(array, start, end);
// 根据索引值 递归 不递归索引值 从0 ~ index-1 | index+1~end
QuickSort(array, 0, index - 1);
QuickSort(array, index + 1, end);
}
}
/**
*
* @param array
* @param start
* @param end
* @return
*/
private int getIndex(int[] array, int start, int end) {
int i = start;
int j = end;
// 定义初始值
int x = array[i];
while (i < j) {
// 移动游标 从 后--》前移动 基数值小于等于后面的值 游标从右向左推进
while (i < j && array[j] >= x) {
j--;
}
// 如果出现满足的值
if (i < j) {
// 把后面的值赋值给第一个基础值
array[i] = array[j];
i++;
}
// 移动游标 从前---》往后 基数值大于前面的值 游标从左往右推进
while (i < j && array[i] < x) {
i++;
}
// 如果出现满足的值
if (i < j) {
// 把前的值赋值给上一个值
array[j] = array[i];
j--;
}
}
array[i] = x;
return i;
}
/**
* 倒序逻辑
*
* @param array
* 数组
* @param start
* 数组索引0
* @param end
* 数组索引最后一位array.length-1
* @return
*/
public void QuickSortDesc(int[] array, int start, int end) {
// 当前游标索引值相等的时候 停止递归
if (start < end) {
int index = getIndexDesc(array, start, end);
// 根据索引值 递归 不递归索引值 从0 ~ index-1 | index+1~end
QuickSortDesc(array, 0, index - 1);
QuickSortDesc(array, index + 1, end);
}
}
private int getIndexDesc(int[] ar, int m, int n) {
int x = ar[m];
while (m < n) {
// X>后者
while (m < n && ar[n]<x) {
n--;
}
if (m < n) {
ar[m]=ar[n];
m++;
}
//x<=前者
while (m < n && ar[m]>=x) {
m++;
}
if (m < n) {
ar[n]=ar[m];
n--;
}
}
ar[m]=x;
return m;
}
}
插入排序
它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。
public void insertSort(int[] array) {
// 设置循环次数 定义游标 取第二个值
for (int i = 1; i < array.length; i++) {
// 游标指向 当前元素下一个值
int temp = array[i];
// 定义第二个游标指针 指向前一个值
int j = i - 1;
// 如果满足 前一个值 大于后一个值,则交换两个的位置,j-- 移动游标 直到与最后一个交换为止
for (; j >= 0 && array[j] > temp; j--) {
// 较小的值与相邻的值换位置
array[j + 1] = array[j];
// j-- 移动游标 向前移动游标 继续比较
}
array[j + 1] = temp;
}
}
希尔排序
希尔排序根据 分组插入排序,该方法又称缩小增量排序。
核心流程:
- 先对数组进行分组 数组长度进行分组【length/2】
- 每次减小分组长的增量
- 移动index进行 插入排序
/**
* 希尔排序根据 分组插入排序,该方法又称缩小增量排序
*
* @author cjl
*
*/
public class ShellSort {
public void ShellSort(int ar[]) {
int len = ar.length;
// 先计算每次分组的个数,分组 长度 =0 时候跳出循环,每次计算完成 组长/2
for (int space = len / 2; space > 0; space = space / 2) {
// 循环每组的个分组个数 长度是8 的数组 分组数为8/2=4 循环4次
for (int currentIndex = 0; currentIndex < space; currentIndex++) {
// 进行循环比较,每次比较完成交换数据 ,游标移动m+space的位置
for (int i = currentIndex + space; i < ar.length; i = i + space) {
// 插入排序
int temp = ar[i];
int x = i - 1;
for (; x > 0 && ar[x] > temp; x--) {
ar[x + 1] = ar[x];
}
ar[x + 1] = temp;
}
}
}
}
}
堆排序
先简单给大家简单分享一下
堆的概念:
堆是一棵完全二叉树,所谓完全二叉树即叶节点只能出现在最下层和次下层,并且最下面一层的结点都集中在该层最左边的若干位置的二叉树。
堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。
堆和二叉树的区别:
堆是一个完全二叉树,并且每个结点的值都大于或等于其左右孩子结点的值(这里的讨论以大根堆为例),所以,堆是结点之间满足一定次序关系的完全二叉树。
树的度:结点拥有的子树数 。二叉树 小于等于2。
大顶堆、小顶堆
/**
* 堆排序
*
* @author cjl
*
*/
public class HeapSort {
public TreeMap HeapSort(int[] array) {
TreeMap tm=new TreeMap<>();
//建立 小根堆
for (int i = (array.length-1)/2; i>=0; i--) {
HeapMap(array, array.length, i);;
}
//输入根堆
int n=array.length;
while (n>0) {
tm.put(n, array[0]);
array[0]=array[n-1];
n--;
HeapMap(array, n, 0);
}
return tm;
}
private void HeapMap(int[] array, int len, int i) {
int iLeft = i * 2 + 1;
int iRight = i * 2 + 2;
if (iLeft>len && iRight>len) {
return ;
}
int tL=Integer.MAX_VALUE;
int tR=Integer.MAX_VALUE;
if (iLeft<len) {
tL=array[iLeft];
}
if (iRight<len) {
tR=array[iRight];
}
//当前根小于左右子节点 的话就满足最小根堆条件
if (tL>array[i]&&tR>array[i]) {
return;
}
//如果不满足的话比较最小的进行交换
if (tL<tR) {
swap(array, i, iLeft);
HeapMap(array, len, iLeft);
}else{
swap(array, i, iRight);
HeapMap(array, len, iRight);
}
}
private void swap(int[] array, int i, int iLeft) {
int t=array[i];
array[i]=array[iLeft];
array[iLeft]=t;
}
}
//调用
public void HeapSort() {
int[] array={
8,7,6,6,10,-1,0,2,20,13,-2,-3,-5};
HeapSort sh=new HeapSort();
TreeMap tm=new TreeMap<>();
tm=sh.HeapSort(array);
Iterator it=tm.descendingKeySet().iterator();
while (it.hasNext()) {
System.out.println(tm.get(it.next()));
}
}
简单选择排序
1)首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置
2)再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。
3)重复第二步,直到所有元素均排序完毕
原理
/**
* 选择排序
*
* @author cjl
*
*/
public class SelectSort {
public void SelectSort(int[] array) {
// 循环次数
for (int i = 0; i < array.length - 1; i++) {
int k = i;
for (int j = k+1; j < array.length; j++) {
if (array[k] > array[j]) {
k = j; // 记录当前 最小值的位置
}
}
if (i!=k) {
int temp=array[i];
array[i]=array[k];
array[k]=temp;
}
}
}
}
归并排序
归并排序(Merge sort)是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。
算法步骤:
- 申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列
- 设定两个指针,最初位置分别为两个已经排序序列的起始位置
- 比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置
- 重复步骤3直到某一指针达到序列尾
- 将另一序列剩下的所有元素直接复制到合并序列尾
基数排序
基数排序是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。由于整数也可以表达字符串(比如名字或日期)和特定格式的浮点数,所以基数排序也不是只能使用于整数。
说基数排序之前,我们简单介绍桶排序:
算法思想:是将阵列分到有限数量的桶子里。每个桶子再个别排序(有可能再使用别的排序算法或是以递回方式继续使 用桶排序进行排序)。桶排序是鸽巢排序的一种归纳结果。当要被排序的阵列内的数值是均匀分配的时候,桶排序使用线性时间(Θ(n))。但桶排序并不是 比较排序,他不受到 O(n log n) 下限的影响。
简单来说,就是把数据分组,放在一个个的桶中,然后对每个桶里面的在进行排序。
排序效率的比较
在网上搜了搜找到了这么一张图,看似蛮有道理的,如下:
从排序效率上来说:
纯数字的话 :快速排序 、系统提供的Arrays.sort 相对较快Arrays.sort 实际上也是快速排序算法
带对象排序的:快速排序 比较快
稳定性来说的话:
归并排序,基数排序 比较好。
时间复杂度的问题
什么是时间复杂度?
时间复杂度:执行的语句次数,称为语句频度或者时间频度。
2.简单算法的时间复杂度举例
列举一些简单例子的时间复杂度。
O(1)的算法是一些运算次数为常数的算法。例如:
x=a;// 频度 1
a=b;// 频度 1
b=x;// 频度 1
上面语句共三条操作,平均每条操作的频度为1,即使他有成千上万条操作,也只是个较大常数,这一类的时间复杂度为O(1)。
O(n)的算法是一些线性算法。例如:
int res =0; //频度 1
for(i=0;i<n;i++) //频度 n
res ++; //频度 n
上面代码中第一行频度1,第二行频度为n,第三行频度为n,所以f(n)=n+n+1=2n+1。所以时间复杂度O(n)。这一类算法中操作次数和n正比线性增长。
O(logn) 一个算法如果能在每个步骤去掉一半数据元素,如二分检索,通常它就取 O(logn)时间 例子:
int s=1;
while (s<=n)
s=s*2;
上面代码设第三行的频度是f(n), 则:2*f(n)<=n;f(n)<=log₂n,取最大值f(n)= log₂n,所以T(n)=O(log₂n ) 。
O(n²)(n的k次方的情况)最常见的就是平时的对数组进行排序的各种简单算法都是O(n²),例如直接插入排序的算法。
而像矩阵相乘算法运算则是O(n³)。
例子:
sum=0;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
sum++;
第一行频度1,第二行n,第三行n²,第四行n²,T(n)=2n²+n+1 =O(n²)
常见的算法时间复杂度由小到大依次为
Ο(1)<Ο(log2n)<Ο(n)<Ο(nlog2n)<Ο(n2)<Ο(n3)<…<Ο(2n)<Ο(n!)
以上是本人参考其他大神代码和博客学习的成果。如果又不足之处各位大神指教。
最新评论
命令: nload
真是个良心站点哇,大公无私,爱了爱了
还可以直接搞一张映射表,存 uid | time | source_index, 第一次直接查对应的 time 选出前100, 第二次直接用 CompleteFuture 去分别用 source_in
干得漂亮,多个朋友堵条路
2021.2.2版本的不适用吧
现在还可以用么
激活码有用,感谢分享
激活码的地址打不开了