算法思想-冒泡&快速排序
选择排序
场景:找出班上身高最高或者最低的人你会怎么找？
选择排序的思路和插入排序非常相似，也分已排序和未排序区间。但选择排序每次会从未排序区间中找到最小的元素，将其放到已排序区间的末尾。但是不像插入排序会移动数组 选择排序会每次进行交换。
例子：4 5 6 3 2 1 按从小到大排序。
第一次从未排序区间找到最小的数为1，4与1交换位置得到：1 5 6 3 2 4
第二次从未排序区间找到最小的数为2，5跟2交换位置得到：1 2 6 3 5 4
第三次从未排序区间找到最小的数为3，3跟6交换位置得到：1 2 3 6 5 4
第四次从未排序区间找到最小的数为4，4跟6交换位置得到：1 2 3 4 5 6
代码实现
/*** @author Howell* @email [email protected]* @date 2021/3/30 11:16 PM*/public class SelectSort {public static void main(String[] args) {int a[] = {9, 8, 7, 1, 5, 3};int n = a.length;//总共要经过n-1轮比较for (int i = 0; i < n - 1; i++) {int minPos = i;for (int j = i + 1; j < n; j++) {if (a[j] < a[minPos]) {//找到最小的元素minPos = j;}}//将找到的最小值和i位置所在的值进行交换if (i != minPos) {int temp = a[i];a[i] = a[minPos];a[minPos] = temp;}System.out.println("第" + i + "次排序：" + Arrays.toString(a));}}}
选择排序分析
1.时间复杂度：O(N^2)
2.空间复杂度:O(n)
3.交换次数
4.稳定性:不稳定
冒泡排序
核心思路：冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系要求。如果不满足就让它俩互换。一次冒泡会让至少一个元素移动到它应该在的位置，重复n次，就完成了n个数据的排序工作。
举例说明：4 5 6 3 2 1，从小到大排序。
第一次冒泡的结果:4 5 6 3 2 1->4 5 3 6 2 1 ->4 5 3 2 6 1 -> 4 5 3 2 1 6 元素6的位置确定了。
第二次冒泡的结果:4 5 3 2 1 6->4 3 5 2 1 6 -> 4 3 2 5 1 6 -> 4 3 2 1 5 6
第三次冒泡的结果:4 3 2 1 5 6->3 4 2 1 5 6 -> 3 2 4 1 5 6 -> 3 2 1 4 5 6
第四次冒泡的结果:3 2 1 4 5 6->2 3 1 4 5 6 -> 2 1 3 4 5 6
第五次冒泡的结果:2 1 3 4 5 6->1 2 3 4 5 6
代码实现
/*** @author Howell* @email [email protected]* @date 2021/3/30 11:51 PM*/public class BubbleSort {public static void main(String[] args) {int a[] = {6, 5, 4, 3, 2, 1}; //从小到大排序int n = a.length;for (int i = 0; i < n - 1; i++) { //排序的次数boolean flag = false;for (int j = 0; j < n - 1 - i; j++) { //冒泡的次数，每循环一次都确定一个元素if (a[j] > a[j + 1]) {int temp = a[j];a[j] = a[j + 1];a[j + 1] = temp;flag = true;}}if (!flag) { //优化点//什么样的情况下不做任何交换了呢？//比如1 2 3 4 5 6 进行排序：那就是所有的数都在它应该在的位置，即已经排好序；时间复杂度O(n)break;}}System.out.println(Arrays.toString(a));}//扩展:a:2 b:3 不借用中间变量temp交换a和b的值，a:3 b:2// 用加减//a = a + b => a = 3+2 =5;//b = a - b => b = 5-3 =2;//a = a - b => a = 5-2 =3;}
冒泡排序分析
1.时间复杂度:O(n^2)
2.空间复杂度:O(n)
3.交换次数:挺大的
4.稳定性:稳定
快速排序
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位基准数的排序完成。
接着左边部分和右边部分循环上述过程，最终如下图所示
代码实现
/*** @author Howell* @email [email protected]* @date 2021/3/31 8:34 AM*/public class QuickSort {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--;}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--;}}// 肯定是递归 分成了三部分,左右继续快排，注意要加条件不然递归就栈溢出了if (left < ll)qSort(data, left, ll - 1);if (ll < right)qSort(data, ll + 1, right);}}
快速排序分析
1.时间复杂度:nlogn 最坏的情况就是O(n^2)
2.空间复杂度:O(n)
3.稳定性：不稳定
4.快排和归并的对比：
（1）归并排序的处理过程是由下到上的，先处理子问题，然后再合并。
（2）快排其实就是从上到下，先分区，在处理子问题，不用合并。
其优化就是优化基准数,提供一个取三个数中间的思路.
各种排序对比
这么多种排序算法我们究竟应该怎么选择呢？:
1.分析场景：稳定还是不稳定
2.数据量：数据量小的时候选什么？比如就50个数，优先选插入
3.分析空间：
综上所述，没有一个固定的排序算法，都是要根据情况分析的。但是如果你不会分析的情况下 选择归并或者快排。
C++ qsort：快排+插入排序
jdk里面有arrays.sort:一种是基础类型，int double 用的快排。对象排序，用的是归并+timeSort
最后思考：
如何对一个省200万学生的高考成绩（假设成绩最多只有2位小数，0~900范围）进行排序，用尽可能高效的算法。
使用计数排序最高效。
代码实现
/*** 如何对一个省200万学生的高考成绩（假设成绩最多只有2位小数，0~900范围）进行排序，用尽可能高效的算法。** @author Howell* @email [email protected]* @date 2021/3/31 10:26 PM*/public class CountSort {public static void main(String[] args) throws Exception {String str = null;String fileName = "E:\\workspace\\sort\\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("数据读取完毕，size为" + 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("E:\\workspace\\sort\\200w-csort.txt");//Writer out = new FileWriter(file);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");System.out.println(i / 100.0 + "");}}}//out.close();}}