排序算法
2021-12-15 15:48:57 0 举报AI智能生成
白话一下：对排序算法的理解 附相对应的代码，每行代码都有相应的解释
作者其他创作
大纲/内容
时间复杂度
每种输入的运行时间，乘以那种输入出现的概率
一个有关输入的统计分布的假设
一个有关输入的统计分布的假设
舍去低阶项和常数项，n趋于无限大，最里层执行的时间
O(1)
一次查询即可得到答案。这种是最优的。比如nio的epoll的回调事件，有了事件直接回调通知selector，selector直接就可以定位到这个通道来获取事件。
一次查询即可得到答案。这种是最优的。比如nio的epoll的回调事件，有了事件直接回调通知selector，selector直接就可以定位到这个通道来获取事件。
O(N)
代表这个方法：N个元素最慢就需要N次查询才能定位到目标。比如NIO的select方法，数组的遍历这类，如果要查最后一个元素，直接遍历就是需要N次查询。
代表这个方法：N个元素最慢就需要N次查询才能定位到目标。比如NIO的select方法，数组的遍历这类，如果要查最后一个元素，直接遍历就是需要N次查询。
O(logn)
基础知识：log默认以10为底，n的对数。logn的结果就是10的多少次方=n。比如log10=1。以2为底，n的对数。
代表这个方法：复杂度随着元素数量增多，增速却在慢慢降低。比如二分查找法，时间复杂度就是O(log(n))
算法时间复杂度为O(log(n))时，不同底数对应的时间复杂度的倍数关系为常数，不会随着底数的不同而不同，因此可以将不同底数的对数函数所代表的时间复杂度，当作是同一类复杂度处理，即抽象成一类问题。
推论：比如N个元素，最多需要查询N/2次，设最多需要查询X次。第一次，元素总共N个，最多查询N/2次。第二次查询，元素就剩N/2个了，那此时最多查询次数就是(N/2)/2，最后就是只需要一次查询(也及时次数是1)。即二分查找在最坏的情况下是n/(2的1次方),n/(2的2次方)，n/n/(2的3次方)。。。。 一直到查询n/(2的x次方)为止。这样经过了x次查询定位到了数据，n/(2的x次方)=1经过x次查询才能查到目标元素，n=2的x次方，x=log(n)
基础知识：log默认以10为底，n的对数。logn的结果就是10的多少次方=n。比如log10=1。以2为底，n的对数。
代表这个方法：复杂度随着元素数量增多，增速却在慢慢降低。比如二分查找法，时间复杂度就是O(log(n))
算法时间复杂度为O(log(n))时，不同底数对应的时间复杂度的倍数关系为常数，不会随着底数的不同而不同，因此可以将不同底数的对数函数所代表的时间复杂度，当作是同一类复杂度处理，即抽象成一类问题。
推论：比如N个元素，最多需要查询N/2次，设最多需要查询X次。第一次，元素总共N个，最多查询N/2次。第二次查询，元素就剩N/2个了，那此时最多查询次数就是(N/2)/2，最后就是只需要一次查询(也及时次数是1)。即二分查找在最坏的情况下是n/(2的1次方),n/(2的2次方)，n/n/(2的3次方)。。。。 一直到查询n/(2的x次方)为止。这样经过了x次查询定位到了数据，n/(2的x次方)=1经过x次查询才能查到目标元素，n=2的x次方，x=log(n)
白话算法+代码demo
冒泡排序
/**
* 冒泡排序，每进行一次大循环，最值就会冒泡一样出来
* @param args
*/
public static void main(String[] args) {
int[] arr={5,4,9,2,1};
//i为每次循环比较时的，冒泡后剩余元素的最大索引值
//比如第二次，已经冒泡出一个，剩下四个元素，那就是0-4中间的比较，最大索引值为4
//最后一次，那就是冒泡出了三个，剩下俩元素，那就是0-1中间的比较，最大索引值为1
for (int i = arr.length-1; i >0; i--) {
//里面层，依次比较临近元素，比较的最大值放在右边，这样最后冒泡出的最大值就在最右边。
//每次就是索引0和1比，1和2比，。。。最后就是i-1和i比。因此j最大为i-1
for (int j = 0; j < i; j++) {
if (arr[j]>arr[j+1]){
int temp=arr[j+1];
arr[j+1]=arr[j];
arr[j]=temp;
}
}
}
}
O(n*n)
选择排序
/**
* 选择排序，每进行一次大循环就选择出当前数组最小(或最大)的数。
* @param args
*/
public static void main(String[] args) {
int[] arr={5,4,9,2,1};
//每执行一次循环，就把最小的元素放到最左边。
//外层是核心元素索引,
for (int i = 0; i <= arr.length-2; i++) {
//里层是每次循环要比的元素，最小就是核心元素后面那个，最大就是数组最后一个元素
for (int j = i+1; j <= arr.length-1; j++) {
if (arr[j]<arr[i]){
int temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
}
}
}
* 选择排序，每进行一次大循环就选择出当前数组最小(或最大)的数。
* @param args
*/
public static void main(String[] args) {
int[] arr={5,4,9,2,1};
//每执行一次循环，就把最小的元素放到最左边。
//外层是核心元素索引,
for (int i = 0; i <= arr.length-2; i++) {
//里层是每次循环要比的元素，最小就是核心元素后面那个，最大就是数组最后一个元素
for (int j = i+1; j <= arr.length-1; j++) {
if (arr[j]<arr[i]){
int temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
}
}
}
O(n*n)
插入排序
/**
* 插入排序：就是从数组目前的第二个元素开始，依次和前面的比较后再插入的。
* 就像数组原来就一个元素，后面的元素插入前都与已存在的元素进行了比较。
* {5,4,22,1,9,13};就当做当前只有一个元素5，后面的元素依次取出，并与已插入的元素(也就是前面的元素)进行比较大小来确定插入新数组所在的索引位置
* 4，5==》4,5,22==》1,4,5,22==》1,4,5,9,22==》1,4,5,9,13,22
* @param arr
*/
//此次是从小到大排序
public static void main(String[] args) {
int[] arr={5,4,9,6,1};
//外层循环意义：新插入元素的老索引.i从1开始，因为第一个元素直接插入不用比较
for (int i = 1; i <= arr.length-1; i++) {
//新插入元素需要与已插入的所有元素进行依次比较，
//比如插入的是第四个元素6，此时数组为{4,5,9,6,1}那就要6和9比，交换，6再和5比，不交换，5再和4比，不交换。
for (int j = i-1; j >= 0; j--) {
if (arr[j+1]<arr[j]){
int temp=arr[j+1];
arr[j+1]=arr[j];
arr[j]=temp;
}else{//因为是依次进行比较的，当不进行交换时，前面的元素都是已经排序插入的，就不需要再比较了
j=0;
}
}
}
}
* 插入排序：就是从数组目前的第二个元素开始，依次和前面的比较后再插入的。
* 就像数组原来就一个元素，后面的元素插入前都与已存在的元素进行了比较。
* {5,4,22,1,9,13};就当做当前只有一个元素5，后面的元素依次取出，并与已插入的元素(也就是前面的元素)进行比较大小来确定插入新数组所在的索引位置
* 4，5==》4,5,22==》1,4,5,22==》1,4,5,9,22==》1,4,5,9,13,22
* @param arr
*/
//此次是从小到大排序
public static void main(String[] args) {
int[] arr={5,4,9,6,1};
//外层循环意义：新插入元素的老索引.i从1开始，因为第一个元素直接插入不用比较
for (int i = 1; i <= arr.length-1; i++) {
//新插入元素需要与已插入的所有元素进行依次比较，
//比如插入的是第四个元素6，此时数组为{4,5,9,6,1}那就要6和9比，交换，6再和5比，不交换，5再和4比，不交换。
for (int j = i-1; j >= 0; j--) {
if (arr[j+1]<arr[j]){
int temp=arr[j+1];
arr[j+1]=arr[j];
arr[j]=temp;
}else{//因为是依次进行比较的，当不进行交换时，前面的元素都是已经排序插入的，就不需要再比较了
j=0;
}
}
}
}
O(n*n)
归并排序
/**
* @ClassName T3
* @description:$将数组当做二叉树，思考会更简单
* @author: 李杰
* @create: 2021-12-01 00:27
* @Version 1.0
**/
public class T {
/**
* 归并排序：先把数组依次拆分，拆分到每个组只有一个，再进行合并。类似于树的递归运算。
* @param args
*/
public static void main(String[] args) {
int[] arr={5,4,22,1,9,13};
sortArr(arr,0,arr.length-1);
for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i]);
}
}
private static void sortArr(int[] arr, int start, int end) {
//首先判断是否已经不用再拆分了
if (end>start){
//拆分
int mid=(start+end)/2;
sortArr(arr, start, mid);
sortArr(arr, mid+1, end);
merge(arr,start,mid,mid+1,end);
}else{
//不用拆分了
System.out.println("拆分到最小了，反转向上合并");
}
}
private static void merge(int[] arr, int start1, int end1, int start2, int end2) {
//定义一个临时数组：存放俩数组合并后的所有元素
int[] temp=new int[end2-start1+1];
//定义左数组的未比较元素的最小索引
int left=start1;
//定义右数组的未比较元素的最小索引
int right=start2;
//依次取出每个数组的最小索引元素来比较,将最小元素放到temp
for (int i = 0; i < temp.length; i++) {
if (left>end1){
//左数组已经没有元素了，不用比较，直接将右数组元素放入temp
temp[i]=arr[right];
right++;
}else if (right>end2){
//右数组已经没有元素了，不用比较，直接将左数组元素放入temp
temp[i]=arr[left];
left++;
}else{//左右数组都有元素，则进行比较
if (arr[left]>arr[right]){
temp[i]=arr[right];
right++;
}else{
temp[i]=arr[left];
left++;
}
}
}
//将排序归并的数组temp覆盖掉原数组
int index=start1;
for (int i = 0; i < temp.length; i++) {
arr[index]=temp[i];
index++;
}
}
}
* @ClassName T3
* @description:$将数组当做二叉树，思考会更简单
* @author: 李杰
* @create: 2021-12-01 00:27
* @Version 1.0
**/
public class T {
/**
* 归并排序：先把数组依次拆分，拆分到每个组只有一个，再进行合并。类似于树的递归运算。
* @param args
*/
public static void main(String[] args) {
int[] arr={5,4,22,1,9,13};
sortArr(arr,0,arr.length-1);
for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i]);
}
}
private static void sortArr(int[] arr, int start, int end) {
//首先判断是否已经不用再拆分了
if (end>start){
//拆分
int mid=(start+end)/2;
sortArr(arr, start, mid);
sortArr(arr, mid+1, end);
merge(arr,start,mid,mid+1,end);
}else{
//不用拆分了
System.out.println("拆分到最小了，反转向上合并");
}
}
private static void merge(int[] arr, int start1, int end1, int start2, int end2) {
//定义一个临时数组：存放俩数组合并后的所有元素
int[] temp=new int[end2-start1+1];
//定义左数组的未比较元素的最小索引
int left=start1;
//定义右数组的未比较元素的最小索引
int right=start2;
//依次取出每个数组的最小索引元素来比较,将最小元素放到temp
for (int i = 0; i < temp.length; i++) {
if (left>end1){
//左数组已经没有元素了，不用比较，直接将右数组元素放入temp
temp[i]=arr[right];
right++;
}else if (right>end2){
//右数组已经没有元素了，不用比较，直接将左数组元素放入temp
temp[i]=arr[left];
left++;
}else{//左右数组都有元素，则进行比较
if (arr[left]>arr[right]){
temp[i]=arr[right];
right++;
}else{
temp[i]=arr[left];
left++;
}
}
}
//将排序归并的数组temp覆盖掉原数组
int index=start1;
for (int i = 0; i < temp.length; i++) {
arr[index]=temp[i];
index++;
}
}
}
O(nlogn)
0 条评论
下一页
