第1章 排序
第1节 最快最简单的排序–桶排序
对一堆0-10的数进行排序：
思路是用一个大小为11的数组存储0-10对应的数量。
package aha; import java.util.Scanner; public class BookSort { public static void main(String[] args) { int[] book = new int[11]; //初始化book for(int i=0;i<book.length;i++) { book[i] = 0; } Scanner sc = new Scanner(System.in); int n = sc.nextInt();//有n个数要排序 //存储到book中 for(int i=0;i<n;i++) { int t = sc.nextInt(); book[t]++; } //输出排序的结果，升序 //如果要降序，只需要从后往前输出 //for(int i=book.length-1;i>0;i--) for(int i=1;i<book.length;i++) { for(int j=0;j<book[i];j++) { System.out.print(i+" "); } } } }
优点是时间复杂度低，缺点是浪费的空间很大。
第2节 邻居好说话–冒泡排序
冒泡排序的基本思想：每次比较两个相邻的元素，如果它们顺序错误就把它们交换过来。
package aha; import java.util.Scanner; public class BubbleSort { public static void main(String[] args) { int a[] = new int[100]; Scanner sc = new Scanner(System.in); int n = sc.nextInt(); //读入n个数到数组a中 for(int i=0;i<n;i++) { a[i] = sc.nextInt(); } //进行冒泡排序 for(int i=0;i<n-1;i++) { for(int j=0;j<n-1-i;j++) { if(a[j]<a[j+1]) { int t = a[j];a[j]=a[j+1];a[j+1] = t; //交换a[j],a[j+1] } } } for(int i=0;i<n;i++) { System.out.print(a[i]+" "); } } }
冒泡排序的时间复杂度为
O(n2);
效率较低，一般不使用。
第3节 最常用的排序–快速排序
快速排序的基本思想：在序列中随机找一个基准数，把比基准大的放在右边，比基准小的放在左边。为了实现这一目的，可以通过两个哨兵，一个在最左边(i)，一个在最右边(j)，j往左走，找到比基准小的数后停下，接着i向右走，找到比基准大的数后停下。交换i和j指向的元素，接着继续刚刚的步骤，继续交换元素。直到两个哨兵相遇时停止，相遇的位置就是基准应该在的位置，将相遇的位置上的元素与基准进行交换。
//和快速排序相关的只有quickSort函数。
package aha; import java.util.Scanner; public class QuickSort { public int a[] = new int[100]; public int once; public int len ; public void quickSort(int left,int right) { if(left>right) return; int i = left; int j = right; int t = a[left]; //基准 while(i<j) { //注意顺序，先从右往左找 while(a[j]>=t&&i<j) j--; while(a[i]<=t&&i<j) i++; if(i<j) { int k = a[i]; a[i] = a[j]; a[j] = k; } } int k = a[i]; a[i] = a[left]; a[left] = k; quickSort(left,i-1); quickSort(i+1,right); } public void print() { for(int i=0;i<len;i++) { System.out.print(a[i]+" "); } } //每个数字只打印一次，忽略重复的数字 public void printOnce() { this.once = 0; if(a[0]!=0) { once++; } for(int i=1;i<len;i++) { if(a[i]!=a[i-1]) { once++; } } System.out.println(once); System.out.print(a[0]); for(int i=1;i<len;i++) { if(a[i]!=a[i-1]) { System.out.print(" "+a[i]); } } } public static void main(String[] args) { QuickSort qs = new QuickSort(); Scanner sc = new Scanner(System.in); qs.len = sc.nextInt(); for(int i=0;i<qs.len;i++) { qs.a[i]=sc.nextInt(); } qs.quickSort(0, qs.len-1); qs.printOnce(); } }
第4节 小哼买书
一个排序例子。
https://www.acoj.com/problems/12001
小结
3种排序方法，时间复杂度上，效率最高的是桶排序，因为桶排序放入元素时就完成排序了，但是浪费空间；效率较高的是快速排序，时间复杂度为O(nLogn)，实现比较简单，只要借助哨兵将基准放在合适的位置上就完成排序了，需要注意哨兵的移动顺序，如果基准是左面的元素，哨兵就是右边的哨兵先动。
void quickSort(int left,int right){ if(left>right) return; int i = left; int r = right; int t = a[left]; while(i<j){ while(a[j]>=t&&i<j) j--; while(a[i]<=t&&i<j) i++; if(i<j) { int k = a[i]; a[i] = a[j]; a[j] = k; } } int k = a[left]; a[left]=a[i]; a[i] = k; quickSort(0,i-1); quickSort(i+1,right); }
