wordpress站点使用期限插件,网站开发国外研究现状,logo素材大图,网站建设收费流程一#xff1a;选择排序 场景#xff1a;找出一个班上身高最高的人你会怎么找#xff1f;A B C D A B 选择排序的思路和插入排序非常相似#xff0c;也分已排序和未排序区间。但选择排序每次会从未排序区间中找到最小的元素#xff0c;将其放到已排序区间的末尾。但是不像插… 一选择排序 场景找出一个班上身高最高的人你会怎么找A B C D A B 选择排序的思路和插入排序非常相似也分已排序和未排序区间。但选择排序每次会从未排序区间中找到最小的元素将其放到已排序区间的末尾。但是不像插入排序会移动数组 选择排序会每次进行交换如以下例子 4 5 6 3 2 1 第一次 1 5 6 3 2 4 第二次 1 2 6 3 5 4 1.时间复杂度O(N^2) 2.空间复杂度:O(n) 3.交换次数 4.稳定性:不稳定 二冒泡排序 核心思路冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较看是否满足大小关系要求。如果不满足就让它俩互换。一次冒泡会让至少一个元素移动到它应该在的位置重复n次就完成了n个数据的排序工作。 举例说明4 5 6 3 2 1,从小到大排序。 1 2 3 4 5 6 进行排序什么样的情况下不做任何交换了呢那就是所有的数都在它应该在的位置O(n) 1.时间复杂度:O(n^2) 2.空间复杂度:O(n) 3.交换次数:挺大的 4.稳定性:稳定 package Sort2;import java.util.Arrays;/*** 冒泡排序*/public class BubbleSort {public static void main(String[] args) {int data[] { 4, 5, 6, 3, 2, 1 };int n data.length;//n-1这里是因为判断两个数是只比较一次 例如 1 2 比较次数只会比一次for (int i 0; i n - 1; i) { //排序的次数//优化如果所有的数都排好了不需要交换了就不需要冒泡了所以直接退出boolean flag false;// n-1-i要减掉i是因为每次冒泡排序都会将后面的值确定所以i就是后面已经排好的数字所以就不需要再比较了所以得减掉for (int j 0; j n - 1 - i; j) { //具体冒泡 n - 1 - i,6,5,4,3,2,1if (data[j] data[j 1]) {//交换int temp data[j]; //用了第三个变量不用第三个变量data[j] data[j 1];data[j 1] temp;flag true;//异或实现
// data[j] data[j] ^ data[j1];
// data[j1] data[j] ^ data[j1];
// data[j] data[j] ^ data[j1];}}if(!flag) break;}System.out.println(Arrays.toString(data));}
}
/*** 下面是交换的时候如果不用第三方变量存储的话如何交换*/
// a:2 b:3
// 3 2 a:3 b:2
// 用加减
//a a b a 32 5;
//b a - b b 5-3 2;
//a a - b a 5-2 3; 2.1 如何进行简单的优化 1. 在交换的时候会需要第三方变量会占空间所以可以用异或交换。 2. 当排好序了就不需要继续循环了所以加flag作为标签。 2.2 如何实现异或交换 异或操作可以实现交换两个数字的值的原因是因为异或操作具有以下几个性质
任何数和0异或的结果仍然是这个数本身a ^ 0 a任何数和自身异或的结果是0a ^ a 0异或操作满足交换律a ^ b b ^ a 利用这些性质我们可以通过异或操作实现交换两个数字的值具体步骤如下 假设有两个变量a和b它们的初始值分别为a0和b0。第一步通过将a与b异或将结果保存在a中a a ^ b。 此时a的值为a0 ^ b0b的值保持不变。第二步再将a与b异或将结果保存在b中b a ^ b。 在这一步中我们可以将上一步得到的a的值(a0 ^ b0)再与b0异或得到的结果就是a0即原始的a的值。 同时由于异或操作满足交换律所以b (a0 ^ b0) ^ b0 a0 ^ (b0 ^ b0) a0 ^ 0 a0。 此时a的值保持不变b的值变为a0。第三步最后将a与b异或将结果保存在a中a a ^ b。 在这一步中我们将上一步得到的a的值a0 ^ b0与上一步得到的b的值(a0)异或得到的结果就是b0。
public class SwapNumbers {public static void main(String[] args) {int a 10;int b 20;System.out.println(交换前);System.out.println(a a);System.out.println(b b);// 使用异或操作交换a和b的值a a ^ b;b a ^ b;a a ^ b;System.out.println(交换后);System.out.println(a a);System.out.println(b b);}
} 三 快速排序 45 28 80 90 50 16 100 10 基准数一般就是取要排序序列的第一个。 第一次排序基准数45 从后面往前找到比基准数小的数进行对换 10 28 80 90 50 16 100 45 从前面往后面找比基准数大的进行对换 10 28 45 90 50 16 100 80 10 28 16 90 50 45 100 80 10 28 16 45 50 90 100 80 以基准数分为3部分左边的比之小右边比之大 {10 28 16} 45 {50 90 100 80} 到此第一次以45位基准数的排序完成。 1.时间复杂度:nlogn 最坏的情况就是O(n^2) 2.空间复杂度:O(n) 3.稳定性不稳定 4.快排和归并的对比 1归并排序的处理过程是由下到上的先处理子问题然后再合并。 2快排其实就是从上到下先分区在处理子问题不用合并。 其优化就是优化基准数,提供一个取三个数中间的思路. package Sort2;public class QuiklySort {public static void qSort(int data[], int left, int right) {int base data[left]; // 就是我们的基准数取序列的第一个,不能用data[0]int ll left; // 表示的是从左边找的位置int rr right; // 表示从右边开始找的位置while (ll rr) {// 从后面往前找比基准数小的数while (ll rr data[rr] base) {rr--;}//这里有个小技巧如果ll rr为true说明 data[rr] base false就找到比基准数小的就要交换if (ll rr) { // 表示是找到有比之大的int temp data[rr];data[rr] data[ll];data[ll] temp;ll;}// 从前面往后找比基准数大的数while (ll rr data[ll] base) {ll;}if (ll rr) {int temp data[rr];data[rr] data[ll];data[ll] temp;rr--;}}// 肯定是递归 分成了三部分,左右继续快排注意要加条件不然递归就栈溢出了//ll:循环终止时为基准数在最中间,然后将ll左右两部分继续递归if (left ll)qSort(data, left, ll - 1);if (ll right)qSort(data, ll 1, right);}
}各种排序比较 这么多种排序算法我们究竟应该怎么选择呢
1.分析场景稳定还是不稳定
2.数据量数据量小的时候选什么比如就50个数优先选插入5000*500025000000
3.分析空间 综上所述没有一个固定的排序算法都是要根据情况分析的。但是如果你不会分析的情况下 选择归并或者快排。 四计数排序 如何对一个省200万学生的高考成绩假设成绩最多只有2位小数0~900范围进行排序用尽可能高效的算法。
package sorttest;import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.UnsupportedEncodingException;
import java.io.Writer;/*** 如何对一个省200万学生的高考成绩假设成绩最多只有2位小数0~900范围进行排序用尽可能高效的算法。* 计数排序*/public class CountSort {public static void main(String[] args) throws Exception {String str null;String fileName D:\\JavaCode\\tulin\\src\\sorttest\\200w.txt;InputStreamReader isr new InputStreamReader(new FileInputStream(fileName), UTF-8);BufferedReader br new BufferedReader(isr);int data[] new int[2100002];int i 0;//遍历所有的数据存到数组中while ((str br.readLine()) ! null) {double a Double.valueOf(str);a a * 100;data[i] (int) a;// System.out.println((int) a);}System.out.println(开始值为 i);long start System.currentTimeMillis();countSort(data, 0, data.length - 1);System.out.println(结束时间为 (System.currentTimeMillis() - start) ms);}public static void countSort(int data[], int min, int max) throws Exception {int counts[] new int[max 1];//将所存的数字按照数组下标存储计数for (int i 0; i data.length; i) {counts[data[i]];}File file new File(D:\\JavaCode\\tulin\\src\\sorttest\\200w-csort.txt);Writer out new FileWriter(file);//同时从0开始遍历所以也默认排好序直接输出for (int i 0; i max; i) {if (counts[i] 0) {for (int j 0; j counts[i]; j) {out.write(((double) (i / 100.0)) \r\n);}}}out.close();}
}
